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: Formal languages for probabilistic modeling enable re-use, modularity, and descriptive clarity, and can foster generic inference techniques. We introduce Church, a universal language for describing stochastic generative processes. Church is based on the Lisp model of lambda calculus, containing a pure Lisp as its deterministic subset. The semantics of Church is defined in terms of evaluation histories and conditional distributions on such histories. Church also includes a novel language construct, the stochastic memoizer, which enables simple description of many complex non-parametric models. We illustrate language features through several examples, including: a generalized Bayes net in which parameters cluster over trials, infinite PCFGs, planning by inference, and various non-parametric clustering models. Finally, we show how to implement query on any Church program, exactly and approximately, using Monte Carlo techniques.

SOLUTION: Church: a language for generative models

PROBLEM: The computational cost of many signal processing and machine learning techniques is often dominated by the cost of applying certain linear operators to high-dimensional vectors. This paper introduces an algorithm aimed at reducing the complexity of applying linear operators in high dimension by approximately factorizing the corresponding matrix into few sparse factors. The approach relies on recent advances in non-convex optimization. It is first explained and analyzed in details and then demonstrated experimentally on various problems including dictionary learning for image denoising, and the approximation of large matrices arising in inverse problems.

SOLUTION: Flexible Multi-layer Sparse Approximations of Matrices and Applications

PROBLEM: We explore the use of segments learnt using Byte Pair Encoding (referred to as BPE units) as basic units for statistical machine translation between related languages and compare it with orthographic syllables, which are currently the best performing basic units for this translation task. BPE identifies the most frequent character sequences as basic units, while orthographic syllables are linguistically motivated pseudo-syllables. We show that BPE units outperform orthographic syllables as units of translation, showing up to 11% increase in BLEU scores. In addition, BPE can be applied to any writing system, while orthographic syllables can be used only for languages whose writing systems use vowel representations. We show that BPE units outperform word and morpheme level units for translation involving languages like Urdu, Japanese whose writing systems do not use vowels (either completely or partially). Across many language pairs, spanning multiple language families and types of writing systems, we show that translation with BPE segments outperforms orthographic syllables, especially for morphologically rich languages.

SOLUTION:
Learning variable length units for SMT between related languages via Byte Pair Encoding