We study decompositions of the global NVALUE constraint. Our main contribution is theoretical: we show that there are propagators for global constraints like NVALUE which decomposition can simulate with the same time complexity but with a much greater space complexity. This suggests that the benefit of a global propagator may often not be in saving time but in saving space. Our other theoretical contribution is to show for the first time that range consistency can be enforced on NVALUE with the same worst-case time complexity as bound consistency. Finally, the decompositions we study are readily encoded as linear inequalities. We are therefore able to use them in integer linear programs.

We consider a common type of symmetry where we have a matrix of decision variables with interchangeable rows and columns. A simple and efficient method to deal with such row and column symmetry is to post symmetry breaking constraints like DOUBLELEX and SNAKELEX. We provide a number of positive and negative results on posting such symmetry breaking constraints. On the positive side, we prove that we can compute in polynomial time a unique representative of an equivalence class in a matrix model with row and column symmetry if the number of rows (or of columns) is bounded and in a number of other special cases. On the negative side, we show that whilst DOUBLELEX and SNAKELEX are often effective in practice, they can leave a large number of symmetric solutions in the worst case. In addition, we prove that propagating DOUBLELEX completely is NP-hard. Finally we consider how to break row, column and value symmetry, correcting a result in the literature about the safeness of combining different symmetry breaking constraints. We end with the first experimental study on how much symmetry is left by DOUBLELEX and SNAKELEX on some benchmark problems.

Components of biological systems interact with each other in order to carry out vital cell functions. Such information can be used to improve estimation and inference, and to obtain better insights into the underlying cellular mechanisms. Discovering regulatory interactions among genes is therefore an important problem in systems biology. Whole-genome expression data over time provides an opportunity to determine how the expression levels of genes are affected by changes in transcription levels of other genes, and can therefore be used to discover regulatory interactions among genes. In this paper, we propose a novel penalization method, called truncating lasso, for estimation of causal relationships from time-course gene expression data. The proposed penalty can correctly determine the order of the underlying time series, and improves the performance of the lasso-type estimators. Moreover, the resulting estimate provides information on the time lag between activation of transcription factors and their effects on regulated genes. We provide an efficient algorithm for estimation of model parameters, and show that the proposed method can consistently discover causal relationships in the large $p$, small $n$ setting. The performance of the proposed model is evaluated favorably in simulated, as well as real, data examples. The proposed truncating lasso method is implemented in the R-package grangerTlasso and is available at http://www.stat.lsa.umich.edu/~shojaie.

This paper studies non-asymptotic model selection for the general case of arbitrary design matrices and arbitrary nonzero entries of the signal. In this regard, it generalizes the notion of incoherence in the existing literature on model selection and introduces two fundamental measures of coherence---termed as the worst-case coherence and the average coherence---among the columns of a design matrix. It utilizes these two measures of coherence to provide an in-depth analysis of a simple, model-order agnostic one-step thresholding (OST) algorithm for model selection and proves that OST is feasible for exact as well as partial model selection as long as the design matrix obeys an easily verifiable property. One of the key insights offered by the ensuing analysis in this regard is that OST can successfully carry out model selection even when methods based on convex optimization such as the lasso fail due to the rank deficiency of the submatrices of the design matrix. In addition, the paper establishes that if the design matrix has reasonably small worst-case and average coherence then OST performs near-optimally when either (i) the energy of any nonzero entry of the signal is close to the average signal energy per nonzero entry or (ii) the signal-to-noise ratio in the measurement system is not too high. Finally, two other key contributions of the paper are that (i) it provides bounds on the average coherence of Gaussian matrices and Gabor frames, and (ii) it extends the results on model selection using OST to low-complexity, model-order agnostic recovery of sparse signals with arbitrary nonzero entries.

Variable selection and dimension reduction are two commonly adopted approaches for high-dimensional data analysis, but have traditionally been treated separately. Here we propose an integrated approach, called sparse gradient learning (SGL), for variable selection and dimension reduction via learning the gradients of the prediction function directly from samples. By imposing a sparsity constraint on the gradients, variable selection is achieved by selecting variables corresponding to non-zero partial derivatives, and effective dimensions are extracted based on the eigenvectors of the derived sparse empirical gradient covariance matrix. An error analysis is given for the convergence of the estimated gradients to the true ones in both the Euclidean and the manifold setting. We also develop an efficient forward-backward splitting algorithm to solve the SGL problem, making the framework practically scalable for medium or large datasets. The utility of SGL for variable selection and feature extraction is explicitly given and illustrated on artificial data as well as real-world examples. The main advantages of our method include variable selection for both linear and nonlinear predictions, effective dimension reduction with sparse loadings, and an efficient algorithm for large p, small n problems.

