Generalized power method for sparse principal component analysis

In this paper we develop a new approach to sparse principal component analysis (sparse PCA). We propose two single-unit and two block optimization formulations of the sparse PCA problem, aimed at extracting a single sparse dominant principal component of a data matrix, or more components at once, respectively. While the initial formulations involve nonconvex functions, and are therefore computationally intractable, we rewrite them into the form of an optimization program involving maximization of a convex function on a compact set. The dimension of the search space is decreased enormously if the data matrix has many more columns (variables) than rows. We then propose and analyze a simple gradient method suited for the task. It appears that our algorithm has best convergence properties in the case when either the objective function or the feasible set are strongly convex, which is the case with our single-unit formulations and can be enforced in the block case. Finally, we demonstrate numerically on a set of random and gene expression test problems that our approach outperforms existing algorithms both in quality of the obtained solution and in computational speed. © 2010 Michel Journée, Yurii Nesterov, Peter Richtárik and Rodolphe Sepulchre.

Natural actor and belief critic: Reinforcement algorithm for learning parameters of dialogue systems modelled as POMDPs

This article presents a novel algorithm for learning parameters in statistical dialogue systems which are modeled as Partially Observable Markov Decision Processes (POMDPs). The three main components of a POMDP dialogue manager are a dialogue model representing dialogue state information; a policy that selects the system's responses based on the inferred state; and a reward function that specifies the desired behavior of the system. Ideally both the model parameters and the policy would be designed to maximize the cumulative reward. However, while there are many techniques available for learning the optimal policy, no good ways of learning the optimal model parameters that scale to real-world dialogue systems have been found yet. The presented algorithm, called the Natural Actor and Belief Critic (NABC), is a policy gradient method that offers a solution to this problem. Based on observed rewards, the algorithm estimates the natural gradient of the expected cumulative reward. The resulting gradient is then used to adapt both the prior distribution of the dialogue model parameters and the policy parameters. In addition, the article presents a variant of the NABC algorithm, called the Natural Belief Critic (NBC), which assumes that the policy is fixed and only the model parameters need to be estimated. The algorithms are evaluated on a spoken dialogue system in the tourist information domain. The experiments show that model parameters estimated to maximize the expected cumulative reward result in significantly improved performance compared to the baseline hand-crafted model parameters. The algorithms are also compared to optimization techniques using plain gradients and state-of-the-art random search algorithms. In all cases, the algorithms based on the natural gradient work significantly better. © 2011 ACM.

A simple combinatorial method aiding research on single-walled carbon nanotube growth on substrates

Establishing fabrication methods of carbon nanotubes (CNTs) is essential to realize many applications expected for CNTs. Catalytic growth of CNTs on substrates by chemical vapor deposition (CVD) is promising for direct fabrication of CNT devices, and catalyst nanoparticles play a crucial role in such growth. We have developed a simple method called "combinatorial masked deposition (CMD)", in which catalyst particles of a given series of sizes and compositions are formed on a single substrate by annealing gradient catalyst layers formed by sputtering through a mask. CMD enables preparation of hundreds of catalysts on a wafer, growth of single-walled CNTs (SWCNTs), and evaluation of SWCNT diameter distributions by automated Raman mapping in a single day. CMD helps determinations of the CVD and catalyst windows realizing millimeter-tall SWCNT forest growth in 10 min, and of growth curves for a series of catalysts in a single measurement when combined with realtime monitoring. A catalyst library prepared using CMD yields various CNTs, ranging from individuals, networks, spikes, and to forests of both SWCNTs and multi-walled CNTs, and thus can be used to efficiently evaluate self-organized CNT field emitters, for example. The CMD method is simple yet effective for research of CNT growth methods. © 2010 The Japan Society of Applied Physics.