Context-specific independenceParameter learning: MLEAnnouncementsClique trees versus VEClique tree summaryGlobal Structure: Treewidth wLocal Structure 1:Context specific indepencenceLocal Structure 1:Context specific indepencenceCSI example: Tree CPDTabular VE with Tree CPDsLocal Structure 2: DeterminismDeterminism and inferenceToday’s Models …Exact inference in large models is possible…Recursive ConditioningThe Computational Power of AssumptionsThe Computational Power of AssumptionsDecompositionCase AnalysisCase AnalysisCase AnalysisCase AnalysisCase AnalysisDecomposition TreeDecomposition TreeDecomposition TreeRC1CachingCachingRC2Decomposition with Local StructureDecomposition with Local StructureDecomposition with Local StructureCaching with Local StructureCaching with Local StructureCaching with Local StructureDeterminism…CSI SummaryWhere are we?Thumbtack – Binomial DistributionMaximum Likelihood EstimationYour first learning algorithmMLE for conditional probabilitiesLearning the CPTsMLE learning CPTs for general BNUse Chapter 3 of K&F as a reference for CSIReading for parameter learning: Chapter 12 of K&FContext-specific independenceParameter learning: MLEGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 5th, 2005Announcements Homework 2: Out today/tomorrow Programming part in groups of 2-3 Class project Teams of 2-3 students Ideas on the class webpage, but you can do your own Timeline: 10/19: 1 page project proposal 11/14: 5 page progress report (20% of project grade) 12/2: poster session (20% of project grade) 12/5: 8 page paper (60% of project grade) All write-ups in NIPS format (see class webpage)Clique trees versus VE Clique tree advantages Multi-query settings Incremental updates Pre-computation makes complexity explicit Clique tree disadvantages Space requirements – no factors are “deleted” Slower for single query Local structure in factors may be lost when they are multiplied together into initial clique potentialClique tree summary Solve marginal queries for all variables in only twice the cost of query for one variable Cliques correspond to maximal cliques in induced graph Two message passing approaches VE (the one that multiplies messages) BP (the one that divides by old message) Clique tree invariant Clique tree potential is always the same We are only reparameterizing clique potentials Constructing clique tree for a BN from elimination order from triangulated (chordal) graph Running time (only) exponential in size of largest clique Solve exactly problems with thousands (or millions, or more) of variables, and cliques with tens of nodes (or less)Global Structure: Treewidth w))exp(( wnOLocal Structure 1:Context specific indepencenceBattery AgeAlternatorFan BeltBatteryCharge DeliveredBattery PowerStarterRadioLights Engine Turn OverGas GaugeGasFuel PumpFuel LineDistributorSpark PlugsEngine StartBattery AgeAlternatorFan BeltBatteryCharge DeliveredBattery PowerStarterRadioLights Engine Turn OverGas GaugeGasFuel PumpFuel LineDistributorSpark PlugsEngine StartContext Specific Independence (CSI)After observing a variable, some varsbecome independentLocal Structure 1:Context specific indepencenceCSI example: Tree CPD Represent P(Xi|PaXi) using a decision tree Path to leaf is an assignment to (a subset of) PaXi Leaves are distributions over Xigiven assignment of PaXion path to leaf Interpretation of leaf: For specific assignment of PaXion path to this leaf – Xiis independent of other parents Representation can be exponentially smaller than equivalent tableApply SAT LetterJobTabular VE with Tree CPDs If we turn a tree CPD into table “Sparsity” lost! Need inference approach that deals with tree CPD directly!Local Structure 2: DeterminismBattery AgeAlternatorFan BeltBatteryCharge DeliveredBattery PowerStarterRadioLights Engine Turn OverGas GaugeGasFuel PumpFuel LineDistributorSpark PlugsEngine StartONOFFOKWEAKDEADLightsBattery Power.99 .01.20.800 1If Battery Power = Dead, then Lights = OFFDeterminismDeterminism and inference Determinism gives a little sparsity in table, but much bigger impact on inference Multiplying deterministic factor with other factor introduces many new zeros Operations related to theorem proving, e.g., unit resolutionONOFFOKWEAKDEADLightsBattery Power.99 .01.20.800 1Today’s Models … Often characterized by: Richness in local structure (determinism, CSI) Massiveness in size (10,000’s variables) High connectivity (treewidth) Enabled by: High level modeling tools: relational, first order Advances in machine learning New application areas (synthesis): Bioinformatics (e.g. linkage analysis) Sensor networksExploiting local structure a must!Exact inference in large models is possible… BN from a relational modelRecursive Conditioning Treewidth complexity (worst case) Better than treewidth complexity with local structure Provides a framework for time-space tradeoffs Only quick intuition today, details: Koller&Friedman: 3.1-3.4, 6.4-6.6 “Recursive Conditioning”, Adnan Darwiche. In Artificial Intelligence Journal, 125:1, pages 5-41A. DarwicheThe Computational Power of AssumptionsBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine StartA. DarwicheThe Computational Power of AssumptionsBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine StartA. DarwicheDecompositionBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine StartA. DarwicheCase AnalysisBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine StartBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine Start+p pA. DarwicheCase AnalysisBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel
View Full Document