Iris recognition technology, used to identify individuals by photographing the iris of their eye, has become popular in security applications because of its ease of use, accuracy, and safety in controlling access to high-security areas. Fusion of multiple algorithms for biometric verification performance improvement has received considerable attention. The proposed method combines the zero-crossing 1 D wavelet Euler number, and genetic algorithm based for feature extraction. The output from these three algorithms is normalized and their score are fused to decide whether the user is genuine or imposter. This new strategies is discussed in this paper, in order to compute a multimodal combined score.

This article reports on the 2008 Reinforcement Learning Competition,  which began in November 2007 and ended with a workshop at the  International Conference on Machine Learning (ICML) in July 2008 in  Helsinki, Finland.  Researchers from around the world developed  reinforcement learning agents to compete in six problems of various  complexity and difficulty.  The competition employed fundamentally  redesigned evaluation frameworks that, unlike those in previous  competitions, aimed to systematically encourage the submission of  robust learning methods. We describe the unique challenges of  empirical evaluation in reinforcement learning and briefly review  the history of the previous competitions and the evaluation  frameworks they employed.  We also describe the novel frameworks  developed for the 2008 competition as well as the software  infrastructure on which they rely.  Furthermore, we describe the six  competition domains and present a summary of selected competition  results.  Finally, we discuss the implications of these results and  outline ideas for the future of the competition.

The considerable interest in ARA techniques and the great diversity of the researchers involved had led to work on ARA being presented at many different venues. Consequently, there was a need to have a single forum where researchers of different backgrounds and disciplines could discuss their work on ARA. As a result, the Symposium on Abstraction, Reformulation, and Approximation (SARA) was established in 1994 after a series of workshops in 1988, 1990, and 1992. The current SARA, held at Lake Arrowhead, California, USA, on July 7-10, 2009, is the eighth in this series, following symposia in 1994, 1995, 1998, 2000, 2002, 2005, and 2007. Following a SARA tradition, this symposium brought together researchers with different backgrounds and facilitated lively discussions during and after the talks. There were 30 researchers from North and South America, Europe, and Australia. Additionally, SARA attendees were able to mingle and have fruitful discussions with members of the collocated Symposium on Combinatorial Search (SoCS). The collocation of SoCS was particularly useful in that many modern techniques in combinatorial search frequently utilize ARA methods. Finally, in addition to the regular and poster talks, there were three invited talks delivered by Jeff Orkin (Massachusetts Institute of Technology), Michael Genesereth (Stanford University), and Robert Holte (University of Alberta).

On Tuesday morning, July 12, the program chairs will welcome attendees, and conference and AAAI awards will be presented. The awards ceremony will be followed by the AAAI-10 keynote address, to be include 199 oral presentations in the is the definitive point of interaction delivered by Leslie Pack Kaelbling main track, as well as 75 additional between entertainment software developers (Massachusetts Institute of Technology) presentations in the special tracks on interested in AI and academic entitled "Intelligent Interaction Bioinformatics, AI and the Web, Challenges and industrial AI researchers. AAAI-10 has an in AI, Integrated Intelligence, by AAAI, the conference is targeted outstanding program of invited presentations, Physically Grounded AI, Nectar, and at both the research and featuring Carla P. Gomes Senior Member, as well as poster presentations commercial communities, promoting (Cornell University), Barry O'Sullivan by a select number of exceptional AI research and practice in the context (University College Cork), David C. technical papers, short papers, of interactive digital entertainment Parkes (Harvard University), and student abstracts, and doctoral systems with an emphasis on commercial Michael Thielscher (The University of consortium abstracts. Registration information with Jay M. Tenenbaum (CollabRx The week is filled with a host of and other program details will Inc.), the 2010 recipient of the other programs, including the AI be available on the AIIDE-10 website Robert S. Engelmore Memorial Lecture Video Competition, the AI Poker at www.aaai.org/aiide10 The IAAI-10 program Semantic Robot Vision Challenge, the Michael Youngblood (University of will also feature talks by Majd Alwan General Game Playing Competition, North Carolina Charlotte). Care Empowered by Applied AI," Registration for AAAI-10, IAAI-10, and Vernor Vinge (San Diego State and EAAI-10 is included in one joint University) on "Species of Mind." fee.

On October 8-10, 2009 an interdisciplinary group met at the Wylie Center in Beverley, Massachusetts to evaluate the state of the art in the computational modeling of narrative. Three important findings emerged: (1) current work in computational modeling is described by three different levels of representation; (2) there is a paucity of studies at the highest, most abstract level aimed at inferring the meaning or message of the narrative; and (3) there is a need to establish a standard data bank of annotated narratives, analogous to the Penn Treebank.