While the most accurate word sense disambiguation systems are built using supervised learning from sense-tagged data, scaling them up to all words of a language has proved elusive, since preparing a sense-tagged corpus for all words of a language is time-consuming and human labor intensive. In this paper, we propose and implement a completely automatic approach to scale up word sense disambiguation to all words of English.  Our approach relies on English-Chinese parallel corpora, English-Chinese bilingual dictionaries, and automatic methods of finding synonyms of Chinese words. No additional human sense annotations or word translations are needed. We conducted a large-scale empirical evaluation on more than 29,000 noun tokens in English texts annotated in OntoNotes 2.0, based on its coarse-grained sense inventory.  The evaluation results show that our approach is able to achieve high accuracy, outperforming the first-sense baseline and coming close to a prior reported approach that requires manual human efforts to provide Chinese translations of English senses.

This paper presents a novel approach to the estimation of user's affective states in Human-Computer Interaction. Most of the present approaches divide emotions strictly between positive or negative. However, recent discoveries in the field of Emotional Intelligence show that emotions should be rather perceived as context-sensitive engagements with the world. This leads to a need to specify whether the emotions conveyed in a conversation are appropriate for a situation they are expressed in. In the proposed method we use a system for affect analysis on textual input to recognize users’ emotions and a Web mining technique to verify the contextual appropriateness of those emotions. On this basis a conversational agent can choose to either sympathize with the user or help them manage their emotions. Finally, the results of evaluation of the proposed method with two different conversational agents are discussed, and perspectives for further development of the method are proposed.

Strategyproof classification deals with a setting where a decision-maker must classify a set of input points with binary labels, while minimizing the expected error. The labels of the input points are reported by self-interested agents, who might lie in order to obtain a classifier that more closely matches their own labels, thus creating a bias in the data; this motivates the design of truthful mechanisms that discourage false reports. Previous work [Meir et al., 2008] investigated both decision-theoretic and learning-theoretic variations of the setting, but only considered classifiers that belong to a degenerate class. In this paper we assume that the agents are interested in a shared set of input points. We show that this plausible assumption leads to powerful results. In particular, we demonstrate that variations of a truthful random dictator mechanism can guarantee approximately optimal outcomes with respect to any class of classifiers.

To apply hierarchical task network (HTN) planning to real-world planning problems, one needs to encode the HTN schemata and action models beforehand. However, acquiring such domain knowledge is difficult and time-consuming because the HTN domain definition involves a significant knowledge-engineering effort. A system that can learn the HTN planning domain knowledge automatically would save time and allow HTN planning to be used in domains where such knowledge-engineering effort is not feasible. In this paper, we present a formal framework and algorithms to acquire HTN planning domain knowledge, by learning the preconditions and effects of actions and preconditions of methods. Our algorithm, HTN-learner, first builds constraints from given observed \emph{decomposition trees} to build action models and method preconditions. It then solves these constraints using a weighted MAX-SAT solver. The solution can be converted to action models and method preconditions. Unlike prior work on HTN learning, we do not depend on complete action models or state information. We test the algorithm on several domains, and show that our HTN-learner algorithm is both effective and efficient.

In this paper, we propose a new spectral clustering method, referred to as Spectral Embedded Clustering (SEC), to minimize the normalized cut criterion in spectral clustering as well as control the mismatch between the cluster assignment matrix and the low dimensional embedded representation of the data. SEC is based on the observation that the cluster assignment matrix of high dimensional data can be represented by a low dimensional linear mapping of data. We also discover the connection between SEC and other clustering methods, such as spectral clustering, Clustering with local and global regularization, K-means and Discriminative K-means. The experiments on many real-world data sets show that SEC significantly outperforms the existing spectral clustering methods as well as K-means clustering related methods.

Recommender systems attempt to highlight items that a target user is likely to find interesting. A common technique is to use collaborative filtering (CF), where multiple users share information so as to provide each with effective recommendations. A key aspect of CF systems is finding users whose tastes accurately reflect the tastes of some target user. Typically, the system looks for other agents who have had experience with many of the items the target user has examined, and whose classification of these items has a strong correlation with the classifications of the target user. Since the universe of items may be enormous and huge data sets are involved, sophisticated methods must be used to quickly locate appropriate other agents. We present a method for quickly determining the proportional intersection between the items that each of two users has examined, by sending and maintaining extremely concise “sketches” of the list of items. These sketches enable the approximation of the proportional intersection within a distance of \epsilon, with a high probability of 1-\delta. Our sketching techniques are based on random minwise independent hash functions, and use very little space and time, so they are well-suited for use in large-scale collaborative filtering systems.

This paper deals with evolutionary clustering, which refers to the problem of clustering data with distribution drifting along time. Starting from a density estimation view to clustering problems, we propose two general on-line frameworks. In the first framework, i.e., historical data dependent (HDD), current model distribution is designed to approximate both current and historical data distributions. In the second framework, i.e., historical model dependent (HMD), current model distribution is designed to approximate both current data distribution and historical model distribution. Both frameworks are based on the general exponential family mixture (EFM) model. As a result, all conventional clustering algorithms based on EFMs can be extended to evolutionary setting under the two frameworks. Empirical results validate the two frameworks.

Most of the existing metric learning methods are accomplished by exploiting pairwise constraints over the labeled data and frequently suffer from the insufficiency of training examples.  To learn a robust distance metric from few labeled examples, prior knowledge from unlabeled examples as well as the metrics previously derived from auxiliary data sets can be useful.  In this paper, we propose to leverage such auxiliary knowledge to assist distance metric learning, which is formulated following the regularized loss minimization principle.  Two algorithms are derived on the basis of manifold regularization and log-determinant divergence regularization technique, respectively, which can simultaneously exploit label information (i.e., the pairwise constraints over labeled data), unlabeled examples, and the metrics derived from auxiliary data sets.  The proposed methods directly manipulate the auxiliary metrics and require no raw examples from the auxiliary data sets, which make them efficient and flexible.  We conduct extensive evaluations to compare our approaches with a number of competing approaches on face recognition task.  The experimental results show that our approaches can derive reliable distance metrics from limited training examples and thus are superior in terms of accuracy and labeling efforts.

This study examines the ability of a semantic space model to represent the meaning of noun compounds such as "information gathering" or "weather forecast," A new algorithm,  comparison, is proposed for computing compound vectors from constituent word vectors, and compared with other algorithms (i.e., predication and centroid) in terms of accuracy of multiple-choice synonym test and similarity judgment test. The result of both tests is that the comparison algorithm is, on the whole, superior to other algorithms, and in particular achieves the best performance when noun compounds have emergent meanings. Furthermore, the comparison algorithm also works for novel noun compounds that do not occur in the corpus. These findings indicate that a semantic space model in general and the comparison algorithm in particular has sufficient ability to compute the meaning of noun compounds.

A folksonomy refers to a collection of user-defined tags with which users describe contents published  on the Web. With the flourish of Web 2.0, folksonomies have become an important mean to develop the Semantic Web. Because tags in folksonomies are authored freely, there is a need to understand the structure and semantics of these tags in various applications. In this paper, we propose a learning approach to create an ontology that captures the hierarchical semantic structure of folksonomies. Our experimental results on two different genres of real world data sets show that our method can effectively learn the ontology structure from the folksonomies.