Paper Group ANR 604
Self-Organization and Artificial Life: A Review. A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation. Linear Independent Component Analysis over Finite Fields: Algorithms and Bounds. Color Image Enhancement Method Based on Weighted Image Guided Filtering. Stochastic Gradient Descent with Exponential Convergence …
Self-Organization and Artificial Life: A Review
| Title | Self-Organization and Artificial Life: A Review |
| Authors | Carlos Gershenson, Vito Trianni, Justin Werfel, Hiroki Sayama |
| Abstract | Self-organization has been an important concept within a number of disciplines, which Artificial Life (ALife) also has heavily utilized since its inception. The term and its implications, however, are often confusing or misinterpreted. In this work, we provide a mini-review of self-organization and its relationship with ALife, aiming at initiating discussions on this important topic with the interested audience. We first articulate some fundamental aspects of self-organization, outline its usage, and review its applications to ALife within its soft, hard, and wet domains. We also provide perspectives for further research. |
| Tasks | Artificial Life |
| Published | 2018-04-03 |
| URL | http://arxiv.org/abs/1804.01144v1 |
| http://arxiv.org/pdf/1804.01144v1.pdf | |
| PWC | https://paperswithcode.com/paper/self-organization-and-artificial-life-a |
| Repo | |
| Framework | |
A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation
| Title | A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation |
| Authors | Jalaj Bhandari, Daniel Russo, Raghav Singal |
| Abstract | Temporal difference learning (TD) is a simple iterative algorithm used to estimate the value function corresponding to a given policy in a Markov decision process. Although TD is one of the most widely used algorithms in reinforcement learning, its theoretical analysis has proved challenging and few guarantees on its statistical efficiency are available. In this work, we provide a simple and explicit finite time analysis of temporal difference learning with linear function approximation. Except for a few key insights, our analysis mirrors standard techniques for analyzing stochastic gradient descent algorithms, and therefore inherits the simplicity and elegance of that literature. Final sections of the paper show how all of our main results extend to the study of TD learning with eligibility traces, known as TD($\lambda$), and to Q-learning applied in high-dimensional optimal stopping problems. |
| Tasks | Q-Learning |
| Published | 2018-06-06 |
| URL | http://arxiv.org/abs/1806.02450v2 |
| http://arxiv.org/pdf/1806.02450v2.pdf | |
| PWC | https://paperswithcode.com/paper/a-finite-time-analysis-of-temporal-difference |
| Repo | |
| Framework | |
Linear Independent Component Analysis over Finite Fields: Algorithms and Bounds
| Title | Linear Independent Component Analysis over Finite Fields: Algorithms and Bounds |
| Authors | Amichai Painsky, Saharon Rosset, Meir Feder |
| Abstract | Independent Component Analysis (ICA) is a statistical tool that decomposes an observed random vector into components that are as statistically independent as possible. ICA over finite fields is a special case of ICA, in which both the observations and the decomposed components take values over a finite alphabet. This problem is also known as minimal redundancy representation or factorial coding. In this work we focus on linear methods for ICA over finite fields. We introduce a basic lower bound which provides a fundamental limit to the ability of any linear solution to solve this problem. Based on this bound, we present a greedy algorithm that outperforms all currently known methods. Importantly, we show that the overhead of our suggested algorithm (compared with the lower bound) typically decreases, as the scale of the problem grows. In addition, we provide a sub-optimal variant of our suggested method that significantly reduces the computational complexity at a relatively small cost in performance. Finally, we discuss the universal abilities of linear transformations in decomposing random vectors, compared with existing non-linear solutions. |
| Tasks | |
| Published | 2018-09-16 |
| URL | http://arxiv.org/abs/1809.05815v1 |
| http://arxiv.org/pdf/1809.05815v1.pdf | |
| PWC | https://paperswithcode.com/paper/linear-independent-component-analysis-over |
| Repo | |
| Framework | |
Color Image Enhancement Method Based on Weighted Image Guided Filtering
| Title | Color Image Enhancement Method Based on Weighted Image Guided Filtering |
| Authors | Qi Mu, Yanyan Wei, Zhanli Li |
| Abstract | A novel color image enhancement method is proposed based on Retinex to enhance color images under non-uniform illumination or poor visibility conditions. Different from the conventional Retinex algorithms, the Weighted Guided Image Filter is used as a surround function instead of the Gaussian filter to estimate the background illumination, which can overcome the drawbacks of local blur and halo artifact that may appear by Gaussian filter. To avoid color distortion, the image is converted to the HSI color model, and only the intensity channel is enhanced. Then a linear color restoration algorithm is adopted to convert the enhanced intensity image back to the RGB color model, which ensures the hue is constant and undistorted. Experimental results show that the proposed method is effective to enhance both color and gray images with low exposure and non-uniform illumination, resulting in better visual quality than traditional method. At the same time, the objective evaluation indicators are also superior to the conventional methods. In addition, the efficiency of the proposed method is also improved thanks to the linear color restoration algorithm. |
| Tasks | Image Enhancement |
| Published | 2018-12-24 |
| URL | http://arxiv.org/abs/1812.09930v1 |
| http://arxiv.org/pdf/1812.09930v1.pdf | |
| PWC | https://paperswithcode.com/paper/color-image-enhancement-method-based-on |
| Repo | |
| Framework | |
Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors
| Title | Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors |
| Authors | Atsushi Nitanda, Taiji Suzuki |
| Abstract | We consider stochastic gradient descent and its averaging variant for binary classification problems in a reproducing kernel Hilbert space. In the traditional analysis using a consistency property of loss functions, it is known that the expected classification error converges more slowly than the expected risk even when assuming a low-noise condition on the conditional label probabilities. Consequently, the resulting rate is sublinear. Therefore, it is important to consider whether much faster convergence of the expected classification error can be achieved. In recent research, an exponential convergence rate for stochastic gradient descent was shown under a strong low-noise condition but provided theoretical analysis was limited to the squared loss function, which is somewhat inadequate for binary classification tasks. In this paper, we show an exponential convergence of the expected classification error in the final phase of the stochastic gradient descent for a wide class of differentiable convex loss functions under similar assumptions. As for the averaged stochastic gradient descent, we show that the same convergence rate holds from the early phase of training. In experiments, we verify our analyses on the $L_2$-regularized logistic regression. |
| Tasks | |
| Published | 2018-06-14 |
| URL | http://arxiv.org/abs/1806.05438v2 |
| http://arxiv.org/pdf/1806.05438v2.pdf | |
| PWC | https://paperswithcode.com/paper/stochastic-gradient-descent-with-exponential |
| Repo | |
| Framework | |
Counting and Sampling from Markov Equivalent DAGs Using Clique Trees
| Title | Counting and Sampling from Markov Equivalent DAGs Using Clique Trees |
| Authors | AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, Kun Zhang |
| Abstract | A directed acyclic graph (DAG) is the most common graphical model for representing causal relationships among a set of variables. When restricted to using only observational data, the structure of the ground truth DAG is identifiable only up to Markov equivalence, based on conditional independence relations among the variables. Therefore, the number of DAGs equivalent to the ground truth DAG is an indicator of the causal complexity of the underlying structure–roughly speaking, it shows how many interventions or how much additional information is further needed to recover the underlying DAG. In this paper, we propose a new technique for counting the number of DAGs in a Markov equivalence class. Our approach is based on the clique tree representation of chordal graphs. We show that in the case of bounded degree graphs, the proposed algorithm is polynomial time. We further demonstrate that this technique can be utilized for uniform sampling from a Markov equivalence class, which provides a stochastic way to enumerate DAGs in the equivalence class and may be needed for finding the best DAG or for causal inference given the equivalence class as input. We also extend our counting and sampling method to the case where prior knowledge about the underlying DAG is available, and present applications of this extension in causal experiment design and estimating the causal effect of joint interventions. |
| Tasks | Causal Inference |
| Published | 2018-02-05 |
| URL | http://arxiv.org/abs/1802.01239v2 |
| http://arxiv.org/pdf/1802.01239v2.pdf | |
| PWC | https://paperswithcode.com/paper/counting-and-sampling-from-markov-equivalent |
| Repo | |
| Framework | |
Fast Exploration with Simplified Models and Approximately Optimistic Planning in Model Based Reinforcement Learning
| Title | Fast Exploration with Simplified Models and Approximately Optimistic Planning in Model Based Reinforcement Learning |
| Authors | Ramtin Keramati, Jay Whang, Patrick Cho, Emma Brunskill |
| Abstract | Humans learn to play video games significantly faster than the state-of-the-art reinforcement learning (RL) algorithms. People seem to build simple models that are easy to learn to support planning and strategic exploration. Inspired by this, we investigate two issues in leveraging model-based RL for sample efficiency. First we investigate how to perform strategic exploration when exact planning is not feasible and empirically show that optimistic Monte Carlo Tree Search outperforms posterior sampling methods. Second we show how to learn simple deterministic models to support fast learning using object representation. We illustrate the benefit of these ideas by introducing a novel algorithm, Strategic Object Oriented Reinforcement Learning (SOORL), that outperforms state-of-the-art algorithms in the game of Pitfall! in less than 50 episodes. |
| Tasks | |
| Published | 2018-06-01 |
| URL | http://arxiv.org/abs/1806.00175v2 |
| http://arxiv.org/pdf/1806.00175v2.pdf | |
| PWC | https://paperswithcode.com/paper/fast-exploration-with-simplified-models-and |
| Repo | |
| Framework | |
Calculated attributes of synonym sets
| Title | Calculated attributes of synonym sets |
| Authors | Andrew Krizhanovsky, Alexander Kirillov |
| Abstract | The goal of formalization, proposed in this paper, is to bring together, as near as possible, the theoretic linguistic problem of synonym conception and the computer linguistic methods based generally on empirical intuitive unjustified factors. Using the word vector representation we have proposed the geometric approach to mathematical modeling of synonym set (synset). The word embedding is based on the neural networks (Skip-gram, CBOW), developed and realized as word2vec program by T. Mikolov. The standard cosine similarity is used as the distance between word-vectors. Several geometric characteristics of the synset words are introduced: the interior of synset, the synset word rank and centrality. These notions are intended to select the most significant synset words, i.e. the words which senses are the nearest to the sense of a synset. Some experiments with proposed notions, based on RusVectores resources, are represented. A brief description of this work can be viewed in slides https://goo.gl/K82Fei |
| Tasks | |
| Published | 2018-03-05 |
| URL | http://arxiv.org/abs/1803.01580v1 |
| http://arxiv.org/pdf/1803.01580v1.pdf | |
| PWC | https://paperswithcode.com/paper/calculated-attributes-of-synonym-sets |
| Repo | |
| Framework | |
Topics in Random Matrices and Statistical Machine Learning
| Title | Topics in Random Matrices and Statistical Machine Learning |
| Authors | Sushma Kumari |
| Abstract | This thesis consists of two independent parts: random matrices, which form the first one-third of this thesis, and machine learning, which constitutes the remaining part. The main results of this thesis are as follows: a necessary and sufficient condition for the inverse moments of $(m,n,\beta)$-Laguerre matrices and compound Wishart matrices to be finite; the universal weak consistency and the strong consistency of the $k$-nearest neighbor rule in metrically sigma-finite dimensional spaces and metrically finite dimensional spaces respectively. In Part I, the Chapter 1 introduces the $(m,n,\beta)$-Laguerre matrix, Wishart and compound Wishart matrix and their joint eigenvalue distribution. While in Chapter 2, a necessary and sufficient condition to have finite inverse moments has been derived. In Part II, the Chapter 1 introduces the various notions of metric dimension and differentiation property followed by our proof for the necessary part of Preiss’ result. Further, Chapter 2 gives an introduction to the mathematical concepts in statistical machine learning and then the $k$-nearest neighbor rule is presented in Chapter 3 with a proof of Stone’s theorem. In chapters 4 and 5, we present our main results and some possible future directions based on it. |
| Tasks | |
| Published | 2018-07-25 |
| URL | http://arxiv.org/abs/1807.09419v1 |
| http://arxiv.org/pdf/1807.09419v1.pdf | |
| PWC | https://paperswithcode.com/paper/topics-in-random-matrices-and-statistical |
| Repo | |
| Framework | |
Dichotomies in Ontology-Mediated Querying with the Guarded Fragment
| Title | Dichotomies in Ontology-Mediated Querying with the Guarded Fragment |
| Authors | Andre Hernich, Carsten Lutz, Fabio Papacchini, Frank Wolter |
| Abstract | We study the complexity of ontology-mediated querying when ontologies are formulated in the guarded fragment of first-order logic (GF). Our general aim is to classify the data complexity on the level of ontologies where query evaluation w.r.t. an ontology O is considered to be in PTime if all (unions of conjunctive) queries can be evaluated in PTime w.r.t. O and coNP-hard if at least one query is coNP-hard w.r.t. O. We identify several large and relevant fragments of GF that enjoy a dichotomy between PTime and coNP, some of them additionally admitting a form of counting. In fact, almost all ontologies in the BioPortal repository fall into these fragments or can easily be rewritten to do so. We then establish a variation of Ladner’s Theorem on the existence of NP-intermediate problems and use this result to show that for other fragments, there is provably no such dichotomy. Again for other fragments (such as full GF), establishing a dichotomy implies the Feder-Vardi conjecture on the complexity of constraint satisfaction problems. We also link these results to Datalog-rewritability and study the decidability of whether a given ontology enjoys PTime query evaluation, presenting both positive and negative results. |
| Tasks | |
| Published | 2018-04-18 |
| URL | http://arxiv.org/abs/1804.06894v1 |
| http://arxiv.org/pdf/1804.06894v1.pdf | |
| PWC | https://paperswithcode.com/paper/dichotomies-in-ontology-mediated-querying |
| Repo | |
| Framework | |
A Framework for Searching in Graphs in the Presence of Errors
| Title | A Framework for Searching in Graphs in the Presence of Errors |
| Authors | Dariusz Dereniowski, Stefan Tiegel, Przemysław Uznański, Daniel Wolleb-Graf |
| Abstract | We consider the problem of searching for an unknown target vertex $t$ in a (possibly edge-weighted) graph. Each \emph{vertex-query} points to a vertex $v$ and the response either admits $v$ is the target or provides any neighbor $s\not=v$ that lies on a shortest path from $v$ to $t$. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide algorithms for the error-less case and for the independent noise model (where each query independently receives an erroneous answer with known probability $p<1/2$ and a correct one with probability $1-p$). We study this problem in both adversarial errors and independent noise models. First, we show an algorithm that needs $\frac{\log_2 n}{1 - H(r)}$ queries against \emph{adversarial} errors, where adversary is bounded with its rate of errors by a known constant $r<1/2$. Our algorithm is in fact a simplification of previous work, and our refinement lies in invoking amortization argument. We then show that our algorithm coupled with Chernoff bound argument leads to an algorithm for independent noise that is simpler and with a query complexity that is both simpler and asymptotically better to one of Emamjomeh-Zadeh et al. [STOC 2016]. Our approach has a wide range of applications. First, it improves and simplifies Robust Interactive Learning framework proposed by Emamjomeh-Zadeh et al. [NIPS 2017]. Secondly, performing analogous analysis for \emph{edge-queries} (where query to edge $e$ returns its endpoint that is closer to target) we actually recover (as a special case) noisy binary search algorithm that is asymptotically optimal, matching the complexity of Feige et al. [SIAM J. Comput. 1994]. Thirdly, we improve and simplify upon existing algorithm for searching of \emph{unbounded} domains due to Aslam and Dhagat [STOC 1991]. |
| Tasks | |
| Published | 2018-04-05 |
| URL | https://arxiv.org/abs/1804.02075v4 |
| https://arxiv.org/pdf/1804.02075v4.pdf | |
| PWC | https://paperswithcode.com/paper/a-framework-for-searching-in-graphs-in-the |
| Repo | |
| Framework | |
Differential Attention for Visual Question Answering
| Title | Differential Attention for Visual Question Answering |
| Authors | Badri Patro, Vinay P. Namboodiri |
| Abstract | In this paper we aim to answer questions based on images when provided with a dataset of question-answer pairs for a number of images during training. A number of methods have focused on solving this problem by using image based attention. This is done by focusing on a specific part of the image while answering the question. Humans also do so when solving this problem. However, the regions that the previous systems focus on are not correlated with the regions that humans focus on. The accuracy is limited due to this drawback. In this paper, we propose to solve this problem by using an exemplar based method. We obtain one or more supporting and opposing exemplars to obtain a differential attention region. This differential attention is closer to human attention than other image based attention methods. It also helps in obtaining improved accuracy when answering questions. The method is evaluated on challenging benchmark datasets. We perform better than other image based attention methods and are competitive with other state of the art methods that focus on both image and questions. |
| Tasks | Question Answering, Visual Question Answering |
| Published | 2018-04-01 |
| URL | http://arxiv.org/abs/1804.00298v2 |
| http://arxiv.org/pdf/1804.00298v2.pdf | |
| PWC | https://paperswithcode.com/paper/differential-attention-for-visual-question |
| Repo | |
| Framework | |
Data-Driven Design: Exploring new Structural Forms using Machine Learning and Graphic Statics
| Title | Data-Driven Design: Exploring new Structural Forms using Machine Learning and Graphic Statics |
| Authors | Lukas Fuhrimann, Vahid Moosavi, Patrick Ole Ohlbrock, Pierluigi Dacunto |
| Abstract | The aim of this research is to introduce a novel structural design process that allows architects and engineers to extend their typical design space horizon and thereby promoting the idea of creativity in structural design. The theoretical base of this work builds on the combination of structural form-finding and state-of-the-art machine learning algorithms. In the first step of the process, Combinatorial Equilibrium Modelling (CEM) is used to generate a large variety of spatial networks in equilibrium for given input parameters. In the second step, these networks are clustered and represented in a form-map through the implementation of a Self Organizing Map (SOM) algorithm. In the third step, the solution space is interpreted with the help of a Uniform Manifold Approximation and Projection algorithm (UMAP). This allows gaining important insights in the structure of the solution space. A specific case study is used to illustrate how the infinite equilibrium states of a given topology can be defined and represented by clusters. Furthermore, three classes, related to the non-linear interaction between the input parameters and the form space, are verified and a statement about the entire manifold of the solution space of the case study is made. To conclude, this work presents an innovative approach on how the manifold of a solution space can be grasped with a minimum amount of data and how to operate within the manifold in order to increase the diversity of solutions. |
| Tasks | |
| Published | 2018-09-23 |
| URL | http://arxiv.org/abs/1809.08660v1 |
| http://arxiv.org/pdf/1809.08660v1.pdf | |
| PWC | https://paperswithcode.com/paper/data-driven-design-exploring-new-structural |
| Repo | |
| Framework | |
Efficient Fusion of Sparse and Complementary Convolutions
| Title | Efficient Fusion of Sparse and Complementary Convolutions |
| Authors | Chun-Fu Chen, Quanfu Fan, Marco Pistoia, Gwo Giun Lee |
| Abstract | We propose a new method to create compact convolutional neural networks (CNNs) by exploiting sparse convolutions. Different from previous works that learn sparsity in models, we directly employ hand-crafted kernels with regular sparse patterns, which result in the computational gain in practice without sophisticated and dedicated software or hardware. The core of our approach is an efficient network module that linearly combines sparse kernels to yield feature representations as strong as those from regular kernels. We integrate this module into various network architectures and demonstrate its effectiveness on three vision tasks, object classification, localization and detection. For object classification and localization, our approach achieves comparable or better performance than several baselines and related works while providing lower computational costs with fewer parameters (on average, a $2-4\times$ reduction of convolutional parameters and computation). For object detection, our approach leads to a VGG-16-based Faster RCNN detector that is 12.4$\times$ smaller and about 3$\times$ faster than the baseline. |
| Tasks | Object Classification, Object Detection |
| Published | 2018-08-07 |
| URL | http://arxiv.org/abs/1808.02167v3 |
| http://arxiv.org/pdf/1808.02167v3.pdf | |
| PWC | https://paperswithcode.com/paper/efficient-fusion-of-sparse-and-complementary |
| Repo | |
| Framework | |
Learning Dynamic Generator Model by Alternating Back-Propagation Through Time
| Title | Learning Dynamic Generator Model by Alternating Back-Propagation Through Time |
| Authors | Jianwen Xie, Ruiqi Gao, Zilong Zheng, Song-Chun Zhu, Ying Nian Wu |
| Abstract | This paper studies the dynamic generator model for spatial-temporal processes such as dynamic textures and action sequences in video data. In this model, each time frame of the video sequence is generated by a generator model, which is a non-linear transformation of a latent state vector, where the non-linear transformation is parametrized by a top-down neural network. The sequence of latent state vectors follows a non-linear auto-regressive model, where the state vector of the next frame is a non-linear transformation of the state vector of the current frame as well as an independent noise vector that provides randomness in the transition. The non-linear transformation of this transition model can be parametrized by a feedforward neural network. We show that this model can be learned by an alternating back-propagation through time algorithm that iteratively samples the noise vectors and updates the parameters in the transition model and the generator model. We show that our training method can learn realistic models for dynamic textures and action patterns. |
| Tasks | |
| Published | 2018-12-27 |
| URL | http://arxiv.org/abs/1812.10587v1 |
| http://arxiv.org/pdf/1812.10587v1.pdf | |
| PWC | https://paperswithcode.com/paper/learning-dynamic-generator-model-by |
| Repo | |
| Framework | |
