looking for "optimal weighting" algorithm

[Alex Martelli]

Bengt Richter wrote:
   ...
>>The problem: I need to design a "decision criterion" to classify
>>"observations".  For each observation I measure the values of a
>>number N of features, x1, x2, ... xN; the desired design criterion
>>is a set of weights w1, w2, ... wN such that for any observation I
>>will then just compute a weighted sum
>>  S = w1*x1 + w2*x2 + ... + wN*xN
>>and classify the observation as Black if S<=1, White if S>1.  To
   ...
> Well, that was my reaction, FWIW. I'm sure I'm not the only one curious
> as to what you are measuring and classifying ;-)

Fair enough -- I owe it to the group to clarify that (AND collective
thanks for the huge numbers of answers, both here and privately --
"logistic regression" is the name I wanted but couldn't remember,
but many other suggestions such as "perceptron" provide fertile
criteris for other studies).

What I'm doing is, now that I (theoretically) have SOME spare time
again (no book projects actively proceeding), going back to my real
passion -- research on the theoretical fundamentals of the game of
contract bridge.  In bridge, every one of the four players is dealt
13 cards out of a 52-cards deck; a phase of "bidding" follows, where 
pairs of players playing as partners try to determine what "contract"
to bid for (if any).  A key issue during the bidding phase is to
evaluate hands' "strength" -- trick-taking potential.  As I mention
in my "short bio" whenever space allows, out of all I've accomplished
in my life, the single achievement of which I'm proudest is the pair of
articles published in the Jan-Fen 2000 issues of "The Bridge World",
under the title of "How Shape Influences Strength", demonstrating how
to use a computer to practically apply an evaluation method described
as an ideal, abstract approach in the 1920's -- and how some results
of such application prove assertions about hand strengths that were
also first made in print in the 1920's and disprove some others.  (If
anybody manages to look at those articles -- no need to tell me that
the variance-evaluation I use in them is wrong -- far too pessimistic,
so I could have gotten away with samples about 1/10th as large to
reach the thousandth-of-a-trick accuracy I required... a note pointing
that out was already published in "American Statistician", providing
ample opportunities for crow-eating for both me, and the Bridge World
editor, whose Ph.D in maths should have helped him see that...;-).

Note that I'm NOT trying to get a computer to play bridge -- I could
care less about that, and several researchers and commercial groups
are dealing with the practical issues around that goal -- MY goal is
to gain "a measure of light" as to how bridge *actually works*, maybe
to help people actually evaluate their hands better at the table, and/or
design better systems and approaches for the task; computers are tools
for the purpose, from my POV.


But anyway, back to my request.  By far the most popular practical
method for hand evaluation is known as "point-counting" -- a weighted
sum of the numbers of aces, kings, etc, in a hand.  And by far the
most popular "point count" (set of weights) in use is one first
published in 1915 (allegedly derived from one used in Italian Tarocco
games as early as 1320, though I think the connection's a bit weak)
which became overwhelmingly popular in the 1940's: 4-3-2-1-0 (count
"4 points" for each Ace, "3 points" for each King, etc, down to "0
points" [i.e., just ignore them] for each Ten-spot).  Almost every
theoretician knows/believes this specific point-count approach is way 
off the mark (with the signal exception of Dr. Jean Rene Vernes, of
France, maybe THE major theoretician of the application of statistics
to contract bridge theory, who claims 4-3-2-1-0 is "good enough" and
tries to support that claim with data which, I believe, show that
things are, in fact, otherwise).  So, I want to see what I can find
out about the issue, mostly by working with a million-deals library
of deals played at "double dummy" (i.e. ignoring the fundamental fact
that the play of the hand at bridge is a game of incomplete
information -- corrections for THAT, if any, will need to come
later) published by Dr. Ginsberg, another major theoretician in the
field (and more than a theoretician -- he ALSO runs a firm which
publishes and sells one of the best computer-player programs, as well
as pursuing his academic research in the same field).

Out of all decisions in bidding, the single most frequent one is
whether to contract for the "game contract" of "three notrumps"
(undertaking for the partnership to make at least 9 of the 13 tricks,
without any trump-suit).  So, I focused on that, as well as on "flat"
hands -- deals for which all suits have between 2 and 4 cards in each
partner's hand (no especially short nor especially long suit) -- for
which the 3NT target is particularly relevant and point-count more
important than for "shapely" hands (hands with certain suits being
particularly long or short, for which many other considerations may
apply).  I extracted the 80,000+ deals from Ginsberg's library that
meet these constraints and classified partners' hands by the counts of
Aces, Kings, ... down to Tens (2,000+ different combinations of
counts), with the "ground truth" information being whether that given
pairs of hands (played at NT at double dummy) makes 9+ tricks, or 8
tricks or less.  With the classic 4-3-2-1-0 "point-count", I have seen
that the correct threshold for 3NT is the sum of 25+ "points" in the
hands of the two partners, which is indeed the threshold currently
taught (for some reason in the '40s and '50s a threshold of 26 was
taught instead, but experience over the decades made the threshold of
25 emerge as more optimal).

It's an error to bid 3NT when the two combined hands make 8 or fewer
tricks; it's also an error NOT to bit 3NT when the two combined hands
make 9 or more tricks.  In one case, a small gain turns into a small
loss; in the other, an opportunity to turn a small gain into a large
gain is missed.  It so happens that (at least in some cases and forms
of bridge competition) the cost of errors of each type is quite close
so for simplicity I can actually start with the assumption that each
kind of error has the same cost.

So, what I propose is to find the best assignment of weights ("point
count") and threshold for the decision of whether to bid 3NT or not --
for starters.  Many variations are clearly possible (e.g. use weights
that best predict the number of tricks, rather than just the fact
of >=9 vs <=8 tricks, etc, etc) and I plan to explore many of them...
but the key intermediate goal is "finding good/optimal assignments
of weights" ("point-counts" -- and later, if and when I've settled
on what's a good point-count, I may then explore variations such as
pluses or minuses for groupings and positioning of honors, etc etc)
and threshold for the 3NT bid to be profitable.


Again thanks to all who helped!

Alex