Updating the links

Updating the links is the most important task in our algorithm, this is also the point where most of our design choices take place.

First, we must define when we can do it. We can do updates only after positive votes, only after negative votes, or both. The first option isn’t a good solution, a long succession of negative votes wouldn’t alter at all the learnt concept, the learning algorithm would endlessly continue to propose the same kind of information fragments. We’re left with the necessity to update after negative votes and the added possibility to update after positive votes.

Unlike Littlestone & Warmuth 1992 our goal is not to find the unique best source, we want all of them to cooperate at each vote. This means we must take care of not over-reacting when some source disagree with our vote, as long as our prediction is not wrong it’s best to keep them around, they may be good contributors for other votes. From a more practical standpoint, if only working after negative votes is good enough there’s no point in working more.

Second, we must decide what to do. we have three main possible actions on our set of links :

• Remove links
  • We can either remove oldest links or links with the lowest weight.
• Update link weights
  • Update can be either multiplicative or additive. It can be an increase for sources agreeing with the user’s vote or a decrease for disagreeing sources. We must also decide what to do with source which haven’t given their opinion about the current fragment.
• Add new links
  • This is the most complex action. The two others only need to work on the (hopefully) smaller set of links, this one must pick a new source among the whole graph of users. We have too many ways to select new sources to cite them all. We can take the one with the largest number of identical votes, the largest number of identical negative votes… Another point to define is the strength of the added link, we can start with an average of current votes, the maximum… Finally, we must also decide how many links we want to add, if it’s after a removal we may select to add as many links as removed, in order to keep a constant number of links, or simple only add one source at a time.

Our routine for adding new links will also be useful in another context. Since we don’t want to show the same information twice to the same user and since we can only pick fragments among those voted positively by at least one source, if our sources votes less often than us, we may be in a starvation situation. To cope with this problem, we must add a new source to our set then select a fragment using this source.

We’ve not yet covered the problem of the initialisation of the link set. At the beginning we have no information to help us, our solution may only rely on a random selection or on information external to the learning system. For now we will focus on our algorithm and solve this practical problem later.