Context-specific independenceGlobal Structure: Treewidth wLocal Structure 1: Context specific indepencenceSlide 4CSI 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 AssumptionsSlide 13DecompositionCase AnalysisSlide 16Slide 17Slide 18Slide 19Decomposition TreeSlide 21Slide 22RC1Slide 24CachingSlide 26RC2Decomposition with Local StructureSlide 29Slide 30Caching with Local StructureSlide 32Slide 33Determinism…CSI SummaryContext-specific independenceGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 16th, 2006Readings:K&F: 4.1, 4.2, 4.3, 4.4, 8.4, 8.5, 8.6“Recursive Conditioning”, Adnan Darwiche. In Artificial Intelligence Journal, 125:1, pp. 5-41Global Structure: Treewidth w))exp(( wnOBattery AgeAlternatorFan BeltBatteryCharge DeliveredBattery PowerStarterRadioLights Engine Turn OverGas GaugeGasFuel PumpFuel LineDistributorSpark PlugsEngine StartLocal Structure 1:Context specific indepencenceBattery 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 CPDRepresent P(Xi|PaXi) using a decision treePath to leaf is an assignment to (a subset of) PaXiLeaves are distributions over Xi given assignment of PaXi on path to leafInterpretation of leaf: For specific assignment of PaXi on path to this leaf – Xi is independent of other parentsRepresentation can be exponentially smaller than equivalent tableApply SAT LetterJobTabular VE with Tree CPDsIf 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 inferenceDeterminism gives a little sparsity in table, but much bigger impact on inferenceMultiplying deterministic factor with other factor introduces many new zerosOperations 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 orderAdvances in machine learningNew 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 ConditioningTreewidth complexity (worst case)Better than treewidth complexity with local structureProvides a framework for time-space tradeoffsOnly quick intuition today, details in readingsA. DarwicheThe Computational Power of AssumptionsBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine StartA. DarwicheBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine StartThe Computational Power of AssumptionsA. DarwicheDecompositionBattery AgeAlternatorFan 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 Startp p+A. DarwicheCase AnalysisBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine StartBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine Startplp+pr*A. DarwicheCase AnalysisBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine StartBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine Startpl+pr*plpr*A. DarwicheCase AnalysisBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine StartBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine Startpl+pr*plpr*A. DarwicheCase AnalysisBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine StartBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine Startpl+pr*plpr*A. DarwicheDecomposition TreeAB C D EAABB CCDDBEBf(A)f(A,B)f(B,C)f(C,D)f(B,D,E)CutsetA. DarwicheDecomposition TreeAB C D EAABB CCDDBEBf(A)f(A,B)f(B,C)f(C,D)f(B,D,E)CutsetA. DarwicheDecomposition TreeAB C D EAABCCDDEBTime: O(n exp(w log n))Space: Linear(using appropriate dtree)f(A)f(A,B)f(B,C)f(C,D)f(B,D,E)CutsetA. DarwicheRC1(T,e) // compute probability of evidence e on dtree TIf T is a leaf nodeReturn Lookup(T,e)Else p := 0for each instantiation c of cutset(T)-E dop := p + RC1(Tl,ec) RC1(Tr,ec)return pRC1A. DarwicheLookup(T,e)X|U : CPT associated with leaf TIf X is instantiated in e, thenx: value of X in eu: value of U in eReturn x|uElse return 1 = xx|uA. DarwicheCachingAB C D E FAABB CCDDEEFA B CABCABCABCABCABCABCABCABCABCCC.27.39ContextA. DarwicheCachingAB C D E FAABB CCDDEEFA B CABCABCABCABCABCABCABCABCTime: O(n exp(w))Space: O(n exp(w))(using appropriate
View Full Document