Dr. Sang-Hyeun Park
Contact
Email: park@ke.tu-darmstadt.deResearch Interests
- Machine Learning:
learning algorithms, (applicable) learning settings, efficacy and efficiency aspects, structured input and output/prediction space, decomposition-based/modular learning - Artificial Intelligence:
search/simulation algorithms, problem-transformation, multiplayer games
Education
- May 2007 - May 2012:
Ph.D. student in Computer Science at the Technische Universität Darmstadt - October 2000 - December 2006:
Studies in Computer Science at the Technische Universität Darmstadt
Activities
- Program committee:
KDML 2009, LeGo 2009, MLD 2010, PL 2008 & 2010 - Reviewer:
CIKM 2011, DS 2009, ECML 2009 & 2010, ICDM 2008, IJCAI 2009, KDML 2008, SDM 2011
AI Communications, Data Mining and Knowledge Discovery, Information Sciences, Machine Learning, Neural Processing Letters
Teaching
Teaching assistant activities:- Einführung in die Künstliche
Intelligenz SS 09,
WS
10/11
(Introduction to Artificial Intelligence) - TUD Computer Poker Challenge SS
08, SS
09, SS
10, SS 11
(academic class project - implementation of an agent for fixed-limit multiplayer Texas Hold'em Poker) - Introduction to Data and Knowledge Engineering SS 11
- Bachelorpraktikum
Knowledge Engineering WS 09/10
(academic class project - implementation of an agent for the round-based multiplayer game Blokus)
Publications
Some overlapping papers (e.g., technical reports) are not listed here. The complete list of publications can be found in our publications database.
|
Abstract: Previous studies have shown that the classification accuracy of a Naïve Bayes classifier in the domain of text-classification can often be improved using binary decompositions such as error-correcting output codes (ECOC). The key contribution of this short note is the realization that ECOC and, in fact, all class-based decomposition schemes, can be efficiently implemented in a Naïve Bayes classifier, so that—because of the additive nature of the classifier—all binary classifiers can be trained in a single pass through the data. In contrast to the straight-forward implementation, which has a complexity of O(n⋅t⋅g), the proposed approach improves the complexity to O((n+t)⋅g). Large-scale learning of ensemble approaches with Naïve Bayes can benefit from this approach, as the experimental results shown in this paper demonstrate. |
BibTeX:
@article{PF2014, author = {Park, Sang-Hyeun and F\"{u}rnkranz, Johannes}, title = {Efficient implementation of class-based decomposition schemes for Naïve Bayes}, journal = {Machine Learning}, year = {2014}, volume = {96}, number = {3}, pages = {295--309}, note = {Technical Note}, doi = {http://dx.doi.org/10.1007/s10994-013-5430-z} } |
|
Abstract: In this paper, we reinterpret error-correcting output codes (ECOCs) as a framework for converting multi-class classification problems into multi-label prediction problems. Different well-known multi-label learning approaches can be mapped upon particular ways of dealing with the original multi-class problem. For example, the label powerset approach obviously constitutes the inverse transformation from multi-label back to multi-class, whereas binary relevance learning may be viewed as the conventional way of dealing with ECOCs, in which each classifier is learned independently of the others. Consequently, we evaluate whether alternative choices for solving the multi-label problem may result in improved performance. This question is interesting because it is not clear whether approaches that do not treat the bits of the code words independently have sufficient error-correcting properties. Our results indicate that a slight but consistent advantage can be obtained with the use of multi-label methods, in particular when longer codes are employed. |
BibTeX:
@inproceedings{FP2012, author = {F\"{u}rnkranz, Johannes and Park, Sang-Hyeun}, title = {Error-Correcting Output Codes as a Transformation from Multi-Class to Multi-Label Prediction}, booktitle = {Proceedings of the 15th International Conference on Discovery Science (DS-12, Lyon, France)}, year = {2012}, pages = {254--267}, doi = {http://dx.doi.org/10.1007/978-3-642-33492-4_21} } |
|
Abstract: This paper makes a first step toward the integration of two subfields of machine learning, namely preference learning and reinforcement learning (RL). An important motivation for a preference-based approach to reinforce- ment learning is the observation that in many real-world domains, numerical feedback signals are not readily available, or are defined arbitrarily in order to satisfy the needs of conventional RL algorithms. Instead, we propose an alternative framework for reinforcement learning, in which qualitative reward signals can be directly used by the learner. The framework may be viewed as a generalization of the conventional RL framework in which only a partial order between policies is required instead of the total order induced by their respective expected long-term reward. Therefore, building on novel methods for preference learning, our general goal is to equip the RL agent with qualita- tive policy models, such as ranking functions that allow for sorting its available actions from most to least promising, as well as algorithms for learning such models from qualitative feedback. As a proof of concept, we realize a first sim- ple instantiation of this framework that defines preferences based on utilities observed for trajectories. To that end, we build on an existing method for approximate policy iteration based on roll-outs. While this approach is based on the use of classification methods for generalization and policy learning, we make use of a specific type of preference learning method called label ranking. Advantages of preference-based policy iteration are illustrated by means of two case studies. |
BibTeX:
@article{FHCP2012, author = {F\"{u}rnkranz, Johannes and H\"{u}llermeier, Eyke and Cheng, Weiwei and Park, Sang-Hyeun}, title = {Preference-based reinforcement learning: a formal framework and a policy iteration algorithm}, journal = {Machine Learning}, year = {2012}, volume = {89}, number = {1-2}, pages = {123--156}, url = {/publications/papers/MLJ-PrefBasedRL.pdf}, doi = {http://dx.doi.org/10.1007/s10994-012-5313-8} } |
|
Abstract: Decomposition-based methods are widely used
for multiclass and multilabel classification. These approaches
transform or reduce the original task to a set of smaller possibly
simpler problems and allow thereby often to utilize many
established learning algorithms, which are not amenable to the
original task. Even for directly applicable learning algorithms,
the combination with a decomposition-scheme may outperform the
direct approach, e.g., if the resulting subproblems are simpler (in
the sense of learnability). This thesis addresses mainly the
efficiency of decomposition-based methods and provides several
contributions improving the scalability with respect to the number
of classes or labels, number of classifiers and number of
instances.
Initially, we present two approaches improving the efficiency of the training phase of multiclass classification. The first of them shows that by minimizing redundant learning processes, which can occur in decomposition-based approaches for multiclass problems, the number of operations in the training phase can be significantly reduced. The second approach is tailored to Naive Bayes as base learner. By a tight coupling of Naive Bayes and arbitrary decompositions, it allows an even higher reduction of the training complexity with respect to the number of classifiers. Moreover, an approach improving the efficiency of the testing phase is also presented. It is capable of reducing testing effort with respect to the number of classes independently of the base learner. Furthermore, efficient decomposition-based methods for multilabel classification are also addressed in this thesis. Besides proposing an efficient prediction method, an approach rebalancing predictive performance, time and memory complexity is presented. Aside from the efficiency-focused methods, this thesis contains also a study about a special case of the multilabel classification setting, which is elaborated, formalized and tackled by a prototypical decomposition-based approach. |
BibTeX:
@phdthesis{Par2012, author = {Sang-Hyeun Park}, title = {Efficient Decomposition-Based Multiclass and Multilabel Classification}, school = {TU Darmstadt}, type = {Dissertation}, year = {2012}, url = {http://tuprints.ulb.tu-darmstadt.de/2994/} } |
|
Abstract: Binary decomposition methods transform multiclass learning problems into a series of two-class learning problems that can be solved with simpler learning algorithms. As the number of such binary learning problems often grows super-linearly with the number of classes, we need efficient methods for computing the predictions. In this article, we discuss an efficient algorithm that queries only a dynamically determined subset of the trained classifiers, but still predicts the same classes that would have been predicted if all classifiers had been queried. The algorithm is first derived for the simple case of pairwise classification, and then generalized to arbitrary pairwise decompositions of the learning problem in the form of ternary error-correcting output codes under a variety of different code designs and decoding strategies. |
BibTeX:
@article{PF2012, author = {Park, Sang-Hyeun and F\"{u}rnkranz, Johannes}, title = {Efficient prediction algorithms for binary decomposition techniques}, journal = {Data Mining and Knowledge Discovery}, year = {2012}, volume = {24}, number = {1}, pages = {40--77}, url = {/publications/papers/dami12.pdf}, doi = {http://dx.doi.org/10.1007/s10618-011-0219-9} } |
|
Abstract: This paper makes a first step toward the integration of two subfields of machine learning, namely preference learning and reinforcement learning (RL). An important motivation for a "preference-based" approach to reinforcement learning is a possible extension of the type of feedback an agent may learn from. In particular, while conventional RL methods are essentially confined to deal with numerical rewards, there are many applications in which this type of information is not naturally available, and in which only qualitative reward signals are provided instead. Therefore, building on novel methods for preference learning, our general goal is to equip the RL agent with qualitative policy models, such as ranking functions that allow for sorting its available actions from most to least promising, as well as algorithms for learning such models from qualitative feedback. Concretely, in this paper, we build on an existing method for approximate policy iteration based on roll-outs. While this approach is based on the use of classification methods for generalization and policy learning, we make use of a specific type of preference learning method called label ranking. Advantages of our preference-based policy iteration method are illustrated by means of two case studies. |
BibTeX:
@inproceedings{CFHP2011, author = {Cheng, Weiwei and F{\"u}rnkranz, Johannes and H{\"u}llermeier, Eyke and Park, Sang-Hyeun}, editor = {Dimitrios Gunopulos and Thomas Hofmann and Donato Malerba and Michalis Vazirgiannis}, title = {Preference-Based Policy Iteration: Leveraging Preference Learning for Reinforcement Learning}, booktitle = {Proceedings of the 22nd European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2011, Athens, Greece), Part I}, publisher = {Springer}, year = {2011}, pages = {312-327}, url = {/publications/papers/ECML-PKDD-11.pdf}, doi = {http://dx.doi.org/10.1007/978-3-642-23780-5_30} } |
|
Abstract: The pairwise approach to multilabel classification reduces the problem to learning and aggregating preference predictions among the possible labels. A key problem is the need to query a quadratic number of preferences for making a prediction. To solve this problem, we extend the recently proposed QWeighted algorithm for efficient pairwise multiclass voting to the multilabel setting, and evaluate the adapted algorithm on several real-world datasets. We achieve an average-case reduction of classifier evaluations from n^2 to n + n d log n, where n is the total number of possible labels and d is the average number of labels per instance, which is typically quite small in real-world datasets. |
BibTeX:
@article{MPF2010, author = {Eneldo {Loza Menc{\'i}a} and Sang-Hyeun Park and Johannes F{\"u}rnkranz}, title = {Efficient voting prediction for pairwise multilabel classification}, journal = {Neurocomputing}, year = {2010}, volume = {73}, number = {7-9}, pages = {1164-1176}, url = {/publications/papers/neucom10.pdf}, doi = {http://dx.doi.org/10.1016/j.neucom.2009.11.024} } |
|
Abstract: We study an approach for speeding up the training of error-correcting output codes (ECOC) classifiers. The key idea is to avoid unnecessary computations by exploiting the overlap of the different training sets in the ECOC ensemble. Instead of re-training each classifier from scratch, classifiers that have been trained for one task can be adapted to related tasks in the ensemble. The crucial issue is the identification of a schedule for training the classifiers which maximizes the exploitation of the overlap. For solving this problem, we construct a classifier graph in which the nodes correspond to the classifiers, and the edges represent the training complexity for moving from one classifier to the next in terms of the number of added training examples. The solution of the Steiner Tree problem is an arborescence in this graph which describes the learning scheme with the minimal total training complexity. We experimentally evaluate the algorithm with Hoeffding trees, as an example for incremental learners where the classifier adaptation is trivial, and with SVMs, where we employ an adaptation strategy based on adapted caching and weight reuse, which guarantees that the learned model is the same as per batch learning. |
BibTeX:
@inproceedings{PWF2010, author = {Park, Sang-Hyeun and Weizs{\"a}cker, Lorenz and F{\"u}rnkranz, Johannes}, editor = {Pfahringer, Bernhard and Holmes, Geoff and Hoffmann, Achim}, title = {Exploiting Code Redundancies in {ECOC}}, booktitle = {Proceedings of the 13th International Conference on Discovery Science (DS 2010, Canberra, Australia)}, publisher = {Springer}, year = {2010}, pages = {266-280}, url = {/publications/papers/DS-10.pdf}, doi = {http://dx.doi.org/10.1007/978-3-642-16184-1_19} } |
|
Abstract: We present an adaptive decoding algorithm for ternary ECOC matrices which reduces the number of needed classifier evaluations for multiclass classification. The resulting predictions are guaranteed to be equivalent with the original decoding strategy except for ambiguous final predictions. The technique works for Hamming Decoding and several commonly used alternative decoding strategies. We show its effectiveness in an extensive empirical evaluation considering various code design types: Nearly in all cases, a considerable reduction is possible. We also show that the performance gain depends on the sparsity and the dimension of the ECOC coding matrix. |
BibTeX:
@inproceedings{PF2009, author = {Sang-Hyeun Park and Johannes F{\"u}rnkranz}, editor = {Wray L. Buntine and Marko Grobelnik and Dunja Mladeni\v{c} and John Shawe-Taylor}, title = {Efficient Decoding of Ternary Error-Correcting Output Codes for Multiclass Classification}, booktitle = {Proceedings of the 20th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2009, Bled, Slovenia), Part II}, publisher = {Springer}, year = {2009}, pages = {189-204}, url = {/publications/papers/ECML-PKDD-09.pdf}, doi = {http://dx.doi.org/10.1007/978-3-642-04174-7_13} } |
|
Abstract: We describe the poker agent AKI-RealBot which participated in the 6-player Limit Competition of the third Annual AAAI Computer Poker Challenge in 2008. It finished in second place, its performance being mostly due to its superior ability to exploit weaker bots. This paper describes the architecture of the program and the Monte-Carlo decision tree-based decision engine that was used to make the bot’s decision. It will focus the attention on the modifications which made the bot successful in exploiting weaker bots. |
BibTeX:
@inproceedings{SPPF2009, author = {Schweizer, Immanuel and Panitzek, Kamill and Park, Sang-Hyeun and F{\"u}rnkranz, Johannes}, editor = {Mertsching, B{\"a}rbel and Hund, Marcus and {Zaheer Aziz}, Muhammad}, title = {An Exploitative {Monte-Carlo} Poker Agent}, booktitle = {Proceedings of the 32nd Annual German Conference on Artificial Intelligence (KI 2009, Paderborn, Germany)}, publisher = {Springer}, year = {2009}, pages = {65--72}, doi = {http://dx.doi.org/10.1007/978-3-642-04617-9_9} } |
|
Abstract: In this paper, we compare and combine two approaches for multi-label classication that both decompose the initial problem into sets of smaller problems. The Calibrated Label Ranking approach is based on interpreting the multi-label problem as a preference learning problem and decomposes it into a quadratic number of binary classiers. The HOMER approach reduces the original problem into a hierarchy of considerably simpler multi-label problems. Experimental results indicate that the use of HOMER is benecial for the pairwise preference-based approach in terms of computational cost and quality of prediction. |
BibTeX:
@inproceedings{TMK_2009, author = {Tsoumakas, Grigorios and {Loza Menc{\'i}a}, Eneldo and Katakis, Ioannis and Park, Sang-Hyeun and F{\"u}rnkranz, Johannes}, editor = {H{\"u}llermeier, Eyke and F{\"u}rnkranz, Johannes}, title = {On the Combination of Two Decompositive Multi-Label Classification Methods}, booktitle = {Proceedings of the ECML PKDD 2009 Workshop on Preference Learning (PL-09, Bled, Slovenia)}, year = {2009}, pages = {114--129}, url = {/events/PL-09/09-Tsoumakas.pdf} } |
|
Abstract: We extend the multi-label classification setting with constraints on labels. This leads to two new machine learning tasks: First, the label constraints must be properly integrated into the classification process to improve its performance and second, we can try to automatically derive useful constraints from data. In this paper, we experiment with two constraint-based correction approaches as post-processing step within the ranking by pairwise comparison (RPC)-framework. In addition, association rule learning is considered for the task of label constraints learning. We report on the current status of our work, together with evaluations on synthetic datasets and two real-world datasets. |
BibTeX:
@inproceedings{PF2008, author = {Park, Sang-Hyeun and F{\"u}rnkranz, Johannes}, editor = {H{\"u}llermeier, Eyke and F{\"u}rnkranz, Johannes}, title = {Multi-Label Classification with Label Constraints}, booktitle = {Proceedings of the ECML PKDD 2008 Workshop on Preference Learning (PL-08, Antwerp, Belgium)}, year = {2008}, pages = {157--171}, url = {http://www.mathematik.uni-marburg.de/~kebi/ws-ecml-08/12.pdf} } |
|
Abstract: Pairwise classification is a class binarization procedure that converts a multi-class problem into a series of two-class problems, one problem for each pair of classes. While it can be shown that for training, this procedure is more efficient than the more commonly used one-against-all approach, it still has to evaluate a quadratic number of classifiers when computing the predicted class for a given example. In this paper, we propose a method that allows a faster computation of the predicted class when weighted or unweighted voting are used for combining the predictions of the individual classifiers. While its worst-case complexity is still quadratic in the number of classes, we show that even in the case of completely random base classifiers, our method still outperforms the conventional pairwise classifier. For the more practical case of well-trained base classifiers, its asymptotic computational complexity seems to be almost linear. |
BibTeX:
@inproceedings{PF2007, author = {Sang-Hyeun Park and Johannes F{\"u}rnkranz}, editor = {Joost N. Kok and Jacek Koronacki and Ramon {Lopez de Mantaras} and Stan Matwin and Dunja Mladeni\v{c} and Andrzej Skowron}, title = {Efficient Pairwise Classification}, booktitle = {Proceedings of the 18th European Conference on Machine Learning (ECML 2007, Warsaw, Poland)}, publisher = {Springer}, year = {2007}, pages = {658--665}, url = {/~juffi/publications/ecml-07-EfficientPairwise.pdf}, doi = {http://dx.doi.org/10.1007/978-3-540-74958-5_65} } |
BibTeX:
@mastersthesis{Par2006, author = {Park, Sang-Hyeun}, title = {Effiziente Klassifikation und Ranking mit paarweisen Vergleichen}, school = {Knowledge Engineering Group, TU Darmstadt}, year = {2006}, note = {Diplom, in german}, url = {/lehre/arbeiten/diplom/2006/Park_Sang-Hyeun.pdf} } |