Discovery Science. 14th International Conference DS 2011 Proceedings (Lecture Notes in Artificial Intelligence)

Lecture Notes in Artiﬁcial Intelligence Subseries of Lecture Notes in Computer Science LNAI Series Editors Randy Goebel...

Author: Tapio Elomaa | Jaakko Hollmen | Heikki Mannila (Editors)

55 downloads 1138 Views 13MB Size Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

Lecture Notes in Artiﬁcial Intelligence Subseries of Lecture Notes in Computer Science LNAI Series Editors Randy Goebel University of Alberta, Edmonton, Canada Yuzuru Tanaka Hokkaido University, Sapporo, Japan Wolfgang Wahlster DFKI and Saarland University, Saarbrücken, Germany

LNAI Founding Series Editor Joerg Siekmann DFKI and Saarland University, Saarbrücken, Germany

6926

Tapio Elomaa Jaakko Hollmén Heikki Mannila (Eds.)

Discovery Science 14th International Conference, DS 2011 Espoo, Finland, October 5-7, 2011 Proceedings

13

Series Editors Randy Goebel, University of Alberta, Edmonton, Canada Jörg Siekmann, University of Saarland, Saarbrücken, Germany Wolfgang Wahlster, DFKI and University of Saarland, Saarbrücken, Germany Volume Editors Tapio Elomaa Tampere University of Technology, Department of Software Systems P.O. Box 553, 33101 Tampere, Finland E-mail: [email protected].ﬁ Jaakko Hollmén Heikki Mannila Aalto University School of Science Department of Information and Computer Science P.O. Box 15400, 00076 Aalto, Finland E-mail:{jaakko.hollmen, heikki.mannila}@aalto.ﬁ

ISSN 0302-9743 e-ISSN 1611-3349 ISBN 978-3-642-24476-6 e-ISBN 978-3-642-24477-3 DOI 10.1007/978-3-642-24477-3 Springer Heidelberg Dordrecht London New York Library of Congress Control Number: 2011937030 CR Subject Classiﬁcation (1998): I.2, H.3, H.4, H.2.8, J.1, H.5, C.2 LNCS Sublibrary: SL 7 – Artiﬁcial Intelligence

© Springer-Verlag Berlin Heidelberg 2011 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, speciﬁcally the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microﬁlms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a speciﬁc statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typesetting: Camera-ready by author, data conversion by Scientiﬁc Publishing Services, Chennai, India Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)

Preface

We are pleased to present the proceedings of the 14th International Conference on Discovery Science (DS 2011), held in Espoo, Finland, during October 5-7, 2011. DS 2011 provided an open forum for intensive discussions and exchange of new ideas among researchers working in the area of discovery science. The scope of the conference includes the development and analysis of methods for automatic scientiﬁc knowledge discovery, machine learning, intelligent data analysis, theory of learning, as well as their application to knowledge discovery. DS 2011 was co-located with the 22nd International Conference on Algorithmic Learning Theory (ALT 2011). The proceedings of ALT 2011 appeared as companion volume number 6925 in the Springer LNCS series. This year we had a decennial celebration of the fruitful co-location of the ALT and DS conference series, which allowed us to cover the whole range from theoretical explorations to practical applications. We were honored to have a strong program. We received 56 submissions from authors coming from 22 countries. The submissions were reviewed by three members of the Program Committee; the Program Chairs evaluated the review reports and decided to accept 24 papers based on the merits of originality, technical quality, and relevance to the ﬁeld of discovery science. The overall acceptance rate was 43%. We were delighted to have ﬁve prestigious invited talks by six speakers. Ming Li from the University of Waterloo in Canada presented “Information Distance and Its Extensions”. Eyke H¨ ullermeier from PhilippsUniversit¨ at Marburg in Germany together with Johannes F¨ urnkranz from Technische Universit¨ at Darmstadt in Germany presented a joint invited talk on the latest research concerning “Learning from Label Preferences”. Yoshua Bengio from the University of Montreal in Canada was the joint invited speaker of ALT 2011 and DS 2011, and he presented “On the Expressive Power of Deep Architectures”. Jorma Rissanen from Helsinki Institute for Information Technology in Finland presented an invited talk on “Optimal Estimation”. Peter Auer from the University of Leoben in Austria presented “Models for Autonomously Motivated Exploration in Reinforcement Learning”. Tutorials were given on the topic of preference learning by Eyke H¨ ullermeier and Johannes F¨ urnkranz jointly and on the topic of bandits by S´ebastien Bubeck from Princeton University in USA. We wish to express our gratitude to all authors of submitted papers, the Program Committee members and the additional reviewers for their eﬀorts in evaluating the submitted papers, as well as the invited speakers and tutorial presenters. We thank the members of the DS Steering Committee, especially its Chair, Einoshin Suzuki, who were very helpful in providing continual support necessary for the continuity of the DS series. We thank the ALT editors Jyrki Kivinen, Csaba Szepesv´ ari, Esko Ukkonen, and Thomas Zeugmann for the fruitful coordination of the co-located ALT and DS conferences. We also thank

VI

Preface

the Local Organizing Committee, chaired by Olli Simula, for making the practical arrangements concerning the ALT and DS conferences. We acknowledge the support from our hosting organizations Aalto University, University of Helsinki, Algodan - Centre of Excellence for Algorithmic Data Analysis Research, and Helsinki Institute for Information Technology in Finland. Finally, we thank the Artiﬁcial Intelligence journal for the ﬁnancial support. August 2011

Tapio Elomaa Jaakko Hollm´en Heikki Mannila

Organization

Organizing Committee Steering Committee Chair Einoshin Suzuki Conference Chair Heikki Mannila Program Chairs Tapio Elomaa Jaakko Hollm´en Local Organization Chair Olli Simula Local Organizing Committee Ella Bingham Tapio Elomaa Jaakko Hollm´en Jyrki Kivinen Mikko Korpela Kai Puolam¨ aki Mika Sulkava Janne Toivola

Program Committee Hiroki Arimura Hideo Bannai Michael R. Berthold Hendrik Blockeel Henrik Bostr¨ om Jean-Francois Bouli¸caut Bruno Cr´emilleux Saˇso Dˇzeroski Tapio Elomaa Peter Flach Johannes F¨ urnkranz

Hokkaido University, Japan Kyushu University, Japan University of Konstanz, Germany K.U. Leuven, Belgium Stockholm University, Sweden INSA Lyon, France University of Caen, France Joˇzef Stefan Institute, Slovenia Tampere University of Technology, Finland University of Bristol, UK TU Darmstadt, Germany

VIII

Organization

Jo˜ ao Gama Mohand-Said Hacid Howard J. Hamilton Makoto Haraguchi Kouichi Hirata Jaakko Hollm´en Geoﬀ Holmes Vasant Honavar Tam´as Horv´ ath Eyke H¨ ullermeier Al´ıpio M. Jorge Hisashi Kashima Ross King Joost N. Kok Stefan Kramer Nada Lavraˇc Philippe Lenca Donato Malerba Taneli Mielik¨ ainen Richard Nock Panagiotis Papapetrou Mykola Pechenizkiy Jean-Marc Petit Bernhard Pfahringer Enric Plaza Juho Rousu Jean Sallantin V´ıtor Santos Costa Mika Sulkava Einoshin Suzuki Nikolaj Tatti Hannu Toivonen Antti Ukkonen Akihiro Yamamoto Zhi-Hua Zhou

