Dr. SangHyeun Park
Contact
Email: park@ke.tudarmstadt.deResearch Interests
 Machine Learning:
learning algorithms, (applicable) learning settings, efficacy and efficiency aspects, structured input and output/prediction space, decompositionbased/modular learning  Artificial Intelligence:
search/simulation algorithms, problemtransformation, 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 fixedlimit 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 roundbased 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 textclassification can often be improved using binary decompositions such as errorcorrecting output codes (ECOC). The key contribution of this short note is the realization that ECOC and, in fact, all classbased 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 straightforward implementation, which has a complexity of O(n⋅t⋅g), the proposed approach improves the complexity to O((n+t)⋅g). Largescale 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, SangHyeun and F\"{u}rnkranz, Johannes}, title = {Efficient implementation of classbased decomposition schemes for Naïve Bayes}, journal = {Machine Learning}, year = {2014}, volume = {96}, number = {3}, pages = {295309}, note = {Technical Note}, doi = {http://dx.doi.org/10.1007/s109940135430z} } 

Abstract: In this paper, we reinterpret errorcorrecting output codes (ECOCs) as a framework for converting multiclass classification problems into multilabel prediction problems. Different wellknown multilabel learning approaches can be mapped upon particular ways of dealing with the original multiclass problem. For example, the label powerset approach obviously constitutes the inverse transformation from multilabel back to multiclass, 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 multilabel 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 errorcorrecting properties. Our results indicate that a slight but consistent advantage can be obtained with the use of multilabel methods, in particular when longer codes are employed. 
BibTeX:
@inproceedings{FP2012, author = {F\"{u}rnkranz, Johannes and Park, SangHyeun}, title = {ErrorCorrecting Output Codes as a Transformation from MultiClass to MultiLabel Prediction}, booktitle = {Proceedings of the 15th International Conference on Discovery Science (DS12, Lyon, France)}, year = {2012}, pages = {254267}, doi = {http://dx.doi.org/10.1007/9783642334924_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 preferencebased approach to reinforce ment learning is the observation that in many realworld 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 longterm 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 rollouts. 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 preferencebased 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, SangHyeun}, title = {Preferencebased reinforcement learning: a formal framework and a policy iteration algorithm}, journal = {Machine Learning}, year = {2012}, volume = {89}, number = {12}, pages = {123156}, url = {http://www.ke.tudarmstadt.de/publications/papers/MLJPrefBasedRL.pdf}, doi = {http://dx.doi.org/10.1007/s1099401253138} } 

Abstract: Decompositionbased 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 decompositionscheme 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 decompositionbased 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 decompositionbased 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 decompositionbased 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 efficiencyfocused 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 decompositionbased approach. 
BibTeX:
@phdthesis{Par2012, author = {SangHyeun Park}, title = {Efficient DecompositionBased Multiclass and Multilabel Classification}, school = {TU Darmstadt}, type = {Dissertation}, year = {2012}, url = {http://tuprints.ulb.tudarmstadt.de/2994/} } 

Abstract: Binary decomposition methods transform multiclass learning problems into a series of twoclass learning problems that can be solved with simpler learning algorithms. As the number of such binary learning problems often grows superlinearly 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 errorcorrecting output codes under a variety of different code designs and decoding strategies. 
BibTeX:
@article{PF2012, author = {Park, SangHyeun 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 = {4077}, url = {http://www.ke.tudarmstadt.de/publications/papers/dami12.pdf}, doi = {http://dx.doi.org/10.1007/s1061801102199} } 

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 "preferencebased" 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 rollouts. 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 preferencebased 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, SangHyeun}, editor = {Dimitrios Gunopulos and Thomas Hofmann and Donato Malerba and Michalis Vazirgiannis}, title = {PreferenceBased 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 = {312327}, url = {http://www.ke.tudarmstadt.de/publications/papers/ECMLPKDD11.pdf}, doi = {http://dx.doi.org/10.1007/9783642237805_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 realworld datasets. We achieve an averagecase 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 realworld datasets. 
BibTeX:
@article{MPF2010, author = {Eneldo {Loza Menc{\'i}a} and SangHyeun Park and Johannes F{\"u}rnkranz}, title = {Efficient voting prediction for pairwise multilabel classification}, journal = {Neurocomputing}, year = {2010}, volume = {73}, number = {79}, pages = {11641176}, url = {http://www.ke.tudarmstadt.de/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 errorcorrecting 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 retraining 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, SangHyeun 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 = {266280}, url = {http://www.ke.tudarmstadt.de/publications/papers/DS10.pdf}, doi = {http://dx.doi.org/10.1007/9783642161841_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 = {SangHyeun Park and Johannes F{\"u}rnkranz}, editor = {Wray L. Buntine and Marko Grobelnik and Dunja Mladeni\v{c} and John ShaweTaylor}, title = {Efficient Decoding of Ternary ErrorCorrecting 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 = {189204}, url = {http://www.ke.tudarmstadt.de/publications/papers/ECMLPKDD09.pdf}, doi = {http://dx.doi.org/10.1007/9783642041747_13} } 

Abstract: We describe the poker agent AKIRealBot which participated in the 6player 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 MonteCarlo decision treebased 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, SangHyeun and F{\"u}rnkranz, Johannes}, editor = {Mertsching, B{\"a}rbel and Hund, Marcus and {Zaheer Aziz}, Muhammad}, title = {An Exploitative {MonteCarlo} Poker Agent}, booktitle = {Proceedings of the 32nd Annual German Conference on Artificial Intelligence (KI 2009, Paderborn, Germany)}, publisher = {Springer}, year = {2009}, pages = {6572}, doi = {http://dx.doi.org/10.1007/9783642046179_9} } 

Abstract: In this paper, we compare and combine two approaches for multilabel classication that both decompose the initial problem into sets of smaller problems. The Calibrated Label Ranking approach is based on interpreting the multilabel 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 multilabel problems. Experimental results indicate that the use of HOMER is benecial for the pairwise preferencebased 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, SangHyeun and F{\"u}rnkranz, Johannes}, editor = {H{\"u}llermeier, Eyke and F{\"u}rnkranz, Johannes}, title = {On the Combination of Two Decompositive MultiLabel Classification Methods}, booktitle = {Proceedings of the ECML PKDD 2009 Workshop on Preference Learning (PL09, Bled, Slovenia)}, year = {2009}, pages = {114129}, url = {http://www.ke.tudarmstadt.de/events/PL09/09Tsoumakas.pdf} } 

Abstract: We extend the multilabel 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 constraintbased correction approaches as postprocessing 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 realworld datasets. 
BibTeX:
@inproceedings{PF2008, author = {Park, SangHyeun and F{\"u}rnkranz, Johannes}, editor = {H{\"u}llermeier, Eyke and F{\"u}rnkranz, Johannes}, title = {MultiLabel Classification with Label Constraints}, booktitle = {Proceedings of the ECML PKDD 2008 Workshop on Preference Learning (PL08, Antwerp, Belgium)}, year = {2008}, pages = {157171}, url = {http://www.mathematik.unimarburg.de/~kebi/wsecml08/12.pdf} } 

Abstract: Pairwise classification is a class binarization procedure that converts a multiclass problem into a series of twoclass 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 oneagainstall 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 worstcase 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 welltrained base classifiers, its asymptotic computational complexity seems to be almost linear. 
BibTeX:
@inproceedings{PF2007, author = {SangHyeun 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 = {658665}, url = {http://www.ke.tudarmstadt.de/~juffi/publications/ecml07EfficientPairwise.pdf}, doi = {http://dx.doi.org/10.1007/9783540749585_65} } 
BibTeX:
@mastersthesis{Par2006, author = {Park, SangHyeun}, title = {Effiziente Klassifikation und Ranking mit paarweisen Vergleichen}, school = {Knowledge Engineering Group, TU Darmstadt}, year = {2006}, note = {Diplom, in german}, url = {http://www.ke.tudarmstadt.de/lehre/arbeiten/diplom/2006/Park_SangHyeun.pdf} } 