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: 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: We introduce a novel training principle for probabilistic models that is an alternative to maximum likelihood. The proposed Generative Stochastic Networks (GSN) framework is based on learning the transition operator of a Markov chain whose stationary distribution estimates the data distribution. The transition distribution of the Markov chain is conditional on the previous state, generally involving a small move, so this conditional distribution has fewer dominant modes, being unimodal in the limit of small moves. Thus, it is easier to learn because it is easier to approximate its partition function, more like learning to perform supervised function approximation, with gradients that can be obtained by backprop. We provide theorems that generalize recent work on the probabilistic interpretation of denoising autoencoders and obtain along the way an interesting justification for dependency networks and generalized pseudolikelihood, along with a definition of an appropriate joint distribution and sampling mechanism even when the conditionals are not consistent. GSNs can be used with missing inputs and can be used to sample subsets of variables given the rest. We validate these theoretical results with experiments on two image datasets using an architecture that mimics the Deep Boltzmann Machine Gibbs sampler but allows training to proceed with simple backprop, without the need for layerwise pretraining. P(X)

SOLUTION: Deep Generative Stochastic Networks Trainable by Backprop

PROBLEM: In this paper, we propose a universal model for high-dimensional data, called the Hybrid Orthogonal Projection and Estimation (HOPE) model, which combines a linear orthogonal projection and a finite mixture model under a unified generative modelling framework. The HOPE model itself can be learned unsupervisedly from un-labelled data based on the maximum likelihood estimation as well as trained discriminatively from labelled data. More interestingly, we have shown the proposed HOPE models are closely related to neural networks (NNs) in a sense that each hidden layer can be reformulated as a HOPE model. As a result, the HOPE framework can be used as a novel tool to probe why and how NNs work, more importantly, it also provides several new learning algorithms to learn NNs either supervisedly or unsupervisedly. In this work, we have investigated the HOPE framework in learning NNs for several standard tasks, including image recognition on MNIST and speech recognition on TIMIT. Experimental results show that the HOPE framework yields significant performance gains over the current stateof-the-art methods in various types of NN learning problems, including unsupervised feature learning, supervised or semi-supervised learning.

SOLUTION:
Hybrid Orthogonal Projection and Estimation (HOPE): A New Framework to Probe and Learn Neural Networks