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.

Input: Consider Input: Standard belief change assumes an underlying logic containing full classical propositional logic. However, there are good reasons for considering belief change in less expressive logics as well. In this paper we build on recent investigations by Delgrande on contraction for Horn logic. We show that the standard basic form of contraction, partial meet, is too strong in the Horn case. This result stands in contrast to Delgrande’s conjecture that orderly maxichoice is the appropriate form of contraction for Horn logic. We then define a more appropriate notion of basic contraction for the Horn case, influenced by the convexity property holding for full propositional logic and which we refer to as infra contraction. The main contribution of this work is a result which shows that the construction method for Horn contraction for belief sets based on our infra remainder sets corresponds exactly to Hansson’s classical kernel contraction for belief sets, when restricted to Horn logic. This result is obtained via a detour through contraction for belief bases. We prove that kernel contraction for belief bases produces precisely the same results as the belief base version of infra contraction. The use of belief bases to obtain this result provides evidence for the conjecture that Horn belief change is best viewed as a ‘hybrid’ version of belief set change and belief base change. One of the consequences of the link with base contraction is the provision of a representation result for Horn contraction for belief sets in which a version of the Core-retainment postulate features.

Output: On the Link between Partial Meet, Kernel, and Infra Contraction and its Application to Horn Logic


Input: Consider Input: 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

Output: Oracle-Efficient Learning and Auction Design


Input: Consider Input: Standard LDA model suffers the problem that the topic assignment of each word is independent and word correlation hence is neglected. To address this problem, in this paper, we propose a model called Word Related Latent Dirichlet Allocation (WR-LDA) by incorporating word correlation into LDA topic models. This leads to new capabilities that standard LDA model does not have such as estimating infrequently occurring words or multi-language topic modeling. Experimental results demonstrate the effectiveness of our model compared with standard LDA.


Output: Modeling Word Relatedness in Latent Dirichlet Allocation