Tom Bylander (email: bylander@cs.utsa.edu )
Stephen Kwek (email: kwek@cs.utsa.edu )

Current Students:

• Chau Nguyen (Thesis: iBoost, Boosting Using an instance Based Exponential Weighting Scheme)
• Michael Jon Maltrud (Thesis: Multiclass Predictions Using Weighted Error Correcting Output Codes)
• John Andrichak IV
• Matthew Grantz
• Trung Nguyen
• Lisa Tate

Seminar Schedule:

• Summer 2002

Projects:

• Foundation (Theory):
1. Foundation of Multiple Classifier Systems and Active Learning
2. Geometric Concept Learning
3. Learning Linear Threshold Functions
4. Miscellaneous Topics
• Empirical (Experimental):
1. Instance Based Weighting Schemes in Ensemble Methods
• Application (Data Mining):

Technical Reports:

• 2002

Useful Computational Research Links:

• Using WEKA in the CSLab
• Bibliography on Computational and Algorithmic Learning Theory
• David Aha's Machine Learning Resources
• KDNuggets Directory, Data Mining and Knowledge Discovery Resources.
• UCI Machine Learning Repository
• Computational Learning Theory Web Site

Funding: National Science Foundation, CCR-0208935 (PI: Kwek)

Theoretical Project 1: Foundation of Multiple Classifier Systems and Active Learning

There are many research problems to consider. The following is a list of some of the problems that this project will examine. The list is not intended to be exhaustive, but rather gives some concrete starting points that are illustrative of the type of research problems to be pursued. Other problems may also be studied in this project. This list also serves to demonstrate some of the work that the PI has done in MCS and active learning. The PI has previously investigated these problems, but many important issues remain to be investigated. Although the main approach in this research is that of COLT, empirical studies will be performed to test the efficacy of the algorithms and heuristics that are derived from the research.

MCS 1: Learning When to Trust Which Experts: If we have a number of experts (or learning algorithms) each having its own strengths and weaknesses, how can a learner learn the conditions in which each expert's predictions can be trusted? Such an understanding will give rise to better ways of combining the experts' advice than simply taking a weighted vote as done in ensemble methods.

MCS 2: Learning Multiple Intermediate Concepts: The target concept may be dependent on or correlated to some other related intermediate concepts. How do we exploit such dependencies and learn these intermediate concepts so that we can use them to enhance our approximation of the target concept? Although such situations occur quite often in practice, most research work concentrates on learning a single target concept.

Active Learning 1: Learning from Data with Unspecified Attribute Values: Almost all work in COLT assumes that the attribute values of the instances are totally specified. However, it is common in practice that the instances are often partially specified. How can a learner learn in the presence of unspecified attribute values where an instance can be classified as 'undeterminable' (based only on those attributes with specified values)?

