May 5, 2019

3076 words 15 mins read

Paper Group ANR 472

Convexified Convolutional Neural Networks. Heuristics for Planning, Plan Recognition and Parsing. A Quantum Implementation Model for Artificial Neural Networks. A Dynamic Bayesian Network Model for Inventory Level Estimation in Retail Marketing. Optimising Rule-Based Classification in Temporal Data. Bandits meet Computer Architecture: Designing a S …

Convexified Convolutional Neural Networks


Title	Convexified Convolutional Neural Networks
Authors	Yuchen Zhang, Percy Liang, Martin J. Wainwright
Abstract	We describe the class of convexified convolutional neural networks (CCNNs), which capture the parameter sharing of convolutional neural networks in a convex manner. By representing the nonlinear convolutional filters as vectors in a reproducing kernel Hilbert space, the CNN parameters can be represented as a low-rank matrix, which can be relaxed to obtain a convex optimization problem. For learning two-layer convolutional neural networks, we prove that the generalization error obtained by a convexified CNN converges to that of the best possible CNN. For learning deeper networks, we train CCNNs in a layer-wise manner. Empirically, CCNNs achieve performance competitive with CNNs trained by backpropagation, SVMs, fully-connected neural networks, stacked denoising auto-encoders, and other baseline methods.
Tasks	Denoising
Published	2016-09-04
URL	http://arxiv.org/abs/1609.01000v1
PDF	http://arxiv.org/pdf/1609.01000v1.pdf
PWC	https://paperswithcode.com/paper/convexified-convolutional-neural-networks
Repo
Framework

Heuristics for Planning, Plan Recognition and Parsing


Title	Heuristics for Planning, Plan Recognition and Parsing
Authors	Miquel Ramirez, Hector Geffner
Abstract	In a recent paper, we have shown that Plan Recognition over STRIPS can be formulated and solved using Classical Planning heuristics and algorithms. In this work, we show that this formulation subsumes the standard formulation of Plan Recognition over libraries through a compilation of libraries into STRIPS theories. The libraries correspond to AND/OR graphs that may be cyclic and where children of AND nodes may be partially ordered. These libraries include Context-Free Grammars as a special case, where the Plan Recognition problem becomes a parsing with missing tokens problem. Plan Recognition over the standard libraries become Planning problems that can be easily solved by any modern planner, while recognition over more complex libraries, including Context-Free Grammars (CFGs), illustrate limitations of current Planning heuristics and suggest improvements that may be relevant in other Planning problems too.
Tasks
Published	2016-05-19
URL	http://arxiv.org/abs/1605.05807v2
PDF	http://arxiv.org/pdf/1605.05807v2.pdf
PWC	https://paperswithcode.com/paper/heuristics-for-planning-plan-recognition-and
Repo
Framework

A Quantum Implementation Model for Artificial Neural Networks


Title	A Quantum Implementation Model for Artificial Neural Networks
Authors	Ammar Daskin
Abstract	The learning process for multi layered neural networks with many nodes makes heavy demands on computational resources. In some neural network models, the learning formulas, such as the Widrow-Hoff formula, do not change the eigenvectors of the weight matrix while flatting the eigenvalues. In infinity, this iterative formulas result in terms formed by the principal components of the weight matrix: i.e., the eigenvectors corresponding to the non-zero eigenvalues. In quantum computing, the phase estimation algorithm is known to provide speed-ups over the conventional algorithms for the eigenvalue-related problems. Combining the quantum amplitude amplification with the phase estimation algorithm, a quantum implementation model for artificial neural networks using the Widrow-Hoff learning rule is presented. The complexity of the model is found to be linear in the size of the weight matrix. This provides a quadratic improvement over the classical algorithms.
Tasks
Published	2016-09-19
URL	http://arxiv.org/abs/1609.05884v2
PDF	http://arxiv.org/pdf/1609.05884v2.pdf
PWC	https://paperswithcode.com/paper/a-quantum-implementation-model-for-artificial
Repo
Framework

A Dynamic Bayesian Network Model for Inventory Level Estimation in Retail Marketing


