1Context-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(( wnO2Battery 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 indepencence3CSI 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!4Local 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 15Today’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 model6Recursive Conditioning Treewidth complexity (worst case) Better than treewidth complexity with local structure Provides a framework for time-space tradeoffs Only quick intuition today, details in readingsA. DarwicheThe Computational Power of AssumptionsBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine Start7A. DarwicheBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine StartThe Computational Power of AssumptionsA. DarwicheDecompositionBattery AgeAlternator Fan BeltBatteryCharge DeliveredBattery PowerStarterRadioLightsEngine Turn OverGas GaugeGasLeakFuel LineDistributorSpark PlugsEngine Start8A. 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*9A. 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*10A. 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 TreeABCDEAABBCCDDBEBf(A)f(A,B)f(B,C)f(C,D)f(B,D,E)Cutset11A. DarwicheDecomposition TreeABCDEAABBCCDDBEBf(A)f(A,B)f(B,C)f(C,D)f(B,D,E)CutsetA. DarwicheDecomposition TreeABCDEAABCCDDEBTime: 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)Cutset12A. 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 = Σxθx|u13A. DarwicheCachingABCDE FAABBCCDDEEFA B CABCABCABCABCABCABCABCABCABCCC.27.39ContextA. DarwicheCachingABCDE FAABBCCDDEEFA B CABCABCABCABCABCABCABCABCTime: O(n exp(w))Space: O(n exp(w))(using appropriate dtree)ABCCC.27.39ContextRecursive ConditioningAn any-space algorithm with treewidth complexityDarwiche AIJ-0114A. DarwicheRC2(T,e)If T is a leaf node, return Lookup(T,e)y := instantiation of context(T)If cacheT[y] <> nil, return cacheT[y] p := 0For each instantiation c of cutset(T)-E dop := p + RC2(Tl,ec) RC2(Tr,ec)cacheT[y] := pReturn pRC2A. DarwicheDecomposition with Local StructureBCXAA, B, CX Independent of B, C given A15A. DarwicheDecomposition with Local StructureBCXAA, B, CX Independent of B, C given AA. DarwicheDecomposition with Local StructureBCXAA, B, CX Independent of B, C given
View Full Document