Active Learning 2: Learning by Observing an Expert Perform the Classification Task: Instead of having a teacher who actively teaches the learner, how can a learner learn by observing an expert perform the classification task? This provides a better alternative than the current teaching model which assumes that the student is unwilling to learn (so as to circumvent the "outright-encoding'' problem).

For more details, please click here .

References:

1. Sally Goldman, Stephen Kwek and Stephen Scott, Learning From Examples With Unspecified Attribute Values. To appear in Information and Computation 2002. An extended abstract appeared in Proceedings of the10th Annual ACM conference on Computational Learning Theory, page 231-242, ACM Press, New York, NY 1997.
2. Stephen Kwek, Learning Intermediate Concepts. Proc . of the 12th International Conference on Algorithmic Learning Theory . Volume 2225 of Lecture Notes in Artificial Intelligence. November 25-28, 2001. Pages 151-166, 2001
3. Stephen Kwek, An Apprentice Learning Model . Proceedings of the 12th Annual ACM conference on Computational Learning Theory. pages 63-74, ACM Press, New York, NY 1999.
4. David Helmbold, Stephen Kwek and Leonard Pitt, Learning When to Trust Which Experts. Proceedings of the 3rd European Conference on Computational Learning Theory, page 134-150, Lecture Notes in Artificial Intelligence, No. 1208, Springer, 1997.

Theoretical Project 2: Geometric Concept Learning

Various results have shown that geometric concepts in arbitrary dimensional space, in particular convex polytopes, are hard to learn in most traditional learning models. One objective of this project is to examine how convex polytopes can be learned with a richer way of interacting with the environment besides using membership queries. Another objective is to investigate how low dimensional geometric concepts can be learned.

References:

1. Sally Goldman, Stephen Kwek and Stephen Scott, Agnostic Learning of Geometric Patterns . Journal of Computer and System Science, 62(1):123-151, 2001.
2. Stephen Kwek and Leonard Pitt, PAC Learning Intersections of Halfspaces with Membership Queries . Algorithmica, Special Issue on Computational Learning Theory, 22 (1998) pp. 53-75.
3. Paul Goldberg and Stephen Kwek, The Precision of Query Points as a Resource for Learning Convex Polytopes with Membership Queries . Proc. of 13th Annual Anniversary on Computational Learning Theory , Morgan Kauffman, pages 225-235, 2000.
4. Stephen Kwek, An Efficient Algorithm for Learning Upper Convex Polytopes Using Membership Queries. In Proc. of 6th International Symposium on Math and Artificial Intelligence , 2000.
5. Peter Auer, Stephen Kwek, Wolfgang Maass and Manfred Warmuth, Learning of Depth Two Neural Networks with Constant Fan-in at the Hidden Nodes . Proceedings of the 9th Annual ACM Conference on Computational Learning Theory, page 244-254, ACM Press, New York, NY 1996.
6. Stephen Kwek, Geometric Concept Learning and Related Topics (Ph. D. Thesis). University of Illinois at Urbana-Champaign, Department of Computer Science, Technical report UIUCDCS-R-97-1980. 1997

For more details, please click here .
 

Theoretical Project 3: Learning Linear Threshold Functions

References:

1. Bylander, The Binary Exponentiated Gradient Algorithm for Learning Linear Functions, Proc. 10th Annu. Conf. on Comput. Learning Theory, pp. 184-192, ACM Press, New York, NY, 1997.
2. Bylander, Estimating Generalization Error on Two-Class Datasets Using Out-of-Bag Estimates, Machine Learning, Vol. 48, Number 1/3, pp. 287-297, Kluwer Academic Publishers, Boston, 2002.
3. Bylander, Learning linear threshold functions in the presence of classification noise,  Proc. 7th Annu. ACM Conf. on Comput. Learning Theory, pp. 340-347, ACM Press, New York, NY, 1994.
4. Bylander, Learning Probabilistically Consistent Linear Threshold Functions, Proc. 10th Annu. Conf. on Comput. Learning Theory, pp. 62-71, ACM Press, New York, NY, 1997.
5. Bylander, Polynomial learnability of linear threshold approximations, Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, pp. 297-302, ACM Press, New York, NY, 1993

Theoretical Projects: Miscellaneous Topics

References:

1. Sally Goldman and Stephen Kwek, On Learning Unions of Pattern Languages and Tree Patterns in the Mistake Bound Model . To appear in Journal of Theoretical Computer Science special issue on Algorithmic Learning Theory 2002. An extended abstract appeared in Proceedings of the 10th International Conference on Algorithmic Learning Theory . page 347-363, Lecture Notes in Artificial Intelligence, No. 1720, Springer, 1999.
2. Daniel Dooly, Sally Goldman and Stephen Kwek, Real-Valued Multiple-Instance Learning with Queries . Proc. of 12th International Conference on Algorithmic Learning Theory . Volume 2225 of Lecture Notes in Artificial Intelligence. November 25-28, 2001. Pages 167-180, 2001.
3. Stephen Kwek,  On a Simple Depth-First Search Strategy for Exploring Unknown Graph . Proceedings of the 5th International Workshop in Algorithms and Data Structures, page 345-353, Lecture Notes in Computer Science, No. 1272, Springer, 1997.
4. Stephen Kwek, Learning Disjunctions of Features . Proceedings of the 8th Int. Conf. on Algorithmic Learning Theory , page 401-415, Lecture Notes in Artificial Intelligence, No.1316, Springer, 1997.

Empirical Project: Instance Based Weighting Schemes in Ensemble Methods

In ensemble methods, the vote of each base classifier either receives the same weight (e.g. Bagging and Arcing) or is weighted according to the estimated error rate (e.g. AdaBoost). Based on my recent work, I am proposing an instance-based approach of assigning weights to the base classifiers that may enhance the performance of ensemble methods.

Instead of assigning a weight to a base classifier that is fixed for all instances, we attempt to assign a weight that is based upon how well we think the base classifier is going to predict on the label of the test instance. Intuitively, given an unlabeled instance, if there is some indication that the base classifier's prediction is correct then we should increase its weight. Otherwise, we should reduce its weight. In our preliminary investigation, on nine UC Irvine datasets where AdaBoost did not perform well, with accuracy between 70% to 80%, we manage to improve the prediction accuracy on all datasets with an average improvement of more than 1%. This suggests that such instance-based weighting scheme does enhance the accuracy of ensemble methods. The implementation is currently still quite crude. We believe it can be further fine-tuned to achieve an even higher accuracy. This project explores instance-based weighting schemes further so as to enhance existing ensemble methods and their derivatives.

References:

1. Stephen Kwek and Chau Nguyen. iBoost: Boosting with an instance-based voting scheme . To appear in the 13th European Conference on Machine Learning 2002.
2. David Helmbold, Stephen Kwek and Leonard Pitt, Learning When to Trust Which Experts . Proceedings of the 3rd European Conference on Computational Learning Theory, page 134-150, Lecture Notes in Artificial Intelligence, No. 1208, Springer, 1997.

For more information, please click here .

Application Projects:

References:

1. Dragoljub Pokrajac, Stephen Kwek, Zoran Obradovic, Tim Fiez and Dragan Obradovic, Distribution Comparison for Site-specific Regression Modeling in Agriculture. Proceedings of the International Joint Conference on Neural Networks , page 346-352, 1999.