Title	A Dynamic Bayesian Network Model for Inventory Level Estimation in Retail Marketing
Authors	Luis I. Reyes-Castro, Andres G. Abad
Abstract	Many retailers today employ inventory management systems based on Re-Order Point Policies, most of which rely on the assumption that all decreases in product inventory levels result from product sales. Unfortunately, it usually happens that small but random quantities of the product get lost, stolen or broken without record as time passes, e.g., as a consequence of shoplifting. This is usual for retailers handling large varieties of inexpensive products, e.g., grocery stores. In turn, over time these discrepancies lead to stock freezing problems, i.e., situations where the system believes the stock is above the re-order point but the actual stock is at zero, and so no replenishments or sales occur. Motivated by these issues, we model the interaction between sales, losses, replenishments and inventory levels as a Dynamic Bayesian Network (DBN), where the inventory levels are unobserved (i.e., hidden) variables we wish to estimate. We present an Expectation-Maximization (EM) algorithm to estimate the parameters of the sale and loss distributions, which relies on solving a one-dimensional dynamic program for the E-step and on solving two separate one-dimensional nonlinear programs for the M-step.
Tasks
Published	2016-04-04
URL	http://arxiv.org/abs/1604.01075v1
PDF	http://arxiv.org/pdf/1604.01075v1.pdf
PWC	https://paperswithcode.com/paper/a-dynamic-bayesian-network-model-for
Repo
Framework

Optimising Rule-Based Classification in Temporal Data


Title	Optimising Rule-Based Classification in Temporal Data
Authors	Polla Fattah, Uwe Aickelin, Christian Wagner
Abstract	This study optimises manually derived rule-based expert system classification of objects according to changes in their properties over time. One of the key challenges that this study tries to address is how to classify objects that exhibit changes in their behaviour over time, for example how to classify companies’ share price stability over a period of time or how to classify students’ preferences for subjects while they are progressing through school. A specific case the paper considers is the strategy of players in public goods games (as common in economics) across multiple consecutive games. Initial classification starts from expert definitions specifying class allocation for players based on aggregated attributes of the temporal data. Based on these initial classifications, the optimisation process tries to find an improved classifier which produces the best possible compact classes of objects (players) for every time point in the temporal data. The compactness of the classes is measured by a cost function based on internal cluster indices like the Dunn Index, distance measures like Euclidean distance or statistically derived measures like standard deviation. The paper discusses the approach in the context of incorporating changing player strategies in the aforementioned public good games, where common classification approaches so far do not consider such changes in behaviour resulting from learning or in-game experience. By using the proposed process for classifying temporal data and the actual players’ contribution during the games, we aim to produce a more refined classification which in turn may inform the interpretation of public goods game data.
Tasks
Published	2016-07-20
URL	http://arxiv.org/abs/1607.05913v1
PDF	http://arxiv.org/pdf/1607.05913v1.pdf
PWC	https://paperswithcode.com/paper/optimising-rule-based-classification-in
Repo
Framework

Bandits meet Computer Architecture: Designing a Smartly-allocated Cache


Title	Bandits meet Computer Architecture: Designing a Smartly-allocated Cache
Authors	Yonatan Glassner, Koby Crammer
Abstract	In many embedded systems, such as imaging sys- tems, the system has a single designated purpose, and same threads are executed repeatedly. Profiling thread behavior, allows the system to allocate each thread its resources in a way that improves overall system performance. We study an online resource al- locationproblem,wherearesourcemanagersimulta- neously allocates resources (exploration), learns the impact on the different consumers (learning) and im- proves allocation towards optimal performance (ex- ploitation). We build on the rich framework of multi- armed bandits and present online and offline algo- rithms. Through extensive experiments with both synthetic data and real-world cache allocation to threads we show the merits and properties of our al- gorithms
Tasks	Multi-Armed Bandits
Published	2016-01-31
URL	http://arxiv.org/abs/1602.00309v1
PDF	http://arxiv.org/pdf/1602.00309v1.pdf
PWC	https://paperswithcode.com/paper/bandits-meet-computer-architecture-designing
Repo
Framework

