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: We present a method for solving implicit (factored) Markov decision processes (MDPs) with very large state spaces. We intro duce a property of state space partitions which we call f-homogeneity. Intuitively, an f-homogeneous partition groups together states that behave approximately the same under all or some subset of policies. Borrow ing from recent work on model minimization in computer-aided software verification, we present an algorithm that takes a factored representation of an MDP and an 0 f I and computes a factored f-homogeneous par tition of the state space. This partition defines a family of related MOPs-those MOP's with state space equal to the blocks of the partition, and transition probabilities "appro:X:imately" like those of any (original MDP) state in the source block. To formally study such families of MDPs, we introduce the new notion of a "bounded parameter MDP" (BMDP), which is a fam ily of (traditional) MOPs defined by speci fying upper and lower bounds on the transi tion probabilities and rewards. We describe algorithms that operate on BMDPs to find policies that are approximately optimal with respect to the original MDP. In combination, our method for reducing a large implicit MDP to a possibly much smaller BMDP using an f-homogeneous par tition, and our methods for selecting actions in BMDP's constitute a new approach for an alyzing large implicit MOP's. Among its ad vantages, this new approach provides insight into existing algorithms to solving implicit MDPs, provides useful connections to work in automata theory and model minimization, and suggests methods, which involve vary ing f, to trade time and space (specifically in terms of the size of the corresponding state space) for solution quality.

SOLUTION: Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes

PROBLEM: An extended, revised form of Tim Buckwalter's Arabic lexical and morphological resource AraMorph, eXtended Revised AraMorph (henceforth XRAM), is presented which addresses a number of weaknesses and inconsistencies of the original model by allowing a wider coverage of real-world Classical and contemporary (both formal and informal) Arabic texts. Building upon previous research, XRAM enhancements include (i) flag-selectable usage markers, (ii) probabilistic mildly context-sensitive POS tagging, filtering, disambiguation and ranking of alternative morphological analyses, (iii) semi-automatic increment of lexical coverage through extraction of lexical and morphological information from existing lexical resources. Testing of XRAM through a front-end Python module showed a remarkable success level.

SOLUTION: Semi-Automatic Data Annotation, POS Tagging and Mildly Context- Sensitive Disambiguation: the eXtended Revised AraMorph (XRAM)

PROBLEM: Sensory inference under conditions of uncertainty is a major problem in both machine learning and computational neuroscience. An important but poorly understood aspect of sensory processing is the role of active sensing. Here, we present a Bayes-optimal inference and control framework for active sensing, C-DAC (Context-Dependent Active Controller). Unlike previously proposed algorithms that optimize abstract statistical objectives such as information maximization (Infomax) [Butko and Movellan, 2010] or one-step look-ahead accuracy [Najemnik and Geisler, 2005], our active sensing model directly minimizes a combination of behavioral costs, such as temporal delay, response error, and sensor repositioning cost. We simulate these algorithms on a simple visual search task to illustrate scenarios in which contextsensitivity is particularly beneficial and optimization with respect to generic statistical objectives particularly inadequate. Motivated by the geometric properties of the CDAC policy, we present both parametric and non-parametric approximations, which retain context-sensitivity while significantly reducing computational complexity. These approximations enable us to investigate a more complex search problem involving peripheral vision, and we notice that the performance advantage of C-DAC over generic statistical policies is even more evident in this scenario.

SOLUTION:
Active Sensing as Bayes-Optimal Sequential Decision-Making