Collective ClassificationCollective ClassificationMustafa [email protected]@CMSC828GSpring 2008OutlineWhat information is used byWhat information is used by Content-onlyRelationalRelational CollectiveFeature constructionFeature construction AggregationHow the information is usedHow the information is used Vector-based approaches to CCThe Relational Markov Network approach to CC2LINQS @ UMDThe Relational Markov Network approach to CCDomain & Task3LINQS @ UMDTask: Classify the nodesContent-only Classification4LINQS @ UMDContent-only Classification5LINQS @ UMDUse the attributes (content).Content-only Classification6LINQS @ UMDRelational Classification7LINQS @ UMDRelational Classification8LINQS @ UMDUse the attributes (content).Relational Classification9LINQS @ UMDUse the attributes of the related objects.Relational Classification10LINQS @ UMDUse the known labels of the related objects.Relational Classification11LINQS @ UMDCollective Classification12LINQS @ UMDCollective Classification13LINQS @ UMDUse the attributes (content).Collective Classification14LINQS @ UMDUse the attributes of the related objects.Collective Classification15LINQS @ UMDUse the known labels of the related objects.Collective Classification16LINQS @ UMDUse the unknown labels of the related objects (during testing).Collective Classification17LINQS @ UMDSummary – Information UsedContent-only classificationContentonly classification Each object’s own attributes only Relational classification Each object’s own attributes Attributes of the neighborsKno n labels of the neighborsKnown labels of the neighbors Collective classificationEach object’s own attributesEach object s own attributes Attributes of the neighbors Known labels of the neighbors18LINQS @ UMD Unknown labels of the neighbors (during testing)Artificial DivisionVector based modelsVector based models Convert each node into a flat vectorLearn Naïve Bayes k-NN Logistic RegressionLearn Naïve Bayes, kNN, Logistic Regression, etc.Graphical modelsGp A graph based representation Learn a relational Bayesian Network, Markov y,Network, Dependency Network, etc. Warning: This division is purely artificial and its sole purpose is to make it easy to understand different models. Otherwise, many, if not all, vector based methods have 19LINQS @ UMDycorresponding graphical models; e.g. Naïve Bayes is a simple Bayesian Network.Content-only Classificationa1 a2 a3 L010Ra1 a2 a3 L110G010R110Ga1 a2 a3 L110?a1a2a3La1a2a3La1a2a3L100?a1a2a3L101?a1 a2 a3 L111B20LINQS @ UMDContent-only Classificationa1 a2 a3 L100R110R011BLearn a classifier, such asNaïve Bayes, k-NN,001B001GLogistic Regression, etc000G011?101?000?Use the classifier topredict these21LINQS @ UMD001?Problemsa1 a2 a3 N1 N2 N3 L010RRBR22LINQS @ UMDProblemsa1 a2 a3 N1 N2 N3 L010RRBRHow do we order the neighbors?a1 a2 a3 N1 N2 N3 L010RBRRHow do we order the neighbors?010RBRR23LINQS @ UMDProblemsa1 a2 a3 N1 N2 N3 L010RRBRa1 a2 a3 N1 N2 N3 L010RBRR010RBRRWhat if different nodes have different number of neighbors?a1 a2 a3 N1 N2 N3 N4 L010RRBRR24LINQS @ UMD010RRBRRAggregationMain idea:Main idea: Aggregate a set of attributes into a fixed length representationp ExamplesCountCount Proportion Mod Exist Mean25LINQS @ UMDCounta1 a2 a3 CR CB CG L010210Ra1 a2 a3 CR CB CG L010210R010210Ra1 a2 a3 CR CB CG L010310R26LINQS @ UMD010310RProportiona1 a2 a3 PR PB PG L0 1 0 0.67 0.33 0 Ra1 a2 a3 PR PB PG L0100670330R0100.670.330Ra1 a2 a3 PR PB PG L0100.750.250R27LINQS @ UMD0100.750.250RExista1 a2 a3 ER EB EG L010 1 1 0 Ra1 a2 a3 ER EB EG L010110R010110Ra1 a2 a3 ER EB EG L010110R28LINQS @ UMD010110RFeature ConstructionAggregation is just the tip of the icebergAggregation is just the tip of the iceberg Which relationships to use? In-links Out-links BothCocitationCo-citation Which attributes to borrow from the neighbors?AllAll Specific ones Words from only the title29LINQS @ UMD Age of my friendsICA Revisited30LINQS @ UMDICA Revisited31LINQS @ UMDICA Revisiteda1 a2 a3CR CB CGL010 Ra1 a2 a3CR CB CGL100 Ga1 a2 a3CR CB CGL100a1 a2 a3CR CB CGLa1 a2 a3CR CB CGL110101a1 a2 a3CR CB CGL111 B32LINQS @ UMDICA Revisited – Traininga1 a2 a3CR CB CGL010000Ra1 a2 a3CR CB CGL100000Ga1 a2 a3CR CB CGL100a1 a2 a3CR CB CGLa1 a2 a3CR CB CGL110101a1 a2 a3CR CB CGL111000B33LINQS @ UMDFor training, only known information is used.ICA Revisited – Step 0 – Bootstrapa1 a2 a3CR CB CGL010000Ra1 a2 a3CR CB CGL100000Ga1 a2 a3CR CB CGL100 Ga1 a2 a3CR CB CGLa1 a2 a3CR CB CGL110 B101 Ba1 a2 a3CR CB CGL111000B34LINQS @ UMDFor testing, we need to bootstrap the unknown labels.Use content information to bootstrap.ICA Revisited – Iteratea1 a2 a3CR CB CGL010000Ra1 a2 a3CR CB CGL100000Ga1 a2 a3CR CB CGL100020Ga1 a2 a3CR CB CGLa1 a2 a3CR CB CGL110 B101 Ba1 a2 a3CR CB CGL111000B35LINQS @ UMDConstruct relational features.ICA Revisited – Iteratea1 a2 a3CR CB CGL010000Ra1 a2 a3CR CB CGL100000Ga1 a2 a3CR CB CGL100020Ba1 a2 a3CR CB CGLa1 a2 a3CR CB CGL110 B101 Ba1 a2 a3CR CB CGL111000B36LINQS @ UMDUpdate the label.ICA Revisited – Iteratea1 a2 a3CR CB CGL010000Ra1 a2 a3CR CB CGL100000Ga1 a2 a3CR CB CGL100020Ba1 a2 a3CR CB CGLa1 a2 a3CR CB CGL110 B101020Ba1 a2 a3CR CB CGL111000B37LINQS @ UMDConstruct relational features.ICA Revisited – Iteratea1 a2 a3CR CB CGL010000Ra1 a2 a3CR CB CGL100000Ga1 a2 a3CR CB CGL100020Ba1 a2 a3CR CB CGLa1 a2 a3CR CB CGL110 B101020Ba1 a2 a3CR CB CGL111000B38LINQS @ UMDUpdate the label.ICA Revisited – Iteratea1 a2 a3CR CB CGL010000Ra1 a2 a3CR CB CGL100000Ga1 a2 a3CR CB CGL100020Ba1 a2 a3CR CB CGLa1 a2 a3CR CB CGL110010B101020Ba1 a2 a3CR CB CGL111000B39LINQS @ UMDConstruct relational features.ICA Revisited – Iteratea1 a2 a3CR CB CGL010000Ra1 a2 a3CR CB CGL100000Ga1 a2 a3CR CB CGL100020Ba1 a2 a3CR CB CGLa1 a2 a3CR CB CGL110010B101020Ba1 a2 a3CR CB CGL111000B40LINQS @ UMDUpdate the label.Summary – Vector Based CCConvert each object into a flat representationConvert each object into a flat representation Use aggregation for information from neighbors Train two classifiers 1stuses content only 2nduses both content and relationalOnly known information is usedOnly known information is used. Bootstrap using the 1stclassifierIterate until convergence using the 2ndclassifierIterate until convergence using the 2classifier Reconstruct relational
View Full Document
Unlocking...