Representation of texts as complex networks: a mesoscopic approach


Title	Representation of texts as complex networks: a mesoscopic approach
Authors	Henrique F. de Arruda, Filipi N. Silva, Vanessa Q. Marinho, Diego R. Amancio, Luciano da F. Costa
Abstract	Statistical techniques that analyze texts, referred to as text analytics, have departed from the use of simple word count statistics towards a new paradigm. Text mining now hinges on a more sophisticated set of methods, including the representations in terms of complex networks. While well-established word-adjacency (co-occurrence) methods successfully grasp syntactical features of written texts, they are unable to represent important aspects of textual data, such as its topical structure, i.e. the sequence of subjects developing at a mesoscopic level along the text. Such aspects are often overlooked by current methodologies. In order to grasp the mesoscopic characteristics of semantical content in written texts, we devised a network model which is able to analyze documents in a multi-scale fashion. In the proposed model, a limited amount of adjacent paragraphs are represented as nodes, which are connected whenever they share a minimum semantical content. To illustrate the capabilities of our model, we present, as a case example, a qualitative analysis of “Alice’s Adventures in Wonderland”. We show that the mesoscopic structure of a document, modeled as a network, reveals many semantic traits of texts. Such an approach paves the way to a myriad of semantic-based applications. In addition, our approach is illustrated in a machine learning context, in which texts are classified among real texts and randomized instances.
Tasks
Published	2016-06-30
URL	http://arxiv.org/abs/1606.09636v2
PDF	http://arxiv.org/pdf/1606.09636v2.pdf
PWC	https://paperswithcode.com/paper/representation-of-texts-as-complex-networks-a
Repo
Framework

Quantum machine learning with glow for episodic tasks and decision games


Title	Quantum machine learning with glow for episodic tasks and decision games
Authors	Jens Clausen, Hans J. Briegel
Abstract	We consider a general class of models, where a reinforcement learning (RL) agent learns from cyclic interactions with an external environment via classical signals. Perceptual inputs are encoded as quantum states, which are subsequently transformed by a quantum channel representing the agent’s memory, while the outcomes of measurements performed at the channel’s output determine the agent’s actions. The learning takes place via stepwise modifications of the channel properties. They are described by an update rule that is inspired by the projective simulation (PS) model and equipped with a glow mechanism that allows for a backpropagation of policy changes, analogous to the eligibility traces in RL and edge glow in PS. In this way, the model combines features of PS with the ability for generalization, offered by its physical embodiment as a quantum system. We apply the agent to various setups of an invasion game and a grid world, which serve as elementary model tasks allowing a direct comparison with a basic classical PS agent.
Tasks	Quantum Machine Learning
Published	2016-01-27
URL	http://arxiv.org/abs/1601.07358v1
PDF	http://arxiv.org/pdf/1601.07358v1.pdf
PWC	https://paperswithcode.com/paper/quantum-machine-learning-with-glow-for
Repo
Framework

Domain Adaptation for Neural Networks by Parameter Augmentation


Title	Domain Adaptation for Neural Networks by Parameter Augmentation
Authors	Yusuke Watanabe, Kazuma Hashimoto, Yoshimasa Tsuruoka
Abstract	We propose a simple domain adaptation method for neural networks in a supervised setting. Supervised domain adaptation is a way of improving the generalization performance on the target domain by using the source domain dataset, assuming that both of the datasets are labeled. Recently, recurrent neural networks have been shown to be successful on a variety of NLP tasks such as caption generation; however, the existing domain adaptation techniques are limited to (1) tune the model parameters by the target dataset after the training by the source dataset, or (2) design the network to have dual output, one for the source domain and the other for the target domain. Reformulating the idea of the domain adaptation technique proposed by Daume (2007), we propose a simple domain adaptation method, which can be applied to neural networks trained with a cross-entropy loss. On captioning datasets, we show performance improvements over other domain adaptation methods.
Tasks	Domain Adaptation
Published	2016-07-01
URL	http://arxiv.org/abs/1607.00410v1
PDF	http://arxiv.org/pdf/1607.00410v1.pdf
PWC	https://paperswithcode.com/paper/domain-adaptation-for-neural-networks-by
Repo
Framework

