FOA Home
InfoSpiders search on-line for information relevant to the user, by
making autonomous decisions about what links to follow.
Figure~(FOAref) shows the InfoSpiders implementation of the
local selection algorithm. A central part of the system is the use of
optional relevance feedback. The user may assess the relevance
of (some of) the documents visited by InfoSpiders up to a certain point.
Such relevance assessments take place asynchronously with respect to the
on-line search, and alter the subsequent behaviors of agents on-line by
changing the energy landscape of the environment. The process is akin to
the replenishment of environmental resources; the user interacts with
the environment to bias the search process. Let us first overview the
algorithm at a high level; representation-dependent details will be
given in the next subsections and experimental parameter values in the
following section.
The user initially provides a list of keywords and a
list of starting points, in the form of a bookmark file. The search is
initialized by pre-fetching the starting documents. Each agent is
``positioned'' at one of these documents and given a random behavior
(depending on the representation of agents) and an initial reservoir of
energy.
Each agent ``senses'' its local neighborhood by analyzing the
text of the document where it is currently situated. This way, the
relevance of all neighboring documents --- those pointed to by the
hyperlinks in the current document --- is estimated. Based on these link
relevance estimates, the agent ``moves'' by choosing and following one
of the links from the current document.
Next, the agent's energy is
updated. Energy is needed in order to survive and move, i.e., continue
to visit documents on behalf of the user. Agents are rewarded with
energy if the visited documents appear to be relevant. The $e()$
function is used by an agent to evaluate the relevance of documents. If
a document had previously been visited and assessed by the user, the
user's assessment is used; if the document had not been visited before,
its relevance must be estimated. This mechanism is implemented via a
cache, which also speeds up the process by minimizing duplicate
transfers of documents. While in the current, client-based
implementation of InfoSpiders this poses no problem, caching is a form
of communications and thus a bottleneck for the performance of
distributed agents. In a distributed implementation, we imagine that
agent will have local caches. When using the current implementation to
simulate the performance of distributed InfoSpiders, we will simply set
the cache size to zero.
Agents are charged energy costs for the network
load incurred by transferring documents. The cost function $c()$ should
depend on used resources, for example transfer latency or document size.
For simplicity we will assume a constant cost for accessing any new
document, and a (possibly smaller) constant cost for accessing the
cache; this way stationary behaviors, such as going back and forth
between a pair of documents, are discouraged.
Just as for graph search,
instantaneous changes of energy are used as reward/penalty signals. This
way agents adapt during their lifetime by Q-learning. This adaptive
process allows an agent to modify its behavior based on prior
experience, by learning to predict the best links to follow.
Depending on
its current energy level, an agent may be killed or be selected for
reproduction. In the latter case offspring are recombined by the use of
{local crossover,} whereby an agent can only recombine with agents
residing on the same document, if there are any. Offspring are also
mutated, providing the variation necessary for adapting agents by way of
evolution.
Finally, the user may provide the system with relevance
feedback. It is important to stress that this process is entirely
optional --- InfoSpiders can search in a completely unsupervised fashion
once they are given a query and a set of starting points. Relevance
feedback takes place without direct on-line interactions between user
and agents. The user may assess any visited document $D$ with feedback
$\in \{-1, 0, +1\}$. All the words in the document are automatically
assessed by updating a ``feedback list'' of encountered words. Each word
in this list, $k$, is associated with a signed integer $\omega_{k}$ that
is initialized with 0 and updated each time any document is assessed by
the user: \forall k \in D: \omega_{k} \leftarrow \omega_{k} + \phi(D).
The word feedback list is maintained to keep a global profile of which
words are relevant to the user.
The ultimate output of the algorithm is a
flux of links to document, ranked according to some relevance estimate
--- modulo relevance assessments by the user. The algorithm terminates
when the population goes extinct for lack of relevant information
resources, or if it is terminated by the user.
Top of Page
The InfoSpiders algorithm