Universidade do Porto, Portugal Universit´e Claude Bernard Lyon 1, France University of Regina, Canada Hokkaido University, Japan Kyushu Institute of Technology, Japan Aalto University, Finland University of Waikato, New Zealand Iowa State University, USA University of Bonn, Fraunhofer IAIS, Germany Philipps-Universit¨ at Marburg, Germany Universidade do Porto, Portugal University of Tokyo, Japan University of Wales, Aberystwyth, UK LIACS, Leiden University, The Netherlands TU M¨ unchen, Germany Joˇzef Stefan Institute, Slovenia T´el´ecom Bretagne, France Universit`a di Bari, Italy Nokia Research Center, USA Universit´e des Antilles et de la Guyane, France Aalto University, Finland Eindhoven University of Technology, The Netherlands University of Lyon, INSA Lyon, France University of Waikato, New Zealand IIIA-CSIC, Spain University of Helsinki, Finland CNRS, France Universidade do Porto, Portugal Aalto University, Finland Kyushu University, Japan University of Antwerp, Belgium University of Helsinki, Finland Yahoo! Research, Spain Kyoto University, Japan Nanjing University, China

Additional Reviewers Ceci, Michelangelo De Knijf, Jeroen Fonseca, Nuno Girschick, Tobias Heinim¨ aki, Teemu Kosina, Petr

Koskela, Markus Kuboyama, Tetsuji Li, Nan Loglisci, Corrado Oliveira, Marcia Onta˜ no´n, Santiago

Organization

Plantevit, Marc Sakamoto, Hiroshi Schietgat, Leander Schmidt, Jana Schmitt, Constanze Seeland, Madeleine

Slavkov, Ivica Sluban, Borut Tashkova, Katerina Vreeken, Jilles Zenko, Bernard Znidarsic, Martin

IX

Table of Contents

On the Expressive Power of Deep Architectures . . . . . . . . . . . . . . . . . . . . . . Yoshua Bengio and Olivier Delalleau

1

Learning from Label Preferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Eyke H¨ ullermeier and Johannes F¨ urnkranz

2

Information Distance and Its Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ming Li

18

Models for Autonomously Motivated Exploration in Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Peter Auer, Shiau Hong Lim, and Chris Watkins

29

Optimal Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jorma Rissanen

30

Monotone Instance Ranking with MIRA . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nicola Barile and Ad Feelders

31

MOA-TweetReader : Real-Time Analysis in Twitter Streaming Data . . . . Albert Bifet, Geoﬀrey Holmes, and Bernhard Pfahringer

46

Application of Semantic Kernels to Literature-Based Gene Function Annotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mathieu Blondel, Kazuhiro Seki, and Kuniaki Uehara “Tell Me More”: Finding Related Items from User Provided Feedback. . . Jeroen De Knijf, Anthony Liekens, and Bart Goethals MEI: Mutual Enhanced Inﬁnite Generative Model for Simultaneous Community and Topic Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dongsheng Duan, Yuhua Li, Ruixuan Li, Zhengding Lu, and Aiming Wen A Methodology for Mining Document-Enriched Heterogeneous Information Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Miha Grˇcar and Nada Lavraˇc Multiple Hypothesis Testing in Pattern Discovery . . . . . . . . . . . . . . . . . . . . Sami Hanhij¨ arvi A Parameter-Free Method for Discovering Generalized Clusters in a Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hiroshi Hirai, Bin-Hui Chou, and Einoshin Suzuki

61 76

91

107 122

135

XII

Table of Contents

Detecting Anti-majority Opinionists Using Value-Weighted Mixture Voter Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Masahiro Kimura, Kazumi Saito, Kouzou Ohara, and Hiroshi Motoda Using Ontologies in Semantic Data Mining with SEGS and g-SEGS . . . . Nada Lavraˇc, Anˇze Vavpetiˇc, Larisa Soldatova, Igor Trajkovski, and Petra Kralj Novak Mining Classiﬁcation Rules without Support: an Anti-monotone Property of Jaccard Measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yannick Le Bras, Philippe Lenca, and St´ephane Lallich

150 165

179

Bootstrapping Parameter Estimation in Dynamic Systems . . . . . . . . . . . . Huma Lodhi and David Gilbert

194

Network Eﬀects on Tweeting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jake T. Lussier and Nitesh V. Chawla

209

Context-Aware Personal Route Recognition . . . . . . . . . . . . . . . . . . . . . . . . . ˇ Oleksiy Mazhelis, Indr˙e Zliobait˙ e, and Mykola Pechenizkiy

221

Scalable Detection of Frequent Substrings by Grammar-Based Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Masaya Nakahara, Shirou Maruyama, Tetsuji Kuboyama, and Hiroshi Sakamoto

236

A Statistical Model for Topically Segmented Documents . . . . . . . . . . . . . . Giovanni Ponti, Andrea Tagarelli, and George Karypis

247

Predicting Structured Outputs k -Nearest Neighbours Method . . . . . . . . . Mitja Pugelj and Saˇso Dˇzeroski

262

The Augmented Itemset Tree: A Data Structure for Online Maximum Frequent Pattern Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jana Schmidt and Stefan Kramer Word Clouds for Eﬃcient Document Labeling . . . . . . . . . . . . . . . . . . . . . . . Christin Seifert, Eva Ulbrich, and Michael Granitzer Global and Local Spatial Autocorrelation in Predictive Clustering Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Daniela Stojanova, Michelangelo Ceci, Annalisa Appice, Donato Malerba, and Saˇso Dˇzeroski

277 292

307

Rule Stacking: An Approach for Compressing an Ensemble of Rule Sets into a Single Classiﬁer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jan-Nikolas Sulzmann and Johannes F¨ urnkranz

323

Graph Clustering Based on Optimization of a Macroscopic Structure of Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yuta Taniguchi and Daisuke Ikeda

335

Table of Contents

Modeling the Temperature of Hot Rolled Steel Plate with Semi-supervised Learning Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Henna Tiensuu, Ilmari Juutilainen, and Juha R¨ oning

XIII

351

Controlled Permutations for Testing Adaptive Classiﬁers . . . . . . . . . . . . . . ˇ Indr˙e Zliobait˙ e

365

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

381

On the Expressive Power of Deep Architectures Yoshua Bengio and Olivier Delalleau Dept. IRO, Universit´e de Montr´eal. Montr´eal (QC), H3C 3J7, Canada

Abstract. Deep architectures are families of functions corresponding to deep circuits. Deep Learning algorithms are based on parametrizing such circuits and tuning their parameters so as to approximately optimize some training objective. Whereas it was thought too diﬃcult to train deep architectures, several successful algorithms have been proposed in recent years. We review some of the theoretical motivations for deep architectures, as well as some of their practical successes, and propose directions of investigations to address some of the remaining challenges.

The full version of this paper is published in the Proceedings of the 22nd International Conference on Algorithmic Learning Theory, Lecture Notes in Artiﬁcial Intelligence Vol. 6925.

T. Elomaa, J. Hollm´ en, and H. Mannila (Eds.): DS 2011, LNCS 6926, p. 1, 2011. c Springer-Verlag Berlin Heidelberg 2011

Learning from Label Preferences Eyke H¨ ullermeier1 and Johannes F¨ urnkranz2 1

2

Philipps-Universit¨ at Marburg, Germany [email protected] Technische Universit¨ at Darmstadt, Germany [email protected]

Abstract. In this paper, we review the framework of learning (from) label preferences, a particular instance of preference learning. Following an introduction to the learning setting, we particularly focus on our own work, which addresses this problem via the learning by pairwise comparison paradigm. From a machine learning point of view, learning by pairwise comparison is especially appealing as it decomposes a possibly complex prediction problem into a certain number of learning problems of the simplest type, namely binary classiﬁcation. We also discuss how a number of common machine learning tasks, such as multi-label classiﬁcation, hierarchical classiﬁcation or ordinal classiﬁcation, may be addressed within the framework of learning from label preferences. We also brieﬂy address theoretical questions as well as algorithmic and complexity issues.

1

Introduction

Preference learning is a recent addition to the suite of learning tasks in machine learning. In preference learning, training information is typically not given in the form of scalar outputs (like in classiﬁcation and regression), but instead in the form of pairwise comparisons expressing preferences between diﬀerent objects. One can distinguish learning from object preferences, where the training data is given in the form of pairwise comparisons between objects, and learning from label preferences, where the training data is given in the form of pairwise comparisons between labels that are attached to the objects. In the former case, a common performance task is to rank a new set of objects (object ranking), whereas in the latter case, the performance task is to rank the set of labels for a new object (label ranking). Besides, the training information may also be given in the form of (ordinal) preference degrees attached to the objects, indicating an absolute (as opposed to a relative/comparative) assessment. If the task is to rank a new set of objects according to their preference degrees, we also speak of instance ranking. Note that this task is diﬀerent from ordinal classiﬁcation, because the goal is to predict a correct ordering of an entire set of objects instead of correct (ordinal) utility degrees for individual objects.

Large parts of this paper are based on [18] and [19].

T. Elomaa, J. Hollm´ en, and H. Mannila (Eds.): DS 2011, LNCS 6926, pp. 2–17, 2011. c Springer-Verlag Berlin Heidelberg 2011

Learning from Label Preferences

3

Given: – a set of training instances {x | = 1, 2, . . . , n} ⊆ X (each instance typically though not necessarily represented by a feature vector) – a set of labels Y = {yi | i = 1, 2, . . . , k} – for each training instance x : a set of pairwise preferences of the form yi x yj Find: – a ranking function that maps any x ∈ X to a ranking x of Y (permutation πx ∈ S k ) Performance measures: – ranking error (e.g., based on rank correlation measures) comparing predicted ranking with target ranking – position error comparing predicted ranking with a target label

Fig. 1. Label ranking

In the remainder of the paper, we focus on the task of label ranking, and, in particular, on our own work in this area. A thorough snapshot of the state-ofthe-art in preference learning along with several review and survey chapters can be found in [17]. A survey on object ranking can be found in [33], a survey on label ranking in [48]. Instance ranking has been discussed in [21].

2

Label Ranking

In label ranking, we assume to be given an instance space X and a ﬁnite set of labels Y = {y1 , y2 , . . . , yk }. The goal is to learn a “label ranker” in the form of an X → SY mapping, where the output space SY is given by the set of all total orders (permutations) of the set of labels Y (the notation is leaned on the common notation Sk for the symmetric group of order k). Thus, label ranking can be seen as a generalization of conventional classiﬁcation, where a complete ranking yπx−1 (1) x yπx−1 (2) x . . . x yπx−1 (k) is associated with an instance x instead of only a single class label. Here, πx is a permutation of {1, 2, . . . , k} such that πx (i) is the position of label yi in the ranking associated with x. The training data T of a label ranker typically consists of a set of pairwise preferences of the form yi x yj , suggesting that, for instance x, yi is preferred to yj . In other words, an “observation” consists of an instance x and an ordered pair of labels (yi , yj ). The label ranking problem is summarized in Fig. 1. This learning scenario has a large number of practical applications. For example, it is relevant for the prediction of every sort of ordering of a ﬁxed set of

4

E. H¨ ullermeier and J. F¨ urnkranz

elements, such as the preferential order of a ﬁxed set of products (e.g., diﬀerent types of holiday apartments) based on demographic properties of a person, or the ordering of a set of genes according to their expression level (as measured by microarray analysis) based on features of their phylogenetic proﬁle [4]. Another application scenario is meta-learning, where the task is to rank learning algorithms according to their suitability for a new dataset, based on the characteristics of this dataset [7]. Finally, every preference statement in the wellknown CP-nets approach [5], a qualitative graphical representation that reﬂects conditional dependence and independence of preferences under a ceteris paribus interpretation, formally corresponds to a label ranking. To measure the predictive performance of a label ranker, a loss function on rankings is needed. In principle, any distance or correlation measure on rankings (permutations) can be used for that purpose. For example Kendall’s tau counts the number of pairs of labels which are incorrectly ordered (i.e., the number of label pairs yi and yj such that yi precedes yj in the predicted ranking although yj is actually preferred to yi ), or Spearman’s rank correlation measures the sum of the squared deviations of the predicted rank from the true rank of each label. Apart from this type of ranking loss, which compares a predicted ranking with a given target ranking, it is also possible to compare a predicted ranking with a single class label. For example, if this class label is the target one is looking for, then it makes sense to evaluate a predicted ranking by the position it assigns to the label; in [30], this type of error (measuring the distance of the assigned position from the top-rank) is called the position error. A general survey of label ranking can be found in [48]. In the remainder of this paper, we speciﬁcally focus on approaches which are based on the idea of learning by pairwise comparison, i.e., of decomposing the original problem into a set of smaller binary classiﬁcation problems.

3

Label Ranking by Pairwise Comparison

The idea of learning by pairwise comparison (LPC), or simply pairwise learning, has been explored quite extensively for conventional classiﬁcation, where it is known under a variety of names such as all pairs, 1-vs-1, or round robin learning. Here, it is used as a special binarization technique, that is, to decompose a polytomous classiﬁcation problem into a set of pairwise problems, thereby making multiclass problems amenable to binary classiﬁcation methods. Motivated by its successful use for classiﬁcation as well as its intuitive appeal from a preference and decision making perspective, the LPC approach has been extended to diﬀerent types of preference learning and ranking problems in recent years, some of which will be reviewed in subsequent sections of this paper. 3.1

Pairwise Classification

The use of the pairwise approach to preference learning is motivated by its successful application in conventional classiﬁcation. As a special type of binary

Learning from Label Preferences

(a) One-vs-all classification transforms each k-class problem into k binary problems, one for each class, where each of these problems uses the examples of its class as the positive examples (here o), and all other examples as negatives.

5

(b) Pairwise classification transforms each k-class problem into k(k − 1)/2 binary problems, one for each pair of classes (here o and x) ignoring the examples of all other classes.

Fig. 2. Decomposition techniques for multi-class classiﬁcation

decomposition technique, it allows one to tackle multiclass problems with binary classiﬁers. The key idea is to transform a k-class problem involving classes Y = {y1 , y2 , . . . , yk } into k(k − 1)/2 binary problems, one for each pair of classes. More speciﬁcally, a separate model (base learner) Mi,j is trained for each pair of labels (yi , yj ) ∈ Y × Y, 1 ≤ i < j ≤ k, using the examples from these two classes as their training set; thus, a total number of k(k − 1)/2 models is needed. Mi,j is intended to separate the objects with label yi from those having label yj . At classiﬁcation time, a query instance x ∈ X is submitted to all models Mi,j , and their predictions Mi,j (x) are combined into an overall prediction. In the simplest case, each prediction Mi,j (x) is interpreted as a vote for either yi or yj , and the label with the highest number of votes is proposed as a ﬁnal prediction. In comparison to alternative decomposition techniques, such as the one-vsall approach which learns one model for each label, the pairwise decomposition facilitates eﬀective learning as it leads to maximally simple problems. In particular, the pairwise problems are computationally less complex, since each of them contains fewer training examples (because all examples that do not belong to either of the two classes are ignored). Perhaps even more importantly, these problems typically have simpler decision boundaries. This is illustrated in the example shown in Fig. 2, where each pair of classes can be separated with a linear decision boundary, while more complex functions are required to separate each class from all other classes. Evidence supporting the conjecture that the decision boundaries of the binary problems are indeed simpler can also be found in practical applications: In [35], it was observed that the classes of a digit

6

E. H¨ ullermeier and J. F¨ urnkranz

recognition task were pairwise linearly separable, while the corresponding one-vsall task was not amenable to single-layer networks. Similarly, in [25] the authors obtained a larger advantage of pairwise classiﬁcation over one-vs-all for support vector machines with a linear kernel than for support vector machines with a non-linear kernel. The basic idea of pairwise classiﬁcation is fairly well-known from the literature. It has been used in the areas of statistics [6,13], neural networks [34,35,45,40], support vector machines [46,24,37,25], and others. We refer to [14] for a brief survey of the literature on this topic. 3.2

Label Ranking by Pairwise Comparisons

Pairwise classiﬁcation can be extended to the problem of learning from label preferences in a natural way [16]. To this end, a preference (order) information of the form yr x ys is turned into a training example (x, z) for the learner Mi,j , where i = min(r, s) and j = max(r, s). Moreover, z = 1 if r < s and z = 0 otherwise. Thus, Mi,j is intended to learn the mapping that outputs 1 if yi x yj and 0 if yj x yi : 1 if yi x yj x → . (1) 0 if yj x yi The model is trained with all examples x for which either yi x yj or yj x yi is known. Examples for which nothing is known about the preference between yi and yj are ignored. The mapping (1) can be realized by any binary classiﬁer. Alternatively, one may also employ base classiﬁers that map into the unit interval [0, 1] instead of {0, 1}, and thereby assign a valued preference relation Rx to every (query) instance x ∈ X : Mi,j (x) if i < j (2) Rx (yi , yj ) = 1 − Mji (x) if i > j for all yi = yj ∈ Y. The output of a [0, 1]-valued classiﬁer can usually be interpreted as a probability or, more generally, a kind of conﬁdence in the classiﬁcation: the closer the output of Mi,j to 1, the stronger the preference yi x yj is supported. 3.3

Combining Predicted Preferences into a Ranking

Given a predicted preference relation Rx for an instance x, the next question is how to derive an associated ranking. This question is non-trivial, since a relation Rx does not always suggest a unique ranking in an unequivocal way. For example, the learned preference relation is not necessarily transitive. In fact, the problem of inducing a ranking from a (valued) preference relation has received a lot of attention in several research ﬁelds, e.g., in fuzzy preference modeling and (multi-attribute) decision making [11]. In the context of pairwise classiﬁcation

Learning from Label Preferences

7

and preference learning, several studies have empirically compared diﬀerent ways of combining the predictions of individual classiﬁers [49,2,29,15]. A simple though eﬀective strategy is a generalization of the aforementioned voting strategy: each alternative yi is evaluated by the sum of (weighted) votes S(yi ) = Rx (yi , yj ), (3) j=i

and all labels are then ordered according to these evaluations, i.e., such that (yi x yj ) ⇒ (S(yi ) ≥ S(yj )).

(4)

Even though this ranking procedure may appear rather ad-hoc at ﬁrst sight, it does have a theoretical justiﬁcation (cf. Section 5).

4

LPC for Generalized Classification Problems

It has been observed by several authors [23,16,10] that, in addition to classiﬁcation, many learning problems, such as multilabel classiﬁcation, ordered classiﬁcation, or ranking may be formulated in terms of label preferences. In this section, we summarize work on using pairwise learning to address such problems. 4.1

Multilabel Classification

Multilabel classiﬁcation refers to the task of learning a function that maps instances x ∈ X to label subsets Px ⊂ Y, where Y = {y1 , y2 , . . . , yk } is a ﬁnite set of predeﬁned labels, typically with a small to moderate number of alternatives. Thus, in contrast to multiclass learning, alternatives are not assumed to be mutually exclusive such that multiple labels may be associated with a single instance. The set of labels Px are called relevant for the given instance, the set Nx = Y \ Px are the irrelevant labels. In conventional label ranking, a training example typically consists of an instance x ∈ X , represented in terms of a ﬁxed set of features, and a set of pairwise preferences over labels Rx ⊂ Y × Y, where (y, y ) ∈ Rx is interpreted as y x y . In multilabel classiﬁcation, the training information consists of a set Px of relevant labels and, implicitly, a set Nx = Y \ Px of irrelevant labels. The idea of applying methods for (pairwise) label ranking in the context of multilabel classiﬁcation is based on the observation that this information can be expressed equivalently in terms of a set of preferences (cf. Fig. 3 (a)): ˆ x = {(y, y ) | y ∈ Px ∧ y ∈ Nx } R

(5)

In fact, this representation is in a sense even more ﬂexible than the original one; for example, it easily remains applicable in the case where the relevance of some labels is unknown (and hence Nx Y \ Px ). The preferences (5) can be used to train a pairwise label ranker, which is then able to predict a ranking over all possible labels of a new, unseen example.

8

E. H¨ ullermeier and J. F¨ urnkranz

(a) the set of preferences (b) introducing a calibra- (c) the set of preferences representing a multilabel tion label y0 that separates representing a calibrated laP and N classiﬁcation problem bel ranking problem

(d) at prediction time, the calibration label y0 indicates the split into ˆ and labels that are predicted labels that are predicted relevant (P) ˆ irrelevant (N ) Fig. 3. Calibrated Label Ranking

Note, however, that a ranking, while determining an order of the labels, does actually not deﬁne a partitioning into subsets of relevant and irrelevant labels. A natural way to obtain such a partitioning as additional information is to ﬁnd an appropriate split-point t in the ranking, suggesting that the ﬁrst t labels in the ranking are relevant while the remaining ones are irrelevant. A “calibrated” ranking of that kind nicely combines two types of prediction, namely a label ranking and a multilabel classiﬁcation [20]. From a ranking point of view, it covers additional information about absolute preferences; from the point of view of multilabel classiﬁcation, it oﬀers additional order information, i.e., information about the relative preferences within the two sets of relevant and irrelevant labels. As none of the previous proposals for determining such a split-point [50] allows one to adjust the thresholds for each individual example, we proposed to incorporate the split-point into the learning process [20]. This was achieved by introducing an artiﬁcial (neutral) label which is associated with the split-point and thus calibrates the ranking: For each training instance, this label is preferred to all irrelevant labels, but is less preferable than all relevant labels; see Fig. 3 (b). A calibrated label ranker trained on the enhanced set of preferences (Fig. 3 (c)) is then able to predict a ranking of all labels, including the artificial one. The position of this label indicates where the ranking has to be split into a relevant and an irrelevant part. Experiments have shown that this approach outperforms standard methods for multilabel classiﬁcation, despite a slight tendency to underestimate the number of relevant labels.

Learning from Label Preferences

4.2

9

Ordered and Hierarchical Classification

Ordered classification and hierarchical classification are problems in which the target label set has an inherent structure. In ordered classiﬁcation, this structure is a total order, such as small < medium < large. In hierarchical problems, the structure is a partial order in the form of a hierarchy, typically deﬁned by various subconcept/superconcept relations; for example, Hessen < Germany < Europe and Bayern < Germany < Europe (while Hessen and Bayern are incomparable, i.e., neither Hessen < Bayern nor Bayern < Hessen). The use of conventional loss functions, such as the 0/1 loss, is obviously questionable in the context of ordered and hierarchical classiﬁcation, as it does not take the relation between class labels into account. If small is the true class, for instance, then medium is a better prediction than large, despite the fact that both are incorrect. An obvious idea, then, is to express this type of information in the form of preferences on labels. Within the framework of LPC, this can be done by associating a training instance with all pairwise preferences that can be inferred from the label structure. For example, if we know that an instance is of class small, we not only know that the label small is preferred to all other labels, but we can also infer that medium would be a better classiﬁcation than large. In other words, the set of training examples for which it is known that medium large could be enriched by instances from the class small. Similarly, if we know that an object belongs to the class Hessen, we can infer that the label Rheinland-Pfalz would be preferred over Lower Austria, because the former is also a German state, while the latter is in a diﬀerent country. One idea is to directly add such inferred preferences to the pairwise training data. Interestingly, in [22], it was shown that this method may be viewed as a generalization of the so-called Pachinko-machine classiﬁer [36], which contains one binary classiﬁer for each internal node of the label hierarchy. However, the experimental results in this paper suggest that this approach does not improve the performance of the conventional pairwise classiﬁer. There is a number of possible reasons and explanations for this. Notably, enriching the training data comes with a loss of a key advantage of the pairwise approach, namely the simplicity of the binary problems and the decision boundaries of the binary classiﬁers. The more inferred preferences are added, the more complex the decision boundary of a single binary classiﬁer will become, eventually approaching the complex decision boundaries of a one-vs-all classiﬁer. Moreover, it seems that in many hierarchical and ordered classiﬁcation problems, the structure on the labels is not so clearly reﬂected in the topology of the instance space. This means that examples that are “close” in label space are not necessarily neighbored in instance space. This aspect has been investigated in more detail in [27]. This work also aimed at answering the question to what extent existing techniques and learning algorithms for ordered classiﬁcation are able to exploit order information, and which properties of these techniques are important in this regard. The main conclusions that could be drawn from this study are as follows: Most learning techniques for

10

E. H¨ ullermeier and J. F¨ urnkranz

ordered classiﬁcation are indeed able to exploit order information about classes if such information is present, which is often the case though not always. An important factor in this regard is the ﬂexibility of the learner. Roughly speaking, the less ﬂexible a learner is, the more it beneﬁts from an ordinal structure. Interestingly enough, it was found that pairwise classiﬁcation is fully competitive to other meta-learning techniques speciﬁcally designed for ordered classiﬁcation problems [12]. This result is surprising, since pairwise classiﬁcation, in its original form, does not explicitly exploit an ordinal structure (and, compared to the other techniques, even uses a smaller amount of training information in terms of the total number of training examples). However, by training only on pairs of classes, it is trivially consistent with each ordinal structure. In a sense, one can argue that it exploits ordinal structure in an implicit way whenever this is possible, but as its binary problems are not explicitly tailored toward the assumption of an ordinal structure, it does not deteriorate when this assumption is invalid.

5

Theoretical Foundations

Despite their intuitive appeal and practical success, it is of course important to justify pairwise learning methods from a theoretical point of view. In particular, one may wonder whether LPC is provably able to produce predictions that are optimal in the sense of minimizing (the expectation of) a given loss function. Corresponding results have recently been derived, not only for classiﬁcation (Section 5.1) but also for ranking (Sections 5.2 and 5.3). Apart from further technical assumptions, which are not detailed here, these results typically rely on the idealized assumption that the prediction of a pairwise model, Mi,j (x), can be interpreted as a probability, for example the probability that, in the label ranking associated with x, label yi precedes label yj . Needless to say, assumptions of that kind are not always easy to satisfy in practice, especially because probability estimation is a challenging problem potentially more diﬃcult than classiﬁcation. Besides, the pairwise approach suﬀers from an inherent limitation, which is sometimes called the “non-competence” problem in the literature. Roughly speaking, this problem is caused by the fact that a pairwise model is only trained on parts of the instance space and, therefore, possibly not competent for inputs coming from other parts. In conventional classiﬁcation, for example, a pairwise model Mi,j is only trained on examples from classes yi and yj and, therefore, arguably non-competent for classifying instances from other classes. Several proposals for addressing this problem can be found in the literature. In [41] it was proposed to combine the pairwise models Mi,j with a separate set of models Mij,Y¯i,j , which predict whether an example belongs to the classes yi or yj , or to the remaining classes Y¯i,j = Y \ {yi , yj }. A similar proposal is to learn ternary models Mi,j,Y¯i,j , which directly discriminate between the three options yi , yj , or none of the two [3]. Both approaches have to sacriﬁce one of the key advantages of the pairwise approach, namely the simplicity of the learned binary models.

Learning from Label Preferences

5.1

11

Classification

Despite the existence of more sophisticated methods, such as pairwise coupling [24,49], the most popular strategy for aggregating the predictions of pairwise classiﬁers is “voting”. In binary voting, each classiﬁer Mi,j can give a “vote” for either yi or yj . In weighted voting, it may split its vote among the two classes, e.g., according to its probability estimate. Having queried all models, the class with the highest number of votes (sum of weighted votes) is eventually predicted. Empirically, weighted voting is known to perform very well. A theoretical justiﬁcation for this performance has been derived in [32]. Under some technical assumptions, it was shown there that weighted voting may be considered as an approximation of a generalized voting strategy, called adaptive voting, which in turn was shown to be optimal in the sense of yielding a maximum posterior probability (MAP) prediction of the true class. Besides, weighted voting appears to be even more robust than adaptive voting in the sense of being less sensitive toward violations of the underlying model assumptions. Moreover, it was shown that the pairwise approach to learning, at least in a slightly generalized form, is able to produce Bayes-optimal decisions in the context of conventional classiﬁcation [47]. 5.2

Label Ranking

In the context of label ranking, it was shown that many standard loss functions on rankings can be minimized in expectation [31]. For example, under some technical assumptions, straight-forward weighted voting is a risk minimizer for the sum of squared rank distances as a loss function (thus, it maximizes the expected Spearman rank correlation between the true and the predicted label ranking). Replacing weighted voting by another aggregation strategy, one can also minimize the number of pairwise inversions (i.e., maximize Kendall’s tau); the aggregation problem itself, however, is NP-hard. On the other hand, there are also loss functions that cannot be minimized by LPC. Roughly speaking, this is due to a loss of information caused by decomposing the original problem into a set of pairwise problems. Examples include the Spearman footrule and Ulam’s distance [30]. 5.3

Position Error

It may also be reasonable to compare a predicted ranking with a single target label instead of target ranking. For example, given a predicted label ranking, the position error is deﬁned by the position on which the true class label is found or, stated diﬀerently, the number of labels that are ranked ahead of this target label. In a normalized form, this measure directly generalizes the conventional 0/1-loss for classiﬁcation, assuming a value of 0 (1) if the target label is put on the ﬁrst (last) position. The problem of predicting a ranking that minimizes the expected position loss can again be solved in a theoretically optimal way by LPC [30].

12

E. H¨ ullermeier and J. F¨ urnkranz

Practically, it was shown that the problem can be reduced to an iterated classiﬁcation problem, which in turn can be solved eﬀectively through a procedure called empirical conditioning. This procedure amounts to iteratively predicting a label and re-training the classiﬁer on the remaining labels. While this is practically infeasible in the general case (essentially one needs to train one classiﬁer for each label subset), it can be realized eﬃciently by means of LPC. This is because, in the pairwise approach, re-training of the classiﬁers is not necessary; instead, only the aggregation phase needs to be changed [30].

6

Complexity

At ﬁrst sight, it seems that LPC is very ineﬃcient for high numbers of labels because one has to train a quadratic number of classiﬁers. However, a closer look reveals that this is often outweighed by a positive eﬀect, namely that the individual problems are much smaller. In fact, an ensemble of pairwise models can often be trained much more eﬃciently than a single classiﬁer, even when both have the same total number of training examples. In particular, this holds true for expensive learning algorithms whose time complexity is super-linear in the number of training examples. Thus, the key problem of LPC is typically not the training time, but instead the prediction time and storage capacity. In the following, we will recapitulate some important results concerning these problems. 6.1

Training Time

For the pairwise classiﬁcation scenario, it is known that even though the number of binary classiﬁers is quadratic in the number of labels, their joint training time is only O(k · n), i.e., linear in the number labels [14]. The reason is that the individual training sets are much smaller because each of the n examples only occurs in k − 1 diﬀerent training sets. This distribution of the training eﬀort on a large number of comparably smaller problem increases the advantage in particular for expensive classiﬁers with a super-linear time complexity. Obviously, these results also hold for ordered and hierarchical classiﬁcation. For multilabel classiﬁcation [20], the crucial factor determining the eﬃciency of the approach is the average number d of labels per training example (which is often small in comparison to the total number of labels). The training complexity in this case is O(d · k · n) = O(k · l) when l is the total number of labels in the training set. In the worst case, when all training examples are associated with a complete ranking of all labels, the training complexity is quadratic in k [31]. 6.2

Prediction Time

A more interesting problem is the eﬃciency at prediction time. In principle, one has to query a quadratic number of classiﬁers in order to derive a ﬁnal ranking of the classes. However, when one is only interested in classiﬁcation, it is not necessary to query all classiﬁers in order to determine the winning class.

Learning from Label Preferences

13

For example, if one class has received more votes than every other class can possibly achieve in their remaining evaluations, this class can be safely predicted without querying the remaining classiﬁers. The QWeighted algorithm [42] tries to enforce this situation by always focusing on the class that has lost the least amount of voting mass. Experiments showed that QWeighted has an average runtime of O(k ·log k) instead of the O(k 2 ) that would be required for computing the same prediction with all evaluations. Because it nevertheless produces the same predictions as regular weighted voting and thus has the same theoretical guarantees, it is preferred to algorithms like pairwise DAGs [44], which only approximate the correct prediction. The algorithm can also be generalized to multilabel prediction [39] and to ternary error-correcting output codes [43]. 6.3

Memory Requirements

Even if training is quite eﬃcient, and classiﬁcation can be handled without the need to query all classiﬁers, we still have to store all k ·(k − 1)/2 binary classiﬁers because each classiﬁer will be needed for some examples (unless some labels are never predicted). For example, we have recently tackled a large-scale real-world text categorization problem, namely the annotation of the EUR-Lex database of legal documents of the European Union with labels that are taken from the EUROVOC ontology [38]. This multilabel classiﬁcation task involved around 20,000 documents, each of which was labeled with about 5 out of 4000 possible labels. The key problem that had to be solved for this task was that the ensemble of almost 8,000,000 binary classiﬁers (perceptrons) that were trained for tackling this task could no longer be kept in main memory. The problem was solved by resorting to the dual representation of the perceptron, which reduced the total number of weights that had to be stored at the expense of a somewhat higher classiﬁcation time. This made the pairwise ranking approach feasible for problems of this size. This solution, however, is only applicable to classiﬁers that can re-formulate their hypothesis as a linear combination of the input examples, such as perceptrons or SVMs. For concept descriptions with varying sizes, such as rule sets or decision trees, one can expect that the learned theories for the pairwise classiﬁers are much smaller than the theories for larger problems such as those of a one-vs-all classiﬁer. However, it is unclear whether these savings on individual theories can compensate for the higher number of classiﬁers that have to be stored. Moreover, a general solution not restricted to any speciﬁc classiﬁer is still an open research problem. Presumably, one will have to resort to ﬁxed approximation techniques, which allow that some classiﬁers are not trained at all.

7

Conclusions and Outlook

This paper has reviewed the task of learning from label preferences, with a particular focus on learning by pairwise comparison (LPC). This paradigm has a natural motivation in the context of preference learning and goes hand in hand

14

E. H¨ ullermeier and J. F¨ urnkranz

with the relational approach to preference modeling. Roughly speaking, LPC learns a binary predicate for comparing two alternatives, which in turn can be seen as a basic building block of more complex decision making procedures. Eventually, complex prediction problems can thus be reduced to the solution of a set of “simple” binary classiﬁcation problems, which makes the LPC approach especially appealing from a machine learning point of view. It was shown that LPC can be used in a quite general way to solve diﬀerent types of preference learning problems. It disposes of sound theoretical foundations and has shown very strong performance in a number of empirical studies. Despite the high number of binary classiﬁers needed (quadratic in the number of class labels), the training time of the approach seems to be competitive with alternative approaches. Storing and querying such a large number of classiﬁers, however, is a more signiﬁcant problem, and an active research area. Besides, there are several other open questions and promising lines of research. From a practical point of view, for example, it would be interesting to develop a uniﬁed framework of LPC for label and object ranking. In such a framework, both the instances (e.g., users of a recommender system) and the labels/objects (e.g., the items to be purchased) can be described in terms of properties. While this can be achieved in a quite straightforward way for other approaches (see e.g., [1]), it is much less obvious for LPC, mainly because the set of “labels” may become very large and change from prediction to prediction. Another line of research concerns the prediction of preference relations more general than rankings, in particular relations which are not necessarily total (i.e., partial orders [9]) or not strict (i.e., allow for the indiﬀerence between alternatives). As an interesting point of departure for a generalization of this type we mention recent work on the learning of valued preference structures [28,26]. Instead of producing, in the ﬁrst step, a single binary relation Rx from which the ﬁnal prediction (e.g., a ranking) is then derived, the idea is to predict a complete preference structure consisting of three such relations: a strict preference relation, an indiﬀerence relation, and an incomparability relation. A structure of that kind conveys much more information which can then be used, amongst other things, for predicting generalized preferences such as weak or partial orders. Currently, we are focusing on adapting preference learning techniques to reinforcement learning tasks [8]. The key motivation for this approach derives from the observation that an agent typically needs to rank a number of available actions in a given situation. This can essentially be seen as a label ranking task, where the actions may be interpreted as labels that have to be ranked for a given state of the environment. Moreover, the numerical reward, which is the main training information in a reinforcement learning task, is often not naturally available. Instead, it may often be simpler or more convenient to compare pairs of actions. Acknowledgments. This research has been supported by the German Science Foundation (DFG). We would like to thank our collaborators Klaus Brinker, Weiwei Cheng, Eneldo Loza Menc´ıa, Sang-Hyeun Park, Jan Frederik Sima, and Stijn Vanderlooy.

Learning from Label Preferences

15

References 1. Aiolli, F., Sperduti, A.: A preference optimization based unifying framework for supervised learning problems. In: [17], pp. 19–42 2. Allwein, E.L., Schapire, R.E., Singer, Y.: Reducing multiclass to binary: A unifying approach for margin classiﬁers. Journal of Machine Learning Research 1, 113–141 (2000) 3. Angulo, C., Ruiz, F.J., Gonz´ alez, L., Ortega, J.A.: Multi-classiﬁcation by using tri-class SVM. Neural Processing Letters 23(1), 89–101 (2006) 4. Balasubramaniyan, R., H¨ ullermeier, E., Weskamp, N., K¨ amper, J.: Clustering of gene expression data using a local shape-based similarity measure. Bioinformatics 21(7), 1069–1077 (2005) 5. Boutilier, C., Brafman, R., Domshlak, C., Hoos, H., Poole, D.: CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. Journal of Artiﬁcial Intelligence Research 21, 135–191 (2004) 6. Bradley, R.A., Terry, M.E.: The rank analysis of incomplete block designs — I. The method of paired comparisons. Biometrika 39, 324–345 (1952) 7. Brazdil, P.B., Soares, C., da Costa, J.P.: Ranking learning algorithms: Using IBL and meta-learning on accuracy and time results. Machine Learning 50(3), 251–277 (2003) 8. Cheng, W., F¨ urnkranz, J., H¨ ullermeier, E., Park, S.-H.: Preference-based policy iteration: Leveraging preference learning for reinforcement learning. In: Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD 2011). Springer, Heidelberg (2011) 9. Cheng, W., Rademaker, M., De Beats, B., H¨ ullermeier, E.: Predicting partial orders: Ranking with abstention. In: Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD 2010), Barcelona, Spain (2010) 10. Dekel, O., Manning, C.D., Singer, Y.: Log-linear models for label ranking. In: Thrun, S., Saul, L.K., Sch¨ olkopf, B. (eds.) Advances in Neural Information Processing Systems (NIPS 2003), pp. 497–504. MIT Press, Cambridge (2003) 11. Fodor, J., Roubens, M.: Fuzzy Preference Modelling and Multicriteria Decision Support. Kluwer Academic Publishers, Dordrecht (1994) 12. Frank, E., Hall, M.: A simple approach to ordinal classiﬁcation. In: Flach, P.A., De Raedt, L. (eds.) ECML 2001. LNCS (LNAI), vol. 2167, pp. 145–156. Springer, Heidelberg (2001) 13. Friedman, J.H.: Another approach to polychotomous classiﬁcation. Technical report, Department of Statistics, Stanford University, Stanford, CA (1996) 14. F¨ urnkranz, J.: Round robin classiﬁcation. Journal of Machine Learning Research 2, 721–747 (2002) 15. F¨ urnkranz, J.: Round robin ensembles. Intelligent Data Analysis 7(5), 385–404 (2003) 16. F¨ urnkranz, J., H¨ ullermeier, E.: Pairwise preference learning and ranking. In: Lavraˇc, N., Gamberger, D., Todorovski, L., Blockeel, H. (eds.) ECML 2003. LNCS (LNAI), vol. 2837, pp. 145–156. Springer, Heidelberg (2003) 17. F¨ urnkranz, J., H¨ ullermeier, E. (eds.): Preference Learning. Springer, Heidelberg (2010) 18. F¨ urnkranz, J., H¨ ullermeier, E.: Preference learning: An introduction. In: [17], pp. 1–17

16

E. H¨ ullermeier and J. F¨ urnkranz

19. F¨ urnkranz, J., H¨ ullermeier, E.: Preference learning and ranking by pairwise comparison. In: [17], pp. 65–82 20. F¨ urnkranz, J., H¨ ullermeier, E., Loza Menc´ıa, E., Brinker, K.: Multilabel classiﬁcation via calibrated label ranking. Machine Learning 73(2), 133–153 (2008) 21. F¨ urnkranz, J., H¨ ullermeier, E.: Stijn Vanderlooy. Binary decomposition methods for multipartite ranking. In: Buntine, W.L., Grobelnik, M., Mladeni´c, D., ShaweTaylor, J. (eds.) Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD 2009), Bled, Slovenia, vol. Part I, pp. 359–374. Springer, Heidelberg (2009) 22. F¨ urnkranz, J., Sima, J.F.: On exploiting hierarchical label structure with pairwise classiﬁers. SIGKDD Explorations 12(2), 21–25 (2010); Special Issue on Mining Unexpected Results 23. Har-Peled, S., Roth, D., Zimak, D.: Constraint classiﬁcation: A new approach to multiclass classiﬁcation. In: Cesa-Bianchi, N., Numao, M., Reischuk, R. (eds.) ALT 2002. LNCS (LNAI), vol. 2533, pp. 365–379. Springer, Heidelberg (2002) 24. Hastie, T., Tibshirani, R.: Classiﬁcation by pairwise coupling. In: Jordan, M.I., Kearns, M.J., Solla, S.A. (eds.) Advances in Neural Information Processing Systems 10 (NIPS 1997), pp. 507–513. MIT Press, Cambridge (1998) 25. Hsu, C.-W., Lin, C.-J.: A comparison of methods for multi-class support vector machines. IEEE Transactions on Neural Networks 13(2), 415–425 (2002) 26. H¨ uhn, J., H¨ ullermeier, E.: FR3: A fuzzy rule learner for inducing reliable classiﬁers. IEEE Transactions on Fuzzy Systems (2008) (to appear) 27. H¨ uhn, J., H¨ ullermeier, E.: Is an ordinal class structure useful in classiﬁer learning? International Journal of Data Mining, Modelling, and Management 1(1), 45–67 (2008) 28. H¨ ullermeier, E., Brinker, K.: Learning valued preference structures for solving classiﬁcation problems. Fuzzy Sets and Systems 159(18), 2337–2352 (2008) 29. H¨ ullermeier, E., F¨ urnkranz, J.: Comparison of ranking procedures in pairwise preference learning. In: Proceedings of the 10th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU 2004), Perugia, Italy (2004) 30. H¨ ullermeier, E., F¨ urnkranz, J.: On predictive accuracy and risk minimization in pairwise label ranking. Journal of Computer and System Sciences 76(1), 49–62 (2010) 31. H¨ ullermeier, E., F¨ urnkranz, J., Cheng, W., Brinker, K.: Label ranking by learning pairwise preferences. Artiﬁcial Intelligence 172, 1897–1916 (2008) 32. H¨ ullermeier, E., Vanderlooy, S.: Combining predictions in pairwise classiﬁcation: An optimal adaptive voting strategy and its relation to weighted voting. Pattern Recognition (2009) (to appear) 33. Kamishima, T., Kazawa, H., Akaho, S.: A survey and empirical comparison of object ranking methods. In: [17], pp. 181–201 34. Knerr, S., Personnaz, L., Dreyfus, G.: Single-layer learning revisited: A stepwise procedure for building and training a neural network. In: Fogelman Souli´e, F., H´erault, J. (eds.) Neurocomputing: Algorithms, Architectures and Applications. NATO ASI Series, vol. F68, pp. 41–50. Springer, Heidelberg (1990) 35. Knerr, S., Personnaz, L., Dreyfus, G.: Handwritten digit recognition by neural networks with single-layer training. IEEE Transactions on Neural Networks 3(6), 962–968 (1992) 36. Koller, D., Sahami, M.: Hierarchically classifying documents using very few words. In: Proceedings of the 14th International Conference on Machine Learning (ICML 1997), Nashville, pp. 170–178 (1997)

Learning from Label Preferences

17

37. Kreßel, U.H.-G.: Pairwise classiﬁcation and support vector machines. In: Sch¨ olkopf, B., Burges, C.J.C., Smola, A.J. (eds.) Advances in Kernel Methods: Support Vector Learning, ch. 15, pp. 255–268. MIT Press, Cambridge (1999) 38. Loza Menc´ıa, E., F¨ urnkranz, J.: Eﬃcient pairwise multilabel classiﬁcation for largescale problems in the legal domain. In: Daelemans, W., Goethals, B., Morik, K. (eds.) ECML PKDD 2008, Part II. LNCS (LNAI), vol. 5212, pp. 50–65. Springer, Heidelberg (2008) 39. Loza Menc´ıa, E., Park, S.-H., F¨ urnkranz, J.: Eﬃcient voting prediction for pairwise multilabel classiﬁcation. In: Proceedings of the 17th European Symposium on Artiﬁcial Neural Networks (ESANN 2009), Bruges, Belgium, pp. 117–122. d-side publications (April 2009) 40. Lu, B.-L., Ito, M.: Task decomposition and module combination based on class relations: A modular neural network for pattern classiﬁcation. IEEE Transactions on Neural Networks 10(5), 1244–1256 (1999) 41. Moreira, M., Mayoraz, E.: Improved pairwise coupling classiﬁcation with correcting classiﬁers. In: N´edellec, C., Rouveirol, C. (eds.) ECML 1998. LNCS, vol. 1398, pp. 160–171. Springer, Heidelberg (1998) 42. Park, S.-H., F¨ urnkranz, J.: Eﬃcient pairwise classiﬁcation. In: Kok, J.N., Koronacki, J., Lopez de Mantaras, R., Matwin, S., Mladeniˇc, D., Skowron, A. (eds.) ECML 2007. LNCS (LNAI), vol. 4701, pp. 658–665. Springer, Heidelberg (2007) 43. Park, S.-H., F¨ urnkranz, J.: Eﬃcient prediction algorithms for binary decomposition techniques. Data Mining and Knowledge Discovery (to appear, 2011) 44. Platt, J.C., Cristianini, N., Shawe-Taylor, J.: Large margin DAGs for multiclass classiﬁcation. In: Solla, S.A., Leen, T.K., M¨ uller, K.-R. (eds.) Advances in Neural Information Processing Systems 12 (NIPS 1999), pp. 547–553. MIT Press, Cambridge (2000) 45. Price, D., Knerr, S., Personnaz, L., Dreyfus, G.: Pairwise neural network classiﬁers with probabilistic outputs. In: Tesauro, G., Touretzky, D., Leen, T. (eds.) Advances in Neural Information Processing Systems 7 (NIPS 1994), pp. 1109–1116. MIT Press, Cambridge (1995) 46. Schmidt, M.S., Gish, H.: Speaker identiﬁcation via support vector classiﬁers. In: Proceedings of the 21st IEEE International Conference Conference on Acoustics, Speech, and Signal Processing (ICASSP 1996), Atlanta, GA, pp. 105–108 (1996) 47. Sulzmann, J.-N., F¨ urnkranz, J., H¨ ullermeier, E.: On pairwise naive bayes classiﬁers. In: Kok, J.N., Koronacki, J., Lopez de Mantaras, R., Matwin, S., Mladeniˇc, D., Skowron, A. (eds.) ECML 2007. LNCS (LNAI), vol. 4701, pp. 371–381. Springer, Heidelberg (2007) 48. Vembu, S., G¨ artner, T.: Label ranking algorithms: A survey. In: [17], pp. 45–64 49. Wu, T.-F., Lin, C.-J., Weng, R.C.: Probability estimates for multi-class classiﬁcation by pairwise coupling. Journal of Machine Learning Research 5, 975–1005 (2004) 50. Yang, Y.: An evaluation of statistical approaches to text categorization. Information Retrieval 1, 69–90 (1999)

Information Distance and Its Extensions Ming Li School of Computer Science, University of Waterloo, Waterloo, Ont. N2L 3G1, Canada [email protected] http://www.cs.uwaterloo.ca/~ mli

Abstract. Consider, in the most general sense, the space of all information carrying objects: a book, an article, a name, a deﬁnition, a genome, a letter, an image, an email, a webpage, a Google query, an answer, a movie, a music score, a Facebook blog, a short message, or even an abstract concept. Over the past 20 years, we have been developing a general theory of information distance in this space and applications of this theory. The theory is object-independent and application-independent. The theory is also unique, in the sense that no other theory is “better”. During the past 10 years, such a theory has found many applications. Recently we have introduced two extensions to this theory concerning multiple objects and irrelevant information. This expository article will focus on explaining the main ideas behind this theory, especially these recent extensions, and their applications. We will also discuss some very preliminary applications.

1

Information in One Object

Kolmogorov complexity [24] may be thought as measuring information in one sequence. We brieﬂy deﬁne the concept here. Fix a universal Turing machine U . The Kolmogorov complexity of a binary string x condition to another binary string y, KU (x|y), is the length of the shortest (preﬁx-free) program for U that outputs x with input y. It can be shown that for a diﬀerent universal Turing machine U , for all x, y KU (x|y) = KU (x|y) + C, where the constant C depends only on U . Thus we can simply write KU (x|y) as K(x|y). We write K(x|), where is the empty string, as K(x). We call a string x random if K(x) ≥ |x|. We refer the readers to [24] for further details of Kolmogorov complexity and its rich applications in computer science and many other disciplines.

2

Information Distance between Two Objects

What would be a good departure point for deﬁning an “information distance” between two objects? In the early 1990’s, in [4], we have studied the energy cost T. Elomaa, J. Hollm´ en, and H. Mannila (Eds.): DS 2011, LNCS 6926, pp. 18–28, 2011. c Springer-Verlag Berlin Heidelberg 2011

Information Distance and Its Extensions

19

of conversion between two strings x and y. John von Neumann hypothesized that performing 1 bit of information processing costs 1KT of energy, where K is the Boltzmann’s constant and T is the room temperature. In the 1960’s, observing that reversible computations can be done for free, Rolf Landauer revised von Neumann’s proposal to hold only for irreversible computations. Starting from this von Neuman-Landauer principle, we proposed in [4] to use the minimum number of bits needed to convert between x and y to deﬁne their distance. Formally, with respect to a universal Turing machine U , the cost of conversion between x and y is deﬁned as: E(x, y) = min{|p| : U (x, p) = y, U (y, p) = x}

(1)

It is clear that E(x, y) ≤ K(x|y) + K(y|x). In [4] the following optimal result was obtained, modulo log(|x| + |y|): Theorem 1. E(x, y) = max{K(x|y), K(y|x)}. Thus, this has enabled us to deﬁne information distance between two sequences x and y as: Dmax (x, y) = max{K(x|y), K(y|x)}. This distance is shown to satisfy the basic distance requirements such as positivity, symmetricity, and triangle inequality. Furthermore, Dmax is “universal” in the following sense. We say a distance D is admissible if 2−D(x,y) ≤ 1. (2) y

Dmax (x, y) satisﬁes the above requirement because of Kraft’s Inequality (with the preﬁx-free version of Kolmogorov complexity). It was proved in [4] that for any admissible computable distance D, there is a constant c, for all x, y, Dmax (x, y) ≤ D(x, y) + c.

(3)

This means: if any such distance D discovers some similarity between x and y, so will Dmax . We thus say Dmax is universal. In the late 1990’s, we were doing whole genome phylogeny of prokaryotes. we ﬁrst thought about using information distance Dmax . However, it turns out that some closely related genomes have very diﬀerent sizes. For example, E. coli has about 4.6 million base pairs while H. infuenzae has about 1.8 million base pairs. Thus, H. inﬂuenzae genome would be closer to a more distant genome of similar length than with E. coli, under the Dmax distance. One solution would be to normalize everything to the [0,1]-interval. This concept was ﬁrst introduced in [19] and it was successfully applied to alignment free whole genome phylogeny [19], chain letter evolution history [5], and plagiarism detection [8].

20

M. Li

Dmax can be normalized [20] as: dmax (x, y) =

max{K(x|y), K(y|x)} . max{K(x), K(y)}

(4)

After the normalization, dmax still satisﬁes all the metric properties. However, unfortunately, the universality property 3 no longer holds [21]. Later, in Section 4, we will consider an alternative approach to avoid irrelavent information. Despite of the problem, this normalized theory has found many more applications beyond the initial applications in [19,5,8]. Especially, this methodology was adopted in [20] which formally deﬁned the dmax measure and repeated some experiments in [19] and [6]. Then many applications have followed. Here we are only able to list a small fraction of the applications: music classiﬁcation [9], parameter-free data mining paradigm [16], protein sequence classiﬁcation [17], protein structure comparison [18], heart rhythm data analysis [33], question and answering system [39], clustering [11], multiword expression linguistic analysis [7], software evolution and engineering [3,2], software design [34], software metrics and obfuscation [15] web page authorship, topic and domain identiﬁcation [32], phylogenetic reconstruction [1,30], hurricane risk assessment [13], SVM kernel for string classiﬁcation [12], ortholog detection [31], analyzing worms and network traﬃc [38], picture similarity [27], internet knowledge discovery [10], multi-document summarization [26], network structure and dynamic behavior [28], and gene expression dynamics in macrophase [29]. In [16], Keogh, Lonardi and Ratanamahatana demonstrated that the information distance compression approach was better than all 51 other methods for time series clustering proposed in the ﬁelds top conferences SIGKDD, SIGMOD, ICDM, ICDE, SSDB, VLDB, PKDD, and PAKDD. They have concluded that the power of method rests in the fact that the method is almost blind to the applications, avoiding overﬁtting or over tuning of parameters.

3

Informatin Distance among Many Objects

In many of these applications, for example [11], even when many objects are involved, only pair-wise information distance is computed. This has limited the applicability of this theory. Can we generalize the theory of information distance to more than two objects? The generalization has been proposed in [22,25] with only key proofs published in [25]. The paper [25] also provided the motivation from the data mining community and the ﬁrst application to this theory. This section will be based on [25] and the unpublished manuscript [22]. Similar to Formula 1, given strings x1 , . . . , xn , we can deﬁne the minimum amount of thermodynamic energy needed to convert from any xi to any xj , for all i, j, as: Em (x1 , . . . , xn ) = min{|p| : U (xi , p, j) = xj for all i, j}

(5)

Information Distance and Its Extensions

21

Clearly, Em (x1 , . . . , xn ) ≤

K(x1 x2 . . . xn |xi ) <

i

K(xi |xj ).

i,j

However, similar to the proof Theorem 1, the following theorem, which sets the basic foundation of an information distance among multiple objects and was proved by [22,25], gives a much tighter actually optimal bound. For completeness sake, we include here the proof which was ﬁrst published in [25]. Theorem 2. Modulo to a logarithmic additive term, Em (x1 , . . . , xn ) = max K(x1 x2 . . . xn |xi ). i

Proof. Suppose all binary strings are given in a list s1 , s2 , . . .. Deﬁne a set V as follows: a vector v = (i1 , i2 , . . . , in ) is in V if and only if K(si1 si2 . . . sin |sij ) ≤ K(x1 x2 . . . xn |xj ) for every j = 1, 2, . . . , n. Regard V as the vertices of a graph G = V, E. Two vertices u = (u1 , . . . , un ) and v = (v1 , . . . , vn ) are such that (u, v) ∈ E if and only if there is 1 ≤ j ≤ n such that uj = vj . For any given u ∈ V and 1 ≤ j ≤ n, by the deﬁnition of V , there are at most 2K(x1 x2 ...xn |xj ) vertices v ∈ V such vj = uj . Denote D = maxi K(x1 x2 . . . xn |xi ). The degree of the graph G is therefore bounded by 2K(x1 ...xn |xj ) ≤ n × 2D . j

It is known that a graph with degree d has a d-coloring. Therefore, G has a coloring V = V1 ∪V2 ∪. . .∪VK such that K ≤ n×2D . Clearly, (x1 , x2 , . . . , xn ) ∈ V . In order to compute xi from xj for any pair of i and j, a universal turing machine only needs to know which Vk contains (x1 , x2 , . . . , xn ). Such a program needs only log2 (n × 2D ) = D + log2 n bits. This ﬁnishes the proof. Em satisﬁes the usual metricity properties, straightforwardly. – Em (x1 , x2 , . . . , xn ) = 0 if all xi ’s are equal. – Em is obviously symmetric. – There is also a straightforward triangular inequality. Let X, Y be disjoint sets, then Em (X ∪ Y ) ≤ Em (X) + Em (Y ) + D(X, Y ), where D(X, Y ) = min{Dmax (x, y)|x ∈ X, y ∈ Y }. Note that without term D(X, Y ), the triangle inequality may not hold sometimes. The “universality” of Em was also stated in [25], but a proof was not included due to its staightforwardness. Here we include the proof from [22] for completeness. To establish the “universality” for Em , let us generalize the normalization condition of (2) to n elements. For S be any set of strings with size n or smaller, and let E(S) be a distance. E(S) is said to be “admissible” if for any string x 2−E(S) ≤ 1. (6) S:x∈S

22

M. Li

Theorem 3. Em is admissible. For any other admissible computable distance function E on n elements, there is a constant C such that for all x1 , . . . , xn , we have Em (x1 , . . . , xn ) ≤ E(x1 , . . . , xn ) + C. Proof. We ﬁrst show that Em is admissible. 2−Em (S) S:x∈S

≤

2−Dmax (x,S\{x})

S:x∈S

=

2−Dmax (x,S )

S

≤ 1.

The ﬁrst inequality is because Em (S) ≥ Dmax (x, S \ {x}) for any x ∈ S. The last inequality is because Dmax satisﬁes the density condition. Because E satisﬁes the admissible condition (6), by Theorem 4.1 in [24], there is a constant c such that for all S, cm(S|x) ≥ 2−E(S) . where m is the universal distribution. By Theorem 4.2 in [24], − log m(S|x) = K(S|x). Since this holds for any x ∈ S, we conclude that there is a constant c such that for all S Em (x1 , . . . , xn ) ≤ E(x1 , . . . , xn ) + O(1).

This ﬁnishes the proof of Em ’s universality.

Notice that Theorem 2 is a strong claim. Comparing to Theorem 1 where the saving is only linear, the saving here is quadratic. It is much better than applying Theorem 1 n2 times and sum up these program lengths. Thus this provides a theory guiding us to compute how much information a given n objects share. Such a theory was ﬁrst motivated and then used in the document summarization system in [25]. The following theorem is straightforward but it connects the Em theory to document summarization applications. Theorem 4. Modulo to a logarithmic additive term, min K(x1 . . . xn |xi ) ≤ Em (x1 , . . . , xn ) ≤ min i

i

Dmax (xi , xk ).

(7)

k=i

Given n objects, the left-hand side of the equation may be interpreted as the most comprehensive object that contains the most information about all of the others. The right-hand side of the equation may be interpreted as the most typical object that is similar to all of the others.

Information Distance and Its Extensions

23

Let us consider news items on the internet. If we wish to choose a news article that covers the most news, we can use the left hand side of Theorem 4. If we wish to look at a typical coverage of a single topic, we can use the righthand side of Theorem 4. We have subsequently and successfully applied this idea to product review summary in [25]. A recent paper [37] has tried to ﬁll in some more details of our theory of information distance among many objects.

4

Information Distance for Partial Matching

The information distance Dmax (x, y) has a problem of including all the irrelevant information in x and y. We have mentioned the case of E. coli and H. inf. genomes. There, we avoided the problem by normalization. However there are cases where even normalization fails. Consider a Question Answering (QA) system. The following three problems arise from our study of on such systems [21,39,40]. The ﬁrst problem is how to remove the impact of irrelevant information. Reiterating [39] and [21], consider the following QA example. “Which city is Lake Washington by?” There are several cities around Lake Washington: Seattle, Kirkland, and Bellevue, which are all good answers. The most popular answer Seattle contains overwhelmingly irrelevant information, not related to the lake. The dmax measure tends to choose a city with higher complexity (lower probability) such as Bellevue, preventing the QA system choosing Seattle. The second problem is: should an “information distance” really satisfy the triangle inequality? Imagine you and a stranger sitting next to you on the plane ﬁnd out you share a common interest, The “distance” between you the stranger gets suddenly much closer via the common interest! Consider a QA problem: The concept of “Marilyn Monroe” is pretty far from the concept “president”. However, Marilyn Monroe is very close to “JFK” and “JFK” is very close to the concept of “president”. In the academic world, this phenomenon is reﬂected by the “Erd¨ os number”. We all feel closely related via a third person Paul Erd¨ os. An information distance must reﬂect what “we think” to be similar. What “we think” to be similar apparently does not really satisfy triangle inequality. Fagin and Stockmeyer gave an example of partial pattern matching where the triangle-inequality does not hold [14]. Veltkamp puts it vividly in [36]: under partial matching, the distance between a man and a horse is larger than the sum of the distances between a man and a centaur and between a centaur and a horse, respectively. The QA problems often depend on partial information, and is in similar situation as partial pattern matching. Some objects are popular, such as Seattle mentioned above, and they are close to many other concepts. To model this phenomenon properly is our third problem. We need to relax the neighborhood constraints of Eq. 2 to allow some selected (very few) elements to have much denser neighborhoods. In fact, in the Dsum (x, y) = K(x|y) + K(y|x) distance [24], we have already observed similar phenomenon many years ago, and proved a theorem about “tough guys having fewer neighbors”, [24], Theorem 8.3.8, page 548. Note that this third problem is

24

M. Li

closely related to the ﬁrst problem: only when we allow a few popular objects to have very dense neighborhoods, it is then possible that they are selected more often. In a diﬀerent application, we are recently building a Question-Answering (QA) system by voice on an iPhone [23], using the Dragon (www.nuance.com) voice recognition server. However, the quality of the current speech recognition technology has not yet become practical because of the following reasons: – Noisy environment. – Speech accent variations – adults vs kids, native speakers vs non-native speakers, female vs male, when training is not possible for individuals (for example for an iPhone game). – Error in speech, corrections. The goal of the research is to use the internet information to solve such problems to make speech recognition practical in the domain of QA. To do this, we have downloaded over 30 million questions from various QA engines, and mainly from answer.com. Let D denote the database of these questions. Given a Question Database D, and a user asked question repeated k times, usually k ≤ 2, recognized by voice recognition software system generating say Q = {q1 , q2 }, the goal is to compute the user’s intended question q which is close to Q and similar to a pattern in D. The ﬁnal answer q could be one of the q1 or q2 ; it could be a combination of the two; it could also be one of the questions in D with some mutations so that it is close to parts of q1 , q2 . We wish to ﬁnd the most plausible question q such that q ﬁts one of the question patterns in D, and q has “close distance” to Q. We have experimentally justiﬁed that, at the size of 30 million, D already contains over 99 percent of all question patterns. Thus our problem can be formulated as below: Given Q, D, ﬁnd q such that it minimizes the “distance” from D to q, and q to Q. Here, D is a huge database of 30M user asked questions. q will only be “similar” to a few of those questions. For example, a user might have asked “Who is the mayor of Waterloo, Ontario?” and in D, there are questions like “Who is the mayor of Toronto, Ontario?” or “Who is the mayor of Washington DC?”. Q sometimes contain things like “Hole is the mayor of Water?” and “Who mayor oﬀ Waterloo”. Thus in order to measure the distance between D and q, it is important to remove all irrelevant information from D. The usual Dmax measure is clearly not proper. In [21] we have systematically presented a Dmin theory, with main parts published earlier in [39,40]. Here let us outline this theory, following [21]. Let us go back to the starting point of information distance. In Eq (1), we asked for smallest number of bits that must be used to convert between x and y. Keeping our motivation in mind: some information in x or y are not relevant to this

Information Distance and Its Extensions

25

conversion, they should be kept aside in this conversion process. We thus deﬁne: with respect to a universal Turing machine U , the cost of conversion between x and y is: Emin (x, y) = min{|p| : U (x, p, r) = y, U (y, p, q) = x, |p| + |q| + |r| ≤ E(x, y)},

(8)

To interpret, the above deﬁnition separates r as the information for x and q as the information for y. Deﬁne Dmin (x, y) = Emin (x, y). Modulo an O(log(|x|+|y|)) additive term, we have proved the following theorem, and here we include its proof from [21] for completeness. Theorem 5. Dmin (x, y) = min{K(x|y), K(y|x)}. Proof. Without loss of generality, assume that K(y|x) ≥ K(x|y). In the original proof of E(x, y) = max{K(x|y), K(y|x)}, in [4,24], it is known that there exists a program p of length K(x|y) and q of length K(y|x) − K(x|y), such that U (xq, p) = y;

U (y, p) = xq.

Since |p| = K(x|y), we know Dmin (x, y) ≤ min{K(x|y), K(y|x)}. We also need to show that q contains no information about x by proving K(x|q) = K(x). By the Symmetry of Information Theorem (Theorem 2.8.2 in [24], page 182), we have K(xq) = K(x|q) + K(q) = K(q|x) + K(x). Thus if K(x|q) < K(x), then we must have K(q|x) < K(q). Thus we can construct y via x, p, plus K(q|x) bits. That is: K(y|x) < |p| + |q| = K(y|x), contradiction. In order to show Dmin (x, y) ≥ min{K(x|y), K(y|x)}. Notice that if less than K(x|y) amount of information is present in p, then extra information of K(x|y)− |p| bits, in addition to K(y|x) − K(x|y), will need to be given in both q and r, hence the sum will be more than E(x, y), violating the condition. Observe the following interesting phenomena: – The extra information q in the proof of Theorem 5 contains no information about x, it is the irrelevant information in y, in a minimal sense. – While Dmin (x, y) is symmetric and positive, it does not satisfy the triangle inequality. To see this, let x and y be independent long Kolmogorov random strings, and z = the empty string. Then Dmin (x, y) > Dmin (x, z) + Dmin (z, y) = O(1). – Dmin (x, y) satisﬁes Eq. 2 only for random x’s. This is perhaps not a surprise as Dsum (x, y) = Dmin (x, y) + Dmax (x, y). In the new metric Dmin, “good guys” (Kolmogorov simple objects) have even more neighbors than Dsum . The above three properties naturally co-exist in the new theory. Dmin can be normalized similar to that of Dmax . Several properties of the normalized version were studied in [21]. We refer the readers to [21] for more details. We now go back to our voice recognition correction system. As we have said, D is very large vs q, the Dmax measure does not make sense here, as most of

26

M. Li

information in D are irrelevant. So we should use Dmin (q, D). For q and Q, we can use Dmax (q, Q). Thus given Q, D, we wish to ﬁnd q that minimizes the following function: δDmin(q, D) + Dmax (Q, q), where δ > 1 is a coeﬃcient that determines how much weight we wish to give to a correct template/pattern in D. Note that q = Q or q = does not minimize the formula. The best way is to ﬁnd a good template in D. There is a tradeoﬀ: sometimes a less popular pattern (taking more bits in the Dmin term) might ﬁt Q better (taking fewer bits in the Dmax term) and a more popular pattern (taking fewer bits in the Dmin item) might miss one or two key words in Q (taking more bits to encode in the Dmax item). δ can be optimized for this. Encoding method design, system developments, user interface, and experiments for this project are in progress. Initial implementation of this system shows a very signiﬁcant improvement over a voice-recognition-only system.

5

Discussions

The normalized information distance dmax is not universal [21]. It was introduced for the purpose of averaging out the irrelevant information. On the other hand, Dmin is universal (but it does not satisfy the triangle inequality) and it is introduced to remove the irrelevant information from the distance calculation. It will be interesting to see if Dmin can be used to replace dmax in some applications. Similarly, Em can be normalized, but it will be interesting to understand why we have to do it as normalization causes mathematical imperfections. With respect to the Em metric, we can also deﬁne a version removing irrelevant information just like Dmin vs Dmax for m = 2 case. We leave this as an exercise to the interested readers. Acknowledgements. I would like to thank Bin Ma for his major contributions in [22]. I also wish to thank the DS 2011 PC chairs Tapio Elomaa and Jaakko Hollmen for their help in preparing this paper. This work was partially supported by NSERC Discovery Grant OGP0046506, Canada Research Chair program, MITACS, an NSERC Collaborative Grant, Premier’s Discovery Award, Killam Prize, and an IDRC Research Chair in Information Technology grant.

References 1. An´e, C., Sanderson, M.J.: Missing the forest for the trees: Phylogenetic compression and its implications for inferring complex evolutionary histories. Systematic Biology 54(1), 146–157 (2005) 2. Arbuckle, T., Balaban, A., Peters, D.K., Lawford, M.: Software documents: comparison and measurement. In: Proc. 18 Int’l Conf. on Software Engineering and Knowledge Engineering 2007 (SEKE 2007), pp. 740–745 (2007)

Information Distance and Its Extensions

27

3. Arbuckle, T.: Studying software evolution using artefacts’ shared information content. Sci. of Comput. Programming 76(2), 1078–1097 (2011) 4. Bennett, C.H., G´ acs, P., Li, M., Vit´ anyi, P., Zurek, W.: Information Distance. IEEE Trans. Inform. Theory 44(4), 1407–1423 (1993) (STOC 1993) 5. Bennett, C.H., Li, M., Ma, B.: Chain letters and evolutionary histories. Scientiﬁc American 288(6), 76–81 (2003) (feature article) 6. Benedetto, D., Caglioti, E., Loreto, V.: Language trees and zipping. Phys. Rev. Lett. 88(4), 048702 (2002) 7. Bu, F., Zhu, X., Li, M.: A new multiword expression metric and its applications. J. Comput. Sci. Tech. 26(1), 3–13 (2011); also in COLING 2010 8. Chen, X., Francia, B., Li, M., Mckinnon, B., Seker, A.: Shared information and program plagiarism detection. IEEE Trans. Information Theory 50(7), 1545–1550 (2004) 9. Cilibrasi, R., Vit´ anyi, P., de Wolf Algorithmic, R.: clustring of music based on string compression. Comput. Music J. 28(4), 49–67 (2004) 10. Cilibrasi, R., Vit´ anyi, P.: Automatic semantics using Google (2005) (manuscript), http://arxiv.org/abs/cs.CL/0412098 (2004) 11. Cilibrasi, R., Vit´ anyi, P.: Clustering by compression. IEEE Trans. Inform. Theory 51(4), 1523–1545 (2005) 12. Cuturi, M., Vert, J.P.: The context-tree kernel for strings. Neural Networks 18(4), 1111–1123 (2005) 13. Emanuel, K., Ravela, S., Vivant, E., Risi, C.: A combined statistical-deterministic approach of hurricane risk assessment. In: Program in Atmospheres, Oceans, and Climate. MIT, Cambridge (2005) (manuscript) 14. Fagin, R., Stockmeyer, L.: Relaxing the triangle inequality in pattern matching. Int’l J. Comput. Vision 28(3), 219–231 (1998) 15. Kirk, S.R., Jenkins, S.: Information theory-baed software metrics and obfuscation. J. Systems and Software 72, 179–186 (2004) 16. Keogh, E., Lonardi, S., Ratanamahatana, C.A.: Towards parameter-free data mining. In: KDD 2004, pp. 206–215 (2004) 17. Kocsor, A., Kertesz-Farkas, A., Kajan, L., Pongor, S.: Application of compressionbased distance measures to protein sequence classiﬁcation: a methodology study. Bioinformatics 22(4), 407–412 (2006) 18. Krasnogor, N., Pelta, D.A.: Measuring the similarity of protein structures by means of the universal similarity metric. Bioinformatics 20(7), 1015–1021 (2004) 19. Li, M., Badger, J., Chen, X., Kwong, S., Kearney, P., Zhang, H.: An informationbased sequence distance and its application to whole mitochondrial genome phylogeny. Bioinformatics 17(2), 149–154 (2001) 20. Li, M., Chen, X., Li, X., Ma, B., Vit´ anyi, P.: The similarity metric. IEEE Trans. Information Theory 50(12), 3250–3264 (2004) 21. Li, M.: Information distance and its applications. Int’l J. Found. Comput. Sci. 18(4), 669–681 (2007) 22. Li, M., Ma, B.: Notes on information distance among many entities, March 23 (2008) (unpublished notes) 23. Li, M., Tang, Y., Wang, D.: Information distance between what I said and what it heard (manuscript, 2011) 24. Li, M., Vit´ anyi, P.: An introduction to Kolmogorov complexity and its applications, 3rd edn. Springer, Heidelberg (2008) 25. Long, C., Zhu, X.Y., Li, M., Ma, B.: Information shared by many objects. In: ACM 17th Conf. Info. and Knowledge Management (CIKM 2008), Napa Valley, California, October 26-30 (2008)

28

M. Li

26. Long, C., Huang, M., Zhu, X., Li, M.: Multi-document summarization by information distance. In: IEEE Int’l Conf. Data Mining, 2009 (ICDM 2009), Miami, Florida, December 6-9 (2009) 27. Nikvand, N., Wang, Z.: Generic image similarity based on Kolmogorov complexity. In: IEEE Int’l Conf. Image Processing, Hong Kong, China, September 26-29 (2010) 28. Nykter, M., Price, N.D., Larjo, A., Aho, T., Kauﬀman, S.A., Yli-Harja, O., Shmulevich, I.: Critical networks exhibit maximal information diversity in structuredynamics relationships. Phy. Rev. Lett. 100, 058702(4) (2008) 29. Nykter, M., Price, N.D., Aldana, M., Ramsey, S.A., Kauﬀman, S.A., Hood, L.E., Yli-Harja, O., Shmulevich, I.: Gene expression dynamics in the macrophage exhibit criticality. Proc. Nat. Acad. Sci. USA 105(6), 1897–1900 (2008) 30. Otu, H.H., Sayood, K.: A new sequence distance measure for phylogenetic tree construction. Bioinformatics 19(6), 2122–2130 (2003) 31. Pao, H.K., Case, J.: Computing entropy for ortholog detection. In: Int’l Conf. Comput. Intell., Istanbul, Turkey, December 17-19 (2004) 32. Parry, D.: Use of Kolmogorov distance identiﬁcation of web page authorship, topic and domain. In: Workshop on Open Source Web Inf. Retrieval (2005), http://www.emse.fr/OSWIR05/ 33. Costa Santos, C., Bernardes, J., Vit´ anyi, P., Antunes, L.: Clustering fetal heart rate tracings by compression. In: Proc. 19th IEEE Intn’l Symp. Computer-Based Medical Systems, Salt Lake City, Utah, June 22-23 (2006) 34. Taha, W., Crosby, S., Swadi, K.: A new approach to data mining for software design, Rice Univ. (2006) (manuscript) 35. Varre, J.S., Delahaye, J.P., Rivals, E.: Transformation distances: a family of dissimilarity measures based on movements of segments. Bioinformatics 15(3), 194–202 (1999) 36. Veltkamp, R.C.: Shape Matching: Similarity Measures and Algorithms. In: Proc. Int ’l Conf. Shape Modeling Applications, Italy, pp. 188–197 (2001) (invited talk) 37. Vitanyi, P.M.B.: Information distance in multiples. IEEE Trans. Inform. Theory 57(4), 2451–2456 (2011) 38. Wehner, S.: Analyzing worms and network traﬃce using compression. J. Comput. Security 15(3), 303–320 (2007) 39. Zhang, X., Hao, Y., Zhu, X., Li, M.: Information distance from a question to an answer. In: 13th ACM SIGKDD Int’l Conf. Knowledge Discovery Data Mining, San Jose, CA, August 12-15 (2007) 40. Zhang, X., Hao, Y., Zhu, X.Y., Li, M.: New information measure and its application in question answering system. J. Comput. Sci. Tech. 23(4), 557–572 (2008); This is the ﬁnal version of [39]

Models for Autonomously Motivated Exploration in Reinforcement Learning Peter Auer1 , Shiau Hong Lim1 , and Chris Watkins2 1

2

Chair for Information Technology, Montanuniversit¨ at Leoben, Austria http://institute.unileoben.ac.at/infotech Department of Computer Science, Royal Holloway University of London, UK http://www.rhul.ac.uk/computerscience

Abstract. One of the striking diﬀerences between current reinforcement learning algorithms and early human learning is that animals and infants appear to explore their environments with autonomous purpose, in a manner appropriate to their current level of skills. An important intuition for autonomously motivated exploration was proposed by Schmidhuber [1,2]: an agent should be interested in making observations that reduce its uncertainty about future observations. However, there is not yet a theoretical analysis of the usefulness of autonomous exploration in respect to the overall performance of a learning agent. We discuss models for a learning agent’s autonomous exploration and present some recent results. In particular, we investigate the exploration time for navigating eﬀectively in a Markov Decsion Process (MDP) without rewards, and we consider extensions to MDPs with inﬁnite state spaces. Keywords: Reinforcement learning, autonomous exploration, intrinsic rewards.

References 1. Schmidhuber, J.: A Possibility for Implementing Curiosity and Boredom in ModelBuilding Neural Controllers. In: Meyer, J.A., Wilson, S.W. (eds.) International Conference on Simulation of Adaptive Behavior: From Animals to Animats, pp. 222–227. MIT Press, Cambridge (1991) 2. Schmidhuber, J.: Developmental Robotics, Optimal Artiﬁcial Curiosity, Creativity, Music, and the Fine Arts. Connection Science 18(2), 173–187 (2006)

The full version of this paper is published in the Proceedings of the 22nd International Conference on Algorithmic Learning Theory, Lecture Notes in Artiﬁcial Intelligence Vol. 6925.

T. Elomaa, J. Hollm´ en, and H. Mannila (Eds.): DS 2011, LNCS 6926, p. 29, 2011. c Springer-Verlag Berlin Heidelberg 2011

Optimal Estimation Jorma Rissanen Helsinki Institute for Information Technology, Tampere University of Technology, Finland

1

Modeling Problem

Data Y = {yt : t = 1, 2, . . . , n}, or Y |X = {(yt , x1,t , x2,t , . . .)}, X explanatory variables. Want to learn properties in Y expressed by set of distributions as models: f (Y |Xs ; θ, s), where θ = θ1 , . . . , θk(s) real-valued parameters, s structure parameter: for picking the most important variables in X. 1.1

Models and Estimators

To simplify notations write yt , x1,t , x2,t , . . . as xt ; structures determined by number k of real-valued parameters. Classes of parametric models Mk = {f (xn ; θ, k) : θ ∈ Ω k ⊂ Rk }; k ≤ n M = {Mk : k = 1, 2, . . . , K, K ≤ n}. ¯ k(·). ¯ Sets of estimator functions θ(·), Consider the distributions defined by estimators ¯ n ), k)/C¯k,n for fixed k : f¯(xn ; k) = f (xn ; θ(x ¯ n ), k)dy n C¯k,n = f (y n ; θ(y ¯ n ))/C¯n in general : f¯(xn ) = f¯(xn ; k(x C¯n = f¯(y n ; k)dy n k

¯ n )=k k(y

ˆ k(·) ˆ be the estimator that maximizes C¯n : Let θ(·), Cˆn = max C¯n . ¯ k(·) ¯ θ(·),

(1)

It also maximizes the probability or density fˆ(xn ) on the observed data, which is taken as the single postulate for this theory of estimation. The maximum Cˆn is called the maximum capacity, and it is also the maximum mutual information that any estimator can obtain about the models in the class.

T. Elomaa, J. Hollm´ en, and H. Mannila (Eds.): DS 2011, LNCS 6926, p. 30, 2011. c Springer-Verlag Berlin Heidelberg 2011

Monotone Instance Ranking with

mira

Nicola Barile and Ad Feelders Universiteit Utrecht, Department of Information and Computing Sciences, PO Box 80089, 3508TB Utrecht, The Netherlands {barile,ad}@cs.uu.nl

Abstract. In many ranking problems, common sense dictates that the rank assigned to an instance should be increasing (or decreasing) in one or more of the attributes describing it. Consider, for example, the problem of ranking documents with respect to their relevance to a particular query. Typical attributes are counts of query terms in the abstract or title of the document, so it is natural to postulate the existence of an increasing relationship between these counts and document relevance. Such relations between attributes and rank are called monotone. In this paper we present a new algorithm for instance ranking called mira which learns a monotone ranking function from a set of labelled training examples. Monotonicity is enforced by applying the isotonic regression to the training sample, together with an interpolation scheme to rank new data points. This is combined with logistic regression in an attempt to remove unwanted rank equalities. Through experiments we show that mira produces ranking functions having predictive performance comparable to that of a state-of-the-art instance ranking algorithm. This makes mira a valuable alternative when monotonicity is desired or mandatory.

1

Introduction

In many applications of ranking it is reasonable to assume that the rank assigned to an instance is increasing (or decreasing) in one or more of the attributes or features. Consider, for example, the problem of ranking documents with respect to their relevance to a particular query. Typical attributes are counts of query terms in the abstract or title of the document, so it is natural to postulate the existence of an increasing relationship between these counts and document relevance. Such relations between attributes and rank are called monotone. Besides being plausible, monotonicity is often a desirable or mandatory property of a ranking model for reasons of fairness (such as in acceptance/rejection decisions) or for reasons of explanation and justiﬁcation. Consider for instance a model that is used by a bank to rank loan applicants: it would be strange if applicant a scored at least as well as b on all criteria but were ranked lower than b. Hence, the rank assigned to loan applicants should be monotone in the application criteria: models that do not satisfy this property are simply inacceptable to subject area experts (i.e. loan oﬃcers) and clients. Similar considerations apply to selection procedures for applicants for e.g. a job or a university program. T. Elomaa, J. Hollm´ en, and H. Mannila (Eds.): DS 2011, LNCS 6926, pp. 31–45, 2011. c Springer-Verlag Berlin Heidelberg 2011

32

N. Barile and A. Feelders

Pazzani et al. [22] report on an application of rule induction algorithms to early detection of dementia and prediction of mild mental retardation. The authors show that, without loss of accuracy, they can enforce rules to satisfy certain plausible monotonicity constraints. An example they give is that the probability that a patient is mentally impaired depends positively on the amount of recall error of the patient. The rules learned with monotonicity constraints were signiﬁcantly more acceptable to medical experts than those learned without the monotonicity restrictions. In general, while human experts tend to feel uncomfortable expressing their knowledge and experience in terms of numeric assessments, they are typically able to state their knowledge in a semi-numerical or qualitative form with relative conviction and clarity, and with less cognitive eﬀort [13]. Experts, for example, can often easily indicate which of two probabilities is smaller. In addition to requiring less cognitive eﬀort, such relative judgements tend to be more reliable than direct numerical assessments [21]. The fact that monotonicity constraints occur frequently in ranking problems and that such constraints can be elicited from subject-area experts with relative ease and reliability motivates the development of algorithms which are able to enforce such constraints in a justiﬁed manner. Several data mining techniques have been developed for monotone classiﬁcation and regression problems. Examples are instance based classiﬁcation [7,8,20], classiﬁcation trees [23,9,26], neural networks [24], Bayesian networks [4,14], and rules [11]. Data mining techniques for monotone ranking is a relatively unexplored area of research however. In this paper we introduce a new instance ranking algorithm named mira (Monotone Instance Ranking Algorithm) which extends these ideas to learning ranking functions. We do so by building on the ideas formulated by F¨ urnkranz et al. in [17] and our own work on nonparametric monotone classiﬁcation [7]. This paper is organised as follows. In the next section we introduce instance ranking, which is the speciﬁc ranking problem addressed by mira. To compute the score of an instance, mira uses an aggregation scheme proposed by F¨ urnkranz et al. [17], which is also discussed in section 2. In section 3 we formalise the concept of monotonicity and deﬁne the monotone instance ranking problem. Subsequently, we present an initial formulation of the monotone scoring function our ranking algorithm uses in section 4. In section 5 we show how this initial scoring function compares to the best-performing algorithm presented in [17], both on artiﬁcal and on real world data. In section 6 we adjust the initial mira scoring function in an attempt to remove unwanted rank equalities. Additional experiments to test this adjusted scoring function are presented in section 7. Finally, in section 8 we draw conclusions and indicate possibilities for future work.

2

Instance Ranking

An exhaustive taxonomy of ranking problems is given in [16]. Of the several types of ranking problems illustrated there, this paper focuses on the problem of instance ranking, which can be formalised as follows.

Monotone Instance Ranking with MIRA

33

Let D = {(xi , yi )}N i=1 denote the set of N observations of the vector of predictors (attributes) X, which takes values x in a p-dimensional input space X = ×Xi , and class label Y , which takes values y in a one-dimensional space Y = {y1 , y2 , . . . , yk }, where k is the number of class labels. We assume the existence of a total order on all Xi ’s, as well as on Y. If there are k distinct class labels, they will be coded simply as Y = {1, 2, . . . , k}. The goal of instance ranking is to learn from these labelled examples a ranking function which, given as an input a subset X of the instance space X with no class labels, outputs a linear order of these instances based on their (unknown) preference degrees. For the case k = 2, this problem is known as the bipartite ranking problem, while for the case k > 2 it has recently been named multipartite ranking [17]. An instance ranker’s ranking function is typically implemented as a scoring function f : X → R, assigning a real-valued score to each element of X . Given a subset X of X , the items in X are ranked according to their respective scores: the higher the score, the better the rank. In the context of instance ranking, the ideal scoring function is one that, when applied to a set of labelled observations, gives instances with higher class label a higher score. Diﬀerent types of accuracy measures have been proposed for predictions of this kind. As the goal is to produce a ranking in which instances from higher classes precede those from lower classes, these measures count the number of ranking errors, namely the number of pairs (x, x ) ∈ X × X such that x is ranked higher than x even though the former belongs to a lower class than the latter. In the two-class case, this corresponds to the area under the ROC-curve, which can be interpreted as the probability that a randomly chosen instance belonging to the ﬁrst class is ranked higher than a randomly chosen instance belonging to the second class. Its generalisation to more than two classes is represented by the probability that a randomly chosen pair of observations (x, y) and (x , y ) belonging to diﬀerent classes is ranked consistently by the ranking function, namely P (f (x) < f (x ) | y < y ) .

(1)

If the training examples are independently and identically drawn from a probability distribution on X × Y, an unbiased estimator of (1) is represented by the concordance index or C-index [18] C (f, X) =

1

i<j

ni nj

i<j (x,x )∈Xi ×Xj

S(f (x), f (x )),

(2)

34

N. Barile and A. Feelders

where Xi and Xj are the subsets of instances x ∈ X having class yi and yj respectively, ni = |Xi |, and S(·, ·) is deﬁned as follows: ⎧ ⎨ 0 if a > b S(a, b) = 1 if a < b ⎩ 1/2 if a = b

(3)

Many approaches to solving the instance ranking problem are based on the idea of learning the optimal scoring function f by turning the initial training data set into a set of order constraints on it and then ﬁnding a function that is as much as possible in agreement with them. Each pair of observed examples (xi , yi ) and (xj , yj ) such that yi > yj gives rise to a constraint f (xi ) > f (xj ). In order to use existing learning algorithms, one common approach consists in expressing these constraints as classiﬁcation examples and then learning a binary probabilistic classiﬁer whose probability estimates are then used as a scoring function. One important example is represented by the algorithm introduced in [19]. F¨ urnkranz et al. [17] introduce two instance ranking algorithms based on a diﬀerent approach which makes better and more explicit use of the ordering of the class labels. Instead of transforming the original problem into a single binary classiﬁcation problem, the authors suggest decomposing it into several binary problems by applying well-established decomposition techniques already used successfully in multi-class classiﬁcation. Several binary classiﬁers, therefore several scoring functions, are learned from the training instances. When applied to a new set of instances, the scoring functions associated with each model are then aggregated into an overall scoring function. Of the algorithms introduced in [17], we shall now describe the one which builds on the ordinal classiﬁcation algorithm presented by Frank and Hall in [15], as our new algorithm will be based on the same aggregation scheme. The ordinal classiﬁcation algorithm presented by Frank and Hall in [15] trains models fi , i = 1, . . . , k − 1 each of which separates the meta-classes C− = {y1 , . . . , yi } and C+ = {yi+1 , . . . , yk }. Given a new instance x, a prediction fi (x) is an estimate of the probability P (y > i | x), namely that the class of x is in C+ ; an estimate of the conditional probability distribution P (y | x) is then derived from these conditional probabilities, and the class with the highest probability is predicted. To obtain a ranking function, F¨ urnkranz, H¨ ullermeier and Vanderlooy [17] suggest aggregating the models fi as

fagg (x) =

k−1 i=1

fi (x) =

k−1

P (y > i | x)

(4)

i=1

because (4) systematically assigns higher scores to instances from higher classes. When the fi in this aggregation scheme are logistic regression models, as implemented in [17], we refer to this ranking function as ffhv or simply fhv.

Monotone Instance Ranking with MIRA

3

35

Monotone Instance Ranking

We now turn our attention to obtaining a monotone ranking function, which assigns higher scores to higher ordered attribute vectors. To this end, we deﬁne a partial order on X , typically but not necessarily the product (or pointwise) order induced by the total orders on each Xi : x x ⇔ ∀i = 1, . . . , p : xi ≤ xi .

(5)

A monotone instance ranking task consists in learning a monotone scoring function f (·), which assigns a score to each instance x ∈ X such that ∀x, x ∈ X : x x ⇒ f (x) ≤ f (x ),

(6)

that is, a lower ordered input is not allowed to have a higher score. In the case of the product order deﬁned in (5) this expresses the constraint that each attribute should have a positive inﬂuence on the score. It is clear from (4) that for (6) to be satisﬁed, it is suﬃcient that we have x x ⇒ P (y > i | x) ≤ P (y > i | x ), for i = 1, . . . , k − 1. We can also express this as a stochastic order constraint. Let Fi (x) denote the cumulative probability P (y ≤ i | x). If we have x x ⇒ Fi (x) ≥ Fi (x ),

(7)

for i = 1, . . . , k − 1, then it follows from (4) that: x x ⇒ fagg (x) ≤ fagg (x ), since P (y > i | x) = 1 − Fi (x). This observation forms the basis for our method to obtain a monotone ranking function.

4

A Monotone Scoring Function

We have shown that to obtain a monotone scoring function using aggregation scheme (4), it is suﬃcient that the stochastic order constraint (7) holds. Therefore, we propose an estimator which satisﬁes this constraint by construction and is as close as possible (in a least squares sense) to the empirical cumulative distributions of y on the training data. Let Z denote the set of distinct values x occurring in D. Deﬁne n(x, j) , Pˆj (x) = n(x)

x∈Z

where n(x) denotes the number of observations in D with attribute values x and n(x, j) denotes the number of observations in D with attribute values x and class label j. Furthermore, let Fˆi (x) = Pˆj (x), x∈Z j≤i

36

N. Barile and A. Feelders

denote the unconstrained maximum likelihood estimate of Fi (x) = P (y ≤ i | x), x ∈ Z.

(8)

Like in [7], in mira we estimate (8) as Fi∗ (x) = arg min h

N

[h(xj ) − Fˆi (xj )]2 = arg min h

j=1

n(x)[h(x) − Fˆi (x)]2

(9)

x∈Z

where h(·) is the class of antitonic functions, that is, x x ⇒ h(x) ≥ h(x ). Note that, since h(·) is restricted to the class of antitonic functions, this estimator does indeed satisfy the stochastic order constraint (7) by construction. If y is binary, then it yields the constrained maximum likelihood estimates of Fi (x). The computation of Fi∗ (x) is an isotonic regression problem. Spouge et al. [25] describe an algorithm to compute the isotonic regression for arbitrary partial order in O(n4 ) steps. In order to estimate all cumulative probabilities, the isotonic regression has to be performed k − 1 times, since obviously Fk∗ (x) = 1. What we have obtained so far are class probability distributions only deﬁned on the observed training instances x ∈ Z. Typically the training sample does not cover the entire input space, so we need to ﬁnd a way to estimate Fi (x0 ) for points x0 not included in the training sample. Because such estimates must also satisfy the stochastic order constraint with respect to F ∗ (x), we can derive bounds on Fi (x0 ). Since we require that Fi (x0 ) ≥ Fi (x) for all x ∈ Z such that x0 x, we get lower bound: Fimin (x0 ) = max Fi∗ (x) x0 x

x ∈ Z ; i = 1, . . . , k.

(10)

x ∈ Z ; i = 1, . . . , k.

(11)

Likewise, we get upper bound: Fimax (x0 ) = min Fi∗ (x) xx0

If there is no point x in Z such that x x0 , then we put Fimax (x0 ) = 1 (i = 1, . . . , k), and if there is no point x in Z such that x0 x, then we put Fimin (x0 ) = 0 (i = 1, . . . , k − 1), and Fkmin (x0 ) = 1. Note that, since Fi∗ is antitonic, it always holds that Fimin ≤ Fimax . Any value in the interval [Fimin , Fimax ] can be chosen, as it satisﬁes the stochastic order constraint with respect to the training data. A simple interpolation scheme that is guaranteed to produce globally monotone estimates is represented by the convex combination F˜i (x0 ) = αF min (x0 ) + (1 − α)F max (x0 ), (12) i

i

with α ∈ [0, 1]. Note that for x0 ∈ Z, we have F˜i (x0 ) = Fi∗ (x0 ), since both Fimin (x0 ) and Fimax (x0 ) are equal to Fi∗ (x0 ) in that case. The value of α can be chosen so as to minimise empirical loss on a test sample. Finally, we obtain the monotone mira scoring function fmira (x) =

k−1 i=1

1 − F˜i (x)

(13)

Monotone Instance Ranking with MIRA

4.1

37

Example

Suppose we have a data set with two input attributes X1 and X2 , and a class label Y with Y = {1, 2, 3}. The attribute vectors observed in the training sample are given in the ﬁrst column of table 1. The number of occurrences of each attribute vector in combination with the three diﬀerent class labels is given in the next three columns. For example, there are two observations with attribute values (1, 1) and class label 1. The product order on the attribute vectors is given in ﬁgure 1. Table 1 gives the maximum likelihood estimates Fˆ and the antitonic regression estimates F˜ of the cumulative distribution of Y for the observed attribute vectors. Recall that F˜ = F ∗ for observed data points.

(1, 2)

(1, 3) (3, 2)

(1, 1) (2, 1)

Fig. 1. Partial order on the attribute vectors in the training sample. Arrows indicate direct precedence in the order. Table 1. Maximum likelihood and mira estimates of cumulative probabilities

(x1 , x2 ) (1, 1) (1, 2) (2, 1) (1, 3) (3, 2)

n(x, y) n(x) Fˆ 12 3 1 2 20 0 2 1 1 12 0 3 1/3 1 02 1 3 0 2/3 00 1 1 0 0 10 1 2 1/2 1/2

F˜ 1 2 1 1 1/3 1 1/5 2/3 0 0 1/5 1/2

The estimates Fˆ violate the stochastic order constraint, because we have (2, 1) (3, 2), but Fˆ1 (2, 1) < Fˆ1 (3, 2). Also, (1, 2) (3, 2), but Fˆ1 (1, 2) < Fˆ1 (3, 2). The antitonic regression resolves these violations by taking the weighted average of Fˆ1 (2, 1) and Fˆ1 (3, 2) and assigning this value to both attribute vectors: 1 3 × 0 + 2 × 1/2 F˜1 (2, 1) = F˜1 (3, 2) = = 3+2 5 Note that the conﬂict between (1, 2) and (3, 2) has been resolved by this averaging as well. In table 2 we see the eﬀect on the score values. If we base the score on Fˆ , that is ﬁll in Fˆ in equation (13) instead of F˜ , then we have fˆ(2, 1) > fˆ(3, 2)

38

N. Barile and A. Feelders Table 2. Scores based on Fˆ and F˜ (x1 , x2 ) (1, 1) (1, 2) (2, 1) (1, 3) (3, 2)

fˆ 0 0.67 1.33 2 1

fmira 0 0.67 1.13 2 1.3

violating the monotonicity constraint. This violation has been resolved in fmira , since fmira (2, 1) < fmira (3, 2). To compute F˜ for a point x0 = (2, 2), we proceed as follows. The points in the training data smaller than x0 are (1, 1), (1, 2) and (2, 1). Hence we have F2max (x0 ) = min{F2∗ (1, 1), F2∗ (1, 2), F2∗ (2, 1)} = min{1, 1, 2/3} = 2/3. The only point in the training data bigger than x0 is (3, 2). Hence we have F2min (x0 ) = F2∗ (3, 2) = 1/2. So for α =

1 2

we would have F˜2 (x0 ) =

1 1 1 2 7 + = 2 2 2 3 12

F˜1 (x0 ) is computed in a similar fashion.

5

Experiments

In order to verify that the desired monotonicity property does not come at the cost of a much worse predictive performance, we now provide the results of an empirical evaluation comparing the performance of scoring function fmira with the performance of ffhv . We compare to ffhv because it is the best performing algorithm among those presented in [17]. We compare the performance on artiﬁcial data as well as real data. To compute the mira scoring function, we use the isotonic regression algorithm described by Spouge et al. in [25]. 5.1

Artificial Data

To show that mira can improve the performance of the fhv logistic regression model, we generate data from a monotone nonlinear model. The class boundaries of this model are depicted in ﬁgure 2. For example, if x1 > 0.4 and x2 > 0.4, then the observation is assigned to class 3. The two features x1 and x2 are drawn independently from the uniform distribution on the interval [0,1]. We consider two diﬀerent training set sizes and four diﬀerent noise levels. For example, a

Monotone Instance Ranking with MIRA

39

noise level of 0.1 indicates that an observation from class 1 is ﬂipped to class 2 with probability 0.05, and is ﬂipped to class 3 with probability 0.05 as well. The concordance-index of trained models was estimated on a test set of size 10,000. We performed ﬁve-fold cross validation on the training set to select the best value of α ∈ {0, 0.25, 0.5, 0.75, 1}. The results (averaged over ﬁve repetitions) on the test set are summarized in table 3. They conform to what one would expect: since the class boundaries are monotone but nonlinear, mira has some advantage over the linear fhv model (with the odd exception of n = 100 and ε = 0.2). This advantage appears to become smaller as the noise level increases. This makes sense, since a nonparametric technique such as mira is more sensitive to noise. It also conforms to expectation that the bigger training set tends to give better results for both methods. Table 3. Results on Artiﬁcial Data. The table gives the concordance-index of mira and fhv on the test set, for two diﬀerent training set sizes and four diﬀerent noise levels. A noise level of ε indicates that the probability that the true label is ﬂipped to one of the other two labels is equal to ε. Size n Noise ε 0.0 0.1 0.2 0.3

5.2

100 fhv mira 0.9013 0.9856 0.8379 0.8957 0.7802 0.7431 0.7148 0.7484

500 fhv mira 0.9041 0.9942 0.8416 0.8906 0.7842 0.8256 0.7271 0.7578

Real Data

The data sets come from diﬀerent (public) sources. The data sets ERA (Employee Rejection/ Acceptance), ESL (Employee Selection), LEV (Lecturer Evaluation), and SWD (Social Workers Decisions) are available on the Weka website [1] and have been donated by Arie Ben-David. The Ohsumed data set is available on the LETOR website [2]. We selected the data for query 3 and selected attributes 5, 6, 7, 18, 20, 21, 22, 35, 36, and 37. The Windsor housing data is available from the Journal of Applied Econometrics Data Archive [3,5]. Finally, the Auto MPG, Boston housing, Computer Hardware (CPU), Haberman’s Survival (Haberman), and Pima Indians Diabetes (Pima) data sets are included in the the UCI machine learning repository [6]. Monotonicity judgements were based on common sense. For example, the Ohsumed attributes are counts of the number of times a query term appears in the title and abstract of a document respectively. The class label indicates the relevance of the document to the query, where a higher label indicates higher relevance (the classes are described as: “irrelevant”, “partially relevant” and “highly relevant”). As a consequence, it is reasonable to assume that the ranking should be increasing in the attributes. When common sense suggested there should be a decreasing rather increasing relationship between an attribute and the score, we simply inverted the attribute values.

40

N. Barile and A. Feelders 0.2

1 x2 1

0

0.4

3

2 1

x1

0.4

2

0.2

1

Fig. 2. Model for artiﬁcial data. Labels are generated according to the indicated class boundaries.

The data sets AutoMPG, Boston Housing, CPU, and Windor Housing originally had numeric target variables. These numeric targets were discretised into ﬁve bins of approximately the same label frequency. Some basic properties of the data sets used are listed in table 4. The last but one column of this table gives the number of comparable pairs, that is, pairs of attribute vectors xi and xj for which xi xj or vice versa, expressed as a percentage of the total number of pairs. This quantity gives some indication of the potential beneﬁt of applying monotonicity constraints: the more comparable pairs there are, the higher the potential beneﬁt is. If all pairs are incomparable, the monotonicity constraint is satisﬁed vacuously. The ﬁnal column gives the percentage of monotone pairs among the comparable ones. If this percentage is low, application of the monotonicity constraint becomes questionable. For each data set, the concordance index of both algorithms was estimated as the average of the concordance index registered during ﬁve repetitions of a 10−fold cross-validation. Within each fold, the best value –in terms of the concordance index– for mira’s α in {0, 0.25, 0.5, 0.75, 1} was chosen by performing 5−fold cross-validation on the training data set for the fold. The best value of α was then used to train mira and complete the fold. Table 5 contains average concordance index values for fhv and for mira. We observe that the diﬀerence in concordance-index is typically very small. Hence we conclude that the desired property of monotonicity can be obtained without sacriﬁcing much in terms of predictive accuracy. Even though the diﬀerence mostly occurs only in the second or third decimal place, we observe that fhv has the higher concordance index 10 out of 11 times. When performing Wilcoxon’s signed-ranks test, as recommended by Demˇsar [12], the p−value obtained is 0.02. We may summarize these ﬁndings by stating that fhv consistently has slightly better predictive performance.

Monotone Instance Ranking with MIRA

41

Table 4. Basic properties of the data sets. N denotes the number of observations, and n the number of distinct attribute vectors. Data set N n # attr # lab % comp % mon AutoMPG 392 387 7 5 81.26 97.08 Boston Housing 506 506 12 5 19.10 87.77 CPU 209 190 6 5 49.53 98.52 ERA 1000 44 4 9 16.77 74.79 ESL 488 199 4 9 70.65 98.85 Haberman 306 283 3 2 33.71 89.28 LEV 1,000 92 4 5 24.08 95.73 Ohsumed 235 55 10 3 52.29 44.77 Pima 768 768 8 2 7.32 97.76 SWD 1,000 117 10 4 12.62 94.21 Windsor Housing 546 529 11 5 27.37 84.83 Table 5. Concordance index attained respectively by mira and by fhv Data set AutoMPG Boston Housing CPU ERA ESL Haberman LEV Ohsumed Pima SWD Windsor Housing

6

mira 0.9327 0.8773 0.9064 0.7326 0.9572 0.7024 0.8617 0.6346 0.7697 0.8070 0.8529

fhv 0.9494 0.9179 0.9085 0.7384 0.9623 0.6815 0.8656 0.6680 0.8298 0.8144 0.8601

An Improved Monotone Ranking Function

The scoring function fmira that we presented has a potential disadvantage: violations of monotonicity are resolved by averaging the conﬂicting (partial) scores, possibly leading to setting the scores equal altogether. To illustrate this point, we consider the simplest case possible: two examples (x1 , y1 ) and (x2 , y2 ) in a binary problem where x1 ≺ x2 but y1 > y2 . The isotonic regression resolves this violation by averaging the probabilities, giving both examples a probability of 0.5 for the lower class. Consequently, the two examples get the same score, giving a concordance index of 0.5. However, the monotonicity constraint expresses our belief that the higher ordered input x2 tends to have higher class labels in general. Therefore, it would be more appropriate to give x2 a higher score than x1 . Note that doing so would actually yield a lower concordance index on the training data, as it would decrease to 0. If the monotonicity constraint is correct,

42

N. Barile and A. Feelders

however, then the concordance index on unseen data will improve by making the inequality a strict one. In an attempt to enforce strict inequalities, we try to break ties by combining each of the probabilities added up in equation (13) with those estimated using the logistic regression model log

p Pi (C+ |x) = β0 + βj xj , Pi (C− |x) j=1

where Pi (C+ |x) and Pi (C− |x) are the conditional probabilities that a given instance belongs to the metaclasses C+ and C− for the i−th initial rank respectively. The reason for using this correction is that if βj > 0, then there is a strictly positive monotone relationship between xj and the probability of belonging to the metaclass C+ , consequently producing a ranking function which is strictly monotone in xj . The new mira scoring function is then given by fmira (x) =

k−1

γPilr (x) + (1 − γ)(1 − F˜i (x)),

(14)

i=1

where each Pilr (x) = Pi (C+ |x) is the ﬁtted probability of the logistic regression model for the i−th metaclass C+ , and γ ∈ [0, 1]. In order to only get positive coeﬃcients in the logistic regression model, the full logistic models (namely, including all descriptive attributes) are ﬁrst estimated. If the models obtained contain negative coeﬃcients, then all of the corresponding descriptive attributes are removed, and the logistic models are re-estimated with the remaining descriptive attributes. The re-estimation of the logistic models is repeated until only attributes with positive coeﬃcients remain. Because we remove attributes with negative coeﬃcients, we may not be able to always enforce the desired strict monotonicity. To illustrate this, let x denote the subset of x included in the logistic regression model. If x ≺ x but x = x , then obviously the logistic regression model will assign the same probabilities to x and x , that is Pi (C+ |x) = Pi (C+ |x ). When γ = 0 in equation (14), we are eﬀectively using scoring function (13), and when γ = 1 only the logistic regression part is used. Note that even if γ = 1, fmira is not identical to ffhv , since mira enforces positive coeﬃcients in order to obtain the required monotonicity directions.

7

Additional Experiments

We used the same experimental set-up as for the experiments reported in section 5.2. Table 6 reports mira’s average concordance index for diﬀerent values of γ as well as the average concordance-index of the fhv instance ranker.

Monotone Instance Ranking with MIRA

43

To test the null-hypothesis that all methods have the same performance, we perform Friedman’s test, as recommended by Demˇsar [12]. This yields a p-value of 0.0003, leading to rejection of this hypothesis at any reasonable value of α. Therefore, we proceed with a post-hoc test, where we compare mira at diﬀerent levels of γ with fhv which is considered to be the baseline or control ranker in this experiment. The p-values of the null-hypothesis of no diﬀerence are given in the ﬁnal row of table 6 for each value of γ. To control for family-wise error, we simply perform the Bonferroni correction. Taking α = 0.1, we divide this by the number of comparisons performed, which is eight. Hence, only p-values below 0.0125 are considered to indicate a signiﬁcant diﬀerence. Summarizing the results, it seems fair to say that striking a balance between the isotonic regression and the logistic regression components works best for mira, since the best results are obtained for γ = 0.5 and γ = 0.7. This can be inferred from the high p-values and low average ranks for these values of γ. Finally, the fact that results for γ = 0 and γ = 1 are among the worst proves that both components of mira’s scoring function should be present in order to achieve the best performance. Table 6. Concordance-index of mira for diﬀerent values of γ, and for fhv (ﬁnal column) Data set AutoMPG Boston CPU ERA ESL Haberman LEV Ohsumed Pima SWD Windsor Housing Average rank p−value

8

γ = 0 γ = 0.05 γ = 0.1 γ = 0.2 γ = 0.5 γ = 0.7 γ = 0.9 γ = 1 fhv 0.9327 0.9389 0.9398 0.9427 0.9488 0.9504 0.9491 0.9479 0.9494 0.8773 0.8817 0.8844 0.8887 0.9000 0.9020 0.9006 0.8951 0.9179 0.9064 0.9134 0.9140 0.9145 0.9194 0.9187 0.9141 0.9097 0.9085 0.7326 0.7333 0.7337 0.7348 0.7369 0.7379 0.7365 0.7356 0.7384 0.9572 0.9579 0.9583 0.9579 0.9469 0.9374 0.9366 0.8601 0.9623 0.7024 0.7003 0.7000 0.6992 0.6951 0.6949 0.6915 0.6841 0.6815 0.8617 0.8626 0.8634 0.8647 0.8669 0.8674 0.8664 0.8656 0.8656 0.6346 0.6434 0.6444 0.6478 0.6583 0.6660 0.6688 0.6700 0.6680 0.7697 0.7924 0.7949 0.7989 0.8126 0.8205 0.8279 0.8288 0.8298 0.8070 0.8082 0.8091 0.8105 0.8129 0.8081 0.8008 0.7949 0.8144 0.8529 0.8570 0.8578 0.8594 0.8609 0.8616 0.8592 0.8582 0.8601 7.7 6.6 5.7 4.9 3.5 3.3 4.5 5.6 3.1 0.0000 0.0005 0.0066 0.0491 0.3476 0.4481 0.0887 0.0094 −

Conclusion and Further Research

We presented mira, a monotone instance ranking algorithm. mira extends our earlier work on non-parametric monotone classiﬁcation [7] to ranking problems and uses a decomposition and aggregation scheme proposed by F¨ urnkranz et al. in [17]. By performing experiments on real data, we have shown that mira’s predictive accuracy measured by means of the concordance index is comparable to that of the best performing algorithm among those presented in [17]. Moreover,

44

N. Barile and A. Feelders

experiments performed on an artiﬁcial data set show that mira can outperform the linear fhv model in case the class boundaries are monotone and nonlinear. More importantly, mira is guaranteed to produce a monotone ranking function. Since monotonicity is desired or even required for many applications, it is a valuable addition to existing ranking algorithms. One issue for future research is whether mira’s predictive accuracy can be further improved by using a diﬀerent estimator capable of attaining higher concordance index values. We tried to do so by using the weighted kNN estimator introduced by Barile and Feelders in [8] without obtaining any improvements however. Another important issue is ﬁnding ways to reduce mira’s execution time. One possibility might be represented by using the O(n2 ) approximation of the isotonic regression presented by Burdakov et al. in [10].

References 1. 2. 3. 4.

5. 6. 7.

8.

9. 10.

11.

12. 13.

http://www.cs.waikato.ac.nz/ml/weka/ http://research.microsoft.com/en-us/um/beijing/projects/letor/ http://econ.queensu.ca/jae/ Altendorf, E.A., Restiﬁcar, A.C., Dietterich, T.G.: Learning from sparse data by exploiting monotonicity constraints. In: Bacchus, F., Jaakkola, T. (eds.) Proceedings of the 21st Conference on Uncertainty in Artiﬁcial Intelligence (UAI 2005), pp. 18–25. AUAI Press (2005) Anglin, P.M., Gen¸cay, R.: Semiparametric estimation of a hedonic price function. Journal of Applied Econometrics 11, 633–648 (1996) Asuncion, A., Newman, D.J.: UCI machine learning repository (2007) Barile, N., Feelders, A.: Nonparametric monotone classiﬁcation with MOCA. In: Giannotti, F. (ed.) Proceedings of the Eighth IEEE International Conference on Data Mining (ICDM 2008), pp. 731–736. IEEE Computer Society, Los Alamitos (2008) Barile, N., Feelders, A.: Nonparametric ordinal classiﬁcation with monotonicity constraints. In: Feelders, A., Potharst, R. (eds.) Workshop Proceedings of MoMo 2009 at ECML PKDD 2009, pp. 47–63 (2009) Ben-David, A.: Monotonicity maintenance in information-theoretic machine learning algorithms. Machine Learning 19, 29–43 (1995) Burdakov, O., Sysoev, O., Grimvall, A., Hussian, M.: An O(n2 ) algorithm for isotonic regression. In: Di Pillo, G., Roma, M. (eds.) Large-Scale Nonlinear Optimization, pp. 25–33. Springer, Heidelberg (2006) Dembczynski, K., Kotlowski, W., Slowinski, R.: Ordinal classiﬁcation with decision rules. In: Ra´s, Z.W., Tsumoto, S., Zighed, D. (eds.) Proceedings of the 3rd ECML/PKDD International Conference on Mining Complex Data, Warsaw, Poland, pp. 169–181. Springer, Heidelberg (2007) Demˇsar, J.: Statistical comparisons of classiﬁers over multiple data sets. The Journal of Machine Learning Research 7, 1–30 (2006) Druzdzel, M.J., van der Gaag, L.C.: Elicitation of probabilities for belief networks: Combining qualitative and quantitative information. In: Proceedings of the 11th Conference on Uncertainty in Artiﬁcial Intelligence (UAI 1995), Los Altos CA, pp. 141–148. Morgan Kaufmann, San Francisco (1995)

Monotone Instance Ranking with MIRA

45

14. Feelders, A., van der Gaag, L.: Learning Bayesian network parameters with prior knowledge about context-speciﬁc qualitative inﬂuences. In: Bacchus, F., Jaakkola, T. (eds.) Proceedings of the 21st Conference on Uncertainty in Artiﬁcial Intelligence (UAI 2005), pp. 193–200. AUAI Press (2005) 15. Frank, E., Hall, M.: A simple approach to ordinal classiﬁcation. In: De Raedt, L., Flach, P.A. (eds.) Proceedings of the 12th European Conference on Machine Learning (ECML/PKDD 2001), Freiburg, Germany, pp. 145–156. Springer, Heidelberg (2001) 16. F¨ urnkranz, J., H¨ ullermeier, E.: Preference Learning. Springer, Heidelberg (2010) 17. F¨ urnkranz, J., H¨ ullermeier, E., Vanderlooy, S.: Binary decomposition methods for multipartite ranking. In: Buntine, W.L., Grobelnik, M., Mladenic, D., ShaweTaylor, J. (eds.) Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD 2009), Bled, Slovenia, vol. Part I, pp. 359–374. Springer, Heidelberg (2009) 18. G¨ onen, M., Heller, G.: Concordance probability and discriminatory power in proportional hazards regression. Biometrika 92(4), 965–970 (2005) 19. Herbrich, R., Graepel, T., Obermayer, K.: Large margin rank boundaries for ordinal regression. Advances in Large-Margin Classiﬁers, 115–132 (2000) 20. Lievens, S., De Baets, B., Cao-Van, K.: A probabilistic framework for the design of instance-based supervised ranking algorithms in an ordinal setting. Annals of Operations Research 163, 115–142 (2008) 21. Meyer, M.A., Booker, J.M.: Eliciting and Analyzing Expert Judgment: A Practical Guide. Series on Statistics and Applied Probability. ASA-SIAM (2001) 22. Pazzani, M.J., Mani, S., Shankle, W.R.: Acceptance of rules generated by machine learning among medical experts. Methods of Information in Medicine 40, 380–385 (2001) 23. Potharst, R., Bioch, J.C.: Decision trees for ordinal classiﬁcation. Intelligent Data Analysis 4(2), 97–112 (2000) 24. Sill, J.: Monotonic networks. In: Advances in Neural Information Processing Systems, NIPS, vol. 10, pp. 661–667 (1998) 25. Spouge, J., Wan, H., Wilbur, W.J.: Least squares isotonic regression in two dimensions. Journal of Optimization Theory and Applications 117(3), 585–605 (2003) 26. van de Kamp, R., Feelders, A., Barile, N.: Isotonic classiﬁcation trees. In: Adams, N., Robardet, C., Siebes, A., Boulicaut, J.-F. (eds.) Proceedings of the 8th International Symposium on Intelligent Data Analysis: Advances in Intelligent Data Analysis VIII, Lyon, France, pp. 405–416. Springer, Heidelberg (2009)

MOA-TweetReader: Real-Time Analysis in Twitter Streaming Data Albert Bifet, Geoﬀrey Holmes, and Bernhard Pfahringer University of Waikato, Hamilton, New Zealand {abifet,geoff,bernhard}@cs.waikato.ac.nz

Abstract. Twitter is a micro-blogging service built to discover what is happening at any moment in time, anywhere in the world. Twitter messages are short, generated constantly, and well suited for knowledge discovery using data stream mining. We introduce MOA-TweetReader, a system for processing tweets in real time. We show two main applications of the new system for studying Twitter data: detecting changes in term frequencies and performing real-time sentiment analysis.

1

Introduction

Traditional web search engines are useful because they capture people’s intent, what they are looking for, what they desire, and what they want to learn about. Instead, Twitter data streams help to capture what people are doing and what they are thinking about. Twitter popularity is growing, and the most interesting aspect from a data analysis point of view, is that a large quantity of data is publicly available, as most people prefer to publish their posts openly, in contrast to other social networks like Facebook or LinkedIn, where the information is only accessible to people that are friends or connections. Twitter has its own conventions that renders it distinct from other textual data. Consider the following Twitter example message or Tweet: RT @toni has a cool #job. It shows that users may reply to other users by indicating user names using the character @, as in, for example, @toni. Hashtags (#) are used to denote subjects or categories, as in, for example #job. RT is used at the beginning of the tweet to indicate that the message is a so-called “retweet”, a repetition or reposting of a previous tweet. Twitter is still growing. On the Twitter Blog in March 2011, the company presented some statistics about its site, in a blog post titled ”#numbers.” [25]. In 2011, users send a billion tweets each week. The average number of tweets people sent per day in 2010 was 50 million. One year later, this number has grown to 140 million. For example, the number of tweets sent on March 11, 2011 was 177 million. The number of new accounts created on March 12, 2011 was 572,000, and the average number of new accounts per day over February 2011 was 460,000. From 2010 to 2011 the number of mobile users grew 182%. One of the main characteristics of Twitter is that tweets arrive in real time following the data stream model. In this model, data arrive at high speed, and T. Elomaa, J. Hollm´ en, and H. Mannila (Eds.): DS 2011, LNCS 6926, pp. 46–60, 2011. c Springer-Verlag Berlin Heidelberg 2011

MOA-TweetReader: Real-Time Analysis in Twitter Streaming Data

47

algorithms that process them must do so under very strict constraints of space and time. Data streams pose several challenges for data mining algorithm design. First, they must make use of limited resources (time and memory). Second, they must deal with data whose nature or distribution changes over time. The main Twitter data stream that provides all messages from every user in real-time is called Firehose and was made available to developers in 2010. This streaming data opens new challenging knowledge discovery issues. To deal with this large amount of data, streaming techniques are needed [4]. In this paper we present a software framework to analyse and mine Twitter data in real time using data stream mining methods. To the best of our knowledge, using the Twitter stream adaptively in real time in an open source data mining software project has not been done before. In Section 2 we present a new framework for mining tweets in real-time and we review brieﬂy the Twitter Streaming API. We present MOA-TweetReader in Section 3, and we present a new adaptive frequent item miner method. We discuss application of the new framework in Section 4: tweet frequent term monitoring and Twitter sentiment analysis. In Section 5 we discuss related work and Section 6 concludes the paper.

2

Real-Time Twitter Analysis Framework

We design a new general framework to mine tweets in real time adapting to changes in the stream. We are interested in – classifying tweets in real time: sentiment/polarity classiﬁcation and any other kind of classiﬁcation – detecting sudden and gradual changes in the frequencies of keywords – showing what are the changes in the most used terms Our main goal is to build a system able to train and test from the Twitter streaming API continuously. The input items are the tweets obtained from the Twitter stream. These tweets are preprocessed and converted by MOA-TweetReader to vectors of attributes or machine learning instances. The second component of the system is a learner trained with several instances, that is able to predict the class label of incoming unlabeled instances. Finally, a change detector monitors the predictions, and outputs an alarm signal when change is detected. The Twitter Application Programming Interface (API) [1] currently provides a Streaming API and two discrete REST APIs. The Streaming API [14] provides real-time access to Tweets in sampled and ﬁltered form. The API is HTTP based: GET, POST, and DELETE requests can be used to access the data. In Twitter terminology, individual messages describe the “status” of a user. The streaming API allows near real-time access to subsets of public status descriptions, including replies and mentions created by public accounts. Status descriptions created by protected accounts and all direct messages are not available. An interesting property of the streaming API is that it can ﬁlter status descriptions using quality metrics, which are inﬂuenced by frequent and repetitious status updates, etc.

48

A. Bifet, G. Holmes, and B. Pfahringer

Tweets

Adaptive Twitter Filter

Space Saving

Change Detector

Instances

Change Detection

Fig. 1. The MOA-TweetReader

The API uses basic HTTP authentication and requires a valid Twitter account. Data can be retrieved as XML and the more succinct JSON format. Parsing JSON data from the streaming API is simple: every object is returned on its own line, and ends with a carriage return. Two subsamples of the main Twitter stream (the “Firehose”) are the so-called “Spritzer” role and “Gardenhose” role respectively. The sampling rate is 5% for the Spritzer role and 15% for Gardenhose, which makes these streams slower, consuming less bandwidth.

3

MOA-TweetReader

We present MOA-TweetReader, a new method to read tweets in real time adaptively using the Twitter streaming API. Our goal is to build a system able to obtain tweets as sparse feature vectors from the Twitter streaming API in a continuous fashion. The main challenge is how to do that dynamically, since the frequency of terms changes over time, and learners can not store complete term statistics in memory. Therefore an adaptive frequent item miner will be employed to track the most recent frequent terms and their actual frequencies. Figure 1 shows the architecture of MOA-TweetReader. The input items are the tweets obtained from the Twitter stream. These tweets are preprocessed and converted by a tf-idf ﬁlter to sparse vectors of attributes or machine learning instances. The second component of the system is a frequent item miner that stores the frequency of the most frequent terms. Finally, a change detector monitors for changes in the frequencies of the items. 3.1

MOA-TweetReader Feature Generation Filter

MOA-TweetReader is able to use standard streaming machine learning methods. Tweets are list of words, and the adaptive Twitter ﬁlter will transform them to vectors of features, obtaining the most relevant ones.

MOA-TweetReader: Real-Time Analysis in Twitter Streaming Data

49

We use an incremental TF-IDF weighting scheme similar to the one used by Salton [28] : freqi,j N fi,j = , idfi = log freq n i ,j

(1)

where – fi,j is the frequency of term i in document j, which is the frequency of term i divided by the sum of the number of occurrences of all terms in document j, that is, the size of the document. – idfi is the inverse document frequency of term i. – N is the number of documents – ni is the number of documents where the term i appears The weight of each query term is given by: wi,q = fi,j · idfi 3.2

(2)

Change Detection

We use ADWIN [5] as a change detector, since it solves in a well-speciﬁed way the problem of tracking the average of real-valued numbers, but other change detectors [11] can be used. ADWIN (ADaptive sliding WINdow) keeps a variablelength window of recently seen items, with the property that the window has the maximal length statistically consistent with the hypothesis “there has been no change in the average value inside the window”. More precisely, an older fragment of the window is dropped if and only if there is enough evidence that its average value diﬀers from that of the rest of the window. This has two consequences: one, that change is reliably detected whenever the window shrinks; and two, that at any time the average over the existing window can be reliably taken as an estimation of the current average in the stream (barring a very small or very recent change that is still not statistically visible). The main technical result in [5] about the performance of ADWIN is a theorem, that provides bounds on the rate of false positives and false negatives for ADWIN. This theorem justiﬁes us in using ADWIN in two ways: – as a change detector, since ADWIN shrinks its window if and only if there has been a signiﬁcant change in recent times (with high probability) – as an estimator for the current average of the sequence it is reading since, with high probability, older parts of the window with a signiﬁcantly diﬀerent average are automatically dropped. ADWIN is parameter- and assumption-free in the sense that it automatically detects and adapts to the current rate of change. Its only parameter is a conﬁdence

50

A. Bifet, G. Holmes, and B. Pfahringer

bound δ, indicating how conﬁdent we want to be in the algorithm’s output, inherent to all algorithms dealing with random processes. Also important, ADWIN does not maintain the window explicitly, but compresses it using a variant of the exponential histogram technique in [9]. This means that it keeps a window of length W using only O(log W ) memory and O(log W ) processing time per item, rather than the O(W ) one expects from a na¨ıve implementation. Space Saving (Metwally et al. [20]) 1 2 3 4 5 6 7 8 9 10 11 12

T ←∅ for every term i do if i ∈ T then freq[i] ← freq[i] +1 else if |T | < k then Add a new item T ← T ∪ {i} freq[i] ← 1 else Replace the item with the lowest freq. j ← arg minj∈T freq[j] T ← T ∪ {i} \ {j} freq[j] ← freq[j] +1

Fig. 2. Algorithm Space Saving

3.3

Adaptive Frequent Item Miner for Data Streams

The most important part of this reader is the adaptive mechanism of feature generation. It is based on the Space Saving Algorithm. We base MOA-TweetReader on Space Saving since it has the best performance results compared with other frequent miners as reported in [19,7]. This method proposed by Metwally et al. [20] is very simple and has interesting and simple theoretical guarantees. Figure 2 shows its pseudocode. The algorithm maintains in memory k pairs of (item,count) elements, initialised by the ﬁrst k distinct elements and their counts. Every time a new item arrives, if it was monitored before, its count is incremented. If not, it replaces the item with the lowest count, and increments its count. This is done using space O(k), and the error of estimating item frequencies is at most n/k, where n is the number of elements in the stream. The main drawback of Space Saving is the lack of fast adaption to changes. Imagine that the currently most frequent elements become very infrequent due to such a change. They will still seem frequent for some time, since the elements being removed are always the ones with lower frequency. Changes over time in the frequency of the elements are not explicitly considered by Space Saving.

MOA-TweetReader: Real-Time Analysis in Twitter Streaming Data

51

Space Saving exponentially decayed (Cormode et al. [8]) 1 T ←∅ 2 for every term i with timestamp ti 3 do if i ∈ T 4 then freq[i] ← freq[i] + exp(λti ) 5 else if |T | < k 6 then Add a new item 7 T ← T ∪ {i} 8 freq[i] ← 1 9 else Replace the item with the lowest freq. 10 j ← arg minj∈T freq[j] 11 T ← T ∪ {i} \ {j} 12 freq[j] ← freq[j] + exp(λti ) Fig. 3. Algorithm Space Saving exponentially decayed Space Saving ADWIN 1 T ←∅ 2 for every term i with timestamp ti 3 do if i ∈ T 4 then Insert 1 into ADWIN[i] and 0 to other ADWINs 5 else if |T | < k 6 then Add a new item 7 T ← T ∪ {i} 8 Init ADWIN[i] 9 Insert 1 into ADWIN[i] and 0 to other ADWINs 10 else Replace the item with the lowest freq. 11 j ← arg minj∈T freq[j] 12 T ← T ∪ {i} \ {j} 13 Insert 1 into ADWIN[j] and 0 to other ADWINs Fig. 4. Algorithm Space Saving ADWIN

Cormode et al. [8] proposed an extension to Space Saving using exponentially decayed factors. The idea is very simple: instead of incrementing the counter by one, increment the counters using exp(λti ) where λ is a parameter and ti the current time. To get the frequency of a item j at time ti compute f reqj · exp(λti ). The strategy is very simple and has solid theoretical guarantees. Figure 3 shows its pseudocode. However, this improved version of Space Saving needs to set the parameter λ that depends on the scale of change. Instead of trying to estimate this scale of change, we propose to use an automatic adaptive estimator that does not need any such parameter that depends on the scale of change. We use ADWIN as an estimator and change detector with theoretical guarantees as explained in Section 3.2. Figure 4 shows its pseudocode.

52

4

A. Bifet, G. Holmes, and B. Pfahringer

Applications

We implement MOA-TweetReader as a component inside the open source data stream mining framework MOA. Massive Online Analysis (MOA) [6] is a system for online learning from data streams. All algorithms presented in this paper were implemented in the Java programming language by using the MOA software. The implementation of MOA-TweetReader allows to read tweets from the streaming API or from ﬁles. This second option permits to store tweets in ﬁles and then use them to analyse the data in more detail, not in real time. 4.1

Twitter Term Frequency Detection

One of the applications of this new system is to detect frequency of words in tweets, and changes in their distribution. We perform two experiments to show this. In the ﬁrst, we plot the distribution of frequency against ranking to check if it follows the Zipf distribution. In the second, we check how fast the diﬀerent frequent itemset miners adapt when they are mining a stream with an abrupt change in the middle of the stream. In the ﬁrst experiment, we use the English tweets in the Edinburgh corpus as a representative sample of the entire stream. The Edinburgh corpus [26] was collected over a period of two months using the Twitter streaming API. It contains 97 million tweets, and takes up 14 GB of disk space uncompressed. Each tweet has the following information: the timestamp of the tweet, an anonymised user name, the tweet’s text, and the posting method that was used. The corpus was collected between November 11th 2009 and February 1st 2010, using Twitter’s streaming API.

Fig. 5. Plot of frequency and ranking following a Zipf Distribution

MOA-TweetReader: Real-Time Analysis in Twitter Streaming Data

53

As an example, in Figure 5, we plot on logarithmic scales, the frequency of words versus their rank. We observe that they follow a Zipﬁan distribution: the frequency of any word is inversely proportional to its rank. To compare Space Saving, Space Saving using exponential decayed factors, and Space Saving ADWIN, we perform an experimental evaluation using synthetic data to compare the frequency estimation with known ground truth. Our synthetic tweet generator simulates real tweets. The main important characteristic is that the frequency of the new tweets is generated following a Zipﬁan distribution. First, we build a table with words and normalised frequencies, and then we generate new tweets using the words from this table and their frequencies. To compare the performance of the diﬀerent Space Saving methods, we use the Hellinger distance between two probability distributions, deﬁned as 2 f (i) − g(i) H(f, g) = i

Figure 6 shows the plot of the Hellinger distance on a stream of 100,000 tweets generated artiﬁcially with a concept drift in the middle of the stream, where 2000 word frequencies are swapped. We observe that Space Saving using exponential decayed factors depends on the λ value used, so for each data stream the optimal value of λ may be diﬀerent. Space Saving needs some instances to recover, and the main advantage of Space Saving ADWIN is that it is able to adapt automatically and ﬁnd the optimal rate of adaption by itself.

Fig. 6. Hellinger distance comparison

4.2

Twitter Sentiment Analysis

Sentiment analysis can be cast as a classiﬁcation problem where the task is to classify messages into two categories depending on whether they convey positive or negative feelings; see [24] for a survey of sentiment analysis, and [18] for opinion mining techniques.

54

A. Bifet, G. Holmes, and B. Pfahringer

Twitter sentiment analysis is not an easy task because a tweet can contain a signiﬁcant amount of information in very compressed form, and simultaneously carry positive and negative feelings. Consider the following example: ‘‘ I just saw that you’re facing Toyota soon. I’m so upset that I won’t get to see it. :-( I’m so proud of you, though! :-) ’’ Also, some tweets may contain sarcasm as in the following example: ‘‘ I’ll probably be late for work. The first day I have to work with my new boss. Marvellous! ’’ Table 1. List of positive and negative emoticons Positive Emoticons Negative Emoticons :) :( :-) :-( :) :( :D =)

To build classiﬁers for sentiment analysis, we need to collect training data so that we can apply appropriate learning algorithms. Labeling tweets manually as positive or negative is a laborious and expensive, if not impossible, task. However, a signiﬁcant advantage of Twitter data is that many tweets have author-provided sentiment indicators: changing sentiment is implicit in the use of various types of emoticons. Hence we may use these to label our training data. Smileys or emoticons are visual cues that are associated with emotional states [27]. They are constructed using the characters available on a standard keyboard, representing a facial expression of emotion. Table 1 shows some examples. When the author of a tweet uses an emoticon, they are annotating their own text with an emotional state. Annotated tweets can be used to train a sentiment classiﬁer. The 2010 Toyota Crisis. As an example of Twitter sentiment analysis, and the need to mine sentiments in real-time, we would like to show the case of the crisis of Toyota, the world’s largest car manufacturer, during 2009 and 2010. Table 2 shows the timeline of the crisis of Toyota during the end of 2009 and beginning of 2010. It is a summary from [17,15]. During these days, it seems that Toyota had problems with accelerator pedals, and had to recall millions of cars to check that they were working properly. In the book “Toyota under Fire” [17], Akio Toyoda, president of Toyota, identiﬁes the gap in understanding of local conditions and urgency between regions and headquarters as a major contributor to the evolution of the crisis:

MOA-TweetReader: Real-Time Analysis in Twitter Streaming Data

55

Table 2. Toyota timeline of its crisis during 2009 and 2010 June

Akio Toyoda, 53, grandson of Toyota’s founder, is named president, replacing Watanabe, 67. Yoshi Inaba is called out of retirement to head Toyota’s U.S. operations. August Fatal crash in Santee, California, of a 2009 model year Lexus ES350. Investigators ﬁnd pedal entrapment by a ﬂoormat may have contributed to the crash. September NHTSA oﬃcials tell Toyota they expect a recall to address possible defects in pedal design in addition to ﬂoormats. Toyota tells agency it will recall the pedals. October Toyota recalls 3.8 million vehicles in the United States to address the risk that ﬂoormats could trap the accelerator pedal in an open position. The recall is expanded in January 2010 to more than 5 million vehicles. December 15 NHTSA oﬃcials meet Toyota executives in Japan seeking prompt action on safety issues. Toyota commits to improving its responsiveness. December 31 Toyota accounted for 33 percent of all unintended acceleration complaints ﬁled with NHTSA in 2009. January 16 Toyota informs NHTSA that accelerator pedals made by supplier CTS Corp may have a dangerous ”sticking” defect. January 19 At a meeting in Washington including Inaba and U.S. sales chief Jim Lentz, NHTSA asks Toyota to take prompt action. Hours later Toyota tells NHTSA it will issue a recall. January 21 Toyota announces recall for about 2.3 million Toyota models to ﬁx sticky pedals. January 25 NHTSA tells Toyota it is must stop selling vehicles that have acknowledged defects even if it does not have a remedy. January 26 Toyota halts U.S. sales of eight models, including its best-selling Camry and Corolla sedans, and says it will halt production for the ﬁrst week of February. January 28 Toyota meets with NHTSA to review its pedal ﬁx. NHTSA says it has no objections to the ﬁx. January 29 NHTSA opens investigation into CTS pedals. NHTSA asks CTS if it sold pedal to other carmakers and when it discovered reports of problems. February 2 Toyota reports a 16 percent drop in January U.S. sales. Monthly U.S. sales drop below 100,000 for the ﬁrst time in more than a decade and Toyota’s U.S. market share falls to its lowest level since January 2006. February 2 NHTSA renews investigation into Toyota’s electronic throttle control system. U.S. Transportation Secretary Ray LaHood says, ”While Toyota is taking responsible action now, it unfortunately took an enormous eﬀort to get to this point.” Toyota says it will cooperate with the probe. February 3 LaHood warns recalled Toyota owners to stop driving, then withdraws his remarks, saying it was a misstatement. Toyota says it is examining braking complaints about its 2010 model Prius hybrid. February 4 NHTSA opens investigation into at least 124 consumer complaints about brakes on Toyota Prius hybrids. February 5 After keeping a low proﬁle for nearly two weeks, President Akio Toyoda appears at a news conference to apologize for safety problems. He announces plans to bring in a task force, including outside analysts to review quality. Toyota considers a recall for Prius braking issue. February 9 Toyota announces recall of nearly 500,000 new Prius and Lexus-brand hybrid cars globally for braking problems. Akio Toyoda says he may visit the United States in the third week of February. February 22 Toyota says it received a federal grand jury subpoena from the Southern District of New York for documents related to unintended acceleration in some of its vehicles and the Prius braking system. It also disclosed that the U.S. Securities and Exchange Commission requested documents related to unintended acceleration and subpoenaed documents related to the automaker’s disclosure policies and practices.

56

A. Bifet, G. Holmes, and B. Pfahringer

There was a gap between the time that our U.S. colleagues realised that this was an urgent situation and the time that we realised here in Japan that there was as urgent situation going on in the U.S. It took three months for us to recognise that this had turned into a crisis. In Japan, unfortunately, until the middle of January we did not think that this was really a crisis. Also, Nancy Fein, who was running the call centre, discovered that as a result of the crisis, there is far more interest in the data that centre is collecting: People are asking for our data now. Our product quality department uses it, public aﬀair uses it, sales uses it, the legal department uses it, and our plants and engineering are using it for kaizen. We think that looking at Twitter data in real time can help people to understand what is happening, what people are thinking about brands, organisations and products, and more importantly, how they feel about them. Using the Edinburgh corpus [26] collected between November 11th 2009 and February 1st 2010, we apply our new methods to get some insights to the Toyota crisis. The number of tweets referring to Toyota is 4381. Applying our new Space Saving ADWIN is possible to detect the following changes in terms of frequencies, see Table 3. Table 3. Frequency changes detected Term Before After Diﬀ gas 0.122 0.484 0.363 pedals 0.129 0.438 0.309 wonder 0.017 0.214 0.198 problem 0.163 0.357 0.194 good 0.016 0.205 0.190 recalling 0.012 0.106 0.095 gm 0.011 0.089 0.077 #heard on the street 0.040 0.113 0.072 social 0.031 0.099 0.068 sticking 0.070 0.125 0.055 ﬁx 0.026 0.076 0.050 popularity 0.016 0.037 0.021 love 0.017 0.024 0.008

To see the evolution of positive and negative tweets, we train and test a Hoeﬀding tree learner (Figure 7). The most well-known tree decision tree learner for data streams is the Hoeﬀding tree algorithm [10]. It employs a pre-pruning strategy based on the Hoeﬀding bound to incrementally grow a decision tree. A node is expanded by splitting as soon as there is suﬃcient statistical evidence, based on the data seen so far, to support the split and this decision is based on the distribution-independent Hoeﬀding bound.

MOA-TweetReader: Real-Time Analysis in Twitter Streaming Data

57

What we see in Figure 7, is that there is a clear correlation between the sentiments in the tweets available in the Twitter streaming API, and the timeline of the crisis of Toyota. It is very clear that around Christmas 2009 positive sentiment in tweets towards Toyota plunged below 50%. Looking at the changes in the frequencies of words, we can understand why these changes are happening. Almost every second tweet mentioning Toyota suddenly includes “gas” and “pedals”. A tool like MOA-TweetReader would have helped Toyota to understand the crisis sooner and to respond more appropriately.

Fig. 7. Positive sentiment detection on Toyota tweets retrieved from Twitter

5

Related Work

In the knowledge discovery context, there are two fundamental data mining tasks that can be considered in conjunction with Twitter data: (a) graph mining based on analysis of the links amongst messages, and (b) text mining based on analysis of the messages’ actual text. There are a number of interesting tasks that have been tackled using Twitter text mining: sentiment analysis, which is the application we consider in this paper, classiﬁcation of tweets into categories, clustering of tweets and trending topic detection. Considering sentiment analysis, O’Connor et al. [22] found that surveys of consumer conﬁdence and political opinion correlate with sentiment word frequencies in tweets, and propose text stream mining as a substitute for traditional polling. Jansen et al. [13] discuss the implications for organisations of using micro-blogging as part of their marketing strategy. Pak et al. [23] used classiﬁcation based on the multinomial na¨ıve Bayes classiﬁer for sentiment analysis. Go et al. [12] compared multinomial na¨ıve Bayes, a maximum entropy classiﬁer, and a linear support vector machine; they all exhibited broadly comparable accuracy on their test data, but small diﬀerences could be observed depending on the features used. Considering sentiment analysis on data streams, [4] was the ﬁrst work that discussed the challenges that Twitter streaming data poses, and proposed the

58

A. Bifet, G. Holmes, and B. Pfahringer

sliding window Kappa statistic as an evaluation metric for data streams. Considering all tests performed and ease of interpretability, this work recommended the SGD-based model, used with an appropriate learning rate, for the Twitter data stream. An advantage of the SGD-based model is that changes in its weights can be inspected to gain insight into changing properties of the data stream. Monitoring these coeﬃcients, which determine how strongly absence/presence of the corresponding word inﬂuences the model’s prediction of negative or positive sentiment, is also an eﬃcient way to detect changes in the population’s opinion. SentiWordNet [2] is a lexical resource for opinion mining. It is based on WordNet [21], a large lexical database of English. In WordNet, nouns, verbs, adjectives and adverbs are grouped into sets of synonyms (synsets), each expressing a distinct concept. SentiWordNet assigns to each synset of WordNet three sentiment scores: positivity, negativity, objectivity. This lexical resource can be used to predict tweet polarities. Lampos et al. [16] presented a framework for monitoring the diﬀusion of Inﬂuenza-like Illness (ILI) in several regions of the United Kingdom using tweets. They used oﬃcial ILI rates from the UK Health Protection Agency (HPA) as ground truth. The main diﬀerences with our system is that their system uses the Twitter Search API, non the streaming one; it stores tweets in a MySQL database; and it uses a non-online classiﬁer, BOLASSO [3], the boot-strapped version of LASSO.

6

Conclusions

Twitter streaming data can potentially enable any user to discover what is happening in the world at any given moment in time. As the Twitter Streaming API delivers a large quantity of tweets in real time, we proposed MOA-TweetReader, a new system to perform twitter stream mining in real time using a new adaptive frequent item miner for data streams. Space Saving ADWIN was introduced as a parameter-free variant of the standard Space Saving algorithm that can adapt more quickly to changes in word frequencies. We discussed some applications of the new framework in frequent item mining and sentiment analysis. As future work, we would like to apply MOA-TweetReader to other classiﬁcation tasks using tweets retrieved in real-time.

References 1. Twitter API (2010), http://apiwiki.twitter.com/ 2. Baccianella, S., Esuli, A., Sebastiani, F.: Sentiwordnet 3.0: An enhanced lexical resource for sentiment analysis and opinion mining. In: LREC. European Language Resources Association (2010) 3. Bach, F.R.: Bolasso: model consistent lasso estimation through the bootstrap. In: ICML, pp. 33–40 (2008)

MOA-TweetReader: Real-Time Analysis in Twitter Streaming Data

59

4. Bifet, A., Frank, E.: Sentiment knowledge discovery in twitter streaming data. In: Pfahringer, B., Holmes, G., Hoﬀmann, A. (eds.) DS 2010. LNCS, vol. 6332, pp. 1–15. Springer, Heidelberg (2010) 5. Bifet, A., Gavald` a, R.: Learning from time-changing data with adaptive windowing. In: SDM (2007) 6. Bifet, A., Holmes, G., Kirkby, R., Pfahringer, B.: MOA: Massive Online Analysis. Journal of Machine Learning Research (2010), http://moa.cs.waikato.ac.nz/ 7. Cormode, G., Hadjieleftheriou, M.: Finding frequent items in data streams. PVLDB 1(2), 1530–1541 (2008) 8. Cormode, G., Korn, F., Tirthapura, S.: Exponentially decayed aggregates on data streams. In: Proceedings of the 24th International Conference on Data Engineering, ICDE 2008, Canc´ un, M´exico, April 7-12, pp. 1379–1381 (2008) 9. Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining stream statistics over sliding windows. SIAM Journal on Computing 14(1), 27–45 (2002) 10. Domingos, P., Hulten, G.: Mining high-speed data streams. In: Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 71–80 (2000) 11. Gama, J., Medas, P., Castillo, G., Rodrigues, P.P.: Learning with drift detection. In: Bazzan, A.L.C., Labidi, S. (eds.) SBIA 2004. LNCS (LNAI), vol. 3171, pp. 286–295. Springer, Heidelberg (2004) 12. Go, A., Huang, L., Bhayani, R.: Twitter sentiment classiﬁcation using distant supervision. In: CS224N Project Report, Stanford (2009) 13. Jansen, B.J., Zhang, M., Sobel, K., Chowdury, A.: Micro-blogging as online word of mouth branding. In: Proceedings of the 27th International Conference Extended Abstracts on Human Factors in Computing Systems, pp. 3859–3864 (2009) 14. Kalucki, J.: Twitter streaming API (2010), http://apiwiki.twitter.com/Streaming-API-Documentation 15. Kim, S., Bailey, D., Orr, B.: Timeline: Toyota from rise to recall crisis, hearings. Reuters Blog Article (2010), http://www.reuters.com/article/2010/02/23/us-toyota-timeline -idUSTRE61M0IT20100223 16. Lampos, V., Bie, T.D., Cristianini, N.: Flu detector - tracking epidemics on twitter. In: Balc´ azar, J.L., Bonchi, F., Gionis, A., Sebag, M. (eds.) ECML PKDD 2010. LNCS, vol. 6323, pp. 599–602. Springer, Heidelberg (2010) 17. Liker, J.K., Ogden, T.N.: Toyota Under Fire: Lessons for Turning Crisis into Opportunity. McGraw-Hill, New York (2011) 18. Liu, B.: Web data mining; Exploring hyperlinks, contents, and usage data. Springer, Heidelberg (2006) 19. Liu, H., Lin, Y., Han, J.: Methods for mining frequent items in data streams: an overview. Knowl. Inf. Syst. 26(1), 1–30 (2011) 20. Metwally, A., Agrawal, D., Abbadi, A.E.: Eﬃcient computation of frequent and top-k elements in data streams. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 398–412. Springer, Heidelberg (2005) 21. Miller, G.A., Fellbaum, C.: Wordnet then and now. Language Resources and Evaluation 41(2), 209–214 (2007) 22. O’Connor, B., Balasubramanyan, R., Routledge, B.R., Smith, N.A.: From tweets to polls: Linking text sentiment to public opinion time series. In: Proceedings of the International AAAI Conference on Weblogs and Social Media, pp. 122–129 (2010) 23. Pak, A., Paroubek, P.: Twitter as a corpus for sentiment analysis and opinion mining. In: Proceedings of the Seventh Conference on International Language Resources and Evaluation, pp. 1320–1326 (2010)

