Showing posts with label David Blackwell. Show all posts
Showing posts with label David Blackwell. Show all posts

Saturday, December 6, 2014

Duda and Hart: Pattern Classification and Scene Analysis (1973)

A lot of references seem to indicate that this book played an important role in the popularization of Bayesian methods in machine learning. It also provides an interesting missing link between the statistics and decision theory of the 1950s and the field of machine learning in the form it now has.



Interestingly, their rejection of minimax approaches to decision theory is rather casual, relative to how toxic the debate actually was:
In fact, the Bayesian approach is avoided by many statisticians, partly because there are problems for which a decision is made only once (so that average loss is not meaningful), and partly because there may be no reasonable way to determine the a priori probabilities. Neither of these difficulties seems to present a serious problem in typical pattern recognition applications, and for simplicity we have taken a strictly Bayesian approach. (p. 36)
Compare this to David Blackwell's compact statement of intent in Basic Statistics (1969):
This book indicates the content of a lower-division basic statistics course I have taught several times at Berkeley. […] The approach is intuitive, informal, concrete, decision-theoretic, and Bayesian. (p. v)
Duda and Hart also provide a number of quite interesting references:
The text by Nilsson (1965) provides an exceptionally clear treatment of classification procedures. (p. 8)
There are many interesting subject areas that are related to this book but beyond its scope. […] Those interested in philosophical issues will find the books by Watanabe (1969) and Bongard (1970) thought provoking. (p. 8)
We are also fond of the the text by Ferguson (1967), who presents many topics in statistics from a decision theoretic viewpoint. (p. 36)
Chow (1957) was one of the first to apply Bayesian decision theory to pattern recognition. His analysis include a provision for rejection, and he later estiablished a funcamental relation between error and reject rates (Chow 1970). (p. 36)

Tuesday, October 28, 2014

Blackwell and Girshick: Theory of Games and Statistical Decisions (1954), Ch. 4

There's an interesting representation theorem in Blackwell and Girshick's textbook in statistics: It provides a set of sufficient conditions for a preference ordering over lotteries to be expressible as a prior probability distribution (Th. 4.3.1, p. 118).

I assume the theorem comes from either Wald, Savage, or de Finetti, but no reference is given.

Well-Behaved Preferences

A lottery can here be defined as a function from the sample space to the real numbers. The conditions in the theorem are then the following:
  • The ordering of two lotteries $f$ and $g$ cannot depend on the availability of other lotteries.
  • If a lottery $f$ provides a higher payoff than a lottery $g$ at all points in the sample space $\Omega$, then $f$ must be preferred to $g$.
  • If $f$ is preferred to $g$, then $f+h$ must be preferred to $g+h$.
An inspection of the proof also shows that they should have included a continuity condition:
  • If $f_1, f_2, \ldots$ is a series of lotteries converging to a limit $f$, and if $f_i$ is preferred to $g$ for all $i$, then $f$ must also be preferred to $g$.
When these conditions are met, the preference ordering over the lotteries can be expressed as a distribution over the sample space, unless it categorizes all lotteries as equally good.

The Large and the Good

The proof of the theorem uses the fact that two convex, disjoint, open sets can be separated by a hyperplane. Here's a sketch:

If we let $e$ be the lottery that pays zero in all situations $\omega \in \Omega,$ then we can define the following sets:
\begin{eqnarray}
F[>] &=& \{f\ |\ \forall \omega \in \Omega: f(\omega) > 0\},
\\
F[\gtrsim] &=& \{f\ |\ f\gtrsim e\},
\end{eqnarray}
and we can further define, in the usual way, $F[>] + F[\gtrsim]$ to be the sums of lotteries from those two sets.

Now, $F[>]$ is an open set, and hence $F[>] + F[\gtrsim]$ is, too. Further, $F[>]$ and $F[\gtrsim]$ are both closed under addition (due to the third assumption), and hence their sum is, too. They are also both closed under multiplication with a scalar, and again, so is their sum — but this latter argument requires a bit more spelling out.

Rational and Real Convexity

Suppose a lottery $f$ is preferred to the zero lottery, that is, $f \in F[\gtrsim]$. The third assumption of the theorem then tells us that
$$
e \;\lesssim\; f \;\lesssim\; f + f \;\lesssim\; f + f + f \;\lesssim\; \ldots \;\lesssim\; nf.
$$
By further adding multiple copies of the zero lottery to both sides of this preference ineqality, we can see that
$$
me \;\lesssim\; (m-1)e + nf \;=\; nf,
$$
where we have selectively used the fact that $e$ is the zero lottery. Putting these facts together, we then have the preference inequality
$$
e \;\lesssim\; \left(\frac{n}{m}\right)f.
$$
By using a positive sequence of rational approximations $(n/m) \rightarrow \lambda$, we can use this fact along with the continuity assumption to conclude that $F[\gtrsim]$ is closed under multiplication with any positive, real scalar $\lambda$.

I don't think there's a way around this last technicality. It is, incidentally, the same proof technique used to prove that the logarithmic functions are the only continuous functions that turn products into sums.

Cutting the Cake

At any rate, $F[>] + F[\gtrsim]$ is an open and convex set separated from the singleton set $\{e\}$. We can therefore conclude that there is a lottery (or vector) $p$ which defines the hyperplane $\{f\ |\ f\cdot p=0\}$ separating $F[>] + F[\gtrsim]$ from $\{e\}$. The set $F[>] + F[\gtrsim]$ is thus a subset of the half-space $\{f\ |\ f\cdot p \geq 0\}$.

This vector $p$ must have nonnegative coordinates, since the set $F[>]$ is unbounded in all positive directions. If $p$ had a negative coordinate, $p(\omega) \leq 0$, we could choose a lottery for which the corresponding coordinate, $f(\omega)$, was so large that $f\cdot p < 0$. This would violate the definition of $p$, and $p$ hence has to be a nonnegative vector which can be interpreted as a probability distribution.

It would also have the property that $f\cdot p \geq g\cdot p$ if and only if $f \gtrsim g$. This follows from the fact that $f\cdot p \geq g\cdot p$ if and only if $(f - g) \in F[>] + F[\gtrsim]$, which holds if and only if $f$ can be expressed as the sum of $g$ and some lottery preferable to the zero lottery.