Multiple-Play Bandits in the Position-Based Model


Title	Multiple-Play Bandits in the Position-Based Model
Authors	Paul Lagrée, Claire Vernade, Olivier Cappé
Abstract	Sequentially learning to place items in multi-position displays or lists is a task that can be cast into the multiple-play semi-bandit setting. However, a major concern in this context is when the system cannot decide whether the user feedback for each item is actually exploitable. Indeed, much of the content may have been simply ignored by the user. The present work proposes to exploit available information regarding the display position bias under the so-called Position-based click model (PBM). We first discuss how this model differs from the Cascade model and its variants considered in several recent works on multiple-play bandits. We then provide a novel regret lower bound for this model as well as computationally efficient algorithms that display good empirical and theoretical performance.
Tasks
Published	2016-06-08
URL	http://arxiv.org/abs/1606.02448v1
PDF	http://arxiv.org/pdf/1606.02448v1.pdf
PWC	https://paperswithcode.com/paper/multiple-play-bandits-in-the-position-based
Repo
Framework

Landmark-Based Plan Recognition


Title	Landmark-Based Plan Recognition
Authors	Ramon Fraga Pereira, Felipe Meneguzzi
Abstract	Recognition of goals and plans using incomplete evidence from action execution can be done efficiently by using planning techniques. In many applications it is important to recognize goals and plans not only accurately, but also quickly. In this paper, we develop a heuristic approach for recognizing plans based on planning techniques that rely on ordering constraints to filter candidate goals from observations. These ordering constraints are called landmarks in the planning literature, which are facts or actions that cannot be avoided to achieve a goal. We show the applicability of planning landmarks in two settings: first, we use it directly to develop a heuristic-based plan recognition approach; second, we refine an existing planning-based plan recognition approach by pre-filtering its candidate goals. Our empirical evaluation shows that our approach is not only substantially more accurate than the state-of-the-art in all available datasets, it is also an order of magnitude faster.
Tasks
Published	2016-04-05
URL	http://arxiv.org/abs/1604.01277v3
PDF	http://arxiv.org/pdf/1604.01277v3.pdf
PWC	https://paperswithcode.com/paper/landmark-based-plan-recognition
Repo
Framework

A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates


Title	A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates
Authors	Tianbao Yang, Qihang Lin, Lijun Zhang
Abstract	This paper focuses on convex constrained optimization problems, where the solution is subject to a convex inequality constraint. In particular, we aim at challenging problems for which both projection into the constrained domain and a linear optimization under the inequality constraint are time-consuming, which render both projected gradient methods and conditional gradient methods (a.k.a. the Frank-Wolfe algorithm) expensive. In this paper, we develop projection reduced optimization algorithms for both smooth and non-smooth optimization with improved convergence rates under a certain regularity condition of the constraint function. We first present a general theory of optimization with only one projection. Its application to smooth optimization with only one projection yields $O(1/\epsilon)$ iteration complexity, which improves over the $O(1/\epsilon^2)$ iteration complexity established before for non-smooth optimization and can be further reduced under strong convexity. Then we introduce a local error bound condition and develop faster algorithms for non-strongly convex optimization at the price of a logarithmic number of projections. In particular, we achieve an iteration complexity of $\widetilde O(1/\epsilon^{2(1-\theta)})$ for non-smooth optimization and $\widetilde O(1/\epsilon^{1-\theta})$ for smooth optimization, where $\theta\in(0,1]$ appearing the local error bound condition characterizes the functional local growth rate around the optimal solutions. Novel applications in solving the constrained $\ell_1$ minimization problem and a positive semi-definite constrained distance metric learning problem demonstrate that the proposed algorithms achieve significant speed-up compared with previous algorithms.
Tasks	Metric Learning
Published	2016-08-11
URL	http://arxiv.org/abs/1608.03487v2
PDF	http://arxiv.org/pdf/1608.03487v2.pdf
PWC	https://paperswithcode.com/paper/a-richer-theory-of-convex-constrained
Repo
Framework

