The problem of consciousness faced several challenges for a few reasons: (a) a lack of necessary and sufficient conditions, without which we would not know how close we are to the solution, (b) a lack of a synthesis framework to build conscious systems and (c) a lack of mechanisms explaining the transition between the lower-level chemical dynamics and the higher-level abstractions. In this paper, I address these issues using a new framework. The central result is that a person is 'minimally' conscious if and only if he knows at least one truth. This lets us move away from the vagueness surrounding consciousness and instead focus equivalently on: (i) what truths are and how our brain represents/relates them to each other and (ii) how we attain a feeling of knowing for a truth. For the former problem, since truths are things that do not change, I replace the abstract notion with a dynamical one called fixed sets. These sets are guaranteed to exist for our brain and other stable parallel looped systems. The relationships between everyday events are now built using relationships between fixed sets, until our brain creates a unique dynamical state called the self-sustaining threshold 'membrane' of fixed sets. For the latter problem, I present necessary and sufficient conditions for attaining a feeling of knowing using a definition of continuity applied to abstractions. Combining these results, I now say that a person is minimally conscious if and only if his brain has a self-sustaining dynamical membrane with abstract continuous paths. A synthetic system built to satisfy this equivalent self-sustaining membrane condition appears indistinguishable from human consciousness.

In nonparametric classification and regression problems, regularized kernel methods, in particular support vector machines, attract much attention in theoretical and in applied statistics. In an abstract sense, regularized kernel methods (simply called SVMs here) can be seen as regularized M-estimators for a parameter in a (typically infinite dimensional) reproducing kernel Hilbert space. For smooth loss functions, it is shown that the difference between the estimator, i.e.\ the empirical SVM, and the theoretical SVM is asymptotically normal with rate $\sqrt{n}$. That is, the standardized difference converges weakly to a Gaussian process in the reproducing kernel Hilbert space. As common in real applications, the choice of the regularization parameter may depend on the data. The proof is done by an application of the functional delta-method and by showing that the SVM-functional is suitably Hadamard-differentiable.

Several problems encountered in application areas such as finance, biology, speech analysis, control engineering, robotics, etc. require the modeling of time-series containing switching among different dynamics regimes (see Ephraim (2002) for a review). For example, system fault diagnosis deals with detecting behavioural deviations from normality originated by failures in the system. Such a modeling is often achieved by employing probabilistic approaches in which regime switching is described by a set of discrete hidden random variables, related by a first-order Markovian dependence. All such models, that we call hidden Markov switching models (HMSMs), can be viewed as extensions of the popular hidden Markov model Rabiner (1989). The wide interdisciplinary attention to this research area has produced many different HMSMs as well as different approaches and implementations of HMSMs of fundamentally similar structure, resulting in a dense literature from which extracting differences and commonalities among models is often challenging. In this paper we provide a simple unified treatment of existing HMSMs, highlighting properties and connections that were not observed in previous review papers Ephraim (2002); Gales and Young (1993); Murphy (2002); Ostendorf et al. (1996); Rabiner (1989); Yu (2010), and introduce novel extensions. Our exposition enables a deep understanding of the fundamental structure and relations of different approaches. This is achieved by using the framework of graphical models, which allows to easily define complex models by using a graphical representation and to derive efficient inference routines by visual inspection of the graph, avoiding complex algebraic manipulations.

Generalized Linear Models (GLMs) and Single Index Models (SIMs) provide powerful generalizations of linear regression, where the target variable is assumed to be a (possibly unknown) 1-dimensional function of a linear predictor. In general, these problems entail non-convex estimation procedures, and, in practice, iterative local search heuristics are often used. Kalai and Sastry (2009) recently provided the first provably efficient method for learning SIMs and GLMs, under the assumptions that the data are in fact generated under a GLM and under certain monotonicity and Lipschitz constraints. However, to obtain provable performance, the method requires a fresh sample every iteration. In this paper, we provide algorithms for learning GLMs and SIMs, which are both computationally and statistically efficient. We also provide an empirical study, demonstrating their feasibility in practice.

