Path: utzoo!attcan!uunet!samsung!gem.mps.ohio-state.edu!tut.cis.ohio-state.edu!purdue!bu-cs!xylogics!merk!alliant!linus!sdo
From: sdo@linus.UUCP (Sean D. O'Neil)
Newsgroups: comp.ai.neural-nets
Subject: Re: Neural Network for ranking football teams.
Summary: Perhaps there's an easier way
Keywords: Hopfield nets, linear algebra
Message-ID: <80663@linus.UUCP>
Date: 16 Nov 89 16:43:29 GMT
References: <13645@boulder.Colorado.EDU>
Reply-To: sdo@faron.UUCP (Sean D. O'Neil)
Organization: The MITRE Corporation, Bedford MA
Lines: 75

In article <13645@boulder.Colorado.EDU> mathis@boulder.Colorado.EDU (Don Mathis) writes:
>Hi folks,                        
>  I recently designed a neural net that ranks football teams based
>on points scored by each team, points scored against each team, and most
>importantly, each team's strength-of-schedule (this was the whole idea
>behind using a neural net).  
>	For those of you who know a bit about neural nets, this is a constraint 
                                                                     ^^^^^^^^^^
>satisfaction network that settles on what I call a "quality  value" for each 
 ^^^^^^^^^^^^ ^^^^^^^

Sometimes known as a Hopfield network.

>team.  The network tries to find a set of quality values that satisfies the 
>following constraint:  "For each game played, the difference in quality 
>between the two teams in the game should equal the difference in the points
>they scored in the game".   Of course, this is impossible to achieve (upsets, 
>etc.), so the network does the best it can at finding reasonable quality values.

Later on, Don describes the connections and inputs to his Hopfield
or constraint satisfaction network.

>*There is one unit per team.
>*The units are fully connected, and the connections are symmetric.
>*The weight between unit i and unit j is equal to the number of times team i
>has played team j this year.
>*The connection from unit i to itself is equal to MINUS the number of games 
>team i has played this year.
>*The external input to unit i is equal to the total PF-PA for team i over the 
>current season.  (That's points_for minus points_against - it's a constant).

My comment is this.  Don has turned the problem of determining the quality
of football teams into a function minimization problem.  I have no problem
with this, it all seems pretty reasonable so far.  Since his function 
is of a particular form (i.e., it is a quadratic function) he plugs it into
a Hopfield network to perform the minimization.  Here's where I begin to
have some problems.

My problem is this:  there is no, repeat no, reason to use a Hopfield network
to solve this problem.  It is an *unconstrained* minimization of a
quadratic function.  This is a trivial problem to solve using first-year
calculus.  Take the derivative of the quadratic function, set it equal
to zero, and solve the set of linear equations to get the quality values.
This *exactly* satisfies Don's function minimization criterion.

Note that I am NOT saying that Hopfield or constraint satisfaction networks
have no use.  Often one wishes to constrain values that the outputs of the
network can take on.  This is usually done implicitly by shaping the transfer 
or activation function in some way---typically a sigmoidal shape is used.
In such cases, one CANNOT take the algebraic approach I described above and
it is often the case that the easiest solution technique is to run the
network and let it converge.  However, such is not the case here.

There is another reason to take the algebraic approach I described.  It allows
us to analyze what's really going on.  The solution we get taking the
algebraic approach is to take the inverse of the connection matrix and
multiply it by the vector of inputs.  In this particular case, the
connection matrix Don describes is singular (the row and column sums
are zero).  In fact, it's not too hard to show that the rank of the
matrix can not be larger than the number of games each team has played.
In this case, since each team has played 10 games and we have 28 football
teams, we have a 28x28 matrix with rank 10.  Our system is underconstrained
by 18 degress of freedom!  Thus, there is not a unique solution, but rather
a whole space of solutions, all equally valid.  The neural network gives
us a particular solution, but if we initialized it with some starting values
other than 0.0, we would get a completely different solution.

In conclusion, I think that it is important to look at what's really going
on when we set up a neural network to solve a problem.  There seems to
be an attitude that the neural network does something mystical and
I want to get away from that.  In many cases, as in this one, the network
is merely mimicking some straightforward mathematical procedure that
can best be handled with standard techniques.

Sean