Dynamic Frame skip Deep Q Network


Title	Dynamic Frame skip Deep Q Network
Authors	Aravind S. Lakshminarayanan, Sahil Sharma, Balaraman Ravindran
Abstract	Deep Reinforcement Learning methods have achieved state of the art performance in learning control policies for the games in the Atari 2600 domain. One of the important parameters in the Arcade Learning Environment (ALE) is the frame skip rate. It decides the granularity at which agents can control game play. A frame skip value of $k$ allows the agent to repeat a selected action $k$ number of times. The current state of the art architectures like Deep Q-Network (DQN) and Dueling Network Architectures (DuDQN) consist of a framework with a static frame skip rate, where the action output from the network is repeated for a fixed number of frames regardless of the current state. In this paper, we propose a new architecture, Dynamic Frame skip Deep Q-Network (DFDQN) which makes the frame skip rate a dynamic learnable parameter. This allows us to choose the number of times an action is to be repeated based on the current state. We show empirically that such a setting improves the performance on relatively harder games like Seaquest.
Tasks	Atari Games
Published	2016-05-17
URL	http://arxiv.org/abs/1605.05365v2
PDF	http://arxiv.org/pdf/1605.05365v2.pdf
PWC	https://paperswithcode.com/paper/dynamic-frame-skip-deep-q-network
Repo
Framework

Descriptor transition tables for object retrieval using unconstrained cluttered video acquired using a consumer level handheld mobile device


Title	Descriptor transition tables for object retrieval using unconstrained cluttered video acquired using a consumer level handheld mobile device
Authors	Warren Rieutort-Louis, Ognjen Arandjelovic
Abstract	Visual recognition and vision based retrieval of objects from large databases are tasks with a wide spectrum of potential applications. In this paper we propose a novel recognition method from video sequences suitable for retrieval from databases acquired in highly unconstrained conditions e.g. using a mobile consumer-level device such as a phone. On the lowest level, we represent each sequence as a 3D mesh of densely packed local appearance descriptors. While image plane geometry is captured implicitly by a large overlap of neighbouring regions from which the descriptors are extracted, 3D information is extracted by means of a descriptor transition table, learnt from a single sequence for each known gallery object. These allow us to connect local descriptors along the 3rd dimension (which corresponds to viewpoint changes), thus resulting in a set of variable length Markov chains for each video. The matching of two sets of such chains is formulated as a statistical hypothesis test, whereby a subset of each is chosen to maximize the likelihood that the corresponding video sequences show the same object. The effectiveness of the proposed algorithm is empirically evaluated on the Amsterdam Library of Object Images and a new highly challenging video data set acquired using a mobile phone. On both data sets our method is shown to be successful in recognition in the presence of background clutter and large viewpoint changes.
Tasks
Published	2016-03-16
URL	http://arxiv.org/abs/1603.05073v2
PDF	http://arxiv.org/pdf/1603.05073v2.pdf
PWC	https://paperswithcode.com/paper/descriptor-transition-tables-for-object
Repo
Framework

Understanding Innovation to Drive Sustainable Development


Title	Understanding Innovation to Drive Sustainable Development
Authors	Prasanna Sattigeri, Aurélie Lozano, Aleksandra Mojsilović, Kush R. Varshney, Mahmoud Naghshineh
Abstract	Innovation is among the key factors driving a country’s economic and social growth. But what are the factors that make a country innovative? How do they differ across different parts of the world and different stages of development? In this work done in collaboration with the World Economic Forum (WEF), we analyze the scores obtained through executive opinion surveys that constitute the WEF’s Global Competitiveness Index in conjunction with other country-level metrics and indicators to identify actionable levers of innovation. The findings can help country leaders and organizations shape the policies to drive developmental activities and increase the capacity of innovation.
Tasks
Published	2016-06-15
URL	http://arxiv.org/abs/1606.06177v1
PDF	http://arxiv.org/pdf/1606.06177v1.pdf
PWC	https://paperswithcode.com/paper/understanding-innovation-to-drive-sustainable
Repo
Framework