Mercurial > dylan
diff categorical/plausible.html @ 2:b4de894a1e2e
initial import
| author | Robert McIntyre <rlm@mit.edu> |
|---|---|
| date | Fri, 28 Oct 2011 00:03:05 -0700 |
| parents | |
| children |
line wrap: on
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/categorical/plausible.html Fri Oct 28 00:03:05 2011 -0700 1.3 @@ -0,0 +1,336 @@ 1.4 +<?xml version="1.0" encoding="iso-8859-1"?> 1.5 +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" 1.6 + "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 1.7 +<html xmlns="http://www.w3.org/1999/xhtml" 1.8 +lang="en" xml:lang="en"> 1.9 +<head> 1.10 +<title>Categorification of Plausible Reasoning</title> 1.11 +<meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"/> 1.12 +<meta name="generator" content="Org-mode"/> 1.13 +<meta name="generated" content="2011-07-09 14:19:42 EDT"/> 1.14 +<meta name="author" content="Dylan Holmes"/> 1.15 +<meta name="description" content=""/> 1.16 +<meta name="keywords" content=""/> 1.17 +<style type="text/css"> 1.18 + <!--/*--><![CDATA[/*><!--*/ 1.19 + html { font-family: Times, serif; font-size: 12pt; } 1.20 + .title { text-align: center; } 1.21 + .todo { color: red; } 1.22 + .done { color: green; } 1.23 + .tag { background-color: #add8e6; font-weight:normal } 1.24 + .target { } 1.25 + .timestamp { color: #bebebe; } 1.26 + .timestamp-kwd { color: #5f9ea0; } 1.27 + .right {margin-left:auto; margin-right:0px; text-align:right;} 1.28 + .left {margin-left:0px; margin-right:auto; text-align:left;} 1.29 + .center {margin-left:auto; margin-right:auto; text-align:center;} 1.30 + p.verse { margin-left: 3% } 1.31 + pre { 1.32 + border: 1pt solid #AEBDCC; 1.33 + background-color: #F3F5F7; 1.34 + padding: 5pt; 1.35 + font-family: courier, monospace; 1.36 + font-size: 90%; 1.37 + overflow:auto; 1.38 + } 1.39 + table { border-collapse: collapse; } 1.40 + td, th { vertical-align: top; } 1.41 + th.right { text-align:center; } 1.42 + th.left { text-align:center; } 1.43 + th.center { text-align:center; } 1.44 + td.right { text-align:right; } 1.45 + td.left { text-align:left; } 1.46 + td.center { text-align:center; } 1.47 + dt { font-weight: bold; } 1.48 + div.figure { padding: 0.5em; } 1.49 + div.figure p { text-align: center; } 1.50 + textarea { overflow-x: auto; } 1.51 + .linenr { font-size:smaller } 1.52 + .code-highlighted {background-color:#ffff00;} 1.53 + .org-info-js_info-navigation { border-style:none; } 1.54 + #org-info-js_console-label { font-size:10px; font-weight:bold; 1.55 + white-space:nowrap; } 1.56 + .org-info-js_search-highlight {background-color:#ffff00; color:#000000; 1.57 + font-weight:bold; } 1.58 + /*]]>*/--> 1.59 +</style> 1.60 +<script type="text/javascript"> 1.61 +<!--/*--><![CDATA[/*><!--*/ 1.62 + function CodeHighlightOn(elem, id) 1.63 + { 1.64 + var target = document.getElementById(id); 1.65 + if(null != target) { 1.66 + elem.cacheClassElem = elem.className; 1.67 + elem.cacheClassTarget = target.className; 1.68 + target.className = "code-highlighted"; 1.69 + elem.className = "code-highlighted"; 1.70 + } 1.71 + } 1.72 + function CodeHighlightOff(elem, id) 1.73 + { 1.74 + var target = document.getElementById(id); 1.75 + if(elem.cacheClassElem) 1.76 + elem.className = elem.cacheClassElem; 1.77 + if(elem.cacheClassTarget) 1.78 + target.className = elem.cacheClassTarget; 1.79 + } 1.80 +/*]]>*///--> 1.81 +</script> 1.82 +<script type="text/javascript" src="../MathJax/MathJax.js"> 1.83 +<!--/*--><![CDATA[/*><!--*/ 1.84 + MathJax.Hub.Config({ 1.85 + // Only one of the two following lines, depending on user settings 1.86 + // First allows browser-native MathML display, second forces HTML/CSS 1.87 + config: ["MMLorHTML.js"], jax: ["input/TeX"], 1.88 + // jax: ["input/TeX", "output/HTML-CSS"], 1.89 + extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js", 1.90 + "TeX/noUndefined.js"], 1.91 + tex2jax: { 1.92 + inlineMath: [ ["\\(","\\)"] ], 1.93 + displayMath: [ ['$$','$$'], ["\\[","\\]"], ["\\begin{displaymath}","\\end{displaymath}"] ], 1.94 + skipTags: ["script","noscript","style","textarea","pre","code"], 1.95 + ignoreClass: "tex2jax_ignore", 1.96 + processEscapes: false, 1.97 + processEnvironments: true, 1.98 + preview: "TeX" 1.99 + }, 1.100 + showProcessingMessages: true, 1.101 + displayAlign: "left", 1.102 + displayIndent: "2em", 1.103 + 1.104 + "HTML-CSS": { 1.105 + scale: 100, 1.106 + availableFonts: ["STIX","TeX"], 1.107 + preferredFont: "TeX", 1.108 + webFont: "TeX", 1.109 + imageFont: "TeX", 1.110 + showMathMenu: true, 1.111 + }, 1.112 + MMLorHTML: { 1.113 + prefer: { 1.114 + MSIE: "MML", 1.115 + Firefox: "MML", 1.116 + Opera: "HTML", 1.117 + other: "HTML" 1.118 + } 1.119 + } 1.120 + }); 1.121 +/*]]>*///--> 1.122 +</script> 1.123 +</head> 1.124 +<body> 1.125 +<div id="content"> 1.126 + 1.127 + 1.128 + 1.129 + 1.130 +<div id="table-of-contents"> 1.131 +<h2>Table of Contents</h2> 1.132 +<div id="text-table-of-contents"> 1.133 +<ul> 1.134 +<li><a href="#sec-1">1 Deductive and inductive posets </a> 1.135 +<ul> 1.136 +<li><a href="#sec-1-1">1.1 Definition </a></li> 1.137 +<li><a href="#sec-1-2">1.2 A canonical map from deductive posets to inductive posets </a></li> 1.138 +</ul> 1.139 +</li> 1.140 +<li><a href="#sec-2">2 Assigning plausibilities to inductive posets </a> 1.141 +<ul> 1.142 +<li><a href="#sec-2-1">2.1 Consistent reasoning as a commutative diagram </a></li> 1.143 +<li><a href="#sec-2-2">2.2 ``Multiplicity'' is reciprocal probability </a></li> 1.144 +<li><a href="#sec-2-3">2.3 Laws for multiplicity </a></li> 1.145 +</ul> 1.146 +</li> 1.147 +</ul> 1.148 +</div> 1.149 +</div> 1.150 + 1.151 +<div id="outline-container-1" class="outline-2"> 1.152 +<h2 id="sec-1"><span class="section-number-2">1</span> Deductive and inductive posets </h2> 1.153 +<div class="outline-text-2" id="text-1"> 1.154 + 1.155 + 1.156 + 1.157 +</div> 1.158 + 1.159 +<div id="outline-container-1-1" class="outline-3"> 1.160 +<h3 id="sec-1-1"><span class="section-number-3">1.1</span> Definition </h3> 1.161 +<div class="outline-text-3" id="text-1-1"> 1.162 + 1.163 +<p>If you have a collection \(P\) of logical propositions, you can order them by 1.164 +implication: \(a\) precedes \(b\) if and only if \(a\) implies 1.165 +\(b\). This makes \(P\) into a poset. Since the ordering arose from 1.166 +deductive implication, we'll call this a <i>deductive poset</i>. 1.167 +</p> 1.168 +<p> 1.169 +If you have a deductive poset \(P\), you can create a related poset \(P^*\) 1.170 +as follows: the underlying set is the same, and for any two 1.171 +propositions \(a\) and \(b\) in \(P\), \(a\) precedes 1.172 +\(ab\) in \(P^*\). We'll call this an <i>inductive poset</i>. 1.173 +</p> 1.174 +</div> 1.175 + 1.176 +</div> 1.177 + 1.178 +<div id="outline-container-1-2" class="outline-3"> 1.179 +<h3 id="sec-1-2"><span class="section-number-3">1.2</span> A canonical map from deductive posets to inductive posets </h3> 1.180 +<div class="outline-text-3" id="text-1-2"> 1.181 + 1.182 +<p>Each poset corresponds with a poset-category, that is a category with 1.183 +at most one arrow between any two objects. Considered as categories, 1.184 +inductive and deuctive posets are related as follows: there is a map 1.185 +\(\mathscr{F}\) which sends each arrow \(a\rightarrow b\) in \(P\) to 1.186 +the arrow \(a\rightarrow ab\) in \(P^*\). In fact, since \(a\) implies 1.187 +\(b\) if and only if \(a = ab\), \(\mathscr{F}\) sends each arrow in \(P\) to 1.188 +an identity arrow in \(P^*\) (specifically, it sends the arrow 1.189 +\(a\rightarrow b\) to the identity arrow \(a\rightarrow a\)). 1.190 +</p> 1.191 + 1.192 +</div> 1.193 +</div> 1.194 + 1.195 +</div> 1.196 + 1.197 +<div id="outline-container-2" class="outline-2"> 1.198 +<h2 id="sec-2"><span class="section-number-2">2</span> Assigning plausibilities to inductive posets </h2> 1.199 +<div class="outline-text-2" id="text-2"> 1.200 + 1.201 + 1.202 +<p> 1.203 +Inductive posets encode the relative (<i>qualitative</i>) plausibilities of its 1.204 +propositions: there exists an arrow \(x\rightarrow y\) only if \(x\) 1.205 +is at least as plausible as \(y\). 1.206 +</p> 1.207 + 1.208 +</div> 1.209 + 1.210 +<div id="outline-container-2-1" class="outline-3"> 1.211 +<h3 id="sec-2-1"><span class="section-number-3">2.1</span> Consistent reasoning as a commutative diagram </h3> 1.212 +<div class="outline-text-3" id="text-2-1"> 1.213 + 1.214 +<p>Inductive categories enable the following neat trick: we can interpret 1.215 +the objects of \(P^*\) as states of given information and interpret 1.216 +each arrow \(a\rightarrow ab\) in \(P^*\) as an inductive inference: the arrow 1.217 +\(a\rightarrow ab\) represents an inferential leap from the state of 1.218 +knowledge where only \(a\) is given to the state of knowledge where 1.219 +both \(a\) and \(b\) are given— in this way, it represents 1.220 +the process of inferring \(b\) when given \(a\), and we label the 1.221 +arrow with \((b|a)\). 1.222 +</p> 1.223 +<p> 1.224 +This trick has several important features that suggest its usefulness, 1.225 +namely 1.226 +</p><ul> 1.227 +<li>Composition of arrows corresponds to compound inference. 1.228 +</li> 1.229 +<li>In the special case of deductive inference, the inferential arrow is an 1.230 + identity; the source and destination states of knowledge are the same. 1.231 +</li> 1.232 +<li>One aspect of the consistency requirement of Jaynes<sup><a class="footref" name="fnr.1" href="#fn.1">1</a></sup> takes the form of a 1.233 + commutative square: \(x\rightarrow ax \rightarrow abx\) = 1.234 + \(x\rightarrow bx \rightarrow abx\) is the categorified version of 1.235 + \((AB|X)=(A|X)\cdot(B|AX)=(B|X)\cdot(A|BX)\). 1.236 +</li> 1.237 +<li>We can make plausibility assignments by enriching the inductive 1.238 + category \(P^*\) over some monoidal category, e.g. the set of real numbers 1.239 + (considered as a category) with its usual multiplication. <i>When we do</i>, 1.240 + the identity arrows of \(P^*\) —corresponding to 1.241 + deductive inferences— are assigned a value of certainty automatically. 1.242 +</li> 1.243 +</ul> 1.244 + 1.245 + 1.246 +</div> 1.247 + 1.248 +</div> 1.249 + 1.250 +<div id="outline-container-2-2" class="outline-3"> 1.251 +<h3 id="sec-2-2"><span class="section-number-3">2.2</span> ``Multiplicity'' is reciprocal probability </h3> 1.252 +<div class="outline-text-3" id="text-2-2"> 1.253 + 1.254 +<p>The natural numbers have a comparatively concrete origin: they are the 1.255 +result of decategorifying the category of finite sets<sup><a class="footref" name="fnr.2" href="#fn.2">2</a></sup>, or the 1.256 +coequalizer of the arrows from a one-object category to a two-object 1.257 +category with a single nonidentity arrow. Extensions of the set of 1.258 +natural numbers— such as 1.259 +the set of integers or rational numbers or real numbers— strike 1.260 +me as being somewhat more abstract (however, see the Eudoxus 1.261 +construction of the real numbers). 1.262 +</p> 1.263 +<p> 1.264 +Jaynes points out that our existing choice of scale for probabilities 1.265 +(i.e., the scale from 0 for impossibility to 1 for 1.266 +certainty) has a degree of freedom: any monotonic function of 1.267 +probability encodes the same information that probability does. Though 1.268 +the resulting laws for compound probability and so on change in form 1.269 +when probabilities are changed, they do not change in content. 1.270 +</p> 1.271 +<p> 1.272 +With this in mind, it seems natural and permissible to use not <i>probability</i> but 1.273 +<i>reciprocal probability</i> instead. This scale, which we might 1.274 + call <i>multiplicity</i>, ranges from 1 (certainty) to 1.275 +positive infinity (impossibility); higher numbers are ascribed to 1.276 +less-plausible events. 1.277 +</p> 1.278 +<p> 1.279 +In this way, the ``probability'' 1.280 +associated with choosing one out of \(n\) indistinguishable choices 1.281 +becomes identified with \(n\). 1.282 +</p> 1.283 +</div> 1.284 + 1.285 +</div> 1.286 + 1.287 +<div id="outline-container-2-3" class="outline-3"> 1.288 +<h3 id="sec-2-3"><span class="section-number-3">2.3</span> Laws for multiplicity </h3> 1.289 +<div class="outline-text-3" id="text-2-3"> 1.290 + 1.291 +<p>Jaynes derives laws of probability; either his method or his results 1.292 +can be used to obtain laws for multiplicities. 1.293 +</p> 1.294 +<dl> 1.295 +<dt>product rule</dt><dd>The product rule is unchanged: \(\xi(AB|X)=\xi(A|X)\cdot 1.296 + \xi(B|AX) = \xi(B|X)\cdot \xi(A|BX)\) 1.297 +</dd> 1.298 +<dt>certainty</dt><dd>States of absolute certainty are assigned a multiplicity 1.299 + of 1. States of absolute impossibility are assigned a 1.300 + multiplicity of positive infinity. 1.301 +</dd> 1.302 +<dt>entropy</dt><dd>In terms of probability, entropy has the form \(S=-\sum_i 1.303 + p_i \ln{p_i} = \sum_i p_i (-\ln{p_i}) = \sum_i p_i \ln{(1/p_i)} 1.304 + \). Hence, in terms of multiplicity, entropy 1.305 + has the form \(S = \sum_i \frac{\ln{\xi_i}}{\xi_i} \). 1.306 + 1.307 +<p> 1.308 + Another interesting quantity is \(\exp{S}\), which behaves 1.309 + multiplicitively rather than additively. \(\exp{S} = 1.310 + \prod_i \exp{\frac{\ln{\xi_i}}{\xi_i}} = 1.311 + \left(\exp{\ln{\xi_i}}\right)^{1/\xi_i} = \prod_i \xi_i^{1/\xi_i} \) 1.312 +</p></dd> 1.313 +</dl> 1.314 + 1.315 + 1.316 + 1.317 +<div id="footnotes"> 1.318 +<h2 class="footnotes">Footnotes: </h2> 1.319 +<div id="text-footnotes"> 1.320 +<p class="footnote"><sup><a class="footnum" name="fn.1" href="#fnr.1">1</a></sup> <i>(IIIa) If a conclusion can be reasoned out in more than one way, then every possible way must lead to the same result.</i> 1.321 +</p> 1.322 + 1.323 +<p class="footnote"><sup><a class="footnum" name="fn.2" href="#fnr.2">2</a></sup> As Baez explains. 1.324 +</p> 1.325 +</div> 1.326 +</div> 1.327 +</div> 1.328 + 1.329 +</div> 1.330 +</div> 1.331 +<div id="postamble"> 1.332 +<p class="date">Date: 2011-07-09 14:19:42 EDT</p> 1.333 +<p class="author">Author: Dylan Holmes</p> 1.334 +<p class="creator">Org version 7.6 with Emacs version 23</p> 1.335 +<a href="http://validator.w3.org/check?uri=referer">Validate XHTML 1.0</a> 1.336 +</div> 1.337 +</div> 1.338 +</body> 1.339 +</html>