We propose a novel ensemble learning algorithm called Triskel, which has two interesting features. First, Triskel learns an ensemble of classifiers, each biased to have high precision on instances from a single class (as opposed to, for example, boosting, where the ensemble members are biased to maximise accuracy over a subset of instances from all classes). Second, the ensemble members' voting weights are assigned so that certain pairs of biased classifiers outweigh the rest of the ensemble, if their predictions agree. Our experiments demonstrate that Triskel often outperforms boosting, in terms of both accuracy and training time. We also present an ROC analysis, which shows that Triskel's iterative structure corresponds to a sequence of nested ROC spaces. The analysis predicts that Triskel works best when there are concavities in the ROC curves; this prediction agrees with our empirical results.

Distributed heterogeneous search systems are an emerging phenomenon in Web search, in which independent topic-specific search engines provide search services, and metasearchers distribute user's queries to only the most suitable search engines. Previous research has investigated methods for engine selection and merging of search results (i.e. performance improvements from the user's perspective) . We focus instead on performance from the service provider's point of view (e.g, income from queries processed vs. resources used to answer them). We consider a scenario in which individual search engines compete for user queries by choosing which documents (topics) to index. The difficulty here stems from the fact that the utilities of local engine actions should depend on the uncertain actions of competitors. Thus, naive strategies (e.g, blindly indexing lots of popular documents) are ineffective. We model the competition between search engines as a stochastic game, and propose a reinforcement learning approach to managing search index contents. We evaluate our approach using a large log of user queries to 47 real search engines.

Distributed heterogeneous search environments are an emerging phenomenon in Web search. We provide a theoretical analysis of the problem and propose a method, utilising reinforcement learning techniques, for automatically managing search engine content. We examine the problem of performance-maximising behaviour for noncooperative specialised search engines in heterogeneous search environments. In particular, we analyse a scenario in which individual search engines compete for queries by choosing which documents to index. We provide game-theoretic analysis of a simplified version of the problem and motivate the use of the concept of "bounded rationality". We then cast our problem as a reinforcement learning task, where the goal of a specialised search engine is to exploit suboptimal behaviour of its competitors to improve own performance.

The predominant Web search model attempts to use multiple computers under centralised management to act as one search engine for the entire Web. As the quantity of online information increases, systems based on this model become prohibitively expensive for all but the largest organisations. We advocate the use of distributed search architectures where multiple independently owned and managed search engines act as one search system. This approach has significant advantages including low market entry cost for individual search providers and the potential to stimulate the provision of high-quality services through competition. The low entry cost allows small organisations and even individual users to influence service features and quality by establishing specialised search services. However, independent proprietorship also greatly complicates the search system design. The potential for competition between engines requires new approaches to effective engine management Many new issues arise such as deciding what information an engine will index. In this paper we analyse the sources of complexity in distributed Web search architectures with independent proprietorship and competition between engines. We outline possible ways to cope with this complexity using techniques from the field of computational economics such as game theory.