TASK DEFINITION: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
PROBLEM: This paper describes a novel approach to learning term-weighting schemes (TWSs) in the context of text classification. In text mining a TWS determines the way in which documents will be represented in a vector space model, before applying a classifier. Whereas acceptable performance has been obtained with standard TWSs (e.g., Boolean and term-frequency schemes), the definition of TWSs has been traditionally an art. Further, it is still a difficult task to determine what is the best TWS for a particular problem and it is not clear yet, whether better schemes, than those currently available, can be generated by combining known TWS. We propose in this article a genetic program that aims at learning effective TWSs that can improve the performance of current schemes in text classification. The genetic program learns how to combine a set of basic units to give rise to discriminative TWSs. We report an extensive experimental study comprising data sets from thematic and non-thematic text classification as well as from image classification. Our study shows the validity of the proposed method; in fact, we show that TWSs learned with the genetic program outperform traditional schemes and other Corresponding author. Email addresses: hugojair@inaoep.mx (Hugo Jair Escalante), mauricio.garcia.cs@gmail.com (Mauricio A. Garćıa-Limón), a.morales@inaoep.mx (Alicia Morales-Reyes), mgraffg@gmail.com (Mario Graff), mmontesg@inaoep.mx (Manuel Montes-y-Gómez), emorales@inaoep.mx (Eduardo F. Morales) Preprint submitted to Elsevier October 8, 2014 TWSs proposed in recent works. Further, we show that TWSs learned from a specific domain can be effectively used for other tasks.

SOLUTION: Term-Weighting Learning via Genetic Programming for Text Classification

PROBLEM: We study truthful mechanisms for matching and related problems in a partial information<lb>setting, where the agents’ true utilities are hidden, and the algorithm only has access to ordi-<lb>nal preference information. Our model is motivated by the fact that in many settings, agents<lb>cannot express the numerical values of their utility for different outcomes, but are still able<lb>to rank the outcomes in their order of preference. Specifically, we study problems where the<lb>ground truth exists in the form of a weighted graph of agent utilities, but the algorithm can<lb>only elicit the agents’ private information in the form of a preference ordering for each agent<lb>induced by the underlying weights. Against this backdrop, we design truthful algorithms to<lb>approximate the true optimum solution with respect to the hidden weights. Our techniques<lb>yield universally truthful algorithms for a number of graph problems: a 1.76-approximation<lb>algorithm for Max-Weight Matching, 2-approximation algorithm for Max k-matching, a 6-<lb>approximation algorithm for Densest k-subgraph, and a 2-approximation algorithm for Max<lb>Traveling Salesman as long as the hidden weights constitute a metric. We also provide im-<lb>proved approximation algorithms for such problems when the agents are not able to lie about<lb>their preferences. Our results are the first non-trivial truthful approximation algorithms for<lb>these problems, and indicate that in many situations, we can design robust algorithms even<lb>when the agents may lie and only provide ordinal information instead of precise utilities.

SOLUTION: Truthful Mechanisms for Matching and Clustering in an Ordinal World

PROBLEM: Clustering categorical distributions in the probability simplex is a fundamental primitive often met in applications dealing with histograms or mixtures of multinomials. Traditionally, the differentialgeometric structure of the probability simplex has been used either by (i) setting the Riemannian metric tensor to the Fisher information matrix of the categorical distributions, or (ii) defining the informationgeometric structure induced by a smooth dissimilarity measure, called a divergence. In this paper, we introduce a novel computationally-friendly non-Riemannian framework for modeling the probability simplex: Hilbert simplex geometry. We discuss the pros and cons of those three statistical modelings, and compare them experimentally for clustering tasks.

SOLUTION:
Clustering in Hilbert simplex geometry