60

A. Bifet, G. Holmes, and B. Pfahringer

24. Pang, B., Lee, L.: Opinion mining and sentiment analysis. Foundations and Trends in Information Retrieval 2(1-2), 1–135 (2008) 25. Penner, C.: #numbers. Twitter Blog Article (2011), http://blog.twitter.com/2011/03/numbers.html 26. Petrovic, S., Osborne, M., Lavrenko, V.: The Edinburgh twitter corpus. In: #SocialMedia Workshop: Computational Linguistics in a World of Social Media, pp. 25–26 (2010) 27. Read, J.: Using emoticons to reduce dependency in machine learning techniques for sentiment classiﬁcation. In: Proceedings of the ACL Student Research Workshop, pp. 43–48 (2005) 28. Salton, G., Buckley, C.: Term-weighting approaches in automatic text retrieval. Inf. Process. Manage. 24(5), 513–523 (1988)

Application of Semantic Kernels to Literature-Based Gene Function Annotation Mathieu Blondel, Kazuhiro Seki, and Kuniaki Uehara Kobe University, 1-1 Rokkodai, Nada, Kobe 657-8501, Japan [email protected]

Abstract. In recent years, a number of machine learning approaches to literature-based gene function annotation have been proposed. However, due to issues such as lack of labeled data, class imbalance and computational cost, they have usually been unable to surpass simpler approaches based on string-matching. In this paper, we investigate the use of semantic kernels as a way to address the task’s inherent data scarcity and we propose a simple yet eﬀective solution to deal with class imbalance. From experiments on the TREC Genomics Track data, our approach achieves better F1 -score than two state-of-the-art approaches based on string-matching and cross-species information. Keywords: gene annotation, text classiﬁcation, kernel methods.