Heuristics are crucial tools in decreasing search effort in varied fields of AI. In order to be effective, a heuristic must be efficient to compute, as well as provide useful information to the search algorithm. However, some well-known heuristics which do well in reducing backtracking are so heavy that the gain of deploying them in a search algorithm might be outweighed by their overhead. We propose a rational metareasoning approach to decide when to deploy heuristics, using CSP backtracking search as a case study. In particular, a value of information approach is taken to adaptive deployment of solution-count estimation heuristics for value ordering. Empirical results show that indeed the proposed mechanism successfully balances the tradeoff between decreasing backtracking and heuristic computational overhead, resulting in a significant overall search time reduction.

The goal of decentralized optimization over a network is to optimize a global objective formed by a sum of local (possibly nonsmooth) convex functions using only local computation and communication. It arises in various application domains, including distributed tracking and localization, multi-agent co-ordination, estimation in sensor networks, and large-scale optimization in machine learning. We develop and analyze distributed algorithms based on dual averaging of subgradients, and we provide sharp bounds on their convergence rates as a function of the network size and topology. Our method of analysis allows for a clear separation between the convergence of the optimization algorithm itself and the effects of communication constraints arising from the network structure. In particular, we show that the number of iterations required by our algorithm scales inversely in the spectral gap of the network. The sharpness of this prediction is confirmed both by theoretical lower bounds and simulations for various networks. Our approach includes both the cases of deterministic optimization and communication, as well as problems with stochastic optimization and/or communication.

A wide class of regularization problems in machine learning and statistics employ a regularization term which is obtained by composing a simple convex function \omega with a linear transformation. This setting includes Group Lasso methods, the Fused Lasso and other total variation methods, multi-task learning methods and many more. In this paper, we present a general approach for computing the proximity operator of this class of regularizers, under the assumption that the proximity operator of the function \omega is known in advance. Our approach builds on a recent line of research on optimal first order optimization methods and uses fixed point iterations for numerically computing the proximity operator. It is more general than current approaches and, as we show with numerical simulations, computationally more efficient than available first order methods which do not achieve the optimal rate. In particular, our method outperforms state of the art O(1/T) methods for overlapping Group Lasso and matches optimal O(1/T^2) methods for the Fused Lasso and tree structured Group Lasso.

Structural equation models and Bayesian networks have been widely used to analyze causal relations between continuous variables. In such frameworks, linear acyclic models are typically used to model the data-generating process of variables. Recently, it was shown that use of non-Gaussianity identifies the full structure of a linear acyclic model, i.e., a causal ordering of variables and their connection strengths, without using any prior knowledge on the network structure, which is not the case with conventional methods. However, existing estimation methods are based on iterative search algorithms and may not converge to a correct solution in a finite number of steps. In this paper, we propose a new direct method to estimate a causal ordering and connection strengths based on non-Gaussianity. In contrast to the previous methods, our algorithm requires no algorithmic parameters and is guaranteed to converge to the right solution within a small fixed number of steps if the data strictly follows the model.

Many statistical methods have been proposed to estimate causal models in classical situations with fewer variables than observations (p>n). In this paper, we propose a method to find exogenous variables in a linear non-Gaussian causal model, which requires much smaller sample sizes than conventional methods and works even when p>>n. The key idea is to identify which variables are exogenous based on non-Gaussianity instead of estimating the entire structure of the model. Exogenous variables work as triggers that activate a causal chain in the model, and their identification leads to more efficient experimental designs and better understanding of the causal mechanism. We present experiments with artificial data and real-world gene expression data to evaluate the method.

We describe a new variational lower-bound on the minimum energy configuration of a planar binary Markov Random Field (MRF). Our method is based on adding auxiliary nodes to every face of a planar embedding of the graph in order to capture the effect of unary potentials. A ground state of the resulting approximation can be computed efficiently by reduction to minimum-weight perfect matching. We show that optimization of variational parameters achieves the same lower-bound as dual-decomposition into the set of all cycles of the original graph. We demonstrate that our variational optimization converges quickly and provides high-quality solutions to hard combinatorial problems 10-100x faster than competing algorithms that optimize the same bound.