sdo@linus.UUCP (Sean D. O'Neil) (11/17/89)
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
mathis@boulder.Colorado.EDU (Don Mathis) (11/18/89)
In article <80663@linus.UUCP> sdo@faron.UUCP (Sean D. O'Neil) wrote a criticism of the football net, in which was said: >>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. No, it's not a Hopfield net. Hopfield nets use binary threshold units and asynchronous updates. This net has continuous-valued activations and updates the units in parallel. It's doing something closer to "pure" gradient- following. >My problem is this: there is no, repeat no, reason to use a Hopfield network >to solve this problem. How about for fun? Your statement is like saying "There is no reason to use Pascal to solve this problem". It's just a way to implement an algorithm. > 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. You're right, in that the net is finding a least-squares solution to an overdetermined linear system. >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. I agree. > ...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. Yes, there are an infinite number of least-squares solutions. But there IS a unique least-squares solution of minimum L2-norm. What I do is take the solution the network finds, and use it to obtain the solution of minimum L2- norm. This composite algorithm is independent of initial values. >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. Well, I think you perceive this attitude because you work at Mitre. Nothing against Mitre specifically, but I've found that in the BUSINESS of neural nets, those who can best lie to their prospective customers about the magic of neural nets make the most money, and they will continue to do so until the myths are exposed. But this problem only exists in industry - where people do things without thinking first. I would hope that the people who read this bboard do enough thinking to sort these things out for themselves. The whole "magic" issue is YOUR problem - you struggle with it. I'm not trying to snow anyone - I'm just trying to have fun. -Don
pa1159@sdcc13.ucsd.edu (Matt Kennel) (11/21/89)
In article <80663@linus.UUCP> sdo@faron.UUCP (Sean D. O'Neil) writes: > >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. Simon says, "Lagrange multipliers." Matt Kennel pa1159@sdcc13.ucsd.edu