1

Introduction

Since the completion of the Human Genome Project, a large number of studies have been conducted to identify the role of individual genes, which would help us understand critical mechanisms of the human body, such as aging and disorders. However, the active research in the domain has been producing numerous publications. As a result, it is extremely labor-intensive for biomedical researchers alone to collect the information relevant to their need, since obtaining such information requires intensive reading. Therefore, researchers can potentially be unaware of rich intellectual resources, for example, containing evidence regarding “the functions of gene X” or “the genes having function Y”. To remedy this problem, a number of organizations have been working on annotating each gene of model organisms with a controlled vocabulary, called Gene Ontology (GO) terms, based on the contents of the published scientiﬁc articles. GO is deﬁned as a directed acyclic graph (DAG) and is organized under three top-level nodes: molecular function (MF), cellular component (CC) and biological process (BP). Currently there are nearly 30,000 GO terms in total. The GO annotation eﬀort has enabled uniform access to diﬀerent model organism databases, including FlyBase, Mouse Genome Database (MGD) and Saccharomyces Genome Database, through a common vocabulary. However, the annotation requires trained human experts with extensive domain knowledge. T. Elomaa, J. Hollm´ en, and H. Mannila (Eds.): DS 2011, LNCS 6926, pp. 61–75, 2011. c Springer-Verlag Berlin Heidelberg 2011

