Spring 2009 CS-795: Ensemble Based Systems in Decision Making [INFS-795, IT-803]

Prerequisites: INFS-755, or equivalent knowledge. Some programming experience is expected. Students should be familiar with basic probability and statistics concepts, linear algebra, optimization, and multivariate calculus.

General Description and Preliminary List of Topics:
This course is about combining the "opinions" of an ensemble of experts (e.g., classifiers) with the objective of computing a new emerging "opinion" that is better than the individual ones. The task of improving classification accuracy by learning ensembles of classifiers is considered as one of the most important directions in machine learning research. Recent empirical work has shown that combining predictors can lead to significant reductions in generalization error.
We will discuss popular ensemble methods such as bagging, boosting, and AdaBoost. We will study the conditions under which combining multiple experts is beneficial; how to construct the individual components; how to select a subset of "good" experts from a large pool of possible components; and how to generate a consensus response from those of the individual members. We will consider ensembles in which the components are supervised learners, unsupervised ones, or learners with constraints. Challenges in each scenario will be discussed.

Course Format:
Material from books and research papers published in major conferences and journals will be studied in depth. The course will include lectures by the instructor, presentations by students, and discussions. Students are required to study the material covered in class. No textbook is required. Research papers, and handouts will be made available. Grading will be based on homework assignments, presentations, and a project. Homeworks will require some programming. The actual format of the course will ultimately depend on the number of students enrolled.

List of papers (UNDER CONSTRUCTION)
Ensembles of Classifiers
- R. Polikar, Ensemble Based Systems in Decision Making, IEEE Circuits and Systems Magazine, 6(3), pp. 21-45, 2006.

T. K. Ho, Nearest Neighbors in Random Subspaces, Advances in Pattern Recognition, Lecture Notes in Computer Science, pp. 640-648, 1998.

T. K. Ho, The random subspace method for constructing decision forests, IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(8), 1998.

D. Margineantu and T. Dietterich, Pruning Adaptive Boosting, International Conference on Machine Learning, 1997.

L. Breiman, Bias, variance, and arcing classifiers, Technical Report 460, Statistics Department, UC Berkeley, 1996.

K. Ali and M. Pazzani, Error reduction through learning multiple descriptions, Machine Learning, 24(3):173-202, 1996.

Y. Freund and R. Schapire, Experiments with a new boosting algorithm, International Conference on Machine Learning, 1996.

Clustering Ensembles
- R. Caruana, M. Elhawary, N. Nguyen, and C. Smith, Meta Clustering, International Conference on Data Mining, pp. 107-118, 2006.

S. T. Hadjitodorov, L. I. Kuncheva, and L. P. Todorova, Moderate diversity for better cluster ensembles, Information Fusion, 7 pp. 264-275, 2006.

A. Strehl and J. Ghosh, Cluster Ensembles - A Knowledge Reuse Framework for Combining Multiple Partitions, Journal of Machine Learning Research, 3 pp. 583-617, 2002.

X. Z. Fern and C. Brodley, Random projection for high dimensional data clustering: A cluster ensemble approach, International Conference on Machine Learning, pp. 186-193, 2003.

X. Z. Fern and C. Brodley, Solving Cluster Ensemble Problems by Bipartite Graph Partitioning, International Conference on Machine Learning, pp. 281-288, 2004.

X. Z. Fern and W. Lin, Cluster Ensemble Selection, SIAM International Conference on Data Mining, pp. 787-797 , 2008.

Ensembles and Semi-supervised learning
- D. Greene and P. Cunningham, An ensemble approach to identifying informative constraints for semi-supervised clustering, European Conference on Machine Learning, pp. 140-151, 2007.

A. Blum and T. Mitchell, Combining Labeled and Unlabeled Data with Co-training, Conference on Computational Learning Theory, pp. 92-100, 1998.

Z. Zhou and M. Li, Tri-Training: Exploiting Unlabeled Data Using Three Classifiers, IEEE Transactions on Knowledge and Data Engineering, 17(11), 2005.

Sources
UNDER CONSTRUCTION

UCI Machine Learning Repository is a repository of databases, domain theories and data generators that are used by the machine learning community for the empirical analysis of machine learning algorithms. A beta version of a new and improved site is also available

UCI Knowledge Discovery in Databases Archive is an online repository of large data sets which encompasses a wide variety of data types, analysis tasks, and application areas

Weka is an open source Java package implementing many learning algorithms

YALE (Yet Another Learning Environment) is another open source Java package. It includes a GUI which allows automation of the whole data process from feature normalization to feature selection, learning and cross-validation

SVM light and LibSVM are two popular implementations of various SVM algorithms

TMG is a Matlab Toolbox that can be used for various tasks in text mining