PreliminariesHierarchyMetropolis methodTraditional Hierarchical ClusteringStructural Inference of Hierarchies in NetworksModelEdge and Node Annotations Learning Annotated Hierarchies from Relational Data Overview Terminology Generative Model InferenceResultsConclusion : Learning Annotated HierarchiesReferencesPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesOrganization, Taxonomy and HierarchyFormationRob Patro Mike PekalaMay 1,2008 / CMSC828GRob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesOutline1PreliminariesHierarchyMetropolis methodTraditional Hierarchical Clustering2Structural Inference of Hierarchies in NetworksModelEdge and Node Annotations3Learning Annotated Hierarchies from Relational DataOverviewTerminologyGenerative ModelInferenceResultsConclusion : Learning Annotated Hierarchies4ReferencesRob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesOutline1PreliminariesHierarchyMetropolis methodTraditional Hierarchical Clustering2Structural Inference of Hierarchies in NetworksModelEdge and Node Annotations3Learning Annotated Hierarchies from Relational DataOverviewTerminologyGenerative ModelInferenceResultsConclusion : Learning Annotated Hierarchies4ReferencesRob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesOutline1PreliminariesHierarchyMetropolis methodTraditional Hierarchical Clustering2Structural Inference of Hierarchies in NetworksModelEdge and Node Annotations3Learning Annotated Hierarchies from Relational DataOverviewTerminologyGenerative ModelInferenceResultsConclusion : Learning Annotated Hierarchies4ReferencesRob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesOutline1PreliminariesHierarchyMetropolis methodTraditional Hierarchical Clustering2Structural Inference of Hierarchies in NetworksModelEdge and Node Annotations3Learning Annotated Hierarchies from Relational DataOverviewTerminologyGenerative ModelInferenceResultsConclusion : Learning Annotated Hierarchies4ReferencesRob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesHierarchyMetropolis methodTraditional Hierarchical ClusteringOutline1PreliminariesHierarchyMetropolis methodTraditional Hierarchical Clustering2Structural Inference of Hierarchies in NetworksModelEdge and Node Annotations3Learning Annotated Hierarchies from Relational DataOverviewTerminologyGenerative ModelInferenceResultsConclusion : Learning Annotated Hierarchies4ReferencesRob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesHierarchyMetropolis methodTraditional Hierarchical ClusteringHierarchical DomainsMany real-world networks have fractal-like structure,groups-of-groups:Biological taxonomies (species, genus, family, order, etc.)Language and semantics (dependency trees)Social Hierarchies (businesses, churches, armies, kinship,flocks)Computation (computer networks, filesystems, software)Selected papers focus on constructing/discoveringhierarchies from data.Some others (e.g. Shen) address constructing them “fromscratch”.Rob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesHierarchyMetropolis methodTraditional Hierarchical ClusteringOutline1PreliminariesHierarchyMetropolis methodTraditional Hierarchical Clustering2Structural Inference of Hierarchies in NetworksModelEdge and Node Annotations3Learning Annotated Hierarchies from Relational DataOverviewTerminologyGenerative ModelInferenceResultsConclusion : Learning Annotated Hierarchies4ReferencesRob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesHierarchyMetropolis methodTraditional Hierarchical ClusteringMetropolis-HastingsWARNING!!!WANML (We are not machine-learners)Relying on you to help us out / keep us in line...Goal: want to sample from sometarget distribution π(x).Can’t be done directly (e.g. statespace too large).Note: the next few slides taken from[SZ05].Rob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesHierarchyMetropolis methodTraditional Hierarchical ClusteringAnother example (from [Mac03])Q(x0; x) =1/2 x0= max(x − 1, 0)1/2 x0= min(x + 1, 20)0 otherwiseT =1/2 1/2 0 0 ...1/2 0 1/2 0 ...0 1/2 0 1/2 ...0 0 1/2 0 ...... ... ... ... ...0 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 200 5 10 15 20Rob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesHierarchyMetropolis methodTraditional Hierarchical ClusteringOutline1PreliminariesHierarchyMetropolis methodTraditional Hierarchical Clustering2Structural Inference of Hierarchies in NetworksModelEdge and Node Annotations3Learning Annotated Hierarchies from Relational DataOverviewTerminologyGenerative ModelInferenceResultsConclusion : Learning Annotated Hierarchies4ReferencesRob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesHierarchyMetropolis methodTraditional Hierarchical ClusteringSome more clustering...Rob , Mike Hierarchy in NetworksPreliminariesStructural Inference of Hierarchies in NetworksLearning Annotated Hierarchies from Relational DataReferencesHierarchyMetropolis methodTraditional Hierarchical ClusteringTraditional Hierarchical Clustering [HTF01]Measure group dissimilarities based on pairwisedissimilarities between N individuals.Merge/divide two clusters at each step, N − 1 steps(hierarchy levels) total.Agglomerative (bottom-up).Divisive (top-down).Monotonicity property.Dissimilarity
View Full Document
Unlocking...