Paper Group ANR 230
Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering. On Identification of Sparse Multivariable ARX Model: A Sparse Bayesian Learning Approach. Algorithms for Graph-Constrained Coalition Formation in the Real World. Prior-based Coregistration and Cosegmentation. Playing Atari Games with Deep Reinforcement Learnin …
Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering
| Title | Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering |
| Authors | Thibault Lesieur, Caterina De Bacco, Jess Banks, Florent Krzakala, Cris Moore, Lenka Zdeborová |
| Abstract | We consider the problem of Gaussian mixture clustering in the high-dimensional limit where the data consists of $m$ points in $n$ dimensions, $n,m \rightarrow \infty$ and $\alpha = m/n$ stays finite. Using exact but non-rigorous methods from statistical physics, we determine the critical value of $\alpha$ and the distance between the clusters at which it becomes information-theoretically possible to reconstruct the membership into clusters better than chance. We also determine the accuracy achievable by the Bayes-optimal estimation algorithm. In particular, we find that when the number of clusters is sufficiently large, $r > 4 + 2 \sqrt{\alpha}$, there is a gap between the threshold for information-theoretically optimal performance and the threshold at which known algorithms succeed. |
| Tasks | |
| Published | 2016-10-10 |
| URL | http://arxiv.org/abs/1610.02918v1 |
| http://arxiv.org/pdf/1610.02918v1.pdf | |
| PWC | https://paperswithcode.com/paper/phase-transitions-and-optimal-algorithms-in |
| Repo | |
| Framework | |
On Identification of Sparse Multivariable ARX Model: A Sparse Bayesian Learning Approach
| Title | On Identification of Sparse Multivariable ARX Model: A Sparse Bayesian Learning Approach |
| Authors | J. Jin, Y. Yuan, W. Pan, D. L. T. Pham, C. J. Tomlin, A. Webb, J. Goncalves |
| Abstract | This paper begins with considering the identification of sparse linear time-invariant networks described by multivariable ARX models. Such models possess relatively simple structure thus used as a benchmark to promote further research. With identifiability of the network guaranteed, this paper presents an identification method that infers both the Boolean structure of the network and the internal dynamics between nodes. Identification is performed directly from data without any prior knowledge of the system, including its order. The proposed method solves the identification problem using Maximum a posteriori estimation (MAP) but with inseparable penalties for complexity, both in terms of element (order of nonzero connections) and group sparsity (network topology). Such an approach is widely applied in Compressive Sensing (CS) and known as Sparse Bayesian Learning (SBL). We then propose a novel scheme that combines sparse Bayesian and group sparse Bayesian to efficiently solve the problem. The resulted algorithm has a similar form of the standard Sparse Group Lasso (SGL) while with known noise variance, it simplifies to exact re-weighted SGL. The method and the developed toolbox can be applied to infer networks from a wide range of fields, including systems biology applications such as signaling and genetic regulatory networks. |
| Tasks | Compressive Sensing |
| Published | 2016-09-30 |
| URL | http://arxiv.org/abs/1609.09660v1 |
| http://arxiv.org/pdf/1609.09660v1.pdf | |
| PWC | https://paperswithcode.com/paper/on-identification-of-sparse-multivariable-arx |
| Repo | |
| Framework | |
Algorithms for Graph-Constrained Coalition Formation in the Real World
| Title | Algorithms for Graph-Constrained Coalition Formation in the Real World |
| Authors | Filippo Bistaffa, Alessandro Farinelli, Jesús Cerquides, Juan A. Rodríguez-Aguilar, Sarvapali D. Ramchurn |
| Abstract | Coalition formation typically involves the coming together of multiple, heterogeneous, agents to achieve both their individual and collective goals. In this paper, we focus on a special case of coalition formation known as Graph-Constrained Coalition Formation (GCCF) whereby a network connecting the agents constrains the formation of coalitions. We focus on this type of problem given that in many real-world applications, agents may be connected by a communication network or only trust certain peers in their social network. We propose a novel representation of this problem based on the concept of edge contraction, which allows us to model the search space induced by the GCCF problem as a rooted tree. Then, we propose an anytime solution algorithm (CFSS), which is particularly efficient when applied to a general class of characteristic functions called $m+a$ functions. Moreover, we show how CFSS can be efficiently parallelised to solve GCCF using a non-redundant partition of the search space. We benchmark CFSS on both synthetic and realistic scenarios, using a real-world dataset consisting of the energy consumption of a large number of households in the UK. Our results show that, in the best case, the serial version of CFSS is 4 orders of magnitude faster than the state of the art, while the parallel version is 9.44 times faster than the serial version on a 12-core machine. Moreover, CFSS is the first approach to provide anytime approximate solutions with quality guarantees for very large systems of agents (i.e., with more than 2700 agents). |
| Tasks | |
| Published | 2016-12-13 |
| URL | http://arxiv.org/abs/1612.04299v1 |
| http://arxiv.org/pdf/1612.04299v1.pdf | |
| PWC | https://paperswithcode.com/paper/algorithms-for-graph-constrained-coalition |
| Repo | |
| Framework | |
Prior-based Coregistration and Cosegmentation
| Title | Prior-based Coregistration and Cosegmentation |
| Authors | Mahsa Shakeri, Enzo Ferrante, Stavros Tsogkas, Sarah Lippe, Samuel Kadoury, Iasonas Kokkinos, Nikos Paragios |
| Abstract | We propose a modular and scalable framework for dense coregistration and cosegmentation with two key characteristics: first, we substitute ground truth data with the semantic map output of a classifier; second, we combine this output with population deformable registration to improve both alignment and segmentation. Our approach deforms all volumes towards consensus, taking into account image similarities and label consistency. Our pipeline can incorporate any classifier and similarity metric. Results on two datasets, containing annotations of challenging brain structures, demonstrate the potential of our method. |
| Tasks | |
| Published | 2016-07-22 |
| URL | http://arxiv.org/abs/1607.06787v1 |
| http://arxiv.org/pdf/1607.06787v1.pdf | |
| PWC | https://paperswithcode.com/paper/prior-based-coregistration-and-cosegmentation |
| Repo | |
| Framework | |
Playing Atari Games with Deep Reinforcement Learning and Human Checkpoint Replay
| Title | Playing Atari Games with Deep Reinforcement Learning and Human Checkpoint Replay |
| Authors | Ionel-Alexandru Hosu, Traian Rebedea |
| Abstract | This paper introduces a novel method for learning how to play the most difficult Atari 2600 games from the Arcade Learning Environment using deep reinforcement learning. The proposed method, human checkpoint replay, consists in using checkpoints sampled from human gameplay as starting points for the learning process. This is meant to compensate for the difficulties of current exploration strategies, such as epsilon-greedy, to find successful control policies in games with sparse rewards. Like other deep reinforcement learning architectures, our model uses a convolutional neural network that receives only raw pixel inputs to estimate the state value function. We tested our method on Montezuma’s Revenge and Private Eye, two of the most challenging games from the Atari platform. The results we obtained show a substantial improvement compared to previous learning approaches, as well as over a random player. We also propose a method for training deep reinforcement learning agents using human gameplay experience, which we call human experience replay. |
| Tasks | Atari Games, Montezuma’s Revenge |
| Published | 2016-07-18 |
| URL | http://arxiv.org/abs/1607.05077v1 |
| http://arxiv.org/pdf/1607.05077v1.pdf | |
| PWC | https://paperswithcode.com/paper/playing-atari-games-with-deep-reinforcement |
| Repo | |
| Framework | |
Symbols of a cosmic order
| Title | Symbols of a cosmic order |
| Authors | F. Hadi Madjid, John M. Myers |
| Abstract | The world runs on communicated sequences of symbols, e.g. numerals. Examining both engineered and natural communications networks reveals an unsuspected order that depends on contact with an unpredictable entity. This order has three roots. The first is a proof within quantum theory that no evidence can ever determine its explanation, so that an agent choosing an explanation must do so unpredictably. The second root is the showing that clocks that step computers do not “tell time” but serve as self-adjusting symbol-handling agents that regulate “logically synchronized” motion in response to unpredictable disturbances. Such a clock-agent has a certain independence as well as the capacity to communicate via unpredictable symbols with other clock-agents and to adjust its own tick rate in response to that communication. The third root is the noticing of unpredictable symbol exchange in natural systems, including the transmission of symbols found in molecular biology. We introduce a symbol-handling agent as a role played in some cases by a person, for example a physicist who chooses an explanation of given experimental outcomes, and in other cases by some other biological entity, and in still other cases by an inanimate device, such as a computer-based detector used in physical measurements. While we forbear to try to explain the propensity of agents at all levels from cells to civilizations to form and operate networks of logically synchronized symbol-handling agents, we point to this propensity as an overlooked cosmic order, an order structured by the unpredictability ensuing from the proof. Appreciating the cosmic order leads to a conception of agency that replaces volition by unpredictability and re-conceives the notion of objectivity in a way that makes a place for agency in the world as described by physics. Some specific implications for physics are outlined. |
| Tasks | |
| Published | 2016-07-26 |
| URL | http://arxiv.org/abs/1607.07437v1 |
| http://arxiv.org/pdf/1607.07437v1.pdf | |
| PWC | https://paperswithcode.com/paper/symbols-of-a-cosmic-order |
| Repo | |
| Framework | |
Fast Training of Triplet-based Deep Binary Embedding Networks
| Title | Fast Training of Triplet-based Deep Binary Embedding Networks |
| Authors | Bohan Zhuang, Guosheng Lin, Chunhua Shen, Ian Reid |
| Abstract | In this paper, we aim to learn a mapping (or embedding) from images to a compact binary space in which Hamming distances correspond to a ranking measure for the image retrieval task. We make use of a triplet loss because this has been shown to be most effective for ranking problems. However, training in previous works can be prohibitively expensive due to the fact that optimization is directly performed on the triplet space, where the number of possible triplets for training is cubic in the number of training examples. To address this issue, we propose to formulate high-order binary codes learning as a multi-label classification problem by explicitly separating learning into two interleaved stages. To solve the first stage, we design a large-scale high-order binary codes inference algorithm to reduce the high-order objective to a standard binary quadratic problem such that graph cuts can be used to efficiently infer the binary code which serve as the label of each training datum. In the second stage we propose to map the original image to compact binary codes via carefully designed deep convolutional neural networks (CNNs) and the hashing function fitting can be solved by training binary CNN classifiers. An incremental/interleaved optimization strategy is proffered to ensure that these two steps are interactive with each other during training for better accuracy. We conduct experiments on several benchmark datasets, which demonstrate both improved training time (by as much as two orders of magnitude) as well as producing state-of-the-art hashing for various retrieval tasks. |
| Tasks | Image Retrieval, Multi-Label Classification |
| Published | 2016-03-09 |
| URL | http://arxiv.org/abs/1603.02844v2 |
| http://arxiv.org/pdf/1603.02844v2.pdf | |
| PWC | https://paperswithcode.com/paper/fast-training-of-triplet-based-deep-binary |
| Repo | |
| Framework | |
Detecting Singleton Review Spammers Using Semantic Similarity
| Title | Detecting Singleton Review Spammers Using Semantic Similarity |
| Authors | Vlad Sandulescu, Martin Ester |
| Abstract | Online reviews have increasingly become a very important resource for consumers when making purchases. Though it is becoming more and more difficult for people to make well-informed buying decisions without being deceived by fake reviews. Prior works on the opinion spam problem mostly considered classifying fake reviews using behavioral user patterns. They focused on prolific users who write more than a couple of reviews, discarding one-time reviewers. The number of singleton reviewers however is expected to be high for many review websites. While behavioral patterns are effective when dealing with elite users, for one-time reviewers, the review text needs to be exploited. In this paper we tackle the problem of detecting fake reviews written by the same person using multiple names, posting each review under a different name. We propose two methods to detect similar reviews and show the results generally outperform the vectorial similarity measures used in prior works. The first method extends the semantic similarity between words to the reviews level. The second method is based on topic modeling and exploits the similarity of the reviews topic distributions using two models: bag-of-words and bag-of-opinion-phrases. The experiments were conducted on reviews from three different datasets: Yelp (57K reviews), Trustpilot (9K reviews) and Ott dataset (800 reviews). |
| Tasks | Semantic Similarity, Semantic Textual Similarity |
| Published | 2016-09-09 |
| URL | http://arxiv.org/abs/1609.02727v1 |
| http://arxiv.org/pdf/1609.02727v1.pdf | |
| PWC | https://paperswithcode.com/paper/detecting-singleton-review-spammers-using |
| Repo | |
| Framework | |
Multifaceted Feature Visualization: Uncovering the Different Types of Features Learned By Each Neuron in Deep Neural Networks
| Title | Multifaceted Feature Visualization: Uncovering the Different Types of Features Learned By Each Neuron in Deep Neural Networks |
| Authors | Anh Nguyen, Jason Yosinski, Jeff Clune |
| Abstract | We can better understand deep neural networks by identifying which features each of their neurons have learned to detect. To do so, researchers have created Deep Visualization techniques including activation maximization, which synthetically generates inputs (e.g. images) that maximally activate each neuron. A limitation of current techniques is that they assume each neuron detects only one type of feature, but we know that neurons can be multifaceted, in that they fire in response to many different types of features: for example, a grocery store class neuron must activate either for rows of produce or for a storefront. Previous activation maximization techniques constructed images without regard for the multiple different facets of a neuron, creating inappropriate mixes of colors, parts of objects, scales, orientations, etc. Here, we introduce an algorithm that explicitly uncovers the multiple facets of each neuron by producing a synthetic visualization of each of the types of images that activate a neuron. We also introduce regularization methods that produce state-of-the-art results in terms of the interpretability of images obtained by activation maximization. By separately synthesizing each type of image a neuron fires in response to, the visualizations have more appropriate colors and coherent global structure. Multifaceted feature visualization thus provides a clearer and more comprehensive description of the role of each neuron. |
| Tasks | |
| Published | 2016-02-11 |
| URL | http://arxiv.org/abs/1602.03616v2 |
| http://arxiv.org/pdf/1602.03616v2.pdf | |
| PWC | https://paperswithcode.com/paper/multifaceted-feature-visualization-uncovering |
| Repo | |
| Framework | |
DeepGraph: Graph Structure Predicts Network Growth
| Title | DeepGraph: Graph Structure Predicts Network Growth |
| Authors | Cheng Li, Xiaoxiao Guo, Qiaozhu Mei |
| Abstract | The topological (or graph) structures of real-world networks are known to be predictive of multiple dynamic properties of the networks. Conventionally, a graph structure is represented using an adjacency matrix or a set of hand-crafted structural features. These representations either fail to highlight local and global properties of the graph or suffer from a severe loss of structural information. There lacks an effective graph representation, which hinges the realization of the predictive power of network structures. In this study, we propose to learn the represention of a graph, or the topological structure of a network, through a deep learning model. This end-to-end prediction model, named DeepGraph, takes the input of the raw adjacency matrix of a real-world network and outputs a prediction of the growth of the network. The adjacency matrix is first represented using a graph descriptor based on the heat kernel signature, which is then passed through a multi-column, multi-resolution convolutional neural network. Extensive experiments on five large collections of real-world networks demonstrate that the proposed prediction model significantly improves the effectiveness of existing methods, including linear or nonlinear regressors that use hand-crafted features, graph kernels, and competing deep learning methods. |
| Tasks | |
| Published | 2016-10-20 |
| URL | http://arxiv.org/abs/1610.06251v1 |
| http://arxiv.org/pdf/1610.06251v1.pdf | |
| PWC | https://paperswithcode.com/paper/deepgraph-graph-structure-predicts-network |
| Repo | |
| Framework | |
Deep video gesture recognition using illumination invariants
| Title | Deep video gesture recognition using illumination invariants |
| Authors | Otkrist Gupta, Dan Raviv, Ramesh Raskar |
| Abstract | In this paper we present architectures based on deep neural nets for gesture recognition in videos, which are invariant to local scaling. We amalgamate autoencoder and predictor architectures using an adaptive weighting scheme coping with a reduced size labeled dataset, while enriching our models from enormous unlabeled sets. We further improve robustness to lighting conditions by introducing a new adaptive filer based on temporal local scale normalization. We provide superior results over known methods, including recent reported approaches based on neural nets. |
| Tasks | Gesture Recognition |
| Published | 2016-03-21 |
| URL | http://arxiv.org/abs/1603.06531v1 |
| http://arxiv.org/pdf/1603.06531v1.pdf | |
| PWC | https://paperswithcode.com/paper/deep-video-gesture-recognition-using |
| Repo | |
| Framework | |
Animal Classification System: A Block Based Approach
| Title | Animal Classification System: A Block Based Approach |
| Authors | Y H Sharath Kumar, Manohar N, H K Chethan |
| Abstract | In this work, we propose a method for the classification of animal in images. Initially, a graph cut based method is used to perform segmentation in order to eliminate the background from the given image. The segmented animal images are partitioned in to number of blocks and then the color texture moments are extracted from different blocks. Probabilistic neural network and K-nearest neighbors are considered here for classification. To corroborate the efficacy of the proposed method, an experiment was conducted on our own data set of 25 classes of animals, which consisted of 4000 sample images. The experiment was conducted by picking images randomly from the database to study the effect of classification accuracy, and the results show that the K-nearest neighbors classifier achieves good performance. |
| Tasks | |
| Published | 2016-09-06 |
| URL | http://arxiv.org/abs/1609.01829v1 |
| http://arxiv.org/pdf/1609.01829v1.pdf | |
| PWC | https://paperswithcode.com/paper/animal-classification-system-a-block-based |
| Repo | |
| Framework | |
Generation of a Supervised Classification Algorithm for Time-Series Variable Stars with an Application to the LINEAR Dataset
| Title | Generation of a Supervised Classification Algorithm for Time-Series Variable Stars with an Application to the LINEAR Dataset |
| Authors | Kyle B Johnston, Hakeem M Oluseyi |
| Abstract | With the advent of digital astronomy, new benefits and new problems have been presented to the modern day astronomer. While data can be captured in a more efficient and accurate manor using digital means, the efficiency of data retrieval has led to an overload of scientific data for processing and storage. This paper will focus on the construction and application of a supervised pattern classification algorithm for the identification of variable stars. Given the reduction of a survey of stars into a standard feature space, the problem of using prior patterns to identify new observed patterns can be reduced to time tested classification methodologies and algorithms. Such supervised methods, so called because the user trains the algorithms prior to application using patterns with known classes or labels, provide a means to probabilistically determine the estimated class type of new observations. This paper will demonstrate the construction and application of a supervised classification algorithm on variable star data. The classifier is applied to a set of 192,744 LINEAR data points. Of the original samples, 34,451 unique stars were classified with high confidence (high level of probability of being the true class). |
| Tasks | Time Series |
| Published | 2016-01-14 |
| URL | http://arxiv.org/abs/1601.03769v1 |
| http://arxiv.org/pdf/1601.03769v1.pdf | |
| PWC | https://paperswithcode.com/paper/generation-of-a-supervised-classification |
| Repo | |
| Framework | |
Bayesian Opponent Exploitation in Imperfect-Information Games
| Title | Bayesian Opponent Exploitation in Imperfect-Information Games |
| Authors | Sam Ganzfried, Qingyun Sun |
| Abstract | Two fundamental problems in computational game theory are computing a Nash equilibrium and learning to exploit opponents given observations of their play (opponent exploitation). The latter is perhaps even more important than the former: Nash equilibrium does not have a compelling theoretical justification in game classes other than two-player zero-sum, and for all games one can potentially do better by exploiting perceived weaknesses of the opponent than by following a static equilibrium strategy throughout the match. The natural setting for opponent exploitation is the Bayesian setting where we have a prior model that is integrated with observations to create a posterior opponent model that we respond to. The most natural, and a well-studied prior distribution is the Dirichlet distribution. An exact polynomial-time algorithm is known for best-responding to the posterior distribution for an opponent assuming a Dirichlet prior with multinomial sampling in normal-form games; however, for imperfect-information games the best known algorithm is based on approximating an infinite integral without theoretical guarantees. We present the first exact algorithm for a natural class of imperfect-information games. We demonstrate that our algorithm runs quickly in practice and outperforms the best prior approaches. We also present an algorithm for the uniform prior setting. |
| Tasks | |
| Published | 2016-03-10 |
| URL | http://arxiv.org/abs/1603.03491v6 |
| http://arxiv.org/pdf/1603.03491v6.pdf | |
| PWC | https://paperswithcode.com/paper/bayesian-opponent-exploitation-in-imperfect |
| Repo | |
| Framework | |
Morphological Inflection Generation with Hard Monotonic Attention
| Title | Morphological Inflection Generation with Hard Monotonic Attention |
| Authors | Roee Aharoni, Yoav Goldberg |
| Abstract | We present a neural model for morphological inflection generation which employs a hard attention mechanism, inspired by the nearly-monotonic alignment commonly found between the characters in a word and the characters in its inflection. We evaluate the model on three previously studied morphological inflection generation datasets and show that it provides state of the art results in various setups compared to previous neural and non-neural approaches. Finally we present an analysis of the continuous representations learned by both the hard and soft attention \cite{bahdanauCB14} models for the task, shedding some light on the features such models extract. |
| Tasks | Morphological Inflection |
| Published | 2016-11-04 |
| URL | http://arxiv.org/abs/1611.01487v3 |
| http://arxiv.org/pdf/1611.01487v3.pdf | |
| PWC | https://paperswithcode.com/paper/morphological-inflection-generation-with-hard |
| Repo | |
| Framework | |
