Random-World Semantics and Syntactic Independence for Expressive Languages
We consider three desiderata for a language combining logic and probability: logical expressivity, random-world semantics, and the existence of a useful syntactic condition for probabilistic independence. Achieving these three desiderata simultaneously is nontrivial. Expressivity can be achieved by...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Published: |
2008
|
| Online Access: | http://hdl.handle.net/1721.1/41516 |
| _version_ | 1826218139387428864 |
|---|---|
| author | McAllester, David Milch, Brian Goodman, Noah D. |
| author2 | Leslie Kaelbling |
| author_facet | Leslie Kaelbling McAllester, David Milch, Brian Goodman, Noah D. |
| author_sort | McAllester, David |
| collection | MIT |
| description | We consider three desiderata for a language combining logic and probability: logical expressivity, random-world semantics, and the existence of a useful syntactic condition for probabilistic independence. Achieving these three desiderata simultaneously is nontrivial. Expressivity can be achieved by using a formalism similar to a programming language, but standard approaches to combining programming languages with probabilities sacrifice random-world semantics. Naive approaches to restoring random-world semantics undermine syntactic independence criteria. Our main result is a syntactic independence criterion that holds for a broad class of highly expressive logics under random-world semantics. We explore various examples including Bayesian networks, probabilistic context-free grammars, and an example from Mendelian genetics. Our independence criterion supports a case-factor inference technique that reproduces both variable elimination for BNs and the inside algorithm for PCFGs. |
| first_indexed | 2024-09-23T17:14:49Z |
| id | mit-1721.1/41516 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T17:14:49Z |
| publishDate | 2008 |
| record_format | dspace |
| spelling | mit-1721.1/415162019-04-11T06:53:42Z Random-World Semantics and Syntactic Independence for Expressive Languages McAllester, David Milch, Brian Goodman, Noah D. Leslie Kaelbling Learning and Intelligent Systems We consider three desiderata for a language combining logic and probability: logical expressivity, random-world semantics, and the existence of a useful syntactic condition for probabilistic independence. Achieving these three desiderata simultaneously is nontrivial. Expressivity can be achieved by using a formalism similar to a programming language, but standard approaches to combining programming languages with probabilities sacrifice random-world semantics. Naive approaches to restoring random-world semantics undermine syntactic independence criteria. Our main result is a syntactic independence criterion that holds for a broad class of highly expressive logics under random-world semantics. We explore various examples including Bayesian networks, probabilistic context-free grammars, and an example from Mendelian genetics. Our independence criterion supports a case-factor inference technique that reproduces both variable elimination for BNs and the inside algorithm for PCFGs. 2008-05-05T15:45:52Z 2008-05-05T15:45:52Z 2008-05-03 MIT-CSAIL-TR-2008-025 http://hdl.handle.net/1721.1/41516 Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 6 p. application/pdf application/postscript |
| spellingShingle | McAllester, David Milch, Brian Goodman, Noah D. Random-World Semantics and Syntactic Independence for Expressive Languages |
| title | Random-World Semantics and Syntactic Independence for Expressive Languages |
| title_full | Random-World Semantics and Syntactic Independence for Expressive Languages |
| title_fullStr | Random-World Semantics and Syntactic Independence for Expressive Languages |
| title_full_unstemmed | Random-World Semantics and Syntactic Independence for Expressive Languages |
| title_short | Random-World Semantics and Syntactic Independence for Expressive Languages |
| title_sort | random world semantics and syntactic independence for expressive languages |
| url | http://hdl.handle.net/1721.1/41516 |
| work_keys_str_mv | AT mcallesterdavid randomworldsemanticsandsyntacticindependenceforexpressivelanguages AT milchbrian randomworldsemanticsandsyntacticindependenceforexpressivelanguages AT goodmannoahd randomworldsemanticsandsyntacticindependenceforexpressivelanguages |