When Golog programs are used to control agents' behaviour in a high-level manner, their partial correctness naturally becomes an important concern. In this paper we propose a sound but incomplete method for automatic verification of partial correctness of Golog programs.  We introduce the notion of extended regression, which reduces partial correctness of Golog programs to first-order entailment problems.  During the process loop invariants are automatically discovered by heuristic methods.  We propose progression of small models wrt Golog programs, which are used to filter out too strong heuristic candidates.  In this way we combine the methods of static and dynamic analysis from the software engineering community.  Furthermore, our method can also be adapted to verify state constraints.  Experiments show that our method can not only handle sequential and nested loops uniformly in a reasonable among of time, but also be used to discover succinct and comprehensible loop invariants and state constraints.

Monte Carlo Tree Search (MCTS) is the state of the art algorithm for many games including the game of Go and General Game Playing (GGP). The standard algorithm for MCTS is Upper Confidence bounds applied to Trees (UCT). For games such as Go a big improvement over UCT is the Rapid Action Value Estimation (RAVE) heuristic. We propose to generalize the RAVE heuristic so as to have more accurate estimates near the leaves. We test the resulting algorithm named GRAVE for Atarigo, Knighthrough, Domineering and Go.

Abstractive summarization is an ideal form of summarization since it can synthesize information from multiple documents to create concise informative summaries. In this work, we aim at developing an abstractive summarizer. First, our proposed approach identifies the most important document in the multi-document set. The sentences in the most important document are aligned to sentences in other documents to generate clusters of similar sentences. Second, we generate K-shortest paths from the sentences in each cluster using a word-graph structure. Finally, we select sentences from the set of shortest paths generated from all the clusters employing a novel integer linear programming (ILP) model with the objective of maximizing information content and readability of the final summary. Our ILP model represents the shortest paths as binary variables and considers the length of the path, information score and linguistic quality score in the objective function. Experimental results on the DUC 2004 and 2005 multi-document summarization datasets show that our proposed approach outperforms all the baselines and state-of-the-art extractive summarizers as measured by the ROUGE scores. Our method also outperforms a recent abstractive summarization technique. In manual evaluation, our approach also achieves promising results on informativeness and readability.

The goal of query conceptualization is to map instances in a query to concepts defined in a certain ontology or knowledge base. Queries usually do not observe the syntax of a written language, nor do they contain enough signals for statistical inference. However, the available context, i.e., the verbs related to the instances, the adjectives and attributes of the instances, do provide valuable clues to understand instances. In this paper, we first mine a variety of relations among terms from a large web corpus and map them to related concepts using a probabilistic knowledge base. Then, for a given query, we conceptualize terms in the query using a random walk based iterative algorithm. Finally, we examine our method on real data and compare it to representative previous methods. The experimental results show that our method achieves higher accuracy and efficiency in query conceptualization.

In practical applications, it is often observed that high-dimensional features can yield good performance, while being more costly in both computation and storage. In this paper, we propose a novel method called Bayesian Hashing to learn an optimal Hamming embedding of high-dimensional features, with a focus on the challenging application of face recognition. In particular, a boosted random FERNs classification model is designed to perform efficient face recognition, in which bit correlations are elaborately approximated with a random permutation technique. Without incurring additional storage cost, multiple random permutations are then employed to train a series of classifiers for achieving better discrimination power. In addition, we introduce a sequential forward floating search (SFFS) algorithm to perform model selection, resulting in further performance improvement. Extensive experimental evaluations and comparative studies clearly demonstrate that the proposed Bayesian Hashing approach outperforms other peer methods in both accuracy and speed. We achieve state-of-the-art results on well-known face recognition benchmarks using compact binary codes with significantly reduced computational overload and storage cost.

We study truthful mechanisms in the context of cake cutting when agents not only value their own pieces of cake but also care for the pieces assigned to other agents. In particular, agents derive benefits or costs from the pieces of cake assigned to other agents. This phenomenon is often referred to as positive or negative externalities. We propose and study the following model: given an allocation, externalities of agents are modeled as percentages of the reported values that other agents have for their pieces. We show that even in this restricted class of externalities, under some natural assumptions, no truthful cake cutting mechanisms exist when externalities are either positive or negative. However, when the percentages agents get from each other are small, we show that there exists a truthful cake cutting mechanism with other desired properties.

The preferences of users are important in route search and planning. For example, when a user plans a trip within a city, their preferences can be expressed as keywords shopping mall, restaurant, and museum, with weights 0.5, 0.4, and 0.1, respectively. The resulting route should best satisfy their weighted preferences. In this paper, we take into account the weighted user preferences in route search, and present a keyword coverage problem, which finds an optimal route from a source location to a target location such that the keyword coverage is optimized and that the budget score satisfies a specified constraint. We prove that this problem is NP-hard. To solve this complex problem, we pro- pose an optimal route search based on an A* variant for which we have defined an admissible heuristic function. The experiments conducted on real-world datasets demonstrate both the efficiency and accu- racy of our proposed algorithms.

It is notable In real world applications, data are often with multiple that strong modal features can lead to a better performance, modalities. Previous works assumed that each nevertheless, are more expensive, therefore a group of serialized modality contains sufficient information for target feature extraction methods were proposed. These methods and can be treated with equal importance. However, extract weak modal features firstly, and then extract more it is often that different modalities are of various strong modal features gradually to improve the performance importance in real tasks, e.g., the facial feature and reduce the overall cost as well. Marcialis et al.[2010] proposed is weak modality and the fingerprint feature is a serial fusion technique for multiple biometric modal strong modality in ID recognition. In this paper, we features through extracting gaits information and face information point out that different modalities should be treated step by step; Zhang et al.[2014] addressed the serialized with different strategies and propose the Auxiliary multi-modal learning techniques in a semi-supervised information Regularized Machine (ARM), which learning scenario. These methods handle strong and weak works by extracting the most discriminative feature modalities independently while leaving the fact of unsatisfied subspace of weak modality while regularizing the performance on weak modality unexplained.

The overwhelming amount of short text data on social media and elsewhere has posed great challenges to topic modeling due to the sparsity problem. Most existing attempts to alleviate this problem resort to heuristic strategies to aggregate short texts into pseudo-documents before the application of standard topic modeling. Although such strategies cannot be well generalized to more general genres of short texts, the success has shed light on how to develop a generalized solution. In this paper, we present a novel model towards this goal by integrating topic modeling with short text aggregation during topic inference. The aggregation is founded on general topical affinity of texts rather than particular heuristics, making the model readily applicable to various short texts. Experimental results on real-world datasets validate the effectiveness of this new model, suggesting that it can distill more meaningful topics from short texts.

Reordering model adaptation remains a big challenge in statistical machine translation because reordering patterns of translation units often vary dramatically from one domain to another. In this paper, we propose a novel adaptive discriminative reordering model (DRM) based on structural learning, which can capture correspondences among reordering features from two different domains. Exploiting both in-domain and out-of-domain monolingual corpora, our model learns a shared feature representation for cross-domain phrase reordering. Incorporating features of this representation, the DRM trained on out-of-domain corpus generalizes better to in-domain data. Experiment results on the NIST Chinese-English translation task show that our approach significantly outperforms a variety of baselines.