62

M. Blondel, K. Seki, and K. Uehara

With limited human resources and the ever-growing literature, it was reported that it would never be completed at the current rate of production [1]. Motivated with this background, we propose a principled machine learning approach, allowing us to leverage annotated articles from the scientiﬁc literature in order to learn how to automatically annotate the function of genes mentioned in new articles. In particular, we report on our experiments with semantic kernels, which, as we shall see, are an eﬀective way to address data scarcity, yet are computationally eﬃcient. Moreover, existing methods for automatic GO annotation usually neglect the so-called class imbalance problem. We propose a simple but eﬀective method to deal with the problem. From experiments on the Genomics Track data, it will be shown that our approach improves upon two existing state-of-the-art methods based on string-matching. After reviewing the related work in Section 2, we proceed with a description of the proposed GO annotation system in Section 3. We provide background on kernel classiﬁers in the context of this system in Section 4 as well on semantic kernels in Section 5. We assert the performance of our approach through extensive experiments in Section 6 and, ﬁnally, we conclude and give orientations for future work in Section 7.

2

Related Work

Due to the large number of genes, gene functions and scientiﬁc articles, manual GO annotation is inevitably labor intensive. In addition, because of the highly specialized contents, it requires skilled professionals with expertise of the domain. To alleviate the burden, TREC 2004 Genomics Track [6] and BioCreative [2] targeted automatic GO domain/term annotation. The Genomics Track attempted to automate the process of assigning the ﬁrst level of GO (i.e., MF, CC, BP), called “GO domains”. The participants of the workshop were given a mouse gene and an article in which the gene appears and were expected to annotate the gene with zero to three GO domains, based on the contents of the article. For this task, Seki and Mostafa [15] developed an approach featuring ﬂexible gene mention extraction techniques based on a synonym dictionary and approximate name matching. They used a gene-centered vector representation by extracting fragments of the articles mentioning the target gene and applied k nearest neighbor (kNN) classiﬁers with supervised term weighting. In contrast to the Genomics Track, which was only targeting GO domains, BioCreative aimed at assigning speciﬁc GO terms to human genes. Among others, Ray and Craven [12] looked at the occurrences of GO terms and their related terms to assign GO terms with a Naive Bayes classiﬁer. Chiang and Yu [4] applied a sentence alignment procedure to learn sentence patterns such as “gene product plays an important role in function” and also employed a Naive Bayes classiﬁer to estimate the probability that a sentence indicates GO term membership. Overall, participants from the Genomics Track reported the eﬀectiveness of supervised classiﬁcation techniques while participants from BioCreative mainly adopted string-matching techniques. These diﬀerent strategies can be attributed

