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: Despite progress in visual perception tasks such as image classification and detection, computers still struggle to understand the interdependency of objects in the scene as a whole, e.g., relations between objects or their attributes. Existing methods often ignore global context cues capturing the interactions among different object instances, and can only recognize a handful of types by exhaustively training individual detectors for all possible relationships. To capture such global interdependency, we propose a deep Variation-structured Reinforcement Learning (VRL) framework to sequentially discover object relationships and attributes in the whole image. First, a directed semantic action graph is built using language priors to provide a rich and compact representation of semantic correlations between object categories, predicates, and attributes. Next, we use a variation-structured traversal over the action graph to construct a small, adaptive action set for each step based on the current state and historical actions. In particular, an ambiguity-aware object mining scheme is used to resolve semantic ambiguity among object categories that the object detector fails to distinguish. We then make sequential predictions using a deep RL framework, incorporating global context cues and semantic embeddings of previously extracted phrases in the state vector. Our experiments on the Visual Relationship Detection (VRD) dataset and the large-scale Visual Genome dataset validate the superiority of VRL, which can achieve significantly better detection results on datasets involving thousands of relationship and attribute types. We also demonstrate that VRL is able to predict unseen types embedded in our action graph by learning correlations on shared graph nodes.

SOLUTION: Deep Variation-structured Reinforcement Learning for Visual Relationship and Attribute Detection

PROBLEM: We consider the design of online learning algorithms in a general learning setting, with the goal of obtaining computationally efficient no-regret algorithms, when given access to an oracle for the offline optimization version of the problem. We present an algorithm that we call Generalized Follow-thePerturbed-Leader (Generalized FTPL) and provide conditions under which it achieves vanishing regret and is efficiently implementable with an oracle. Our second main contribution is the introduction of a new online adversarial auction-design framework for revenue maximization and an application of our oracle-efficient learning results to the adaptive optimization of auctions. Our learning algorithm is a generalization of the classic FTPL algorithm of Kalai and Vempala [27], playing at every iteration the historically best-performing action after adding some perturbation to the performance of each of its actions. The crux of our design is adding perturbations in a manner that leads to oracle-efficiency. We reduce this to designing a translation matrix, which translates a low dimensional vector with independent noise components into a high dimensional vector of perturbations on the learner’s action space. Our approach generalizes prior work on oracle-efficient online learning [11, 22, 27, 35], ranging from online combinatorial optimization, learning in simultaneous auctions, and contextual learning. Our auction-design framework considers an auctioneer learning an optimal auction rule in an online manner, every day observing an adversarially chosen vector of valuations. The auctioneer’s goal is to achieve revenue that competes with the revenue of the optimal auction in hindsight among those in some target class. We give oracle-efficient learning results for: (1) VCG auctions with bidder-specific reserves in single-parameter settings with matroid constraints, (2) envy-free item pricing in multi-item auctions with unlimited supply, and (3) s-level auctions of Morgenstern and Roughgarden [28] for singleitem settings. The last result implies good regret against the optimal overall auction when valuations are coming from a fast mixing Markov chain, that is independent across bidders. We also extend our results to the case when the learner observes side information on the bidders before running the auction (contextual learning). We present additional extensions to contextual learning and learning with approximate oracles, implemented by FPTAS or Maximal-in-Range algorithms. We provide further applications in online welfare maximization in multi-unit auctions and in no-regret learning in simultaneous item auctions, answering an open question from prior work. ∗Microsoft Research, New York, mdudik@microsoft.com †Computer Science Department, Carnegie Mellon University, nhaghtal@cs.cmu.edu ‡Microsoft Research, New York, haipeng@microsoft.com §Microsoft Research, New York, schapire@microsoft.com ¶Microsoft Research, New England, vasy@microsoft.com ‖Microsoft Research, New York, jenn@microsoft.com ar X iv :1 61 1. 01 68 8v 1 [ cs .L G ] 5 N ov 2 01 6

SOLUTION: Oracle-Efficient Learning and Auction Design

PROBLEM: Scikit-learn is a Python module integrating a wide range of state-of-the-art machine learning algorithms for medium-scale supervised and unsupervised problems. This package focuses on bringing machine learning to non-specialists using a general-purpose high-level language. Emphasis is put on ease of use, performance, documentation, and API consistency. It has minimal dependencies and is distributed under the simplified BSD license, encouraging its use in both academic and commercial settings. Source code, binaries, and documentation can be downloaded from http://scikit-learn.sourceforge.net.

SOLUTION:
Scikit-learn: Machine Learning in Python