Mercurial > dylan

annotate categorical/plausible.org @ 2:b4de894a1e2e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial import
author Robert McIntyre <rlm@mit.edu>
date Fri, 28 Oct 2011 00:03:05 -0700
parents
children
rev   line source
rlm@2 1 #+TITLE: Categorification of Plausible Reasoning
rlm@2 2 #+AUTHOR: Dylan Holmes
rlm@2 3 #+MATHJAX: align:"left" mathml:t path:"../MathJax/MathJax.js"
rlm@2 4 * COMMENT #+OPTIONS: LaTeX:dvipng
rlm@2 5
rlm@2 6 * Deductive and inductive posets
rlm@2 7
rlm@2 8 ** Definition
rlm@2 9 If you have a collection \(P\) of logical propositions, you can order them by
rlm@2 10 implication: \(a\) precedes \(b\) if and only if \(a\) implies
rlm@2 11 \(b\). This makes \(P\) into a poset. Since the ordering arose from
rlm@2 12 deductive implication, we'll call this a /deductive poset/.
rlm@2 13
rlm@2 14 If you have a deductive poset \(P\), you can create a related poset \(P^*\)
rlm@2 15 as follows: the underlying set is the same, and for any two
rlm@2 16 propositions \(a\) and \(b\) in \(P\), \(a\) precedes
rlm@2 17 \(ab\) in \(P^*\). We'll call this an /inductive poset/.
rlm@2 18
rlm@2 19 ** A canonical map from deductive posets to inductive posets
rlm@2 20 Each poset corresponds with a poset-category, that is a category with
rlm@2 21 at most one arrow between any two objects. Considered as categories,
rlm@2 22 inductive and deuctive posets are related as follows: there is a map
rlm@2 23 \(\mathscr{F}\) which sends each arrow \(a\rightarrow b\) in \(P\) to
rlm@2 24 the arrow \(a\rightarrow ab\) in \(P^*\). In fact, since \(a\) implies
rlm@2 25 \(b\) if and only if \(a = ab\), \(\mathscr{F}\) sends each arrow in \(P\) to
rlm@2 26 an identity arrow in \(P^*\) (specifically, it sends the arrow
rlm@2 27 \(a\rightarrow b\) to the identity arrow \(a\rightarrow a\)).
rlm@2 28
rlm@2 29
rlm@2 30 ** Assigning plausibilities to inductive posets
rlm@2 31
rlm@2 32 Inductive posets encode the relative (/qualitative/) plausibilities of its
rlm@2 33 propositions: there exists an arrow \(x\rightarrow y\) only if \(x\)
rlm@2 34 is at least as plausible as \(y\).
rlm@2 35
rlm@2 36 *** Consistent reasoning as a commutative diagram
rlm@2 37 Inductive categories enable the following neat trick: we can interpret
rlm@2 38 the objects of \(P^*\) as states of given information and interpret
rlm@2 39 each arrow \(a\rightarrow ab\) in \(P^*\) as an inductive inference: the arrow
rlm@2 40 \(a\rightarrow ab\) represents an inferential leap from the state of
rlm@2 41 knowledge where only \(a\) is given to the state of knowledge where
rlm@2 42 both \(a\) and \(b\) are given\mdash{} in this way, it represents
rlm@2 43 the process of inferring \(b\) when given \(a\), and we label the
rlm@2 44 arrow with \((b|a)\).
rlm@2 45
rlm@2 46 This trick has several important features that suggest its usefulness,
rlm@2 47 namely
rlm@2 48 - Composition of arrows corresponds to compound inference.
rlm@2 49 - In the special case of deductive inference, the inferential arrow is an
rlm@2 50 identity; the source and destination states of knowledge are the same.
rlm@2 51 - One aspect of the consistency requirement of Jaynes[fn:1] takes the form of a
rlm@2 52 commutative square: \(x\rightarrow ax \rightarrow abx\) =
rlm@2 53 \(x\rightarrow bx \rightarrow abx\) is the categorified version of
rlm@2 54 \((AB|X)=(A|X)\cdot(B|AX)=(B|X)\cdot(A|BX)\).
rlm@2 55 - We can make plausibility assignments by enriching the inductive
rlm@2 56 category \(P^*\) over some monoidal category, e.g. the set of real numbers
rlm@2 57 (considered as a category) with its usual multiplication. /When we do/,
rlm@2 58 the identity arrows of \(P^*\) \mdash{}corresponding to
rlm@2 59 deductive inferences\mdash{} are assigned a value of certainty automatically.
rlm@2 60
rlm@2 61 [fn:1] /(IIIa) If a conclusion can be reasoned out in more than one
rlm@2 62 way, then every possible way must lead to the same result./
rlm@2 63
rlm@2 64
rlm@2 65 *** Reciprocal probabilities
rlm@2 66 The natural numbers have a comparatively concrete origin: they are the
rlm@2 67 result of decategorifying the category of finite sets[fn:2], or the
rlm@2 68 coequalizer of the arrows from a one-object category to a two-object
rlm@2 69 category with a single nonidentity arrow. Extensions of the set of
rlm@2 70 natural numbers\mdash{} such as
rlm@2 71 the set of integers or rational numbers or real numbers\mdash{} strike
rlm@2 72 me as being somewhat more abstract.
rlm@2 73
rlm@2 74 Jaynes points out that our existing choice of scale for probabilities
rlm@2 75 (i.e., the scale from 0 for impossibility to 1 for
rlm@2 76 certainty) has a degree of freedom: any monotonic function of
rlm@2 77 probability encodes the same information that probability does.
rlm@2 78
rlm@2 79 With this in mind, it seems useful to use not /probability/ but
rlm@2 80 /reciprocal probability/ instead. This scale, which we might
rlm@2 81 tentatively call freeness, is a scale ranging 1 (certainty) to
rlm@2 82 positive infinity (impossibility).
rlm@2 83
rlm@2 84 In this way, the ``probability''
rlm@2 85 associated with choosing one out of \(n\) indistinguishable choices
rlm@2 86 becomes identified with \(n\).
rlm@2 87
rlm@2 88 The entropy
rlm@2 89
rlm@2 90 [fn:2] As Baez says.
rlm@2 91
rlm@2 92
rlm@2 93
rlm@2 94 ** self-questions
rlm@2 95
rlm@2 96 What circumstances would make \(\mathscr{F}\) an injection?
rlm@2 97
rlm@2 98 What if \(P=\{\top,\bot\}\)?
rlm@2 99
rlm@2 100
rlm@2 101
rlm@2 102 ** COMMENT
rlm@2 103 Inductive and deductive posets are related as follows: there is a monotone
rlm@2 104 inclusion map \(\mathscr{i}:P^*\hookrightarrow P\) which\mdash{} since \(a\)
rlm@2 105 implies \(b\) is equivalent to \(a=ab\)\mdash{} sends comparable
rlm@2 106 propositions in \(P\) to the same proposition in \(P^*\). Conversely,
rlm@2 107 only comparable propositions in \(P\) are sent to the same proposition
rlm@2 108 in \(P^*\).
rlm@2 109
rlm@2 110
rlm@2 111
rlm@2 112 ** Inductive posets and plausibility
rlm@2 113
rlm@2 114 * Inverse Probability