Application of Semantic Kernels

63

to the fact that Genomics Track only considered three classes (i.e., GO domains) while BioCreative targeted the GO terms, which can amount to up to 30,000. One striking characteristic of the existing literature-based GO term annotation methods is their quite low accuracy rates (around 0.2). This suggests that GO term annotation is a challenging task and that it is diﬃcult to improve upon existing methods. The diﬃculty of the task can be explained by several reasons. Among them is the inherent diﬃculty of scientiﬁc natural language. GO terms usually have several synonyms, therefore GO tokens may not explicitly appear in the article. Even when they do appear, the presence of tokens does not necessarily imply that the gene need be annotated with the GO term. For this reason, existing methods solely based on string matching usually have a high false positive rate, resulting in poor precision. Another reason for the poor accuracy is due to the great number of GO terms. Inevitably, there are GO terms which have only few training examples and GO terms which have many more training examples than others. This is the socalled class imbalance problem and need be carefully addressed in order to learn reliable classiﬁers. To overcome these challenges, researchers have been working on combining textual information with other types of evidence. Stoica and Hearst [17] took advantage of orthologs of a given gene and limited the candidate search to GO terms already associated with them. Orthologs are genes from diﬀerent species rooted from the same gene of their common ancestor and thus often have the same functions. In addition, they used GO term co-annotation to remove illogical candidates. Seki et al. [14] expanded on this idea and dynamically built classiﬁers based on the training data under ortholog constraints. Si et al. [16], on the other hand, computed ﬁve scores from three kinds of evidence (textual information, prior knowledge and biological sequence similarity) and used a logistic regression to combine them. Blending diﬀerent kinds of evidence using ensemble methods is clearly an important line of research. However, it is important to improve the performance of purely literature-based prediction too, since certain kinds of information such as orthologs are not always available for certain genes or certain species. In this paper, we report on our experiments with semantic kernels. We show that they are computationally eﬃcient and lend themselves to embedding additional useful topic information. From experiments on the Genomics Track data, our approach performs better than two existing state-of-the-art approaches based on string-matching and cross-species information.

3

System Description

The goal of this research is to design a system that can leverage annotated articles from the scientiﬁc literature in order to learn how to automatically map the function of genes mentioned in new articles to appropriate GO terms. More precisely, for a new non-annotated article, we would like to be able to answer the question: does the article contain supporting evidence that gene X has GO term Y? Our system is divided into a learning phase and a prediction phase, as

64

M. Blondel, K. Seki, and K. Uehara

depicted in Figure 1. Both are preceded by information extraction, preprocessing and bag-of-words conversion. The following provides a brief description of the system components. Information extraction. Articles are ﬁrst represented as strings by extracting and concatenating three kinds of textual evidence: 1) relevant text fragments extracted by a ﬂexible gene mention matching technique, when the full text is available (following Seki and Mostafa [15]), 2) article title and abstract, as they are usually information-rich and summarize the main ﬁndings described in the article, 3) description of the GO terms an article is annotated with (at learning time only). Pre-processing and Bag-of-words. Subsequently, article strings are preprocessed and converted to the popular bag-of-words representation. Formally, let xi = (xi1 , . . . , xiD ) ∈ RD be such an article. xij is the number of occurrences of the j th word and D is the vocabulary size (total number of unique words). Learning. Gene function annotation is a multi-label classiﬁcation problem, namely each article instance is associated with a set of labels (including the empty set). There are several ways to build multi-label classiﬁers. In this research, we use the popular one-vs-all scheme [13], which in the context of this research, consists in building one binary classiﬁer per GO term. This method has several advantages including simplicity, interpretability (what features are discriminative for the GO term?) and easy parallelization (since each classiﬁer is independent from one another). Formally, we note that an article xi is associated with a label vector yi = (yi1 , · · · , yiM ) ∈ {−1, +1}M , where M is the number of GO terms. yic = +1 means that the cth GO term is assigned to xi , while yic = −1 means that it is not.

Annotated articles

New article

Information extraction

Information extraction

Pre-processing

Pre-processing

Bag-of-words conversion

Bag-of-words conversion

Learning

Prediction

Classiﬁers

Post-processing GO Terms

Fig. 1. System overview: the learning (left) and prediction (right) phases

Application of Semantic Kernels

65

Prediction and Post-processing. The learned classiﬁers can be employed to predict what GO terms a given gene has, according to the supporting evidence contained in a new non-annotated article. However, because of the one-vs-all scheme that we use, prediction is a succession of binary decisions and the resulting set of GO term candidates may contain GO terms which are inconsistent with one another. For this reason, we introduce post-processing of the GO term candidates. Since the GO terms belong to the Gene Ontology, it is possible to take advantage of the DAG structure for post-processing. When two GO term candidates have an ancestor relationship, we only keep the most likely candidate of the two. Additionally, we also experiment with ortholog-based post-processing in Section 6.3.

4

Kernel Classifiers

As mentioned previously, this paper investigates the use semantic kernels as a way to address lack of data. In this section, we provide background on kernel classiﬁers in the context of our system. 4.1

Regularized Linear Classifiers

Given an article x∗ , we deﬁne sc : RD → R, the score function of the cth GO term. (1) sc (x∗ ) = β c · φ(x∗ ) βc = (βc1 , . . . , βcD ) ∈ RD is the weight/prototype vector of the cth GO term. Intuitively, a strong positive (respectively, negative) weight βcj means that the j th feature is a strong membership (respectively, non-membership) indicator of the GO term. This is very useful for interpretability, as researchers can gain insights from the model. φ is a function that maps inputs to a higher dimensional space and we will have φ(x) = x in the linear case. To determine the membership of an article x∗ to the cth GO term, we deﬁne fc : RD → {−1, +1} the prediction function of the cth GO term. fc (x∗ ) = sign(sc (x∗ ))

(2)

sign(a) is a function which outputs +1 when a > 0 and −1 otherwise. Note that fc does not require any threshold to be determined. Given a set of articles x1 , . . . , xN and their associated label vectors y1 , . . . , yN , the goal of the learning algorithm is to estimate the weight vector β c which minimizes the following objective function. Lc (βc ) = Cc

N

1 (yic , sc (xi )) + βc 2 2 i=1

(3)

Cc is the hyperparameter of the cth GO term. It controls the complexity of the model and reduces the risk of overﬁtting. Cc → ∞ corresponds to no regularization, while Cc = 0 corresponds to inﬁnite regularization. It is usually estimated

66

M. Blondel, K. Seki, and K. Uehara

through cross-validation. is a function which measures the “loss” of making wrong predictions. It is well known that the hinge loss, log loss and squared error loss result in the solutions of support vector machines (SVM), logistic regression (LR) and regularized least square classiﬁer (RLSC), respectively. These are the three regularized linear models that we adopt and compare in this research. See elsewhere for a discussion of the diﬀerent optimization strategies. 4.2

Kernelization

The representer theorem states that the solution to an optimization problem of the nature of Equation (3) can be written in the form of a linear combination of the training instances. N βc = αci φ(xi ) (4) i=1

Therefore, given an article x∗ , we can rewrite the score sc (x∗ ) of the cth GO term. N N sc (x∗ ) = αci φ(xi )φ(x∗ ) = αci K(xi , x∗ ) (5) i=1

i=1

K is the kernel function and the xi for which αci = 0 are the support vectors of the cth GO term. 4.3

Class Imbalance Handling

As we emphasized before, there are many GO terms and manual GO term annotation is very labor-intensive. Inevitably, this results in GO terms associated with only few articles and GO terms with many more articles than others. Moreover, the one-vs-all scheme that we employ implies that for each binary classiﬁer, there are several orders of magnitude more negative than positive examples. Existing methods usually neglect this class imbalance problem. However, in our experience, it is crucial to deal with this issue in order to obtain reliable classiﬁers. We employ a simple heuristic inspired by Osuna et al. [11] which consists in applying a stronger weight to positive examples than to negative examples. Put diﬀerently, we apply a stronger regularization to the negative class than to the positive class, thereby reducing the inﬂuence of the many negative examples. Concretely, we replace the objective function from Equation (3) by the following: Lc (β c ) = Cc

N

1 μic (yic , sc (xi )) + βc 2 2 i=1

μic =

n¬c /nc , if yic = +1 1, if yic = −1

(6)

(7)

Application of Semantic Kernels

67

where μic is equal to the ratio between n¬c (the number of examples which are not labeled with the cth GO term) and nc (the number of examples which are labeled with the cth GO term) when xi is annotated with the cth GO term and to 1 otherwise. Formally, we deﬁne nc = |{xi |yic = +1}| and n¬c = N −nc . Since n¬c > nc , this consists in assigning a stronger weight to positive examples than to negative examples. In our experience, this simple heuristic produces better results than other techniques such as negative example downsampling. 4.4

Hyperparameter Tuning

The objective function in Equation (7) includes a hyperparameter Cc , which controls the complexity of the model and reduces the risk of overﬁtting. In practice, it is very important to optimize it in order to obtain the best performance possible. However, we need to take into account the fact that, for each GO term, there are many more negative examples than positive examples. For that purpose, we employ a form of stratiﬁed cross-validation and proceed as follows. We build a validation set by setting aside one positive example and by setting aside negative examples such that the positive-negative example ratio is respected. We train a classiﬁer with the rest of the data and measure the F1 -score with the validation set. We repeat until all the positive examples have been used and select the parameter Cc which, on average, obtained the best F1 -score.

5

Latent Topic Kernels

As we mentioned previously, examples are formed by concatenating three kinds of textual evidence: relevant fragments, abstracts/titles and GO term descriptions. This results in very sparse vectors which contain on average less than 300 unique words. Unlike long documents, we can therefore expect the document “topics” to be quite concentrated and related to the context of sentences which are relevant to GO term prediction. We provide background on pLSA and its kernels in this section. Since they are estimated from all the articles, we can expect the latent topics used in these kernels to smooth the probability of words based on their context. This is especially useful for GO terms which are annotated with only few articles. 5.1

pLSA Background

Probabilistic Latent Semantic Analysis (pLSA) [8] is a probabilistic framework that can uncover latent “topics” from the document-term matrix. Documents which share frequently co-occurring terms share common topics, even if they have no terms in common. In the latent topic model of pLSA, documents and words are assumed to be independent conditioned on the state of the associated latent topic. Since the number of topics is typically smaller than the number of documents/words in the collection, topics eﬀectively act as bottlenecks in predicting words conditioned on the context of a particular document.

68

M. Blondel, K. Seki, and K. Uehara

x1

P(

xi | zk )

z1

x2

|z k P (w j

)

w1 w2

z2

x3

w3 x4 Topics

Documents

Words

Fig. 2. The pLSA graphical model, with N = 4 articles, K = 2 topics and D = 3 words. Since they are estimated from all the articles, we can expect the latent topics used in the pLSA-kernels to smooth the probability of words based on their context. This is especially useful for GO terms which are annotated with only few articles.

As depicted in Figure 2, pLSA consists of three sets of parameters: {P (wj |zk )}j,k (probability of the j th word given the k th latent topic), {P (xi |zk )}i,k (probability of the ith article given the k th latent topic) and {P (zk )}k (probability of the k th latent topic). pLSA is an unsupervised model and the standard procedure for parameter estimation is Expectation Maximization (EM). See the work of Hofmann [8] for more details. EM is known to be sensitive to initializing conditions and prone to local extrema. For this reason, we average our results from ﬁve diﬀerent random initializations. We also tried tempered EM [8] but the convergence was slower and we did not get better results than by simple averaging. 5.2

pLSA Kernels

Jaakkola and Haussler [10] introduced the Fisher kernel as a generic mechanism for incorporating generative models into discriminative classiﬁers. This kernel is theoretically motivated from the point of view of information geometry and is invariant to any invertible and diﬀerentiable transformation of the parameters. Hofmann [7] employed the Fisher kernel as a framework to derive two kernels for pLSA: P (zk |xi )P (zk |xn )/P (zk ) (8) Kz (xi , xn ) = Kw (xi , xn ) =

j

k

Pˆ (wj |xi )Pˆ (wj |xn ) P (zk |xi , wj )P (zk |xn , wj ) k

P (wj |zk )

(9)

Application of Semantic Kernels

69

where Pˆ (wj |xi ) = xij / j xij are the empirical word probabilities, computed from the word counts. Hofmann showed experimentally that they could eﬀectively improve classiﬁcation accuracy by employing unlabeled data when the amount of labeled data is limited. Although their derivation was theoretically motivated, the two kernels have an intuitive interpretation. On one hand, Kz compares two articles xi and xn based on their topic overlap. On the other hand, Kw compares two articles based on their empirical word distribution, but the similarity is weighted by their respective posterior probabilities overlap (right-hand side of the equation). Since Kz and Kw can be rewritten as inner products, the corresponding feature mapping functions φz and φw exist. φz (x)k = P (zk |x)/ P (zk ) (10) φw (x)j,k = Pˆ (wj |x)P (zk |x, wj )/

P (wj |zk )

(11)

φz outputs a K-dimensional dense vector and φw outputs a D × K-dimensional sparse vector. Basically, the fact that these functions exist means that, even though we are using a pLSA kernel, we can use a linear SVM implementation to train our classiﬁers and make predictions. We discuss the eﬃciency of using a linear SVM implementation over a kernel SVM implementation in section 6.4. Since pLSA is an unsupervised model, as a byproduct, the two kernels allow classiﬁers to take advantage of additional unlabeled data (semi-supervised learning) and to be tailored to a particular test set (transductive learning). We explore these two particular settings in Section 6.2. Following Hofmann, we use the sum of the two pLSA-based kernels. We use the notation @K to indicate that the underlying pLSA model was trained with K topics. @K @K (xi , xn ) = Kz@K (xi , xn ) + Kw (xi , xn ) (12) Kz+w Note that, in feature space, adding Kz and Kw is equivalent to concatenating the outputs of φz and φw .

6

Experiments

For evaluation, following Seki et al. [14], we used the test dataset provided for the TREC 2004 Genomics Track and supplemented it by GO term information.1 The resulting dataset consists of 863 test instances. Each instance is a pair represented by a PubMed ID article and a gene mentioned in the article. There are on average 2.14 GO terms per test instance (from 543 GO terms in total). 1

The reason for not using the BioCreative dataset is two-fold. First, although the dataset was made public, the article full texts were only provided to the workshop participants. Second, the predictions submitted by the participants were evaluated by human experts, which means that the dataset can not be used to fairly compare new approaches.

70

M. Blondel, K. Seki, and K. Uehara

Table 1. Classiﬁcation performance comparison of Naive Bayes (NB), Support Vector Machines (SVM), Logistic Regression (LR) and Regularized Least-Squares Classiﬁer (RLSC), with a linear kernel

Classifier Precision Recall F1 -score NB 0.21 0.14 0.17 SVM 0.36 0.20 0.26 LR 0.39 0.18 0.25 RLSC 0.34 0.18 0.24

For training data, we used the Genomics Track training dataset (1418 instances with full text available) supplemented with GO terms in the same way and MGD database (6750 instances with abstract only). There are on average 2.52 GO terms per training instance (from 825 GO terms in total). There are 226 GO terms which exist in both the training set and the test set (41.6% overlap). These datasets are dealing with mouse genes only. We performed the usual document preprocessing: stop-word, punctuation and long-word (> 50 characters) removal, stemming and lowercase conversion. After this preprocessing, the vocabulary size D was 47,859. As an evaluation metric, we used the F1 score for direct comparison with the previous work. F1 is deﬁned as the harmonic mean of the precision and the recall. The precision is deﬁned as the number of correct GO term predictions divided by the number of GO term predictions. The recall is the number of correct GO term predictions divided by the number of GO terms in the test data. 6.1

Classifier Comparison

In this experiment, we compared three diﬀerent regularized classiﬁers: support vector machines (SVM), logistic regression (LR) and regularized least-squares classiﬁer (RLSC). The kernel used is the linear kernel from Equation (13). As we described before, the latter three classiﬁers have the same prediction rule and only diﬀer in their deﬁnition of the optimal weight vector β c . To contrast, we also added a Naive Bayes (NB) classiﬁer. Results are summarized in Table 1. Our results show that, although SVM perform best, regularized linear classiﬁers are competitive with each-other and outperform the simpler Naive Bayes classiﬁer. Overall, we found that regularized linear classiﬁers are appropriate for the task and provide good results, as long as they are carefully trained. In particular, two important aspects are the hyperparameter tuning and class imbalance handling summarized in sections 4.3 and 4.4. As an example, when the latter two were not carried out, the F1 -score of the SVM classiﬁer was only of the order of 0.10. We include the comparison of three methods with respect to class imbalance: 1) proposed heuristic 2) downsampling negative examples 3) do nothing. Results are presented in Table 2.

Application of Semantic Kernels

71

Table 2. Class imbalance handling comparison using Support Vector Machines (SVM) Class imbalance handling Precision Recall F1 -score Proposed heuristic 0.36 0.20 0.26 Downsampling 0.26 0.18 0.21 Do nothing 0.14 0.09 0.11

Table 3. Kernel performance comparison using Support Vector Machines (SVM) Kernel Precision Recall F1 -score Klinear 0.36 0.20 0.26 0.35 0.19 0.25 Kpoly (d = 2) 0.38 0.20 0.26 Kplsa 0.39 0.22 0.28 Kplsa (+U) 0.38 0.24 0.29 Kplsa (+U + T)

6.2

Kernel Comparison

In this experiment, we use support vector machines as our classiﬁer and compare three diﬀerent kernels: Klinear , Kpoly and Kplsa . Klinear (xi , xn ) =

xi · xn xi xn

Kpoly (xi , xn ) = (1 + Klinear (xi , xn ))d Kplsa (xi , xn ) =

@K Kz+w (xi , xn )

(13)

(14) (15)

K∈{8,16,32}

Klinear is a simple linear kernel where examples have been normalized with their norm. It corresponds to the cosine similarity. Kpoly is the polynomial kernel of degree d and is implicitly equivalent to learning a weight for all possible (unordered) 1-grams, 2-grams, . . . , up to d-grams. Inspired by Hofmann [7], we deﬁne Kplsa as the sum of the pLSA-based kernels when the underlying pLSA models are trained with 8, 16 and 32 topics. A summary of the results is reported in Table 3. Kplsa (+U) corresponds to the results obtained when an additional 10,000 unlabeled abstracts from the MGD database were used to learn the pLSA model (semi-supervised learning). Kplsa (+U + T) corresponds to the results obtained when the test set was also used to learn the pLSA model, thereby tailoring the classiﬁers to the task of interest (transductive learning). Although the improvements over the linear kernel were modest, we believe that embedding generative model knowledge in a kernel is a promising way to address the inherent data scarcity in GO term annotation. We have also tried the popular tf-idf scheme but its F1 -score was only 0.21.

72

M. Blondel, K. Seki, and K. Uehara Table 4. Comparison with existing methods Method Precision Recall F1 -score Proposed 0.38 0.24 0.29 Proposed (+O) 0.42 0.23 0.30 Stoica & Hearst 0.19 0.46 0.27 Seki et al. 0.26 0.27 0.26

6.3

Comparison with Existing Methods

To put our results in perspective, we provide direct comparison with the methods of Stoica and Hearst [17] and Seki et al. [14]. Stoica and Heart’s method was the best performing on the BioCreative dataset. The results from Stoica and Hearst’s method were obtained from a re-implementation by the authors, while the results of Seki et al. were obtained directly from their paper. As explained below, “PROPOSED (+O)” corresponds to the results when post-processing based on cross-species (orthologs) constraints was added to the best proposed method. Results are summarized in Table 4. Our method achieves the highest precision and F1 score. On the other hand, Stoica and Hearst accomplish the highest recall. This is because they perform string matching using the entirety of the GO term descriptors but eliminate inconsistent candidates, using ortholog constraints. Orthologs are genes from diﬀerent species rooted from the same gene of their common ancestor and thus often have the same functions. For comparison, we experimented with additional ortholog-based post-processing. We suppressed GO term candidates which are not associated with the gene’s rat ortholog. Results are reported in “Proposed (+O)”. While the recall slightly decreased, the precision increased from 0.38 to 0.42 and the F1 -score also increased to 0.30. Since mouse and rat are two closely related species, suppressing GO term candidates which are not assigned to a given mouse gene’s rat ortholog can improve the precision, while keeping the recall deterioration to a minimum. Based on the t-test, the diﬀerence between our best method and the method of Stoica and Hearst was found statistically signiﬁcant at the 0.05 signiﬁcance level (p = 0.03). Besides the higher performance, one advantage of our approach over stringmatching approaches is model interpretability. It is possible to discover what were the most discriminative features for the cth GO term with the featureweight vector β c . Likewise, it possible to discover what were the most helpful articles with the example-weight vector αc . 6.4

Fast Learning, Prediction and Cross-Validation

Numerous methods for eﬃciently learning large-scale linear SVM have been proposed over the past few years. Among them, the dual coordinate descent method [9] can be much more eﬃcient than the decomposition methods [11] commonly used in kernel SVM implementations, especially if the number of examples N is very large.

Time in seconds

Application of Semantic Kernels 450 400 350 300 250 200 150 100 50 0

73

Kernel SVM (learn) Kernel SVM (predict) Linear SVM (learn) Linear SVM (predict) 5000 10000 15000 20000 25000

Number of examples

Fig. 3. Learning and prediction time for linear SVM and kernel SVM with a linear kernel in a one-vs-all scheme, with 300 non-zero features. The number of binary classiﬁers is equal to the number of examples divided by 50. For our GO-term annotation system, kernel SVM is computationally more eﬃcient since the number of GO terms is large.

However, when the number of classes M is large as well, which is precisely the case with GO terms, even in the linear kernel case, learning can be more eﬃcient with kernel SVM than with linear SVM. In a one-vs-all scheme, most of the negative examples are shared by all binary classiﬁers. Therefore, we can expect many computations to be redundant in linear SVM. In contrast, the kernel matrix is shared by all binary kernel SVM classiﬁers; only the labels yic (+1 or −1) vary from a GO term to another. Even though the computation time of kernel SVM is dominated by the kernel matrix computation and takes O(N 2 D) time, once the kernel matrix is computed, it is inexpensive to update the dual coeﬃcients αic . To illustrate this, we generated an artiﬁcial dataset with 300 non-zero features and measured the performance for the numbers of examples N = 5000, 10000, . . . , 25000. To simulate a one-vs-all scheme, we trained M = N/50 binary classiﬁers, which corresponds to each class having 50 positive examples. Results are summarized in Figure 3 and show that, in our experimental setting, learning is computationally more eﬃcient with kernel SVM than linear SVM until N = 25, 000. When doing cross-validation such as described in section 4.4, numerous classiﬁers must be learned for the same GO term, each using diﬀerent training data splits. However, unless the parameter to be optimized is a kernel parameter, the kernel matrix does not need to be recomputed either. Therefore, with kernel SVM, many parameters can be searched inexpensively. For prediction, however, linear SVM clearly outperforms kernel SVM. This is because the number of support vectors, used in Equation (5), grows with the number of examples N . We also measured the computation time on the Genomics track dataset (Table 5). Contrary to the artiﬁcial data experiment, this experiment comprises the time which was required to perform cross-validation, as explained in

74

M. Blondel, K. Seki, and K. Uehara

Table 5. Computation time comparison in seconds on the Genomicks track dataset

Klinear Kplsa

Learning Prediction Linear SVM Kernel SVM Linear SVM Kernel SVM 78 36 3 8 362 84 11 18

