While parallel corpora are an indispensable resource for data-driven multilingual natural language processing tasks such as machine translation, they are limited in quantity, quality and coverage. As a result, learning translation models from non-parallel corpora has become increasingly important nowadays, especially for low-resource languages. In this work, we propose a joint model for iteratively learning parallel lexicons and phrases from nonparallel corpora. The model is trained using a Viterbi EM algorithm that alternates between constructing parallel phrases using lexicons and updating lexicons based on the constructed parallel phrases. Experiments on Chinese-English datasets show that our approach learns better parallel lexicons and phrases and improves translation performance significantly.

Most word embedding methods take a word as a basic unit and learn embeddings according to words' external contexts, ignoring the internal structures of words. However, in some languages such as Chinese, a word is usually composed of several  characters and contains rich internal information. The semantic meaning of a word is also related to the meanings of its composing characters. Hence, we take Chinese for example, and present a character-enhanced word embedding model (CWE). In order to address the issues of character ambiguity and non-compositional words, we propose multiple-prototype character embeddings and an effective word selection method. We evaluate the effectiveness of CWE on word relatedness computation and analogical reasoning. The results show that CWE outperforms other baseline methods which ignore internal character information.

Learning representations for semantic relations is important for various tasks such as analogy detection, relational search, and relation classification.Although there have been several proposals for learning representations for individual words,learning word representations that explicitly capture the semantic relations between words remains under developed.We propose an unsupervised method for learning vector representations for words such that the learnt representations are sensitive to the semantic relations that exist between two words.First, we extract lexical patterns from the co-occurrence contexts of two words in a corpus to represent the semantic relations that exist between those two words.Second, we represent a lexical pattern as the weighted sum of the representations of the words that co-occur with that lexical pattern. Third, we train a binary classifier to detect relationally similar versus non-similar lexical pattern pairs.The proposed method is unsupervised in the sense that the lexical pattern pairs we use as train data are automatically sampled from a corpus, without requiring any manual intervention.Our proposed method statistically significantly outperforms the current state-of-the-art word representations on three benchmark datasets for proportional analogy detection, demonstrating its ability to accurately capture the semantic relations among words.

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 margin of victory of an election is a useful measure to capture the robustness of an election outcome. It also plays a crucial role in determining the sample size of various algorithms in post election audit, polling etc. In this work, we present efficient sampling based algorithms for estimating the margin of victory of elections. More formally, we introduce the (c, ε, δ)–MARGIN OF VICTORY problem, where given an election E on n voters, the goal is to estimate the margin of victory M(E) of E within an additive factor of cM(E)+εn. We study the (c, ε, δ)–MARGIN OF VICTORY problem for many commonly used voting rules including scoring rules, approval, Bucklin, maximin, and Copelandα. We observe that even for the voting rules for which computing the margin of victory is NP-Hard, there may exist efficient sampling based algorithms, as observed in the cases of maximin and Copelandα voting rules.

In this work, we investigate the problem of large-scale mobile crowdsourcing, where workers are financially motivated to perform location-based tasks physically. Unlike current industry practice that relies on workers to manually pick tasks to perform, we automatically make task recommendation based on workers' historical trajectories and desired time budgets. The challenge of predicting workers' trajectories is that it is faced with uncertainties, as a worker does not take same routes every day. In this work, we depart from deterministic modeling and study the stochastic task recommendation problem where each worker is associated with several predicted routine routes with probabilities. We formulate this problem as a stochastic integer linear program whose goal is to maximize the expected total utility achieved by all workers. We further exploit the separable structures of the formulation and apply the Lagrangian relaxation technique to scale up computation. Experiments have been performed over the instances generated using the real Singapore transportation network. The results show that we can find significantly better solutions than the deterministic formulation.

The probabilistic serial (PS) rule is a prominent randomized rule for assigning indivisible goods to agents. Although it is well known for its good fairness and welfare properties, it is not strategyproof. In view of this, we address several fundamental questions regarding equilibria under PS. Firstly, we show that Nash deviations under the PS rule can cycle. Despite the possibilities of cycles, we prove that a pure Nash equilibrium is guaranteed to exist under the PS rule. We then show that verifying whether a given profile is a pure Nash equilibrium is coNP-complete, and computing a pure Nash equilibrium is NP-hard. For two agents, we present a linear-time algorithm to compute a pure Nash equilibrium which yields the same assignment as the truthful profile. Finally, we conduct experiments to evaluate the quality of the equilibria that exist under the PS rule, finding that the vast majority of pure Nash equilibria yield social welfare that is at least that of the truthful profile.

In this work, we target at the problem of offline sketch parsing, in which the temporal orders of strokes are unavailable. It is more challenging than most of existing work, which usually leverages the temporal information to reduce the search space. Different from traditional approaches in which thousands of candidate groups are selected for recognition, we propose the idea of shapeness estimation to greatly reduce this number in a very fast way. Based on the observation that most of hand-drawn shapes with well-defined closed boundaries can be clearly differentiated from non-shapes if normalized into a very small size, we propose an efficient shapeness estimation method. A compact feature representation as well as its efficient extraction method is also proposed to speed up this process. Based on the proposed shapeness estimation, we present a three-stage cascade framework for offline sketch parsing. The shapeness estimation technique in this framework greatly reduces the number of false positives, resulting in a 96.2% detection rate with only 32 candidate group proposals, which is two orders of magnitude less than existing methods. Extensive experiments show the superiority of the proposed framework over state-of-the-art works on sketch parsing in both effectiveness and efficiency, even though they leveraged the temporal information of strokes.

Geometry reasoning and proof form a major and challenging component in the K-121 mathematics curriculum. Although several computerized systems exist that help students learn and practice general geometry concepts, they do not target geometry proof problems, which are more advanced and difficult. Powerful geometry theorem provers also exist, however they typically employ advanced algebraic methods and generate complex, difficult to understand proofs, and thus do not meet general K-12 students’ educational needs. This paper tackles these weaknesses of prior systems by introducing a geometry proof system, iGeoTutor, capable of generating human-readable elementary proofs, i.e. proofs using standard Euclidean axioms. We have gathered 77 problems in total from various sources, including ones unsolvable by other systems and from Math competitions. iGeoTutor solves all but two problems in under two minutes each, and more importantly, demonstrates a much more effective and intelligent proof search than prior systems. We have also conducted a pilot study with 12 high school students, and the results show that iGeoTutor provides a clear benefit in helping students learn geometry proofs. We are in active discussions with Khan Academy and local high schools for possible adoption of iGeo-Tutor in real learning environments.

We consider a setting where a team of humans oversee the coordination of multiple Unmanned Aerial Vehicles (UAVs) to perform a number of search tasks in dynamic environments that may cause the UAVs to drop out. Hence, we develop a set of multi-UAV supervisory control interfaces and a multi-agent coordination algorithm to support human decision making in this setting. To elucidate the resulting interactional issues, we compare manual and mixed-initiative task allocation in both static and dynamic environments in lab studies with 40 participants and observe that our mixed-initiative system results in lower workloads and better performance in re-planning tasks than one which only involves manual task allocation. Our analysis points to new insights into the way humans appropriate flexible autonomy.