|
Article Excerpt
1. Introduction
In many decision-making scenarios, decisions of multiple human experts or classifiers are fused to determine the overall decision. Examples include a group of accounting experts and classifiers making going-concern decisions and an ensemble of classifiers in a fraud-detection application making decisions on whether a transaction is fraudulent. Multiclassifier combination (MCC) is a technique that can be used to improve the classification performance in various classification problems by combining the decisions of multiple individual classifiers (Suen and Lam 2000). In MCC, individual classifiers, commonly referred to as base classifiers, classify objects based on inputs consisting of object feature vectors (see Figure 1). These classifications or decisions are then combined using a combiner method into a single decision about the object's class label.
[FIGURE 1 OMITTED]
The basic premise behind MCC is that different classifiers in an ensemble have different strengths and weaknesses and therefore provide complementary information (referred to as diversity in MCC) about the classification problem. These differences can be leveraged to improve classification performance by combining base-classifiers' decisions (Kittler et al. 1998). Different combiner methods have been proposed and examined in the literature; these can be categorized based on whether they require training data. For example, naive Bayes, decision templates, and weighted average (WAVG) require training data, whereas average (AVG), majority (MAJ), and product do not. Existing combiner methods that require training data have limitations including the requirement for training data, and restrictive assumptions such as (1) constant ensemble base-classifier composition and (2) training data performance being a good proxy for subsequent actual performance. Experimental results generally indicate that MCC provides performance benefits and that the performance of MAJ and AVG methods is comparable or superior to that of methods requiring training (Duin and Tax 2000).
To improve performance while overcoming these limitations, we propose an information market-based fusion approach for multiclassifier combination that (1) has superior performance, (2) does not require offline training data, and (3) through online learning can adapt to changes in ensemble composition and base-classifier performance. In evaluating the effectiveness of our proposed approach, we compare information market-based fusion (IMF) against three combiner methods, AVG, MAJ, and WAVG. These methods have performed relatively well in prior research (Duin and Tax 2000) and have been used as benchmarks in recent MCC research. (1) For example, Zheng and Padmanabhan (2007) use AVG, which they refer to as unweighted average, and a version of WAVG with variance-based weights, which they refer to as variance-based weighting. Our experimental evaluation was performed using computational experiments with 17 data sets that were obtained from the University of California, Irvine Machine Learning Repository (Newman et al. 1998) and 22 different base classifiers from Weka (Witten and Frank 2005).
The remainder of this paper is organized as follows. In [section]2, we provide a review of related research. IMF is introduced in [section]3 along with an overview of information markets. We then present details on the computational experiments and results in [section][section]4 and 5, respectively. In [section]6, we discuss these results and conclude in [section]7 with a review of our contributions and suggestions for future research.
2. Related Research
A classifier is a model that makes decisions about an object's class membership based on the object's feature set. Examples of classifiers include neural networks, logistic regression, decision trees, and Bayesian classifiers (Witten and Frank 2005). Classifier performance is typically dependent on the problem domain as well as on the calibration of the classifier. Multiple classifiers are therefore typically tested to identify the best classifier for a given problem domain. However, it is generally difficult to determine which classifier(s) will perform well in subsequent classifications. Furthermore, classification for certain cases may even be improved by an "inferior" classifier (Kittler et al. 1998). Thus, by combining the decisions of diverse classifiers, it is possible to improve the overall performance.
Prior MCC research has primarily focused on one of two areas: (1) training and selection of ensemble base classifiers or (2) combination of base-classifier decisions. Methods such as bagging, boosting, and stacking fall into the first category (Witten and Frank 2005); combiner methods such as MAJ, AVG, and WAVG fall into the second category. Recent research within the former stream has used receiver operating characteristic analysis to select dominant classifiers (Provost and Fawcett 2001) and data envelopment analysis to select efficient classifiers (Zheng and Padmanabhan 2007) under various cost and class distributions, and then combine these classifiers' decisions. Fan et al. (1999) have adapted AdaBoost to an online learning environment where new training instances become available continuously or periodically. This paper does not focus on classifier selection and training, but on the combiner methods. Prior research within the combiner method research stream has found that methods that use measurement data are typically more accurate than methods that handle unique labels; methods that require training data typically outperform methods that do not require training (Jain et al. 2000), but that MAJ and AVG, which do not require training, perform either at the same level or significantly better than more complex methods (Duin and Tax 2000).
Another important but largely overlooked aspect of combiner methods is how well they fit with different system architectures. Software agents offer a new paradigm to support decision making (Nissen and Sengupta 2006) where human-driven or autonomous software agents embodying classifiers and other intelligent algorithms can leverage their individual strengths to make collective decisions. The base-classifiers, combiner method, and providers of object features in an MCC can be implemented as software agents in multiagent systems. Research in data mining has implemented MCC agent systems for credit card fraud detection (Stolfo et al. 1997) and network intrusion detection (Lee et al. 2000).
In MCC multiagent systems that are implemented in dynamic real-world settings, the relative performance of base classifiers and the ensemble composition can change over time as agents are retired, added, or temporarily unavailable. Existing combiner methods that require offline training do not take this into consideration and assume that the ensemble composition is static and that individual classifier performance does not change subsequent to training and validation.
3. Information Market-Based Fusion
IMF is theoretically grounded in information markets. More specifically, the IMF aggregation mechanism used in this paper is based on parimutuel betting markets.
3.1. Information Markets
Information markets are markets specifically designed for the purpose of information aggregation. Equilibrium prices, derived using conventional market mechanisms, provide information based on private and public information maintained by the market participants about a specific situation, future event, or object of interest (Hanson 2003). Although the concept of information markets is fairly recent, the underlying notion of markets being capable of aggregating information is not new (Hayek 1945), and the efficient market hypothesis states that all private and public information is reflected in equilibrium prices (Fama 1970). Empirical research has found support for the efficient market hypothesis and for information aggregation in information markets in general (Berg and Rietz 2003), and parimutuel betting markets in particular (Plott et al. 2003).
Our combiner method is based on parimutuel betting, which originated in horserace gambling in France in 1865, and since then has become a popular betting mechanism in the horseracing world. Pari-mutuel means "wager mutual" and comes from the fact that in parimutuel betting, a winning wager (i.e., bet) receives a share of the total wagers (winning and loosing bets minus a track commission) as a proportion of this winning wager to all winning wagers. The final track odd for a given horse is the total amount bet on all the horses in the race divided by the total amount bet on the given horse. The payout for a winning horse is the product of the amount bet on it and its odd (less track commission). From an MCC perspective, the odd associated with a horse is of great importance, as it represents the aggregated market information about the probability estimate of that horse winning the race. We use parimutuel betting over mechanisms such as continuous double auctions because parimutuel betting does not suffer from liquidity problems that could potentially impact continuous double auction markets when there are large bid-ask spreads or when bid-ask queues are empty (Pennock 2004). Hence, parimutuel mechanisms would work effectively, even when the ensemble of base-classifiers is small.
Plott et al. (2003) experimentally examined information aggregation and different betting behaviors in parimutuel betting markets using two private information models--decision theory private information (DTPI) and competitive equilibrium private information (CEPI)--and one model with belief updating--competitive equilibrium rational expectations. Plott et al. (2003) found that DTPI and CEPI best described the behavior of human participants in their probabilistic information condition experimental parimutuel betting market.
In DTPI, agents only consider their own private information and ignore market prices when deciding on their bets and in forming beliefs. In CEPI, agents base their bets on the current market price, although they do not update their beliefs based on market prices. In both models, agents maximize their conditional expected utility given their private probability estimates and constraints such as available funds. In both DTPI and CEPI, prices are assumed to be in equilibrium; however, as each betting round starts without prices defined, the equilibrium must be obtained before the agents can place their final bets. Assuming no track take, in equilibrium, all potential payouts are equal to the total amount that is bet across all events.
3.2. Information Market-Based Fusion
IMF is a multiclassifier combiner method based on a parimutuel betting information market that can be used in any classification application domain. We present IMF in the context of a fraud-detection application. In this application, object t (i.e., transaction t) can be classified as fraudulent (j = 1) or nonfraudulent (j = 2) by an ensemble E of agent classifiers. In this application, the set J = {1, 2} is the index set of the two classes (i.e., fraudulent and nonfraudulent). The ensemble E has m agents embodying different base classifiers (referred to as agents) represented by indices i in the index set D = {1, ..., m}. While determining the class membership of object t, agent i [member of] D uses the feature vector associated with t to determine the posterior probability estimate [p.sub.itj] [member of] [0,1] that t belongs to class j [member of] J. Agent i bets [q.sub.itj] that object t belongs to class j and is paid according to the parimutuel mechanism based on four factors: (1) the agent's bets, [q.sub.itj]; (2) the total bets on class j, [Q.sub.tj] = [[SIGMA].sub.i[member of]D] [q.sub.itj]; (3) the total bets on all classes, [Q.sub.t] = [[SIGMA].sub.i[member of]J] [[SIGMA].sub.[i[member of]D]] [q.sub.itj]; and (4) the true class of object t. Ensemble E's overall probability estimate that t belongs to j [member of] J is given by 1/[O.sub.tj] [member of] [0, 1], where [O.sub.tj] is the odd that t belongs to j [member of] J. The odd [O.sub.tj], which is equal...
|