section 4.4. For kernel SVM, we used libsvm [3] and used Klinear and Kplsa directly. For linear SVM, we used liblinear [5] and used the φ function corresponding to Klinear and Kplsa . In the Kplsa case, in addition to the time showed in Table 5, 55 minutes were necessary to learn the underlying pLSA model (500 iterations). The machine used was an Intel(R) Core(TM) i5 CPU750 @ 2.67GHz (4Gb RAM). In light of these results, we therefore recommend to carry out learning with kernel SVM and prediction with linear SVM. The dual coeﬃcient vector αc obtained from kernel SVM learning can be converted to the primal coeﬃcient vector β c of linear SVM with Equation (4). By doing so, not only does the prediction becomes faster but the need to store support vectors is also lifted.

7

Conclusion and Future Work

This study investigated the use of semantic kernels for GO term annotation. From the experiments on the Genomics Track data, we observed that 1) our system exhibits high precision and performs better in terms of F1 -score than two existing state-of-the-art methods based on string-matching and cross-species information (orthologs) 2) latent topics can be advantageously embedded into kernels and are a promising way to address the inherent data scarcity in GO term annotation 3) kernels are computationally eﬃcient for learning and crossvalidation because the number of GO terms is large 4) per-class regularization is a simple and eﬀective way to deal with the class imbalance problem. Motivated with these promising results, for future work, we would like to explore two lines of work based on kernels. First, we would like to run experiments with large-scale datasets, taking advantage of recent advances in large-scale kernel methods. Second, we would like to explore ways of bringing the domain knowledge of the Gene Ontology DAG as well as other sources of evidence into kernels and combine them with Multiple Kernel Learning (MKL).

References 1. Baumgartner, W.A., Cohen, J., Fox, K.B., Acquaah-Mensah, L.M., Hunter, G., Manual, L.: curation is not suﬃcient for annotation of genomic databases. Bioinformatics 23(13), i41–i48 (2007) 2. Blaschke, C., Leon, E., Krallinger, M., Valencia, A.: Evaluation of BioCreAtIvE assessment of task 2. BMC Bioinformatics 6(suppl. 1), S16 (2005)

Application of Semantic Kernels

75

3. Chang, C.C., Lin, C.J.: LIBSVM: a library for support vector machines (2001), software available at http://www.csie.ntu.edu.tw/~ cjlin/libsvm 4. Chiang, J.H., Yu, H.C.: MeKE: discovering the functions of gene products from biomedical literature via sentence alignment. Bioinformatics 19(11), 1417–1422 (2003) 5. Fan, R.E., Chang, K.W., Hsieh, C.J., Wang, X.R., Lin, C.J.: LIBLINEAR: A library for large linear classiﬁcation. Journal of Machine Learning Research 9, 1871– 1874 (2008) 6. Hersh, W., Bhuptiraju, R.T., Ross, L., Cohen, A.M., Kraemer, D.F.: TREC 2004 genomics track overview. In: Proceedings of the 13th Text Retrieval Conference, TREC (2004) 7. Hofmann, T.: Learning the similarity of documents: An information-geometric approach to document retrieval and categorization. In: Solla, S.A., Leen, T.K., M¨ uller, K.R. (eds.) Advances in Neural Information Processing Systems, vol. 12, pp. 914– 920 (1999) 8. Hofmann, T.: Probabilistic Latent Semantic Analysis. In: Proc. of Uncertainty in Artiﬁcial Intelligence, UAI 1999, Stockholm (1999) 9. Hsieh, C.J., Chang, K.W., Lin, C.J., Keerthi, S.S., Sundararajan, S.: A dual coordinate descent method for large-scale linear svm. In: Proceedings of the 25th International Conference on Machine Learning, ICML 2008, pp. 408–415. ACM, New York (2008) 10. Jaakkola, T., Haussler, D.: Exploiting Generative Models in Discriminative Classiﬁers. Advances in Neural Information Processing Systems 11, 487–493 (1998) 11. Osuna, E.E., Freund, R., Girosi, F.: Support vector machines: Training and applications. Tech. rep., Massachusetts Institute of Technology (1997) 12. Ray, S., Craven, M.: Learning statistical models for annotating proteins with function information using biomedical text. BMC Bioinformatics 6(suppl. 1), S18 (2005) 13. Rifkin, R., Klautau, A.: In defense of one-vs-all classiﬁcation. J. Mach. Learn. Res. 5, 101–141 (2004) 14. Seki, K., Kino, Y., Uehara, K.: Gene functional annotation with dynamic hierarchical classiﬁcation guided by orthologs. In: Gama, J., Costa, V.S., Jorge, A.M., Brazdil, P.B. (eds.) DS 2009. LNCS, vol. 5808, pp. 425–432. Springer, Heidelberg (2009) 15. Seki, K., Mostafa, J.: Gene ontology annotation as text categorization: An empirical study. Information Processing & Management 44(5), 1754–1770 (2008) 16. Si, L., Yu, D., Kihara, D., Fang, Y.: Combining gene sequence similarity and textual information for gene function annotation in the literature. Information Retrieval 11, 389–404 (2008) 17. Stoica, E., Hearst, M.: Predicting gene functions from text using a cross-species approach. In: Proc. of Paciﬁc Biocomputing Symposium, vol. 11, pp. 88–99 (2006)

“Tell Me More”: Finding Related Items from User Provided Feedback Jeroen De Knijf1 , Anthony Liekens2 , and Bart Goethals1 1

Department of Mathematics and Computer Science, Antwerp University 2 VIB Department of Molecular Genetics, Antwerp University

Abstract. The results returned by a search, datamining or database engine often contains an overload of potentially interesting information. A daunting and challenging problem for a user is to pick out the useful information. In this paper we propose an interactive framework to efficiently explore and (re)rank the objects retrieved by such an engine, according to feedback provided on part of the initially retrieved objects. In particular, given a set of objects, a similarity measure applicable to the objects and an initial set of objects that are of interest to the user, our algorithm computes the k most similar objects. This problem, previously coined as ’cluster on demand’ [10], is solved by transforming the data into a weighted graph. On this weighted graph we compute a relevance score between the initial set of nodes and the remaining nodes based upon random walks with restart in graphs. We apply our algorithm “Tell Me More” (TMM) on text, numerical and zero/one data. The results show that TMM for almost every experiment significantly outperforms a k-nearest neighbor approach.

1 Introduction The increasing usage of information technology to store, process and exchange data the last decades, has resulted in the availability in enormous amounts of data. One of the major challenges in modern society is to efficiently find and retrieve the desired information. Although a vast amount of efficient and powerful tools are available to assist in the daily information need, the number of potentially interesting objects retrieved is in general tremendous and unrelated to the user needs. For a user it is an challenging task, if the goal can be accomplished at all, to filter out all or a great deal of the useful objects. It is our belief that the main problem is not the expressiveness of the query language, but that it is the case that user does not have enough apriori knowledge of what is interesting and what is not. In order to enhance the retrieval capabilities of modern search, mining and database engines, we argue that an interactive framework that allows for simple and intuitive user directed exploration of the relevant objects is needed. A particularly intuitive and appealing approach is where a user wants to find objects that are similar to some manually inspected objects selected for his specific interest. For example, consider a text retrieval engine. The initial results of the user query contains about 10,000 relevant documents. After manually inspecting the ten highest ranked documents, the user marked three of them as relevant. In the framework we propose, the initial list of 10,000 documents is reordered, such that the most similar documents to the three interesting documents are ranked higher. In this reordered list, T. Elomaa, J. Hollm´en, and H. Mannila (Eds.): DS 2011, LNCS 6926, pp. 76–90, 2011. c Springer-Verlag Berlin Heidelberg 2011

“Tell Me More”: Finding Related Items from User Provided Feedback

77

the user can again manually inspect the top ten documents and mark the interesting ones. As a second example consider a binary database, where each record consists of an unique customers id and all the goods purchased by the customer over the past year. Suppose that a marketeer is interested in specific groups of customers, and tries to distill interesting groups based on their purchasing behavior. A common approach to achieve this, is by using a frequent itemset mining algorithm [1]. However, once some interesting patterns are discovered and the initial group of interesting customers is identified, the marketeer wants to find similar customers. That is, clients that purchased more or less the same products. However, given an initial frequent itemset, the number of frequent itemsets with a few different items can be overwhelming. Our approach can efficiently compute the k most similar customers (i.e. transactions) with respect to an initial customer group (i.e. set of transactions) of interest. The previous examples contained situations where we proposed to improve the results of a search or datamining engine by using user feedback, however one can also think off different situations where the most related objects on itself might be of interest. For instance, consider a clinical trial where some of the patients are given a drug to cure a certain disease. A natural question is, which of the patients that did not participate at the trial are alike the patients that responded positive to the drug. In this paper we introduce an efficient and interactive framework Tell Me More (TMM) to solve the aforementioned problems. We transform the problem into a weighted graph, where the weight of the link between object i and j is the similarity between i and j. On this graph we compute a relevance score between a set of nodes and the remaining nodes based upon random walks and random walks with restart in graphs. The main contribution of the paper are as follows: – We propose a framework to rerank the results of a search, database or datamining engine based upon feedback provided by the user. – We propose an algorithm to find the most related nodes based upon an non-empty initial set of nodes. – We propose a relatedness score that corrects for objects that are apriori highly related to many objects (hubs). – TMM is independent of any specific data type, i.e. we demonstrate the usability on binary, text and numerical data. – Thorough experimental evaluation on real-life data shows that TMM significantly outperforms a k-nearest neighbor approach. Moreover, the experimental results shows that the adjustment of the score in order to compensate for objects that are apriori similar to many objects in the dataset, leads, in a substantial number of settings, in significant better results. The remainder of this paper is organized as follows. In the next section we formally define the problem. In section 3 we discuss related work. In the following section we discuss random walks and random walks with restart and present our algorithm: Tell Me More. In section 5 we discuss the experimental setup and similarity measures used. Moreover, we report on the results obtained by TMM on various benchmark datasets and compare these with the results obtained by the k-nearest neighbor approach and by a ranking approach which is solely based upon random walk with restarts. Finally, in the last section we draw conclusions and give directions for further research.

78

J. De Knijf, A. Liekens, and B. Goethals

2 Problem Statement Let D denote the data collection, that is D is the initial set of objects. The problem addressed in this paper is the following: given a (small) subset S ⊂ D of the dataset, find the k most related objects to S in D, with k a user specified parameter. In order to conduct a proper evaluation and to avoid philosophical discussion of what is related, we assume that there exists a set of m class labels C = {c1 , . . . , cm }, such that every object in the dataset belongs to exactly one class. Moreover, every object x ∈ S belongs to the same class. In this setting the most related objects, becomes the objects with the same class as the class of the objects in S. Given a dataset, an initial set of interest S and a similarity function, the k-nearest neighbor approach selects the k objects of D that are most similar to the objects in S. In case S contains a single object, KNN returns the k objects with the highest similarity score. In case that S consists of multiple objects, then the similarity score for an object j ∈ D is the average similarity with respect to all objects in S. Hence, KNN return the k objects that have the largest average similarity score with the objects in S. We will experimentally compare our approach with the KNN approach in section 5.

3 Related Work The problem previously described can be seen as a special instance of clustering, that is, some part of an unknown cluster is given and the task is to complete the cluster. Because of this resemblance, the problem was previously coined by Ghahramani and Heller [10] as ’clustering on demand’. In this paper we adopt this terminology. However, in general the goal of clustering is to divide the data into multiple parts, where our goal is to partially complete one cluster. Moreover, clustering is generally performed unsupervised where in the clustering on demand setting we get some examples that provides hints of the class membership. Under the assumption that the objects consists of binary features, Ghahramani and Heller [10] take a probabilistic Bayesian viewpoint to solve the clustering on demand problem. In particular, for each object, every feature is assumed to be drawn from a fixed Bernoulli distribution with parameter θj , where θj equals the probability that feature j is equal to one. Moreover, it is assumed that the objects are generated independently and identically. In this setting, the relevance score for an object x boils down to : Pr(x|S) Pr(x) . Ghahramani and Heller [10] show that the log score can be computed efficiently with a conjugate Beta prior on the Bernoulli model parameters. The main difference with our approach is that we do pose no restriction on the type of data. Very similar to our clustering on demand problem, is the problem of finding similar web pages of the current web page [5,12]. However, the problem mainly focus on finding good similarity measures for web pages. Once an appropriate measure is found, a standard k-nearest neighbor search is performed. A further difference with our approach is that their problem is defined to find only related pages to one web page, where we generalize to sets of objects.

“Tell Me More”: Finding Related Items from User Provided Feedback

79

Different types of random walks are commonly used in graph mining to measure the relatedness between nodes in a graph. For example, in the work by Tong and Faloutsos [22], where in a social network the goal is to find subgraphs that are ’best’ connected with some given query nodes. In Pang et al. [18] the aim is, given a multimedia collection, to automatically assign keywords to multimedia objects. In Sun et al. [21] random walks are used to derive the most similar nodes and the most abnormal nodes on bipartite graphs. Also in the Information Retrieval field are random walks commonly used. For example, Craswell and Szummer [4] use a random walk on the bipartite clickgraph to adjust the ranking of the search engine. In order to generate a set of appropriate keywords for an online advertiser, Fuxman et al. [9] uses an approach where a bipartite query-click graph is constructed. Given a set of URLs that are of interest to the advertiser, their method suggest keyword for the URL based upon performing a random walk with absorbing states on the bipartite click graph. This overview of related work is far from complete, however to summarize all work that is somewhat related demands a survey paper on itself. Especially in the area of Information Retrieval and Web Mining, there are many methods bases upon random walk with restarts to find related objects. Although TMM also uses random walks with restarts to rank objects, there are some major differences with the different methods that make use of random walks with restart. First, TMM find related objects based upon user provided feedback. Second, our framework is suitable for any type of data, as long as their is a similarity measure applicable between the objects. Finally, instead of solely using the score obtained by performing random walks with restarts, we also adjust the score for the hubinnes of the nodes. In section 5, we show that this adjustment for hubiness does result, in a substantial number of settings, in significant improvement.

4 Algorithm In this section we will present our main algorithm. First we describe how our problem can be transformed to a weighted graph. Then we discuss random walks and random walks with restarts on graphs. Next we present our TMM algorithm. Finally, we give a straightforward k-nearest neighbor algorithm. 4.1 Graph Construction The first step is to transform the problem into a graph based setting. A graph G = {V, E, λ} is defined as an undirected weighted graph, where V is a set of vertices, E a set of edges (unordered pair of vertices) and λ a labeling function that assigns a weight from the interval [0, 1] to each edge, i.e. λ : E → [0, 1]. Given our dataset D and a similarity function Sim(i, j) that gives for every pair of objects from D a similarity score between i and j in the [0, 1] interval. A score of 1 meaning that the objects are identical, while a score of 0 implies that the objects are completely dissimilar. The graph G is constructed as follows: First, all objects i in the dataset D are added as nodes in the graph G. Second, for every unordered pair of vertices i and j, with i = j, and edge is added if Sim(i, j) > 0. Furthermore, the weight of the edge is equal to the similarity between i and j, that is λ{i, j} = Sim(i, j). Note that, in general this

80

J. De Knijf, A. Liekens, and B. Goethals

graph will be dense. Specifically , this graph is often an (almost) complete graph. This is caused by the particular setting, where the dataset is the initial answer set from an search or datamining engine. Hence, the objects in the dataset are apriori related with each other. 4.2 Random Walk with Restarts Informally, a random walk on a graph G can be described as follows: consider a random particle currently at node v in G, at each iteration the particle moves to a neighbor with a probability that is proportional to its edge weight. The steady state probability of a node w, denoted as u(w) states the probability that the particle visits this node in the long term. Intuitively, the steady state probability of node w states the importance of w in the graph. In our setting, u(w) defines how central w is in the graph. Under the assumption that a random walk on G is ergodic, it is well known that the steady state probability of a random walk on G satisfies Equation 1, with MG the column normalized adjacency matrix of G. uk+1 = MG × uk

(1)

Like a random walk, a random walk with restart can informally be described as a particle currently at node v in G. Let q S be the normalized vector where for each node in S the corresponding value in q S is set to 1, while the remaining values of q S are set to 0. Informally, q S contains the restart nodes, with an uniform distribution over the nodes in S. Additional to moving at each iteration to one of its neighbors with a probability that is proportional to its edge weight, the particle has a probability c of moving uniformly at random to one of the restart nodes. The relevance score of node w with the set of nodes S (uS (w)) is then defined as the steady state probability of the random walk with restart. Under the assumption that a random walk on G is ergodic, the random walk with restart on a graph G satisfies Equation 2. With MG the column normalized adjacency matrix of G, c the restart probability and q S the restart vector. uS = (1 − c) × MG × uS + c × q S

(2)

In our specific setting, we work with undirected, non-bipartite and connected graphs. It trivially follows that a random walk on these graph is ergodic. Consequently, in the limit, random walks and random walks with restart converges to a steady state probability. The steady state probability of a random walk with restart, can be easily computed by iteratively applying Equation 2, this method is also known as the power iteration method. The pseudo code to compute the steady state probability of a random walk with restart is given in Algorithm 1. Note that, Algorithm 1 can be trivially used to compute the steady state probability of a random walk. In this case the input parameter c should be set to zero. Also note that in the actual implementation, we do not have to construct the graph. Instead, a normalized version of the similarity matrix is sufficient to obtain the desired output. Further worth mentioning, is that different optimizations techniques are available to compute the steady state probability of a random walk on graphs. In particular, Tong et al. [23] report significant speedups compared with the power iteration method.

“Tell Me More”: Finding Related Items from User Provided Feedback

81

Algorithm 1. Random Walk with Restart Input: adjacency matrix MG , restart probability c, set of restart nodes S Output: uS 1: initialize q S ← 0 2: for all i ∈ S do 3: qS ← 1 4: end for 5: normalize q S 6: column normalize MG 7: while not converged uS do 8: uS ← (1 − c) × MG × uS + c × q S 9: end while 10: return uS

4.3 Tell Me More Most graph mining algorithms based upon random walks (for example [18]) solely uses the steady state probability as the relevance score between nodes. However, consider the following example: Given two nodes w and v, and a set of restart nodes S. Suppose that uS (w) = 0.2 and uS (v) = 0.3, moreover u(w) = 0.1 and u(v) = 0.6. Hence, the apriori relevance of node v is much higher than the relevance score of node v with respect to the set of nodes S. In fact the initial set S harms the importance of node v, while node w becomes far more important due to the initial set S. But nevertheless, when only using the steady state probability of the random walk with restart, v is preferred above w. In our Algorithm, we take the prior importance of a node into account to adjust the score of the steady state probability. In particular, for an initial set S the score of a node v is determined by uS (v) ×

uS (v) . u(v)

Intuitively, this adjustment lowers the probability of objects that are similar to most other objects, however the prior importance of a node is not completely neglected. The restart probability parameter (needed in Algorithm 1) was determined experimentally. We found that a broad range of values (between 0.1 and 0.99) delivered almost equally good results. However, the optimal setting for all experiments was when the restart probability was set to 0.99. Note that, in this setting the influence of the nodes in the restart vector is maximal. Moreover, a restart probability of 1 is pointless, because then the steady state probabilities of nodes that are not in the restart vector is equal to zero. The TMM algorithm is given in Algorithm 2. The input parameters are the dataset D, the initial objects of interest S and the number of related objects (i.e. k) a user is interested in. The first step is to create the adjacency matrix MG . That is, the adjacency matrix representation of the graph G, constructed from D. Note that, in this step we assume that the similarity function between objects in the dataset is available. In the next steps the steady state probability of the random walk with restart and the random

82

J. De Knijf, A. Liekens, and B. Goethals

walk is computed. This step is performed by Algorithm 1. Then the final relevance score for every node in the dataset is computed. Finally, the k objects with the highest relevance score are returned. Algorithm 2. Tell Me More Input: Dataset D, set of initial objects of interest S, k Output: list of k most interesting objects given S 1: MG ← construct the normalized adjacency matrix 2: uS ← RWR(MG , 0.99, S) 3: u ←RWR(MG , 0, S) 4: for all d ∈ D do S (d) 5: LK(d) ← uS (d) × uu(d) 6: end for 7: return the k objects with the highest score in LK

5 Experiments In this section we describe the experiments conducted on different datasets. First, we discuss the general experimental setup. Then, for each of the different types of data, we discuss in detail the similarity measure and the pre-processing step performed. Additionally, we characterize the adopted datasets and report about the obtained results. The goal of the experiments is to evaluate the effectiveness of TMM, that is how well TMM performs in finding similar objects. We compare the results of TMM with the results obtained by KNN. Additionally, to investigate the effect of the score adjustment, we compare TMM with a pure random walk with restart based ranking. That is, we only use Algorithm 1 (RWR) to compute the ranking of the nodes. Note that, the goal of the experiments is not to find the best similarity function. We used off the shelf similarity measures that are available for the particular types of objects. In order to conduct a proper evaluation, we assume that every object in the dataset belongs to exactly one class. Similarity between objects is then defined as belonging to the same class. The primary performance measure is precision at a certain cut-off value, denoted as @k. That is, given that the objects in S are of class c, the number of objects of class c in the k highest ranked objects divided by k. More formally, let c be the class label of the documents in the initial set S, and let L be the list of the k highest ranked documents, then # of documents of class c in L . @k = |L| Note that, in our experiments we did not count objects of S that were in the top k of most related objects. The reason for this, is because TMM always returned the objects of S as most relevant objects. However, this would lead to a strong bias in favor of TMM. In our experiments we used different values for k, namely k = 10, 20, 50 and 100. For a dataset D with |C| classes, we randomly selected for each class |S| = 1, 2, 3, 4 objects as initial input. For each of these sets we run our TMM algorithm, the k-nearest

“Tell Me More”: Finding Related Items from User Provided Feedback

83

neighbor algorithm and the ranking method solely based upon RWR. Next, we computed the score at the different cutoff points. Depending on the number of elements in the dataset, we repeated this procedure either 100 or 1000 times. We combine the results of the different random initial sets of the same size and the different classes, and reported the average precision@k over these combined results. Hence, for each initial set size and each k value, we report the mean value of |C| × n precision@k scores, with |C| the number of classes and n = 100 or n = 1000 depending on the dataset. In order to test whether the scores obtained for TMM are significantly different from the scores obtained by the other approaches, we performed a paired t test over the results at a 0.95 confidence level. Whenever the scores obtained for a certain batch are significantly higher than the scores obtained for a corresponding batch with another algorithm, we printed the results in boldface. All experiments where conducted on a quad core 2.1Ghz desktop computer, containing 4GB of main memory. Over all used datasets, the response time of TMM was reasonable good. At worst it took TMM around 4.1 second to provide the k most related objects, while in the best case the results were completed in less than 1 second. However, the run time can easily be improved by using more sophisticated methods (for example the work described in [23]) to compute random walks on graphs. Moreover, another feature of their algorithm is that it does not require that the complete matrix is loaded into main memory, which makes it feasible to run random walks on extreme large datasets. 5.1 Text Documents In order to apply our method to search engines for text documents, we represent each object (document) d ∈ D as a bag of words, i.e. a vector where each dimension corresponds to a separate word. In case a word occurs in the document, then its corresponding value in the vector will be non zero. The dimension of the vectors is equal to the number of different words in the dataset. We used the so called tf-idf [19] weighting scheme to calculate a value for a word in the document. That is, the weight vector v d for document d ∈ D is: [w1,d , . . . , wn,d ]. Where wt,d = tf (t, d) × log

|D| . |{d ∈ D : t ∈ d}|

With tf (t, d) the term frequency of t in d, i.e. the number of different occurrences of the |D| term t in document d. And log |{d∈D:t∈d}| the inverse document frequency, that is the logarithm of the total number of documents in D divided by the number of documents in which t occurs. The similarity between two text documents is then defined as the cosine similarity between the two vectors that represent the document. That is, let d, e ∈ D, and let there be n different terms in the collection then Sim(d, e) = n wi,d × wi,e d˙e n = 1 − n i=12 2 . ||d|| ||e|| w i=1 i,d × i=1 wi,e Clearly, the similarity takes as maximal value 1 whenever two documents are identical. Likewise, when there is no term in common between the documents the similarity equals 0. Hence, this similarity function can be used in our framework.

84

J. De Knijf, A. Liekens, and B. Goethals

Table 1. Results obtained on the Wikipedia collection (top, W) and the Reuters text categorization dataset (bottom, R). Boldfont means that the results for TMM are significantly better (at 95% confidence level), than the corresponding results for both the RWR and the KNN approach. An asterisk indicated that the results are significantly better over the KNN approach only.

|S| 1 2 W 3 4 1 2 R 3 4

@10 53.10∗ 55.02∗ 56.40∗ 56.92∗ 70.23∗ 74.38∗ 78.10∗ 79.60∗

TMM @20 @50 51.31∗ 48.34∗ 53.03∗ 50.10∗ 54.48∗ 51.72∗ 54.85∗ 51.96∗ 67.66 63.88 71.89∗ 68.37 76.02∗ 72.57 77.41∗ 74.12

@100 46.07∗ 47.73∗ 49.52∗ 49.61∗ 57.87 62.45 66.43 68.00

@10 53.10 55.02 56.40 56.92 69.92 74.21 78.16 79.40

RWR @20 @50 51.31 48.34 53.03 50.10 54.48 51.72 54.85 51.96 67.26 62.74 71.85 67.39 75.85 71.23 77.34 73.06

@100 46.07 47.73 49.52 49.61 56.24 60.07 64.33 66.00

@10 46.97 48.41 49.72 49.81 69.78 72.85 76.11 78.15

KNN @20 @50 45.20 43.15 46.91 44.62 48.06 45.97 48.38 46.25 67.10 62.41 70.43 65.95 73.98 69.24 75.58 70.95

@100 41.34 42.72 43.81 44.19 55.69 59.33 62.31 63.88

Test Collection. We used two different document collections, namely the Wikipedia XML dataset and the Reuters 21578 text categorization dataset. The Wikipedia XML dataset [6] was provided for the document mining track at INEX 2006 [7]. The collection consists of 150, 094 XML documents with 60 different class labels. The collection was constructed by converting web pages from the Wikipedia project to XML documents. The class labels correspond to the Wikipedia portal categories of the web pages. For the document mining track a subset of the total Wikipedia collection was selected such that each document belonged to exactly one class. We did not use any structural features of the XML documents, only the content of XML documents. We used the tfidf vector for all documents, that was provided by the organizers of the XML document mining track. In order to reduce the number of objects in the dataset, such that the matrix would fit into main memory, we selected from the complete dataset the documents that belong to one of the four largest classes. In total our dataset consists of 13, 146 documents divided over four different classes. The Reuters-21578 text categorization dataset, is a collection of documents that appeared on Reuters news wire in 1987. These documents were manually assembled and categorized. From this collection we selected only the documents that belong to exactly one category. From the resulting set, we filtered out all documents that belonged to a category with less than hundred documents. The resulting dataset contains 7, 783 documents divided over ten classes. In order to use the dataset in our experiments, we used the Lemur Toolkit1 to preprocess the data. We first performed stemming and stop word removal, then we computed over the remaining data the tf-idf score for the words in the documents. Results. The results obtained over the text collection are displayed in Table 1. The results reported for the Wikipedia collection are the average values over 4, 000 runs, i.e. 1, 000 randomly selected initial sets S per class. For all setting, the results obtained 1

http://www.lemurproject.org/

“Tell Me More”: Finding Related Items from User Provided Feedback

85

by TMM where significantly better than the corresponding results with the KNN algorithm. The difference is maximal when the ten most similar documents are considered. For example, for k = 10 and |S| = 4 the score for the TMM approach is more than 7 percent points higher than the score obtained by the KNN algorithm. But also in case that more than ten similar documents are required, the difference is still considerable; the score for TMM is between 1 and 7 percent points higher than the score obtained for the KNN approach. Further noteworthy, is that the ranking for both TMM and KNN keeps improving when more documents are added to the initial set of interesting documents S. Comparing TMM with the RWR approach, we have the remarkable result that TMM and RWR obtain exactly the same score on the Wikipedia dataset. Further investigation revealed that also the ranking of the documents was identical between the two approaches. These results indicate, with the similarity measure and pre-processing steps used, that there were no hub nodes in the Wikipedia collection. Because some classes of the Reuters collection contain less than 1, 000 documents, the reported presicion@k results are the average values over 1, 000 runs. That is, for each of the ten classes 100 randomly selected initial sets S were generated. Also in this case are the results obtained by TMM significantly better than the results of the KNN approach. However, the difference in accuracy scores is lower then the difference obtained over the Wikipedia collection. The differences reaches its maximum value, of more than 4 percent points, when more initial documents of interest are considered and when the cutoff value is large enough. In the other settings is the difference between 0.5 and 2 percent points. Further noteworthy, is that for both methods the addition of extra documents in the initial set S increases the predictive performance. Comparing TMM with the RWR approach, it can be observed that there is a significant improvement over the accuracy scores when the RWR score is adjusted to compensate for hub nodes. However, this only occurs for larger cutoff values, i.e. @50, @100. Note that, the difference is increasing when more documents are considered. There is one setting were the RWR algorithm obtains better results than the TMM approach, namely with @10 and |S| = 3. However, this difference is minimal and neglectable. 5.2 Binary Data Besides the wide availability of binary datasets, many data can be represented as binary strings. For example, the work by Cilibrasi et al. [2] transforms music files to binary strings. Due to the wide availability of binary data and the universal applicability, we include some experiments with binary data. In this setting, each object x ∈ D is a binary vector of length n, i.e. x = [i1 , . . . , in ]. With ij ∈ {0, 1}, and n the fixed number of features for the objects in the dataset. Recently, there has been a growing interest in the data mining community in using compression to extract valuable knowledge, see for instance [25,8,26,13]. This is because, as stated by Faloutsos and Megalooikonomou [8], several core aspect of datamining are essentially related with compression. In order to define a similarity score for binary data, we use a compression based similarity method, namely: normalized compression distance [14]. The intuition behind this method is that two objects are deemed

86

J. De Knijf, A. Liekens, and B. Goethals

Table 2. Results obtained on the Chess dataset (top, C) and the Mushroom dataset (bottom, M). Bold font means that these results are significantly better (at 95% confidence level), than the corresponding results for both the RWR and the KNN approach. An asterisk indicated that the results are significantly better over the KNN approach only

|S| 1 2 C 3 4 1 2 M 3 4

@10 72.41 69.15 67.87 65.46 99.71∗ 99.84 99.89∗ 99.85

TMM @20 @50 68.58 63.49 65.94 61.84 65.05 61.17 63.37 59.92 99.43∗ 98.35∗ 99.63∗ 98.97∗ 99.75∗ 99.35∗ 99.75∗ 99.16∗

