(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 58903, 1852]*) (*NotebookOutlinePosition[ 62595, 1971]*) (* CellTagsIndexPosition[ 61852, 1943]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell["Notes", "Section 1"], Cell[CellGroupData[{ Cell["Editorial Changes", "Subsection"], Cell["\<\ \"Footnotes\" section added to end of the paper to list the single footnote \ that originally appeared at the foot of one page. A hyperlink to this \ footnote has also been added to the body of the paper.\ \>", "Text"], Cell["\"ie\" changed to \"i.e.\" throughout the paper.", "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change1", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change4", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "Equation reformatted to make it more readable." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change2", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["H", FontSlant->"Italic"]}]], "1"], "/", RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["Q", FontSlant->"Italic"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], TraditionalForm]]], "\" changed to \"", Cell[BoxData[ FormBox[ FractionBox[ SubscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["H", FontSlant->"Italic"]}]], "1"], RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["Q", FontSlant->"Italic"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], TraditionalForm]]], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change3", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"exp", "(", RowBox[{ RowBox[{ RowBox[{"-", SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{"\[LeftBracketingBar]", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "i"]}], "\[RightBracketingBar]"}], "\[RightBracketingBar]"}], "2"]}], "/", "2"}], \(\[Epsilon]\^2\)}], ")"}], "/", \(\@\(2 \[Pi]\ \[Epsilon]\^2\)\)}], TraditionalForm]]], "\" changed to \"", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[\((1\/\@\(2 \[Pi]\ \[Epsilon]\^2\))\), RowBox[{"dim", " ", StyleBox["x", FontWeight->"Bold"]}]], RowBox[{"exp", "(", RowBox[{"-", FractionBox[ SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{"\[LeftBracketingBar]", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "i"]}], "\[RightBracketingBar]"}], "\[RightBracketingBar]"}], "2"], \(2 \[Epsilon]\^2\)]}], ")"}]}], TraditionalForm]]], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change5", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["H", FontSlant->"Italic"]}]], "2"], "/", RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["Q", FontSlant->"Italic"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], TraditionalForm]]], "\" changed to \"", Cell[BoxData[ FormBox[ FractionBox[ SubscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["H", FontSlant->"Italic"]}]], "2"], RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["Q", FontSlant->"Italic"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], TraditionalForm]]], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change6", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "Figure moved to a more appropriate point in the text." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["\<\ A maximum entropy interpretation of random access memory network computations \ \>", "Title"], Cell["\<\ Stephen P Luttrell Pattern Processing Principles SP4 division, RSRE Malvern, WORCS, WR14 3PS\ \>", "Author"], Cell["\<\ This paper appeared as SP4 Research Note, No. 137, 19th November 1990.\ \>", "Text"], Cell["Copyright \[Copyright] Controller HMSO, London, 1990.", "Text"], Cell[TextData[{ StyleBox["Abstract", FontWeight->"Bold"], "\n\nWe briefly summarise the maximum entropy method and its application to \ the problem of assigning a probability measure in a state space. We show how \ one can impose constraints on the marginal probabilities to guarantee that \ the maximum entropy solution can be interpreted in terms of random access \ memory network (specifically WISARD) computations. We thus achieve a \ unification of the theoretical analyses of this type of network and Gibbs \ distribution (or Markov random field) networks." }], "Abstract"], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], " Introduction" }], "Section 1"], Cell[TextData[{ "In this report", Cell[BoxData[ FormBox[ ButtonBox["FOOTNOTE", ButtonData:>"Footnote:1", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], " we examine the connection between using the maximum entropy method to \ assign probabilities given limited information [", ButtonBox["1", ButtonData:>"Ref:Jaynes1968", ButtonStyle->"Hyperlink"], "], and using random access memory networks (specifically, WISARD [", ButtonBox["2", ButtonData:>"Ref:AleksanderStonham1979", ButtonStyle->"Hyperlink"], "]) to perform pattern recognition tasks." }], "Text"], Cell[TextData[{ "WISARD is a real-time hardware network solution to a wide variety of \ pattern recognition problems. WISARD operates by computing the number of \ coincidences between configurations of binary digits (bits) in the input \ pattern and those in a predefined pattern category. If there are several \ categories for which such coincidences are computed, then an attempt to \ classify the input pattern can be made. The success of this approach to \ pattern recognition is a sufficient justification for its use. However, the \ nature of the information processing that WISARD performs is not entirely \ clear, which is why we have turned to the maximum entropy method to obtain \ some theoretical insight", Cell[BoxData[ FormBox[ ButtonBox["FOOTNOTE", ButtonData:>"Footnote:2", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], ". Our maximum entropy derivation can be taken to be a description of \ WISARD, so it should not be necessary to repeat here the description of \ WISARD that was given in [", ButtonBox["2", ButtonData:>"Ref:AleksanderStonham1979", ButtonStyle->"Hyperlink"], "])", Cell[BoxData[ FormBox[ ButtonBox["FOOTNOTE", ButtonData:>"Footnote:3", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], " ", "Maximum entropy method (MEM)" }], "Section"], Cell[TextData[{ "Frequently one is confronted with the problem of assigning a single \ probability density function (PDF) ", Cell[BoxData[ FormBox[ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " as an approximation to the true PDF ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " of some state vector ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], ", given only limited information about ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], ". There is a host of techniques for doing this, but the maximum entropy \ method (MEM) is desirable because it can be derived assuming only a few \ consistency criteria [", ButtonBox["3", ButtonData:>"Ref:ShoreJohnson1980", ButtonStyle->"Hyperlink"], "]." }], "Text"], Cell[TextData[{ "Let us summarise how the MEM is used to solve the probability assignment \ problem [", ButtonBox["1", ButtonData:>"Ref:Jaynes1968", ButtonStyle->"Hyperlink"], "]. Assume that we possess information about ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " that is expressed in the form" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(\[Sigma]\_i\), "=", RowBox[{ RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], RowBox[{\(S\_i\), "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], StyleBox[" ", FontWeight->"Plain"], "i"}]}], "=", "1"}]}], ",", "2", ",", "\[CenterEllipsis]", ",", "n"}], TraditionalForm]], "NumberedEquation",\ CellTags->"Eq:1"], Cell[TextData[{ "where the ", Cell[BoxData[ FormBox[ RowBox[{\(S\_i\), "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], TraditionalForm]]], " are \"sampling functions\" of the state vector ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], ", and the ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\_i\)]], " are the corresponding averages. We assume that the ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\_i\)]], " are known with sufficient precision that any residual uncertainties have \ a negligible eflect on the solution ", Cell[BoxData[ FormBox[ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " that we obtain. We demand that the problem of inverting this integral \ equation to recover ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " from the ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\_i\)]], " be solved, despite the fact that it is ill-conditioned and thus admits an \ infinite number of solutions ", Cell[BoxData[ FormBox[ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], ". The MEM selects a unique inverse by introducing the entropy ", Cell[BoxData[ \(TraditionalForm\`H\)]], " defined as" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{"H", "\[Congruent]", RowBox[{"-", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], StyleBox["log", FontWeight->"Plain"], StyleBox[" ", FontWeight->"Plain"], RowBox[{ StyleBox["Q", FontWeight->"Plain"], StyleBox["(", FontWeight->"Plain"], StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}]}]}]}]}], TraditionalForm]], "NumberedEquation"], Cell[TextData[{ "and maximising ", Cell[BoxData[ \(TraditionalForm\`H\)]], " subject to the conditions" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(\[Sigma]\_i\), "=", RowBox[{ RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], ")"}], RowBox[{\(S\_i\), "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], StyleBox[" ", FontWeight->"Plain"], "i"}]}], "=", "1"}]}], ",", "2", ",", "\[CenterEllipsis]", ",", "n"}], TraditionalForm]], "NumberedEquation",\ CellTags->"Eq:3"], Cell[TextData[{ "This can be solved by introducing Lagrange multipliers ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\_i\)]], " and maximising the cost function ", Cell[BoxData[ \(TraditionalForm\`H\_1\)]], " defined as" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{\(H\_1\), "\[Congruent]", RowBox[{"H", "-", RowBox[{\(\[Sum]\+\(i = 1\)\%n\), RowBox[{\(\[Lambda]\_i\), RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], ")"}], RowBox[{\(S\_i\), "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}]}]}]}]}]}]}], TraditionalForm]], "NumberedEquation", CellTags->"Eq:4"], Cell[TextData[{ "Functionally differentiate ", Cell[BoxData[ \(TraditionalForm\`H\_1\)]], " to obtain" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ FractionBox[ SubscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["H", FontSlant->"Italic"]}]], "1"], RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["Q", FontSlant->"Italic"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], "=", "\[AlignmentMarker]", RowBox[{ RowBox[{ RowBox[{"-", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["\[Xi]", FontWeight->"Bold"]}]], " ", RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], StyleBox["\[Xi]", FontWeight->"Bold"]}], ")"}], "log", " ", RowBox[{"Q", "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}]}]}]}], "-", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["\[Xi]", FontWeight->"Bold"]}]], " ", RowBox[{"Q", "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}], FractionBox[ RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], StyleBox["\[Xi]", FontWeight->"Bold"]}], ")"}], RowBox[{"Q", "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}]]}]}], "-", RowBox[{\(\[Sum]\+\(i = 1\)\%n\), RowBox[{\(\[Lambda]\_i\), RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["\[Xi]", FontWeight->"Bold"]}]], " ", RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], StyleBox["\[Xi]", FontWeight->"Bold"]}], ")"}], RowBox[{\(S\_i\), "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}]}]}]}]}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{ RowBox[{\(-log\), " ", RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}]}], StyleBox["-", FontWeight->"Plain"], StyleBox["1", FontWeight->"Plain"], StyleBox["-", FontWeight->"Plain"], RowBox[{\(\[Sum]\+\(i = 1\)\%n\), RowBox[{\(\[Lambda]\_i\), RowBox[{\(S\_i\), "(", StyleBox["x", FontWeight->"Bold"], ")"}]}]}]}]}]}], TraditionalForm]], "NumberedEquation", TextAlignment->AlignmentMarker, CellTags->"Ed:Change1"], Cell[TextData[{ "The solution ", Cell[BoxData[ FormBox[ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], TraditionalForm]]], " which satisfies ", Cell[BoxData[ FormBox[ RowBox[{ FractionBox[ SubscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["H", FontSlant->"Italic"]}]], "1"], RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["Q", FontSlant->"Italic"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], "=", "0"}], TraditionalForm]]], " is" }], "Text", CellTags->"Ed:Change2"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], StyleBox["=", FontWeight->"Plain"], RowBox[{ FractionBox[ StyleBox["1", FontWeight->"Plain"], "Z"], RowBox[{"exp", "(", RowBox[{"-", RowBox[{\(\[Sum]\+\(i = 1\)\%n\), RowBox[{\(\[Lambda]\_i\), RowBox[{\(S\_i\), "(", StyleBox["x", FontWeight->"Bold"], ")"}]}]}]}], ")"}]}]}], TraditionalForm]], "NumberedEquation"], Cell[TextData[{ "where the normalisation ", Cell[BoxData[ \(TraditionalForm\`Z\)]], " and the Lagrange multipliers ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\_i\)]], " must be chosen so that the constraints in ", ButtonBox["equation", ButtonData:>"Eq:3", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:3"], ") are satisfied." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], TraditionalForm]]], " has the familiar form of a Gibbs distribution, as encountered in \ statistical physics, and it can be shown to be equivalent to a Markov random \ field. Informally, ", Cell[BoxData[ FormBox[ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], TraditionalForm]]], " embodies the information expressed by the constraints in ", ButtonBox["equation", ButtonData:>"Eq:3", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:3"], "), but is otherwise noncommittal. This ", Cell[BoxData[ FormBox[ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], TraditionalForm]]], " is the only consistent assignment that can be made that satisfies the \ constraints and that satisfies the conditions of consistency of inference [", ButtonBox["3", ButtonData:>"Ref:ShoreJohnson1980", ButtonStyle->"Hyperlink"], "]." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], " ", "Constrained marginal probabilities" }], "Section"], Cell[TextData[{ "A flexible type of sampling function to use in ", ButtonBox["equation", ButtonData:>"Eq:1", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:1"], ") is the Dirac delta function ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(S\_i\), "(", StyleBox["x", FontWeight->"Bold"], ")"}], "=", RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "i"]}], ")"}]}], TraditionalForm]]], " which yields ", Cell[BoxData[ FormBox[ RowBox[{\(\[Sigma]\_i\), "=", RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "i"], ")"}]}], TraditionalForm]]], ": the average of ", Cell[BoxData[ FormBox[ RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "i"]}], ")"}], TraditionalForm]]], " is simply the PDF ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " evaluated at ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["=", FontWeight->"Plain"], SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "i"]}], TraditionalForm]]], ". One could also use a smeared version of ", Cell[BoxData[ FormBox[ RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "i"]}], ")"}], TraditionalForm]]], ", such as the Gaussian ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[\((1\/\@\(2 \[Pi]\ \[Epsilon]\^2\))\), RowBox[{"dim", " ", StyleBox["x", FontWeight->"Bold"]}]], RowBox[{"exp", "(", RowBox[{"-", FractionBox[ SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{"\[LeftBracketingBar]", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "i"]}], "\[RightBracketingBar]"}], "\[RightBracketingBar]"}], "2"], \(2 \[Epsilon]\^2\)]}], ")"}]}], TraditionalForm]]], ", which yields a ", StyleBox["weighted", FontSlant->"Italic"], " local average of ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " in the vicinity of ", Cell[BoxData[ FormBox[ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "i"], TraditionalForm]]], ". However, the simplest type of sampling function that can be implemented \ on a computer is a histogram bin, which yields an ", StyleBox["unweighted", FontSlant->"Italic"], " local average of ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], ". By defining a multidimensional tessellation of the space in which ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " sits one creates a set of nonoverlapping histogram bins: this is \ equivalent to computing the probabilitis of the states of a quantised version \ of the original state vector." }], "Text", CellTags->"Ed:Change3"], Cell["\<\ We shall henceforth assume that we use histogram bins in practical \ implementations, but we use Dirac delta functions in our derivations. This \ simplifies our theoretical notation, but (discrete) histogram bin expressions \ can easily be obtained at any stage from the (continuous) delta function \ expressions.\ \>", "Text"], Cell[TextData[{ "It proves to be useful to partition the components of ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " into subspaces, and to measure histograms only in these subspaces. This \ avoids an exponential explosion in the number of histogram bins that would be \ needed if we were to construct a histogram directly from ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " itself. We partition the components of ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " into ", Cell[BoxData[ \(TraditionalForm\`n\)]], " mutually exclusive sets" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["=", FontWeight->"Plain"], RowBox[{ StyleBox["(", FontWeight->"Plain"], RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((1)\)], ",", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((2)\)], ",", "\[CenterEllipsis]", ",", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((n)\)]}], StyleBox[")", FontWeight->"Plain"]}]}], TraditionalForm]], "NumberedEquation"], Cell[TextData[{ "where the set ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalC]\_i\)]], " of components of ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " that are contained in ", Cell[BoxData[ FormBox[ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], TraditionalForm]]], " has the properties" }], "Text"], Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalC]\_i \[Intersection] \[ScriptCapitalC]\ \_j = \[EmptySet]\ \ \ \ \ i \[NotEqual] j\)], "NumberedEquation", CellTags->"Eq:8"], Cell[BoxData[ FormBox[ RowBox[{\(\[Union]\+\(i = 1\)\%n \[ScriptCapitalC]\_i\), "=", SubscriptBox["\[ScriptCapitalC]", StyleBox["total", FontSlant->"Italic"]]}], TraditionalForm]], "NumberedEquation", CellTags->"Eq:9"], Cell[TextData[{ "where ", Cell[BoxData[ FormBox[ SubscriptBox["\[ScriptCapitalC]", StyleBox["total", FontSlant->"Italic"]], TraditionalForm]]], " is the set of all components of ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], "." }], "Text"], Cell["Implement Dirac delta sampling functions as follows", "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{\(P\_i\), "(", SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)], ")"}], "=", RowBox[{ RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], RowBox[{"\[Delta]", "(", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], "-", SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)]}], ")"}], " ", "i"}]}], "=", "1"}]}], ",", "2", ",", "\[CenterEllipsis]", ",", "n"}], TraditionalForm]], "NumberedEquation"], Cell[TextData[{ "which defines a set of marginal PDFs ", Cell[BoxData[ FormBox[ RowBox[{\(P\_i\), "(", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], ")"}], TraditionalForm]]], " of ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], ", and should be compared with ", ButtonBox["equation", ButtonData:>"Eq:1", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:1"], "). The corresponding set of constraint equations is" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{\(P\_i\), "(", SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)], ")"}], "=", RowBox[{ RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], ")"}], RowBox[{"\[Delta]", "(", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], "-", SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)]}], ")"}], " ", "i"}]}], "=", "1"}]}], ",", "2", ",", "\[CenterEllipsis]", ",", "n"}], TraditionalForm]], "NumberedEquation", CellTags->"Eq:11"], Cell[TextData[{ "which should be compared with ", ButtonBox["equation", ButtonData:>"Eq:3", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:3"], "). Note that we assume that the values of the constraints are known \ precisely, whereas in practice the ", Cell[BoxData[ FormBox[ RowBox[{\(P\_i\), "(", SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)], ")"}], TraditionalForm]]], " are discretised into histogram bins whose contents will be only an \ estimate of the ideal histogram values. We do not analyse the sensitivity of \ the maximum entropy ", Cell[BoxData[ FormBox[ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " to estimation errors", Cell[BoxData[ FormBox[ ButtonBox["FOOTNOTE", ButtonData:>"Footnote:4", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "." }], "Text"], Cell[TextData[{ "The constraints are now indexed by both a discrete index ", Cell[BoxData[ \(TraditionalForm\`i\)]], " and a continuous \"index\" ", Cell[BoxData[ FormBox[ SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)], TraditionalForm]]], ", so we have to use ", Cell[BoxData[ FormBox[ RowBox[{\(\[Sum]\_\(i = 1\)\%n\), RowBox[{\(\[Lambda]\_i\), "\[LongRightArrow]", RowBox[{\(\[Sum]\_\(i = 1\)\%n\), RowBox[{"\[Integral]", RowBox[{ SuperscriptBox[ StyleBox[ RowBox[{"d", StyleBox["y", FontWeight->"Bold"]}]], \((i)\)], RowBox[{\(\[Lambda]\_i\), "(", SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)], ")"}]}]}]}]}]}], TraditionalForm]]], " to replace the Lagrange multipliers ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\_i\)]], " in ", ButtonBox["equation", ButtonData:>"Eq:4", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:4"], ") by Lagrange multiplier functions ", Cell[BoxData[ FormBox[ RowBox[{\(\[Lambda]\_i\), "(", SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)], ")"}], TraditionalForm]]], ". We must therefore maximise ", Cell[BoxData[ \(TraditionalForm\`H\_2\)]], " defined as" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{\(H\_2\), "\[Congruent]", RowBox[{"H", "-", RowBox[{\(\[Sum]\+\(i = 1\)\%n\), RowBox[{"\[Integral]", RowBox[{ SuperscriptBox[ StyleBox[ RowBox[{"d", StyleBox["y", FontWeight->"Bold"]}]], \((i)\)], RowBox[{\(\[Lambda]\_i\), "(", SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)], ")"}], RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], ")"}], RowBox[{"\[Delta]", "(", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], "-", SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)]}], ")"}]}]}]}]}]}]}]}], TraditionalForm]], "NumberedEquation"], Cell[TextData[{ "Functionally differentiate ", Cell[BoxData[ \(TraditionalForm\`H\_2\)]], " to obtain" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ FractionBox[ SubscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["H", FontSlant->"Italic"]}]], "2"], RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["Q", FontSlant->"Italic"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], "=", "\[AlignmentMarker]", RowBox[{ RowBox[{ RowBox[{"-", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["\[Xi]", FontWeight->"Bold"]}]], " ", RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], StyleBox["\[Xi]", FontWeight->"Bold"]}], ")"}], "log", " ", RowBox[{"Q", "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}]}]}]}], "-", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["\[Xi]", FontWeight->"Bold"]}]], " ", RowBox[{"Q", "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}], FractionBox[ RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], StyleBox["\[Xi]", FontWeight->"Bold"]}], ")"}], RowBox[{"Q", "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}]]}]}], "-", RowBox[{\(\[Sum]\+\(i = 1\)\%n\), RowBox[{"\[Integral]", RowBox[{ SuperscriptBox[ StyleBox[ RowBox[{"d", StyleBox["y", FontWeight->"Bold"]}]], \((i)\)], RowBox[{\(\[Lambda]\_i\), "(", SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)], ")"}], RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["\[Xi]", FontWeight->"Bold"]}]], " ", RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], StyleBox["-", FontWeight->"Plain"], StyleBox["\[Xi]", FontWeight->"Bold"]}], ")"}], RowBox[{"\[Delta]", "(", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], "-", SuperscriptBox[ StyleBox["y", FontWeight->"Bold"], \((i)\)]}], ")"}]}]}]}]}]}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{ RowBox[{\(-log\), " ", RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}]}], StyleBox["-", FontWeight->"Plain"], StyleBox["1", FontWeight->"Plain"], StyleBox["-", FontWeight->"Plain"], RowBox[{\(\[Sum]\+\(i = 1\)\%n\), RowBox[{\(\[Lambda]\_i\), "(", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], ")"}]}]}]}]}], TraditionalForm]], "NumberedEquation", TextAlignment->AlignmentMarker, CellTags->"Ed:Change4"], Cell[TextData[{ "Setting ", Cell[BoxData[ FormBox[ RowBox[{ FractionBox[ SubscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["H", FontSlant->"Italic"]}]], "2"], RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["Q", FontSlant->"Italic"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], "=", "0"}], TraditionalForm]]], " yields the maximum entropy solution in the form" }], "Text", CellTags->"Ed:Change5"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], StyleBox["=", FontWeight->"Plain"], StyleBox["\[AlignmentMarker]", FontWeight->"Plain"], RowBox[{ RowBox[{ FractionBox[ StyleBox["1", FontWeight->"Plain"], "Z"], RowBox[{"exp", "(", RowBox[{"-", RowBox[{\(\[Sum]\+\(i = 1\)\%n\), RowBox[{\(\[Lambda]\_i\), "(", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], ")"}]}]}], ")"}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{ RowBox[{\(1\/Z\), SuperscriptBox["e", RowBox[{"-", RowBox[{\(\[Lambda]\_1\), "(", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((1)\)], ")"}]}]], SuperscriptBox["e", RowBox[{"-", RowBox[{\(\[Lambda]\_2\), "(", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((2)\)], ")"}]}]], "\[CenterEllipsis]", " ", SuperscriptBox["e", RowBox[{"-", RowBox[{\(\[Lambda]\_n\), "(", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((n)\)], ")"}]}]]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{ RowBox[{\(P\_1\), "(", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((1)\)], ")"}], RowBox[{\(P\_2\), "(", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((2)\)], ")"}], "\[CenterEllipsis]", " ", RowBox[{\(P\_n\), "(", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((n)\)], ")"}]}]}]}]}], TraditionalForm]], "NumberedEquation", TextAlignment->AlignmentMarker, CellTags->"Eq:14"], Cell[TextData[{ "In the final step of ", ButtonBox["equation", ButtonData:>"Eq:14", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:14"], ") we use the non-intersection property in ", ButtonBox["equation", ButtonData:>"Eq:8", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:8"], ") to select ", Cell[BoxData[ \(TraditionalForm\`Z\)]], " and the ", Cell[BoxData[ FormBox[ RowBox[{\(\[Lambda]\_i\), "(", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], ")"}], TraditionalForm]]], " in such a way that the constraints in ", ButtonBox["equation", ButtonData:>"Eq:11", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:11"], ") are satisfied. The convenient factorisation of this result into a \ product of the marginal probabilities does not occur if ", ButtonBox["equation", ButtonData:>"Eq:8", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:8"], ") is violated. ", ButtonBox["Equation", ButtonData:>"Eq:14", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:14"], ") also has an intuitive interpretation: it is the only ", Cell[BoxData[ FormBox[ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], TraditionalForm]]], " that both satisfies the constraints and does not introduce any \ correlations between the separate partitions ", Cell[BoxData[ FormBox[ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], TraditionalForm]]], " of the components of ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], "." }], "Text"], Cell[TextData[{ "This might seem to be a rather circuitous way of deriving ", ButtonBox["equation", ButtonData:>"Eq:14", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:14"], "). However, the MEM also allows us to handle cases where ", ButtonBox["equation", ButtonData:>"Eq:8", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:8"], ") is violated, so the MEM provides a unification between the simple case \ that we have studied here and the more complicated Gibbs distribution cases \ that arise elsewhere. One obvious benefit of using ", ButtonBox["equation", ButtonData:>"Eq:8", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:8"], ") is that the MEM leads to an assignment for ", Cell[BoxData[ FormBox[ RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], TraditionalForm]]], " that we can express in closed form, where the values of all the Lagrange \ multipliers are known. This avoids the need to perform extensive numerical \ simulations to determine the Lagrange multipliers, as is usually the case \ with Gibbs distributions." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], " ", "Random access memory (RAM) network" }], "Section"], Cell[TextData[Cell[TextData[{ " ", ButtonBox["OPEN", ButtonData:>{ URL[ "http://www.luttrell.org.uk/papers/sp4_137/fig1.gif"], None}, Active->True, ButtonStyle->"Hyperlink"], " " }]]], "NumberedFigure", TextAlignment->Center, CellTags->{"Fig:1", "Ed:Change6"}], Cell["Block diagram of MEM solution", "Caption"], Cell[TextData[{ "The factorised solution in ", ButtonBox["equation", ButtonData:>"Eq:14", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:14"], ") could be implemented in hardware as shown in ", ButtonBox["figure", ButtonData:>"Fig:1", ButtonStyle->"Hyperlink"], " ", CounterBox["NumberedFigure", "Fig:1"], ". This implementation assumes that the state vector ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " is quantised by representing each of its components using a finite number \ of binary digits (bits). The ", Cell[BoxData[ \(TraditionalForm\`i\)]], "-th block in this circuit is a look-up table which implements a \ transformation from ", Cell[BoxData[ FormBox[ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], TraditionalForm]]], " (the address of an entry in the table) to ", Cell[BoxData[ FormBox[ RowBox[{"log", " ", RowBox[{\(P\_i\), "(", SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], \((i)\)], ")"}]}], TraditionalForm]]], " (the corresponding entry in the table). The data bus at the bottom of ", ButtonBox["figure", ButtonData:>"Fig:1", ButtonStyle->"Hyperlink"], " ", CounterBox["NumberedFigure", "Fig:1"], " carries the components of ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " (represented bitwise) to the relevant look-up table. Note that each bit \ of ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " is used exactly once in forming addresses for the look-up tables (this \ follows from the conditions in ", ButtonBox["equation", ButtonData:>"Eq:8", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:8"], ") and ", ButtonBox["equation", ButtonData:>"Eq:9", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:9"], ")), so the mapping from ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " to the set of addresses is ", StyleBox["bijective", FontSlant->"Italic"], ". The upper part of ", ButtonBox["figure", ButtonData:>"Fig:1", ButtonStyle->"Hyperlink"], " ", CounterBox["NumberedFigure", "Fig:1"], " shows how the outputs are directed to an accumulator where they are \ summed to form ", Cell[BoxData[ FormBox[ RowBox[{"log", " ", RowBox[{"Q", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}]}], TraditionalForm]]], "." }], "Text"], Cell[TextData[{ ButtonBox["Figure", ButtonData:>"Fig:1", ButtonStyle->"Hyperlink"], " ", CounterBox["NumberedFigure", "Fig:1"], " is a variant of the WISARD pattern recognition network [", ButtonBox["2", ButtonData:>"Ref:AleksanderStonham1979", ButtonStyle->"Hyperlink"], "]. The elements that our MEM solution and WISARD have in common are: a \ bijective mapping from the bits of an input state vector onto the address \ lines of a set of RAMs, and the accumulation of the outputs of the RAMs to \ form the overall network output." }], "Text"], Cell[TextData[{ "However, there are some differences between the MEM and the WISARD \ prescriptions for the contents of the RAMs. The MEM specifies a set of \ functions (i.e. logarithms of marginal probabilities) to tabulate in the \ RAMs. Suppose that we truncate these table entries to a 1-bit representation, \ so that we use 0 to represent small logarithmic probabilities and 1 to \ represent large logarithmic probabilities. Each entry (i.e. 1 or 0) in the \ table then records whether the configuration of binary digits (i.e. the \ address of the entry) frequently occurs in the set of patterns corresponding \ to ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " (the \"training set\"). The final output is therefore the total number of \ l's that the input pattern addresses in the ", Cell[BoxData[ \(TraditionalForm\`n\)]], " tables. In effect, this is the total number of coincidences between \ configurations of bits in the input pattern and those in a predefined \ category. This 1-bit version of the MEM solution is qualitatively the same as \ the table look-up and summation operations performed in the simplest WISARD \ network, so we have completed the connection between MEM probability \ assignment and WISARD." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], " ", "Conclusions" }], "Section"], Cell[TextData[{ "We have shown how the maximum entropy method, when appropriately \ constrained by a set of marginal PDFs, yields a factorised form for the \ estimate of a PDF: this is a very simple type of Gibbs distribution. \ Furthermore, we have shown how the structure of this solution is closely \ related to the computations that are performed in the simplest type of WISARD \ network. We propose that the MEM could be used as an aid to deriving and \ interpreting WISARD-like computations", Cell[BoxData[ FormBox[ ButtonBox["FOOTNOTE", ButtonData:>"Footnote:5", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "." }], "Text"], Cell["\<\ Although we have applied the MEM to only a single category of input vector, \ it can be generalised to the multi-category case, although this involves a \ considerable amount of algebra.\ \>", "Text"], Cell[TextData[{ "The MEM can also be applied to more complicated systems, where marginal \ PDFs of functions derived from the input vector are constrained ", StyleBox["in addition to", FontSlant->"Italic"], " the existing constraints on marginal PDFs obtained directly from the \ data", Cell[BoxData[ FormBox[ ButtonBox["FOOTNOTE", ButtonData:>"Footnote:6", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["References", "Section"], Cell[TextData[{ "[1] Jaynes E T. Prior probabilities. ", StyleBox["IEEE Trans. SSC", FontSlant->"Italic"], ", ", StyleBox["4", FontWeight->"Bold"], "(3), 227-241, 1968." }], "Reference", CellTags->"Ref:Jaynes1968"], Cell[TextData[{ "[2] Aleksander I and Stonham T J. Guide to pattern recognition using \ random access memories. ", StyleBox["Computers and Digital Techniques", FontSlant->"Italic"], ", ", StyleBox["2", FontWeight->"Bold"], "(1), 29-40, 1979." }], "Reference", CellTags->"Ref:AleksanderStonham1979"], Cell[TextData[{ "[3] Shore J E and Johnson R W. Axiomatic derivation of the principle of \ maximum entropy and the principle of minimum cross-entropy. ", StyleBox["IEEE Trans. IT", FontSlant->"Italic"], ", ", StyleBox["26", FontWeight->"Bold"], "(1), 26-37, 1980." }], "Reference", CellTags->"Ref:ShoreJohnson1980"] }, Closed]], Cell[CellGroupData[{ Cell["Footnotes", "Section"], Cell["\<\ 1. This report is the last resting place of a letter that was rejected by \ both Network and by Neural Computation! I do not now intend to get this \ published - it is simply not worth the time and effort.\ \>", "Text", CellTags->"Footnote:1"], Cell["\<\ 2. A referee for Neural Computation insisted that I was deriving a random \ access memory interpretation of maximum entropy solutions, rather than the \ other way around! Of course, this is absurd. How could a specific application \ of the maximum entropy method be regarded as a way of interpreting maximum \ entropy solutions in general?\ \>", "Text", CellTags->"Footnote:2"], Cell["\<\ 3. It is an open question whether random access memory techniques such as \ WISARD are relevant to \"neural\" research. In my opinion the underlying \ ideas have the spirit of neural research, but the specific embodiment of \ those ideas is definitely not neural. Referees for both Network and Neural \ Computation insisted that these techniques were not neural.\ \>", "Text", CellTags->"Footnote:3"], Cell["\<\ 4. By making an appropriate choice for the size of the histogram bins one can \ make a trade-off between a high resolution noisy histogram or a low \ resolution smooth histogram. One could also attempt to fit a smooth curve \ (i.e. use a parametric PDF model) to the contents of the histogram bins.\ \>", "Text", CellTags->"Footnote:4"], Cell["\<\ 5. This is an example of the use of theoretical analysis to interpret a \ soft/hardware solution to a problem - not the other way around.\ \>", "Text", CellTags->"Footnote:5"], Cell["\<\ 6. This oblique remark is a reference to the Adaptive Cluster Expansion (ACE) \ technique that I have successfully applied to the problem of anomaly \ detection.\ \>", "Text", CellTags->"Footnote:6"] }, Closed]] }, Open ]] }, FrontEndVersion->"5.0 for Microsoft Windows", ScreenRectangle->{{0, 1280}, {0, 941}}, WindowToolbars->{}, WindowSize->{665.375, 641}, WindowMargins->{{307.25, Automatic}, {Automatic, 50}}, Magnification->1, StyleDefinitions -> "Report.nb" ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{ "Eq:1"->{ Cell[11934, 387, 829, 23, 70, "NumberedEquation", CellTags->"Eq:1"]}, "Eq:3"->{ Cell[15403, 499, 829, 23, 70, "NumberedEquation", CellTags->"Eq:3"]}, "Eq:4"->{ Cell[16492, 534, 793, 21, 70, "NumberedEquation", CellTags->"Eq:4"]}, "Ed:Change1"->{ Cell[17417, 564, 3686, 97, 70, "NumberedEquation", CellTags->"Ed:Change1"]}, "Ed:Change2"->{ Cell[21106, 663, 811, 28, 70, "Text", CellTags->"Ed:Change2"]}, "Ed:Change3"->{ Cell[24438, 784, 4274, 131, 70, "Text", CellTags->"Ed:Change3"]}, "Eq:8"->{ Cell[30962, 991, 179, 3, 70, "NumberedEquation", CellTags->"Eq:8"]}, "Eq:9"->{ Cell[31144, 996, 262, 6, 70, "NumberedEquation", CellTags->"Eq:9"]}, "Eq:11"->{ Cell[33500, 1074, 1055, 28, 70, "NumberedEquation", CellTags->"Eq:11"]}, "Ed:Change4"->{ Cell[38668, 1232, 4402, 113, 70, "NumberedEquation", CellTags->"Ed:Change4"]}, "Ed:Change5"->{ Cell[43073, 1347, 632, 20, 70, "Text", CellTags->"Ed:Change5"]}, "Eq:14"->{ Cell[43708, 1369, 2387, 63, 70, "NumberedEquation", CellTags->"Eq:14"]}, "Fig:1"->{ Cell[49409, 1552, 288, 10, 70, "NumberedFigure", CellTags->{"Fig:1", "Ed:Change6"}]}, "Ed:Change6"->{ Cell[49409, 1552, 288, 10, 70, "NumberedFigure", CellTags->{"Fig:1", "Ed:Change6"}]}, "Ref:Jaynes1968"->{ Cell[56097, 1764, 234, 9, 70, "Reference", CellTags->"Ref:Jaynes1968"]}, "Ref:AleksanderStonham1979"->{ Cell[56334, 1775, 318, 10, 70, "Reference", CellTags->"Ref:AleksanderStonham1979"]}, "Ref:ShoreJohnson1980"->{ Cell[56655, 1787, 335, 10, 70, "Reference", CellTags->"Ref:ShoreJohnson1980"]}, "Footnote:1"->{ Cell[57058, 1804, 255, 5, 70, "Text", CellTags->"Footnote:1"]}, "Footnote:2"->{ Cell[57316, 1811, 389, 7, 70, "Text", CellTags->"Footnote:2"]}, "Footnote:3"->{ Cell[57708, 1820, 412, 7, 70, "Text", CellTags->"Footnote:3"]}, "Footnote:4"->{ Cell[58123, 1829, 348, 6, 70, "Text", CellTags->"Footnote:4"]}, "Footnote:5"->{ Cell[58474, 1837, 187, 4, 70, "Text", CellTags->"Footnote:5"]}, "Footnote:6"->{ Cell[58664, 1843, 211, 5, 70, "Text", CellTags->"Footnote:6"]} } *) (*CellTagsIndex CellTagsIndex->{ {"Eq:1", 59572, 1870}, {"Eq:3", 59664, 1873}, {"Eq:4", 59756, 1876}, {"Ed:Change1", 59854, 1879}, {"Ed:Change2", 59959, 1882}, {"Ed:Change3", 60051, 1885}, {"Eq:8", 60139, 1888}, {"Eq:9", 60230, 1891}, {"Eq:11", 60322, 1894}, {"Ed:Change4", 60423, 1897}, {"Ed:Change5", 60530, 1900}, {"Eq:14", 60618, 1903}, {"Fig:1", 60714, 1906}, {"Ed:Change6", 60828, 1909}, {"Ref:Jaynes1968", 60946, 1912}, {"Ref:AleksanderStonham1979", 61062, 1915}, {"Ref:ShoreJohnson1980", 61185, 1918}, {"Footnote:1", 61293, 1921}, {"Footnote:2", 61385, 1924}, {"Footnote:3", 61477, 1927}, {"Footnote:4", 61569, 1930}, {"Footnote:5", 61661, 1933}, {"Footnote:6", 61753, 1936} } *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1776, 53, 26, 0, 70, "Section 1"], Cell[CellGroupData[{ Cell[1827, 57, 39, 0, 70, "Subsection"], Cell[1869, 59, 228, 4, 70, "Text"], Cell[2100, 65, 64, 0, 70, "Text"], Cell[2167, 67, 412, 14, 70, "Text"], Cell[2582, 83, 1148, 40, 70, "Text"], Cell[3733, 125, 2034, 54, 70, "Text"], Cell[5770, 181, 1148, 40, 70, "Text"], Cell[6921, 223, 252, 8, 70, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[7222, 237, 103, 3, 70, "Title"], Cell[7328, 242, 118, 5, 70, "Author"], Cell[7449, 249, 94, 2, 70, "Text"], Cell[7546, 253, 69, 0, 70, "Text"], Cell[7618, 255, 587, 10, 70, "Abstract"], Cell[CellGroupData[{ Cell[8230, 269, 78, 4, 70, "Section 1"], Cell[8311, 275, 637, 18, 70, "Text"], Cell[8951, 295, 1358, 31, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[10346, 331, 98, 5, 70, "Section"], Cell[10447, 338, 1055, 32, 70, "Text"], Cell[11505, 372, 426, 13, 70, "Text"], Cell[11934, 387, 829, 23, 70, "NumberedEquation", CellTags->"Eq:1"], Cell[12766, 412, 1553, 48, 70, "Text"], Cell[14322, 462, 948, 28, 70, "NumberedEquation"], Cell[15273, 492, 127, 5, 70, "Text"], Cell[15403, 499, 829, 23, 70, "NumberedEquation", CellTags->"Eq:3"], Cell[16235, 524, 254, 8, 70, "Text"], Cell[16492, 534, 793, 21, 70, "NumberedEquation", CellTags->"Eq:4"], Cell[17288, 557, 126, 5, 70, "Text"], Cell[17417, 564, 3686, 97, 70, "NumberedEquation", CellTags->"Ed:Change1"], Cell[21106, 663, 811, 28, 70, "Text", CellTags->"Ed:Change2"], Cell[21920, 693, 689, 21, 70, "NumberedEquation"], Cell[22612, 716, 402, 15, 70, "Text"], Cell[23017, 733, 1277, 39, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[24331, 777, 104, 5, 70, "Section"], Cell[24438, 784, 4274, 131, 70, "Text", CellTags->"Ed:Change3"], Cell[28715, 917, 337, 6, 70, "Text"], Cell[29055, 925, 752, 22, 70, "Text"], Cell[29810, 949, 709, 22, 70, "NumberedEquation"], Cell[30522, 973, 437, 16, 70, "Text"], Cell[30962, 991, 179, 3, 70, "NumberedEquation", CellTags->"Eq:8"], Cell[31144, 996, 262, 6, 70, "NumberedEquation", CellTags->"Eq:9"], Cell[31409, 1004, 345, 13, 70, "Text"], Cell[31757, 1019, 67, 0, 70, "Text"], Cell[31827, 1021, 1034, 27, 70, "NumberedEquation"], Cell[32864, 1050, 633, 22, 70, "Text"], Cell[33500, 1074, 1055, 28, 70, "NumberedEquation", CellTags->"Eq:11"], Cell[34558, 1104, 1014, 32, 70, "Text"], Cell[35575, 1138, 1586, 49, 70, "Text"], Cell[37164, 1189, 1372, 34, 70, "NumberedEquation"], Cell[38539, 1225, 126, 5, 70, "Text"], Cell[38668, 1232, 4402, 113, 70, "NumberedEquation", CellTags->"Ed:Change4"], Cell[43073, 1347, 632, 20, 70, "Text", CellTags->"Ed:Change5"], Cell[43708, 1369, 2387, 63, 70, "NumberedEquation", CellTags->"Eq:14"], Cell[46098, 1434, 1896, 68, 70, "Text"], Cell[47997, 1504, 1268, 36, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[49302, 1545, 104, 5, 70, "Section"], Cell[49409, 1552, 288, 10, 70, "NumberedFigure", CellTags->{"Fig:1", "Ed:Change6"}], Cell[49700, 1564, 48, 0, 70, "Caption"], Cell[49751, 1566, 2833, 98, 70, "Text"], Cell[52587, 1666, 575, 15, 70, "Text"], Cell[53165, 1683, 1352, 25, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[54554, 1713, 81, 5, 70, "Section"], Cell[54638, 1720, 689, 15, 70, "Text"], Cell[55330, 1737, 210, 4, 70, "Text"], Cell[55543, 1743, 485, 14, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[56065, 1762, 29, 0, 70, "Section"], Cell[56097, 1764, 234, 9, 70, "Reference", CellTags->"Ref:Jaynes1968"], Cell[56334, 1775, 318, 10, 70, "Reference", CellTags->"Ref:AleksanderStonham1979"], Cell[56655, 1787, 335, 10, 70, "Reference", CellTags->"Ref:ShoreJohnson1980"] }, Closed]], Cell[CellGroupData[{ Cell[57027, 1802, 28, 0, 70, "Section"], Cell[57058, 1804, 255, 5, 70, "Text", CellTags->"Footnote:1"], Cell[57316, 1811, 389, 7, 70, "Text", CellTags->"Footnote:2"], Cell[57708, 1820, 412, 7, 70, "Text", CellTags->"Footnote:3"], Cell[58123, 1829, 348, 6, 70, "Text", CellTags->"Footnote:4"], Cell[58474, 1837, 187, 4, 70, "Text", CellTags->"Footnote:5"], Cell[58664, 1843, 211, 5, 70, "Text", CellTags->"Footnote:6"] }, Closed]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)