DOC PREVIEW
CMU CS 10708 - Context-specific independence Parameter learning: MLE

This preview shows page 1-2-3-21-22-23-43-44-45 out of 45 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 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 45 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 45 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 45 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 45 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 45 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 45 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 45 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 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

CMU CS 10708 - Context-specific independence Parameter learning: MLE

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 Parameter learning: MLE
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 Parameter learning: MLE 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 Parameter learning: MLE 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?