Mercurial > dylan

     1 <?xml version="1.0" encoding="iso-8859-1"?>

     2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"

     3                "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

     4 <html xmlns="http://www.w3.org/1999/xhtml"

     5 lang="en" xml:lang="en">

     6 <head>

     7 <title>Categorification of Plausible Reasoning</title>

     8 <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"/>

     9 <meta name="generator" content="Org-mode"/>

    10 <meta name="generated" content="2011-07-09 14:19:42 EDT"/>

    11 <meta name="author" content="Dylan Holmes"/>

    12 <meta name="description" content=""/>

    13 <meta name="keywords" content=""/>

    14 <style type="text/css">

    15  <!--/*--><![CDATA[/*><!--*/

    16   html { font-family: Times, serif; font-size: 12pt; }

    17   .title  { text-align: center; }

    18   .todo   { color: red; }

    19   .done   { color: green; }

    20   .tag    { background-color: #add8e6; font-weight:normal }

    21   .target { }

    22   .timestamp { color: #bebebe; }

    23   .timestamp-kwd { color: #5f9ea0; }

    24   .right  {margin-left:auto; margin-right:0px;  text-align:right;}

    25   .left   {margin-left:0px;  margin-right:auto; text-align:left;}

    26   .center {margin-left:auto; margin-right:auto; text-align:center;}

    27   p.verse { margin-left: 3% }

    28   pre {

    29 	border: 1pt solid #AEBDCC;

    30 	background-color: #F3F5F7;

    31 	padding: 5pt;

    32 	font-family: courier, monospace;

    33         font-size: 90%;

    34         overflow:auto;

    35   }

    36   table { border-collapse: collapse; }

    37   td, th { vertical-align: top;  }

    38   th.right  { text-align:center;  }

    39   th.left   { text-align:center;   }

    40   th.center { text-align:center; }

    41   td.right  { text-align:right;  }

    42   td.left   { text-align:left;   }

    43   td.center { text-align:center; }

    44   dt { font-weight: bold; }

    45   div.figure { padding: 0.5em; }

    46   div.figure p { text-align: center; }

    47   textarea { overflow-x: auto; }

    48   .linenr { font-size:smaller }

    49   .code-highlighted {background-color:#ffff00;}

    50   .org-info-js_info-navigation { border-style:none; }

    51   #org-info-js_console-label { font-size:10px; font-weight:bold;

    52                                white-space:nowrap; }

    53   .org-info-js_search-highlight {background-color:#ffff00; color:#000000;

    54                                  font-weight:bold; }

    55   /*]]>*/-->

    56 </style>

    57 <script type="text/javascript">

    58 <!--/*--><![CDATA[/*><!--*/

    59  function CodeHighlightOn(elem, id)

    60  {

    61    var target = document.getElementById(id);

    62    if(null != target) {

    63      elem.cacheClassElem = elem.className;

    64      elem.cacheClassTarget = target.className;

    65      target.className = "code-highlighted";

    66      elem.className   = "code-highlighted";

    67    }

    68  }

    69  function CodeHighlightOff(elem, id)

    70  {

    71    var target = document.getElementById(id);

    72    if(elem.cacheClassElem)

    73      elem.className = elem.cacheClassElem;

    74    if(elem.cacheClassTarget)

    75      target.className = elem.cacheClassTarget;

    76  }

    77 /*]]>*///-->

    78 </script>

    79 <script type="text/javascript" src="../MathJax/MathJax.js">

    80 <!--/*--><![CDATA[/*><!--*/

    81     MathJax.Hub.Config({

    82         // Only one of the two following lines, depending on user settings

    83         // First allows browser-native MathML display, second forces HTML/CSS

    84             config: ["MMLorHTML.js"], jax: ["input/TeX"],

    85         //  jax: ["input/TeX", "output/HTML-CSS"],

    86         extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js",

    87                      "TeX/noUndefined.js"],

    88         tex2jax: {

    89             inlineMath: [ ["\\(","\\)"] ],

    90             displayMath: [ ['$$','$$'], ["\\[","\\]"], ["\\begin{displaymath}","\\end{displaymath}"] ],

    91             skipTags: ["script","noscript","style","textarea","pre","code"],

    92             ignoreClass: "tex2jax_ignore",

    93             processEscapes: false,

    94             processEnvironments: true,

    95             preview: "TeX"

    96         },

    97         showProcessingMessages: true,

    98         displayAlign: "left",

    99         displayIndent: "2em",

   100 

   101         "HTML-CSS": {

   102              scale: 100,

   103              availableFonts: ["STIX","TeX"],

   104              preferredFont: "TeX",

   105              webFont: "TeX",

   106              imageFont: "TeX",

   107              showMathMenu: true,

   108         },

   109         MMLorHTML: {

   110              prefer: {

   111                  MSIE:    "MML",

   112                  Firefox: "MML",

   113                  Opera:   "HTML",

   114                  other:   "HTML"

   115              }

   116         }

   117     });

   118 /*]]>*///-->

   119 </script>

   120 </head>

   121 <body>

   122 <div id="content">

   123 

   124 

   125 

   126 

   127 <div id="table-of-contents">

   128 <h2>Table of Contents</h2>

   129 <div id="text-table-of-contents">

   130 <ul>

   131 <li><a href="#sec-1">1 Deductive and inductive posets </a>

   132 <ul>

   133 <li><a href="#sec-1-1">1.1 Definition </a></li>

   134 <li><a href="#sec-1-2">1.2 A canonical map from  deductive posets to inductive posets </a></li>

   135 </ul>

   136 </li>

   137 <li><a href="#sec-2">2 Assigning plausibilities to inductive posets </a>

   138 <ul>

   139 <li><a href="#sec-2-1">2.1 Consistent reasoning as a commutative diagram </a></li>

   140 <li><a href="#sec-2-2">2.2 ``Multiplicity'' is reciprocal probability </a></li>

   141 <li><a href="#sec-2-3">2.3 Laws for multiplicity </a></li>

   142 </ul>

   143 </li>

   144 </ul>

   145 </div>

   146 </div>

   147 

   148 <div id="outline-container-1" class="outline-2">

   149 <h2 id="sec-1"><span class="section-number-2">1</span> Deductive and inductive posets </h2>

   150 <div class="outline-text-2" id="text-1">

   151 

   152 

   153 

   154 </div>

   155 

   156 <div id="outline-container-1-1" class="outline-3">

   157 <h3 id="sec-1-1"><span class="section-number-3">1.1</span> Definition </h3>

   158 <div class="outline-text-3" id="text-1-1">

   159 

   160 <p>If you have a collection \(P\) of logical propositions, you can order them by

   161 implication: \(a\) precedes \(b\) if and only if \(a\) implies

   162 \(b\). This makes \(P\) into a poset. Since the ordering arose from

   163 deductive implication, we'll call this a <i>deductive poset</i>.

   164 </p>

   165 <p>

   166 If you have a deductive poset \(P\),  you can create a related poset \(P^*\)

   167 as follows: the underlying set is the same, and for any two

   168 propositions \(a\) and \(b\) in \(P\), \(a\) precedes

   169 \(ab\) in \(P^*\). We'll call this an <i>inductive poset</i>.

   170 </p>

   171 </div>

   172 

   173 </div>

   174 

   175 <div id="outline-container-1-2" class="outline-3">

   176 <h3 id="sec-1-2"><span class="section-number-3">1.2</span> A canonical map from  deductive posets to inductive posets </h3>

   177 <div class="outline-text-3" id="text-1-2">

   178 

   179 <p>Each poset corresponds with a poset-category, that is a category with

   180 at most one arrow between any two objects. Considered as categories,

   181 inductive and deuctive posets are related as follows: there is a map

   182 \(\mathscr{F}\) which sends each arrow \(a\rightarrow b\) in \(P\) to

   183 the arrow \(a\rightarrow ab\) in \(P^*\). In fact, since \(a\) implies

   184 \(b\) if and only if \(a = ab\), \(\mathscr{F}\) sends each arrow  in \(P\) to

   185 an identity arrow  in \(P^*\) (specifically, it sends the arrow

   186 \(a\rightarrow b\) to the identity arrow \(a\rightarrow a\)).

   187 </p>

   188 

   189 </div>

   190 </div>

   191 

   192 </div>

   193 

   194 <div id="outline-container-2" class="outline-2">

   195 <h2 id="sec-2"><span class="section-number-2">2</span> Assigning plausibilities to inductive posets </h2>

   196 <div class="outline-text-2" id="text-2">

   197 

   198 

   199 <p>

   200 Inductive posets encode the relative (<i>qualitative</i>) plausibilities of its

   201 propositions: there exists an arrow \(x\rightarrow y\) only if \(x\)

   202 is at least as plausible as \(y\).

   203 </p>

   204 

   205 </div>

   206 

   207 <div id="outline-container-2-1" class="outline-3">

   208 <h3 id="sec-2-1"><span class="section-number-3">2.1</span> Consistent reasoning as a commutative diagram </h3>

   209 <div class="outline-text-3" id="text-2-1">

   210 

   211 <p>Inductive categories enable the following neat trick: we can interpret

   212 the objects of \(P^*\) as states of given information and interpret

   213 each arrow \(a\rightarrow ab\) in \(P^*\) as an inductive inference: the arrow

   214 \(a\rightarrow ab\) represents an inferential leap from the state of

   215 knowledge where only \(a\) is given to the state of knowledge where

   216 both \(a\) and \(b\) are given&mdash; in this way, it represents

   217 the process of inferring \(b\) when  given \(a\), and we label the

   218 arrow with \((b|a)\).

   219 </p>

   220 <p>

   221 This trick has several important features that suggest its usefulness,

   222 namely

   223 </p><ul>

   224 <li>Composition of arrows corresponds to compound inference.

   225 </li>

   226 <li>In the special case of deductive inference, the inferential arrow is an

   227    identity; the source and destination states of knowledge are the same.

   228 </li>

   229 <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

   230    commutative square: \(x\rightarrow ax \rightarrow abx\) =

   231    \(x\rightarrow bx \rightarrow abx\) is the categorified version of

   232    \((AB|X)=(A|X)\cdot(B|AX)=(B|X)\cdot(A|BX)\).

   233 </li>

   234 <li>We can make plausibility assignments by enriching the inductive

   235    category \(P^*\) over some monoidal category, e.g. the set of real numbers

   236    (considered as a category) with its usual multiplication. <i>When we do</i>,

   237    the identity arrows of \(P^*\) &mdash;corresponding to

   238    deductive inferences&mdash; are assigned a value of certainty automatically.

   239 </li>

   240 </ul>

   241 

   242 

   243 </div>

   244 

   245 </div>

   246 

   247 <div id="outline-container-2-2" class="outline-3">

   248 <h3 id="sec-2-2"><span class="section-number-3">2.2</span> ``Multiplicity'' is reciprocal probability </h3>

   249 <div class="outline-text-3" id="text-2-2">

   250 

   251 <p>The natural numbers have a comparatively concrete origin: they are the

   252 result of decategorifying the category of finite sets<sup><a class="footref" name="fnr.2" href="#fn.2">2</a></sup>, or the

   253 coequalizer of the arrows from a one-object category to a two-object

   254 category with a single nonidentity arrow. Extensions of the set of

   255 natural numbers&mdash; such as

   256 the set of integers or rational numbers or real numbers&mdash; strike

   257 me as being somewhat more abstract (however, see the Eudoxus

   258 construction of the real numbers).

   259 </p>

   260 <p>

   261 Jaynes points out that our existing choice of scale for probabilities

   262 (i.e., the scale from 0 for impossibility to 1 for

   263 certainty) has a degree of freedom: any monotonic function of

   264 probability encodes the same information that probability does. Though

   265 the resulting laws for compound probability and so on change in form

   266 when probabilities are changed, they do not change in content. 

   267 </p>

   268 <p>

   269 With this in mind, it seems natural  and permissible to use not <i>probability</i> but

   270 <i>reciprocal probability</i> instead. This scale, which we might

   271  call <i>multiplicity</i>, ranges from 1 (certainty) to

   272 positive infinity (impossibility); higher numbers are ascribed to

   273 less-plausible events.

   274 </p>

   275 <p>

   276 In this way, the ``probability''

   277 associated with choosing one out of \(n\) indistinguishable choices

   278 becomes identified with \(n\).

   279 </p>

   280 </div>

   281 

   282 </div>

   283 

   284 <div id="outline-container-2-3" class="outline-3">

   285 <h3 id="sec-2-3"><span class="section-number-3">2.3</span> Laws for multiplicity </h3>

   286 <div class="outline-text-3" id="text-2-3">

   287 

   288 <p>Jaynes derives laws of probability; either his method or his results

   289 can be used to obtain laws for multiplicities.

   290 </p>

   291 <dl>

   292 <dt>product rule</dt><dd>The product rule is unchanged: \(\xi(AB|X)=\xi(A|X)\cdot

   293                    \xi(B|AX) = \xi(B|X)\cdot \xi(A|BX)\)

   294 </dd>

   295 <dt>certainty</dt><dd>States of absolute certainty are assigned a multiplicity

   296                 of 1. States of absolute impossibility are assigned a

   297                 multiplicity of positive infinity.

   298 </dd>

   299 <dt>entropy</dt><dd>In terms of probability, entropy has the form \(S=-\sum_i

   300               p_i \ln{p_i} = \sum_i p_i (-\ln{p_i}) = \sum_i p_i \ln{(1/p_i)}

   301               \). Hence, in terms of multiplicity, entropy

   302               has the form \(S = \sum_i \frac{\ln{\xi_i}}{\xi_i} \).

   303 

   304 <p>

   305               Another interesting quantity is \(\exp{S}\), which behaves

   306               multiplicitively rather than additively. \(\exp{S} =

   307               \prod_i \exp{\frac{\ln{\xi_i}}{\xi_i}} =

   308               \left(\exp{\ln{\xi_i}}\right)^{1/\xi_i} =  \prod_i \xi_i^{1/\xi_i} \)

   309 </p></dd>

   310 </dl>

   311 

   312 

   313 

   314 <div id="footnotes">

   315 <h2 class="footnotes">Footnotes: </h2>

   316 <div id="text-footnotes">

   317 <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>

   318 </p>

   319 

   320 <p class="footnote"><sup><a class="footnum" name="fn.2" href="#fnr.2">2</a></sup> As Baez explains.

   321 </p>

   322 </div>

   323 </div>

   324 </div>

   325 

   326 </div>

   327 </div>

   328 <div id="postamble">

   329 <p class="date">Date: 2011-07-09 14:19:42 EDT</p>

   330 <p class="author">Author: Dylan Holmes</p>

   331 <p class="creator">Org version 7.6 with Emacs version 23</p>

   332 <a href="http://validator.w3.org/check?uri=referer">Validate XHTML 1.0</a>

   333 </div>

   334 </div>

   335 </body>

   336 </html>
author	Robert McIntyre <rlm@mit.edu>
date	Fri, 28 Oct 2011 00:03:05 -0700
parents
children