@100 60.19 58.83 61.46 57.97 97.03 97.98 98.78∗ 98.58∗

@10 66.64 62.14 60.23 58.19 99.67 99.83 99.86 99.88

RWR @20 @50 63.28 59.14 59.70 56.92 58.55 56.24 56.40 54.92 99.47 98.33 98.65 98.83 99.28 99.11 99.73 99.13

@100 56.73 55.34 54.98 54.01 96.94 97.59 98.71 98.55

@10 63.78 60.95 59.01 57.31 99.56 99.75 99.75 99.84

KNN @20 @50 59.69 53.78 58.36 52.16 57.55 50.84 55.71 50.89 98.26 91.76 99.02 94.94 99.28 96.30 99.37 97.10

@100 43.78 42.95 42.89 42.92 76.94 85.22 89.15 91.83

close if we can significantly ’compress’ one given the information in the other. Here compression is based on the ideal mathematical notion of Kolmogorov complexity, which is unfortunately not effectively computable. However, this similarity measure is approximated by using any available off the shelf compressor, e.g. gzip, zlib. More formally, N CD(x, y) = C(x, y) − min(C(x), C(y)) . max(C(x), C(y)) Where C(x, y) is the compressed size of the concatenation of x and y. Likewise, C(x) and C(y) is the length of the compressed version of x and y respectively. The N CD value is minimal, that is N CD(x, y) = 0, when x = y. Moreover, when there is no common information between x and y the N CD value equals one. Hence, in order to fit in our framework the similarity between two items x and y (Sim(x, y)) is defined as: 1 − N CD(x, y). The NCD between objects was computed with a tool2 provided by the authors of [14]. Testsets. We used binary versions of the Chess(kr-kp) and the Mushroom UCI dataset. These binary version where made available by [3]. The Chess dataset contains 3, 196 objects, divided over two classes. The Mushroom dataset contains 8, 124 objects and also consists of two classes. Results. The results on the binary datasets are shown in Table 2. The results for the Chess dataset are obtained by computing the average values over 2, 000 runs, i.e. 1, 000 randomly selected initial sets S per class. For this dataset are all the results of the TMM approach significantly better than results for both the KNN as well as the RWR approach. The advantage of TMM is considerable: it varies between 16 percent points 2

available at http://www.complearn.org/

“Tell Me More”: Finding Related Items from User Provided Feedback

87

and 6 percent point over the KNN approach, and between 3 and 6 percent points over the RWR approach. Notice, that for all algorithms the addition of objects to the initial set S, especially for lower cutoff values, leads to remarkably worse results. Although this observation seems counter intuitive to the principle of using feedback to improve the ranking, a possible explanation lies in the experimental setup. In our experimental setting, we randomly select objects from a given class to be used as initial set. When the objects of a given class are widely spread, it is likely that by selecting at random objects from this class, these objects can be quite dissimilar from each other. First worth noticing about the results on the Mushroom dataset, is that all algorithms obtained a remarkably good ranking. This suggests that the NCD is indeed a good similarity measure to use with binary data. The second remarkable observation is that the difference of the scores between TMM and KNN is largely dependent on the cutoff value. For example, when only the ten most similar objects are considered the difference between TMM and KNN varies between 0.15 and 0.04 percent points. However, if we consider the parameter setting @100, then the difference ranges from 7 to 20 percent points. The difference between TMM and the RWR method, is for all cases minimal. Solely in the setting, where the number of initial objects is low and the cutoff value is large, resulted in significantly better performance for TMM. In all other settings were the two methods equally good. That is, most of the times TMM obtained better performance and sometimes RWR obtained a higher precision score, but all these differences in obtained precision@k are minimal and neglectable. 5.3 Numerical Data The last type of data considered in our experiments is numerical data. That is, every object x in the dataset is a point in a d-dimensional space Rd . Hence, each object x in the dataset is a numerical vector of length d, i.e. x = [i1 , . . . , id ] with ij ∈ R for 1 ≤ j ≤ d. For numerical data we use a similarity measure based upon the Euclidean distance. The similarity between points x and y in the dataset, equals one minus the Euclidean distance between x and y, divided by the maximal distance between any point two points in the dataset. That is, with Δ(x, y) the Euclidean distance between x and y, Sim(x, y) = Δ(x, y) . 1− max{Δ(i, j)|i, j ∈ D} Hence, Sim(x, y) gets the value of 1 if x is identical to y and a value of 0 if x and y are the two points with the largest distance in the dataset. Testsets. We used three different datasets available at the UCI repository. Two of these datasets contain a relatively low number of objects, namely 351 for the Ionosphere and 561 for the Breast Cancer dataset. The Spambase dataset contains 4, 601 objects. In all three datasets are the objects divided over two classes. Due to the relatively low number of objects in the Ionosphere and Breast Cancer dataset, we only conducted 200 runs per initial set S, i.e. 100 runs for each class.

88

J. De Knijf, A. Liekens, and B. Goethals

Table 3. Results obtained for the Ionospehere dataset (I, top), the Breast cancer dataset (B, middle) and the Spambase dataset (S, bottom). Boldfont means that the result is significantly better (at 95% confidence level), than the corresponding result for both the RWR and the KNN approach. Likewise, an asterisk means that the score is significantly better than the score for the KNN approach only.

|S| 1 2 I 3 4 1 2 B 3 4 1 2 S 3 4

@10 84.45 81.05 85.90 84.10 95.25 97.75 97.80∗ 98.70 84.80∗ 90.80 89.60 90.65

TMM @20 @50 79.25 71.22 76.65 70.09 81.33 72.99 79.00 71.31 94.75 93.47 97.18 96.27 97.55 96.47 98.40 97.56 83.48 80.59 88.98 86.07 88.60 84.80 89.18 86.75

@100 63.99 64.00 64.23 65.75 91.71 94.56 95.13 95.95 79.15 83.53 82.07 84.59

@10 74.30 72.55 73.40 71.45 94.25 96.00 96.70 97.30 83.25 87.55 84.60 86.80

RWR @20 @50 69.15 63.05 67.83 62.29 69.03 63.56 67.65 62.60 93.25 91.36 95.33 93.79 95.88 94.14 96.80 95.67 81.03 77.76 85.28 82.33 83.05 79.90 84.35 80.40

@100 59.43 59.23 59.32 60.31 88.21 90.87 91.21 92.86 75.28 78.83 76.40 77.75

@10 69.85 70.07 70.07 68.90 94.25 96.00 96.60 97.70 82.00 85.25 84.75 83.34

KNN @20 @50 66.30 61.33 67.00 62.14 67.00 62.14 65.70 61.33 93.30 91.23 95.35 93.78 95.98 94.13 97.03 95.57 80.48 77.68 83.15 81.33 83.18 80.00 81.88 79.03

@100 58.22 59.32 59.32 59.11 88.29 90.91 91.21 92.83 74.89 78.13 76.84 76.02

Results. The results obtained over the numerical datasets are displayed in Table 3. The first remarkable observation, which only holds for the numerical datasets, is that the scores obtained for KNN and RWR are quite similar. That is, most of the times RWR obtains a slightly higher score than KNN. This in contrast with earlier experiments, where the scores obtained by RWR was, in general, considerably better than the scores obtained with the KNN approach. The results in Table 3 show that TMM performs—over all numerical datasets considered—significantly better in all but two settings than RWR. Moreover, TMM obtained significantly higher scores in all settings over KNN. The largest difference (more than 15 percent points) is obtained on the Ionosphere dataset. Likewise, the smallest significant difference (1 percent point) is obtained on the Breast Cancer dataset.

6 Discussion and Conclusion In this paper we introduced an interactive framework to effectively explore and rerank objects retrieved by a search or datamining engine, based upon user provided feedback. We argued that such an framework can be a valuable tool for a user to find the desired information. The TMM approach can be used for very different data types and is in spite of its naive implementation relatively efficient. We thoroughly experimentally evaluated TMM, and for every dataset considered for almost every setting, the results show that TMM performs significantly better at a 95 percent confidence level than a straightforward k-nearest neighbor approach. Also the effect of the score adjustment in TMM, in order to compensate for objects that are apriori similar to many objects, has a positive effect on the ranking results. For a substantial number of settings, this adjustment results in a significantly better ranking at a

“Tell Me More”: Finding Related Items from User Provided Feedback

89

95 percent confidence level. However, the improvement of TMM over a purely RWR methods is dependent on the dataset. For the Wikipedia dataset there was no improvement, which is likely caused because of the omission of hub nodes in the dataset. For the Reuters dataset and the Mushroom dataset, the improvement of TMM resulted only in a limited number of settings in significant better results. Nevertheless, in none of the experiments conducted it was the case that the score adjustment resulted in significantly worse results. Concluding, the proposed adjustment to compensate for hub nodes is, in general, extremely valuable. Another issue worth reflecting one, is the assumption we made that the objects are similar if they belong to the same class. Obviously, this is a coarse level of similarity. However, the alternative is to let a domain expert decide what is most related to an object. For many data types, this is however an unrealistic option. In the IR field, where it is common practice to let experts decide which documents are relevant for a given query, it is an issue of debate [24]. In our case, we need a domain experts to judge the relevance of document given a set of documents, with is even more cumbersome than deciding whether a document is relevant given a query. For the other data types, it is even more problematic for a domain expert to decide whether two objects are similar or not. Hence, in order to perform an extensive proper evaluation the assumption that two objects are related if they are from the same class is the best option that is achievable for a wide range of different data types. Concluding, the proposed framework Tell Me More offers and an interactive tool that allows for simple and intuitive user directed exploration of the relevant objects. The flexibility of TMM allows it to be used with different types of data in a search, database or datamining engine. Moreover, because of its relatively quick response time, TMM can be used in an online setting. Interesting directions for further research includes the exploration of different similarity functions between objects, especially appealing is a similarity function between web pages that takes both the structure of the web (i.e. the link information) and the content of the web page into account. Another direction is to let the user specify not only the relevant objects but also the objects that are not of his interest.

References 1. Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., Verkamo, A.: Fast discovery of association rules. In: ADMA, pp. 307–328 (1996) 2. Cilibrasi, R., Vit´anyi, P., Wolf, R.: Algorithmic clustering of music. In: 4th International Conference on WEB Delivering of Music, pp. 110–117 (2004) 3. Coenen, F.: The lucs-kdd discretised/normalised arm and carm data library 4. Craswell, N., Szummer, M.: Random walks on the click graph. In: SIGIR, pp. 239–246 (2007) 5. Dean, J., Henzinger, M.: Finding related pages in the world wide web. Computer Networks 31(11-16), 1467–1479 (1999) 6. Denoyer, L., Gallinari, P.: The Wikipedia XML Corpus. SIGIR Forum 40(1), 64–69 (2006) 7. Denoyer, L., Gallinari, P.: Report on the XML mining track at inex 2005 and inex 2006: categorization and clustering of XML documents. SIGIR Forum 41(1), 79–90 (2007) 8. Faloutsos, C., Megalooikonomou, V.: On data mining, compression, and Kolmogorov complexity. Data Mining and Knowledge Discovery 15(1), 3–20 (2007)

90

J. De Knijf, A. Liekens, and B. Goethals

9. Fuxman, A., Tsaparas, P., Achan, K., Agrawal, R.: Using the wisdom of the crowds for keyword generation. In: WWW (2008) 10. Ghahramani, Z., Heller, K.: Bayesian sets. In: Advances in Neural Information Processing Systems (2005) 11. Haveliwala, T.: Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. IEEE Trans. Knowl. Data Eng. 15(4), 784–796 (2003) 12. Haveliwala, T., Gionis, A., Klein, D., Indyk, P.: Evaluating strategies for similarity search on the web. In: WWW, pp. 432–442 (2002) 13. De Knijf, J.: Mining tree patterns with almost smallest supertrees. In: SIAM International Conference on Data Mining. SIAM, Philadelphia (2008) 14. Li, M., Chen, X., Li, X., Ma, B., Vit´anyi, P.: The similarity metric. IEEE Transactions on Information Theory 50(12), 3250–3264 (2004) 15. Newman, D., Hettich, S., Blake, C., Merz, C.: UCI repository of machine learning databases (1998) 16. Onuma, K., Tong, H., Faloutsos, C.: Tangent: a novel, ’surprise me’, recommendation algorithm. In: KDD, pp. 657–666 (2009) 17. Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project (1998) 18. Pan, J., Yang, H., Faloutsos, C., Duygulu, P.: Automatic multimedia cross-modal correlation discovery. In: KDD, pp. 653–658 (2004) 19. Salton, G., McGill, M.: Introduction to Modern Information Retrieval. McGraw-Hill, Inc., New York (1986) 20. Siebes, A., Vreeken, J., van Leeuwen, M.: Item sets that compress. In: SIAM International Conference on Data Mining (2006) 21. Sun, J., Qu, H., Chakrabarti, D., Faloutsos, C.: Neighborhood formation and anomaly detection in bipartite graphs. In: IEE Intl. Conf. on Data Mining, pp. 418–425 (2005) 22. Tong, H., Faloutsos, C.: Center-piece subgraphs: problem definition and fast solutions. In: KDD, pp. 404–413 (2006) 23. Tong, H., Faloutsos, C., Pan, J.: Random walk with restart: fast solutions and applications. Knowl. Inf. Syst. 14(3), 327–346 (2008) 24. Voorhees, E.: Variations in relevance judgments and the measurement of retrieval effectiveness. In: SIGIR, pp. 315–323 (1998) 25. Vreeken, J., van Leeuwen, M., Siebes, A.: Krimp: mining itemsets that compress. Data Min. Knowl. Discov. 23(1), 169–214 (2011) 26. Xin, D., Han, J., Yan, X., Cheng, H.: On compressing frequent patterns. Data & Knowledge Engeneering 60(1), 5–29 (2007)

MEI: Mutual Enhanced Infinite Generative Model for Simultaneous Community and Topic Detection Dongsheng Duan, Yuhua Li , Ruixuan Li, Zhengding Lu, and Aiming Wen School of Computer Science and Technology, Huazhong University of Science and Technology Wuhan 430074, P. R. China {duandongsheng,wenaiming}@smail.hust.edu.cn {idcliyuhua,rxli,zdlu}@hust.edu.cn

Abstract. Community and topic are two widely studied patterns in social network analysis. However, most existing studies either utilize textual content to improve the community detection or use link structure to guide topic modeling. Recently, some studies take both the link emphasized community and text emphasized topic into account, but community and topic are modeled by using the same latent variable. However, community and topic are diﬀerent from each other in practical aspects. Therefore, it is more reasonable to model the community and topic by using diﬀerent variables. To discover community, topic and their relations simultaneously, a mutual enhanced infinite generative model (MEI) is proposed. This model discriminates the community and topic from one another and relates them together via community-topic distributions. Community and topic can be detected simultaneously and can be enhanced mutually during learning process. To detect the appropriate number of communities and topics automatically, Hierarchical/Dirichlet Process Mixture model (H/DPM) is employed. Gibbs sampling based approach is adopted to learn the model parameters. Experiments are conducted on the co-author network extracted from DBLP where each author is associated with his/her published papers. Experimental results show that our proposed model outperforms several baseline models in terms of perplexity and link prediction performance. Keywords: social network analysis, community detection, topic modeling, mutual enhanced inﬁnite generative model, dirichlet process, gibbs sampling.

1

Introduction

Social network is usually modeled as a graph where nodes represent users and edges represent links among users. However, in many applications we encounter not only the link structure but also user generated textual contents in a social network, such as papers published by authors in a co-author network. With the

Corresponding author.

T. Elomaa, J. Hollm´ en, and H. Mannila (Eds.): DS 2011, LNCS 6926, pp. 91–106, 2011. c Springer-Verlag Berlin Heidelberg 2011

92

D. Duan et al.

widespread of social networking sites and micro-blogs, social networks with user generated textual contents become ubiquitous and have been growing rapidly, which makes it a hot topic to mine latent patterns from them. Community and topic are two important patterns receiving much attention recently. Overall speaking, communities are densely linked sub-graphs with relatively sparse links to the outside in the social network and topics are semantic coherent clusters of correlated words in the user generated textual contents. In the following, we review the related works and show the key points of our work. There are large volume of works about link emphasized community detection [3] and text emphasized topic modeling [7,1]. However, these works consider only one aspect (either links or contents) of the social network. Community detection algorithms discover communities by summarizing the link structure but ignoring the textual contents, while topic modeling regards the textual contents as a collection of separated documents without links among them. In the most recent studies, some models and algorithms are put forward to combine the links and contents. However, these works combine link structure and textual content either for community detection [18,4,11] or for topic modeling [9,5,8,15] only. Although [12] proposes Pairwise LinkLDA and Link-PLSA-LDA that take both the link structure and textual content into a uniﬁed generative model, both community and topic are modeled by using the same latent variable. In contrast, we explicitly discriminate community and topic from each other by modeling them via diﬀerent variables. Our model is motivated by the common sense that a community can be interested in more than one topics and a topic can be interested by more than one communities. In addition, community and topic are related together via the community-topic distributions in our model. Group-topic model [17] also discriminates group from topic. In group-topic model the textual contents are associated with events while in our model the textual contents are associated with users. Moreover, the textual contents in group-topic model is not generated by users but distributed by governments or oﬃcial organizations. Group-topic model can not be directly applied to solve the community and topic detection issues in our problem setting. Moreover, most previous works for community detection or topic modeling require the number of latent classes to be speciﬁed in advance. However, the appropriate number of latent classes are diﬃcult to estimate in prior. To alleviate this problem, we leverage non-parametric Bayesian approach, Hierarchical/Dirichlet Process Mixture model (H/DPM), to automatically select the number of communities and topics. Since community and topic can be enhanced by each other via community-topic distributions and the number of both communities and topics are allowed to grow inﬁnitely, our model is named mutual enhanced infinite generative model (MEI for short). The main contributions of this paper are summarized as follows. – A generative model MEI is proposed to model the social network with textual contents. This model explicitly discriminates community and topic from each other through modeling them by diﬀerent latent variables, and relates them together via community-topic distributions. Moreover, non-parametric

MEI: Mutual Enhanced Inﬁnite Generative Model

93

Bayesian approach H/DPM is employed to select the appropriate number of communities and topics automatically. Compared to the previous models, our model captures both the diﬀerence and correlation between community and topic. – The performance of MEI is evaluated and compared with several baseline community or topic models through experiments on the co-author network extracted from DBLP. Experimental results show MEI outperforms the baseline models in terms of both perplexity and link prediction performance. The rest of the paper is organized as follows. Section 2 proposes the mutual enhanced inﬁnite generative model. Section 3 gives out the Gibbs Sampling based learning algorithm. The experimental settings and results are reported in section 4 and we conclude this paper and show some future works in section 5.

2

Mutual Enhanced Infinite Generative Model

In this section, mutual enhanced inﬁnite generative model is proposed. Firstly, we present ﬁnite version of the model. Secondly, the inﬁnite version of the model is proposed by using Hierarchical/Dirichlet Process (H/DPM). Finally, we explain how the proposed model can allow the number of communities and topics grow inﬁnitely by using Chinese Restaurant Process metaphor. 2.1

Mutual Enhanced Generative Model

The graphical representation of the ﬁnite version of the proposed model, i.e. mutual enhanced generative model (ME), is shown in Figure 1. This model is actually a combination of Stochastic Block Model (SBM) [14] and Latent Dirichlet Allocation (LDA) [1]. Concretely, SBM is a generative model for the link emphasized community structure of the social network. It uses community-pair speciﬁc Binomial distributions to model the presence and absence of edges between pairs of users. LDA is a generative model for the textual contents associated with users. It models the generating process of words by using two Multinomial distributions, i.e user-speciﬁc topic distribution and topic-speciﬁc word distribution. The detailed generative process of ME for link structure and textual contents are very similar to SBM and LDA. The novel parts of ME compared to the previous models are community-topic distributions {φg }K g=1 , which correlate community and topic together. In ME generative model, the community variable k is mainly used to model the link structure of the social network while the topic variable z is used to model the textual content associated with users. Although community and topic model diﬀerent aspects of the social network, they can be integrated together to reﬁne each other. On one hand, communities are coherent parts of the social network, in which there are much denser links than to the outside. According to the homophyly phenomenon [10] in the social network, users from the same community tend to be interested in similar topics. Therefore, concatenating the

94

D. Duan et al.

S k

E

P

I

\

K

T

k

z

k r

wN M

M2

K

U K2

Fig. 1. Graphical representation of ME

textual contents associated with users from the same community together can beneﬁt the topic detection results. On the other hand, users with the similar topics tend to be from the same community, thus topics can also be leveraged to improve the community detection results. The mutual enhanced process is controlled by community-topic distribution, which naturally correlates community and topic together. In Figure 1, the number of communities and topics are ﬁxed to be K and T respectively. However, it is usually a diﬃcult task to specify the number of communities and topics in prior. Fortunately, Hierarchical/Dirichlet Process Mixture model (H/DPM) allows the number of latent classes to grow inﬁnitely in a probabilistic model, and they are widely used to select the appropriate number of latent classes in mixture models automatically. We employ H/DPM into ME, which forms mutual enhanced infinite generative model denoted as MEI for short. Next, we describe MEI in detail. 2.2

Mutual Enhanced Infinite Generative Model

Based on ME, MEI utilizes H/DPM to select the number of both communities and topics automatically. More precisely, DPM and HDP are used for modeling community part and topic part of ME respectively. In an informal but convenient way, we state that in community part the topical vectors z of users are observable while in topic part the community assignment k of users are known. For the purpose of clarity, Figure 2 illustrates the community part and topic part of ME in a graphical view. Following [13], DPM model for the community part is deﬁned as zi |θi ∼ f (zi ; θi ) θi |G ∼ G G ∼ DP (α, H0 )

(1)

where G is a Dirichlet Process with base measure H0 and concentration α, f (zi ; θi ) is a multinomial distribution with parameters θi = φki = {φki 1 , . . . , φki T } where ki denotes the community assignment of user i and T is the number of topics. For the purpose of simplicity, the base measure H0 is assumed to follow a symmetric Dirichlet prior with parameter β.

MEI: Mutual Enhanced Inﬁnite Generative Model

S

E I

k K

z

I

E k

k r

N M

M2

U K

95

z

P K

\

T

wN

g

K

2

(b)

(a)

Fig. 2. Graphical representation of (a) community part and (b) topic part

Following [16], HDP mixture model for topic part is deﬁned as wgn |θgn ∼ f (wgn ; θgn ) θgn |Gg ∼ Gg Gg |G0 ∼ DP (α0 , G0 ) G0 ∼ DP (γ, H)

(2)

where wgn is the n-th word in community g, Gg is a Dirichlet Process with concentration α0 and base measure G0 which is drawn from an overall Dirichlet Process with concentration γ and base measure H, f (wgn ; θgn ) is a multinomial distribution with parameters θgn = ψzgn = {ψzgn 1 , . . . , ψzgn V }, where zgn is the topic assigned to word wgn and V is the number of unique words in the vocabulary. The prior of base measure H is deﬁned as a symmetric Dirichlet distribution with parameter μ. H/DPM deﬁned above are formal enough to be understood. In the following, we resort to the Chinese Restaurant Process to describe the model in a more comprehensible way. 2.3

Chinese Restaurant Process Metaphor

Chinese restaurant process [16] can be used to explain how DPM and HDP allow the number of communities and topics to grow inﬁnitely. For the DPM in our model, each community corresponds to a table in a restaurant and each user corresponds to a customer. When a new customer is coming, she/he chooses a Cg , which is proportional to non-empty table g to sit at with probability M−1+α the number Cg of customers already sitting at that table, and chooses a new α . table with probability M−1+α For the HDP in our model, each community corresponds to a restaurant and there are inﬁnite number of tables in each restaurant. Each word corresponds to a customer and each topic corresponds to a dish on the global menu. In each restaurant, a customer chooses a non-empty table t to sit at with probability Cgt α0 +Ng −1 , which is proportional to the number Cgt of customers already sitting α0 . For each table, at that table, and chooses a new table with probability α0 +N g −1 Dl the waiter serves an existing dish l with probability γ+D , which is proportional to the number Dl of tables already served that dish, and serves a new dish with γ probability γ+D .

96

D. Duan et al.

As the above description, there is probability for assigning a new community to an user and a new topic to a word, thus DPM and HDP indeed allow the number of communities and topics to grow inﬁnitely.

3

Model Learning via Gibbs Sampling

In this section, Gibbs sampling based approach is presented for the learning of MEI model. Then the model parameters are estimated after the sampling process, and ﬁnally the settings for some hyper-parameters are discussed. 3.1

Sampling Equations

Inspired by the Gibbs sampling equation for DPM [13] and HDP [16], we list the sampling equations for our model. The detailed derivation of these equations is omitted due to space limit. Notice that in the following table refers to that in HDP not DPM, since in DPM a table is just a community. Sampling equation of the user community variables for each user i. p(ki = g|k−i , zi , z −i , r, α, β, ρ) ∝ ⎧ T −i −i Γ( T Cg l=1 Γ(Cgl +Cil +β) l=1 Cgl +T β) ⎪ ⎪ T T −i −i ⎪ M−1+α Γ( l=1 (C +Cil )+T β) ⎪ l=1 Γ(Cgl +β) gl ⎪ ⎪ ⎨ K (C +ρ)Γ(C +ρ)Γ(C −i +C −i +2ρ) gh gh gh gh × Cg−i > 0 −i −i Γ(C +C +2ρ)Γ(C gh gh gh +ρ)Γ(C gh +ρ) ⎪ h=1 ⎪ ⎪ T K ⎪ Γ(Cil +β) Γ(Cih +ρ)Γ(C ih +ρ)Γ(2ρ) ⎪ Γ(T β) α ⎪ Otherwise ⎩ M−1+α T Γ(β) Γ(l=1 T Cil +T β) Γ(Cih +C ih +2ρ)Γ(ρ)Γ(ρ) l=1

l=1

(3)

h=1

Sampling equation of the word table variables for each word wgn . p(tgn = t|t−gn , wgn = v, w−gn , z, α0 , γ, μ) ∝ ⎧ ⎨ Cgt V Clv +μ Cgt > 0 α0 +Ng −1 Clv +V μ v =1 T Γ(μ) C +μ γ Dl α0 lv ⎩ α +N + γ+D Γ(V μ) Otherwise V l=1 γ+D C +V μ 0 g −1 v =1

(4)

lv

Sampling equation of the table topic variables for a new table tnew when the word wgn is sampled to that table. Dl V Clv +μ Dl > 0 γ+D Clv +V μ v =1 (5) p(zgtnew = l|z−gtnew , wgn = v, w−gn , γ, μ) ∝ Γ(μ) γ Otherwise γ+D Γ(V μ) Sampling equation of the table topic variables for each table t in each community g. p(zgt = l|z−gt , wgt , w−gt , γ, μ) ∝ ⎧ V −gt Γ(Clv +Ctv +μ) Γ( V C −gt +V μ) ⎨ Dl V v=1 lv−gt v=1 Dl−gt > 0 −gt V γ+D Γ( (C +C )+V μ) Γ(C +μ) ⎩

tv V v=1 lv γ v=1 Γ(Ctv +μ) Γ(V μ) V γ+D Γ( V v=1 Ctv +V μ) v=1 Γ(μ)

v=1

lv

Otherwise

(6)

MEI: Mutual Enhanced Inﬁnite Generative Model

97

In all the above sampling equations, Γ(·) represents Gamma function and C·· and D· represent the number of samples during Gibbs sampling and superscript −gt ‘− ’ represents excluding the instances sampled currently. For example, Clv is number of topic l is assigned to word v excluding the words on the table t of community g, and Dl−gt is the number of tables assigned to topic l except the table t in community g. 3.2

Parameter Estimation Algorithm

Once the community assignment for each object and the topic assignment for K,K T each word are sampled, the model parameters {φg }K g=1 , {ψl }l=1 and {ηgh }g=1,h=1 can be estimated by using Maximum Likelihood Estimation (MLE) as follows. φgl = T

Cgl + β

l =1

Cgl + T β

ψlv = V

Clv + μ

v =1

Clv + V μ

ηgh =

Cgh + ρ Cgh + C gh + 2ρ

(7)

Based on all the above analysis and formulas, the learing algorithm for MEI is summarized in Algorithm 1. Algorithm 1. Parameter Estimation Algorithm for MEI

1 2 3 4 5 6 7

3.3

Input: A social network r = {rij |1 ≤ i, j ≤ M } and user generated textual contents wi = {wi1 , . . . , wiNi } for 1 ≤ i ≤ M Output: The community assignment for each object ki and the K,K T parameters {φg }K g=1 , {ψl }l=1 and {ηgh }g=1,h=1 Initialize the community of each object, the table and the topic associated with each word randomly; repeat Sample the community of each object through Eqn. 3; Sample the table of each word through Eqn. 4; If t is a new table, then sample the topic of that table through Eqn. 5; Sample the topic of each table through Eqn. 6; until Reaches Iteration Number ; K,K T Estimate model parameters {φg }K g=1 , {ψl }l=1 and {ηgh }g=1,h=1 through Eqn. 7; Hyper-parameter Setting

In the MEI model, there are some hyper-parameters, including the concentration parameters of Dirichlet Process, α, α0 , γ, and Dirichlet prior parameters β, μ, and Beta prior parameter ρ. For the Dirichlet prior parameters β and μ and ρ, we set all of them to be 0.01 empirically. For the concentration parameters, instead of setting them manually we sample them iteratively by using the method proposed in [16] and [2]. Those methods assume that the concentration parameters have Gamma priors and sample them with the help of one or two auxiliary variables. Particularly, in our model α,

98

D. Duan et al.

α0 and γ are supposed to have Gamma(1, 0.1), Gamma(1, 1), Gamma(1.0, 0.1) as priors respectively and set the iteration number for sampling these hyperparameters to be 20.

4 4.1

Experiments Evaluation Criterion

To evaluate the performance of MEI model, two widely used criterion, perplexity and link prediction performance, are used. Since MEI simultaneously models textual content and link structure, perplexity is used to measure how well MEI models the textual content and link prediction performance is used to measure how well MEI models the link structure. Perplexity. Perplexity [6] is a widely used measure to evaluate the generalization performance of a probability model. Lower perplexity value indicates better generalization performance. For MEI, the perplexity for a