DOC PREVIEW
CMU CS 10708 - Context-specific independence

This preview shows page 1-2-3-4-5-6 out of 18 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 networksExploiting 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

CMU CS 10708 - Context-specific independence

Documents in this Course
Lecture

Lecture

15 pages

Lecture

Lecture

25 pages

Lecture

Lecture

24 pages

causality

causality

53 pages

lecture11

lecture11

16 pages

Exam

Exam

15 pages

Notes

Notes

12 pages

lecture

lecture

18 pages

lecture

lecture

16 pages

Lecture

Lecture

17 pages

Lecture

Lecture

15 pages

Lecture

Lecture

17 pages

Lecture

Lecture

19 pages

Lecture

Lecture

42 pages

Lecture

Lecture

16 pages

r6

r6

22 pages

lecture

lecture

20 pages

lecture

lecture

35 pages

Lecture

Lecture

19 pages

Lecture

Lecture

21 pages

lecture

lecture

21 pages

lecture

lecture

13 pages

review

review

50 pages

Semantics

Semantics

30 pages

lecture21

lecture21

26 pages

MN-crf

MN-crf

20 pages

hw4

hw4

5 pages

lecture

lecture

12 pages

Lecture

Lecture

25 pages

Lecture

Lecture

25 pages

Lecture

Lecture

14 pages

Lecture

Lecture

15 pages

Load more
Download Context-specific independence
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Context-specific independence and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Context-specific independence 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?