Paper Group ANR 114
Online Reinforcement Learning for Real-Time Exploration in Continuous State and Action Markov Decision Processes. The Mean Partition Theorem of Consensus Clustering. Laser light-field fusion for wide-field lensfree on-chip phase contrast nanoscopy. Sentiment Analysis of Twitter Data: A Survey of Techniques. On the Phase Transition of Finding a Bicl …
Online Reinforcement Learning for Real-Time Exploration in Continuous State and Action Markov Decision Processes
| Title | Online Reinforcement Learning for Real-Time Exploration in Continuous State and Action Markov Decision Processes |
| Authors | Ludovic Hofer, Hugo Gimbert |
| Abstract | This paper presents a new method to learn online policies in continuous state, continuous action, model-free Markov decision processes, with two properties that are crucial for practical applications. First, the policies are implementable with a very low computational cost: once the policy is computed, the action corresponding to a given state is obtained in logarithmic time with respect to the number of samples used. Second, our method is versatile: it does not rely on any a priori knowledge of the structure of optimal policies. We build upon the Fitted Q-iteration algorithm which represents the $Q$-value as the average of several regression trees. Our algorithm, the Fitted Policy Forest algorithm (FPF), computes a regression forest representing the Q-value and transforms it into a single tree representing the policy, while keeping control on the size of the policy using resampling and leaf merging. We introduce an adaptation of Multi-Resolution Exploration (MRE) which is particularly suited to FPF. We assess the performance of FPF on three classical benchmarks for reinforcement learning: the “Inverted Pendulum”, the “Double Integrator” and “Car on the Hill” and show that FPF equals or outperforms other algorithms, although these algorithms rely on the use of particular representations of the policies, especially chosen in order to fit each of the three problems. Finally, we exhibit that the combination of FPF and MRE allows to find nearly optimal solutions in problems where $\epsilon$-greedy approaches would fail. |
| Tasks | |
| Published | 2016-12-12 |
| URL | http://arxiv.org/abs/1612.03780v1 |
| http://arxiv.org/pdf/1612.03780v1.pdf | |
| PWC | https://paperswithcode.com/paper/online-reinforcement-learning-for-real-time |
| Repo | |
| Framework | |
The Mean Partition Theorem of Consensus Clustering
| Title | The Mean Partition Theorem of Consensus Clustering |
| Authors | Brijnesh J. Jain |
| Abstract | To devise efficient solutions for approximating a mean partition in consensus clustering, Dimitriadou et al. [3] presented a necessary condition of optimality for a consensus function based on least square distances. We show that their result is pivotal for deriving interesting properties of consensus clustering beyond optimization. For this, we present the necessary condition of optimality in a slightly stronger form in terms of the Mean Partition Theorem and extend it to the Expected Partition Theorem. To underpin its versatility, we show three examples that apply the Mean Partition Theorem: (i) equivalence of the mean partition and optimal multiple alignment, (ii) construction of profiles and motifs, and (iii) relationship between consensus clustering and cluster stability. |
| Tasks | |
| Published | 2016-04-22 |
| URL | http://arxiv.org/abs/1604.06626v2 |
| http://arxiv.org/pdf/1604.06626v2.pdf | |
| PWC | https://paperswithcode.com/paper/the-mean-partition-theorem-of-consensus |
| Repo | |
| Framework | |
Laser light-field fusion for wide-field lensfree on-chip phase contrast nanoscopy
| Title | Laser light-field fusion for wide-field lensfree on-chip phase contrast nanoscopy |
| Authors | Farnoud Kazemzadeh, Alexander Wong |
| Abstract | Wide-field lensfree on-chip microscopy, which leverages holography principles to capture interferometric light-field encodings without lenses, is an emerging imaging modality with widespread interest given the large field-of-view compared to lens-based techniques. In this study, we introduce the idea of laser light-field fusion for lensfree on-chip phase contrast nanoscopy, where interferometric laser light-field encodings acquired using an on-chip setup with laser pulsations at different wavelengths are fused to produce marker-free phase contrast images of superior quality with resolving power more than five times below the pixel pitch of the sensor array and more than 40% beyond the diffraction limit. As a proof of concept, we demonstrate, for the first time, a wide-field lensfree on-chip instrument successfully detecting 300 nm particles, resulting in a numerical aperture of 1.1, across a large field-of-view of $\sim$ 30 mm$^2$ without any specialized or intricate sample preparation, or the use of synthetic aperture- or shift-based techniques. |
| Tasks | |
| Published | 2016-04-27 |
| URL | http://arxiv.org/abs/1604.08145v2 |
| http://arxiv.org/pdf/1604.08145v2.pdf | |
| PWC | https://paperswithcode.com/paper/laser-light-field-fusion-for-wide-field |
| Repo | |
| Framework | |
Sentiment Analysis of Twitter Data: A Survey of Techniques
| Title | Sentiment Analysis of Twitter Data: A Survey of Techniques |
| Authors | Vishal. A. Kharde, Prof. Sheetal. Sonawane |
| Abstract | With the advancement of web technology and its growth, there is a huge volume of data present in the web for internet users and a lot of data is generated too. Internet has become a platform for online learning, exchanging ideas and sharing opinions. Social networking sites like Twitter, Facebook, Google+ are rapidly gaining popularity as they allow people to share and express their views about topics,have discussion with different communities, or post messages across the world. There has been lot of work in the field of sentiment analysis of twitter data. This survey focuses mainly on sentiment analysis of twitter data which is helpful to analyze the information in the tweets where opinions are highly unstructured, heterogeneous and are either positive or negative, or neutral in some cases. In this paper, we provide a survey and a comparative analyses of existing techniques for opinion mining like machine learning and lexicon-based approaches, together with evaluation metrics. Using various machine learning algorithms like Naive Bayes, Max Entropy, and Support Vector Machine, we provide a research on twitter data streams.General challenges and applications of Sentiment Analysis on Twitter are also discussed in this paper. |
| Tasks | Opinion Mining, Sentiment Analysis |
| Published | 2016-01-26 |
| URL | http://arxiv.org/abs/1601.06971v3 |
| http://arxiv.org/pdf/1601.06971v3.pdf | |
| PWC | https://paperswithcode.com/paper/sentiment-analysis-of-twitter-data-a-survey |
| Repo | |
| Framework | |
On the Phase Transition of Finding a Biclique in a larger Bipartite Graph
| Title | On the Phase Transition of Finding a Biclique in a larger Bipartite Graph |
| Authors | Roberto Alonso, Raúl Monroy, Eduardo Aguirre |
| Abstract | We report on the phase transition of finding a complete subgraph, of specified dimensions, in a bipartite graph. Finding a complete subgraph in a bipartite graph is a problem that has growing attention in several domains, including bioinformatics, social network analysis and domain clustering. A key step for a successful phase transition study is identifying a suitable order parameter, when none is known. To this purpose, we have applied a decision tree classifier to real-world instances of this problem, in order to understand what problem features separate an instance that is hard to solve from those that is not. We have successfully identified one such order parameter and with it the phase transition of finding a complete bipartite subgraph of specified dimensions. Our phase transition study shows an easy-to-hard-to-easy-to-hard-to-easy pattern. Further, our results indicate that the hardest instances are in a region where it is more likely that the corresponding bipartite graph will have a complete subgraph of specified dimensions, a positive answer. By contrast, instances with a negative answer are more likely to appear in a region where the computational cost is negligible. This behaviour is remarkably similar for problems of a number of different sizes. |
| Tasks | |
| Published | 2016-09-19 |
| URL | http://arxiv.org/abs/1609.05876v1 |
| http://arxiv.org/pdf/1609.05876v1.pdf | |
| PWC | https://paperswithcode.com/paper/on-the-phase-transition-of-finding-a-biclique |
| Repo | |
| Framework | |
Stochastic Rank-1 Bandits
| Title | Stochastic Rank-1 Bandits |
| Authors | Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, Claire Vernade, Zheng Wen |
| Abstract | We propose stochastic rank-$1$ bandits, a class of online learning problems where at each step a learning agent chooses a pair of row and column arms, and receives the product of their values as a reward. The main challenge of the problem is that the individual values of the row and column are unobserved. We assume that these values are stochastic and drawn independently. We propose a computationally-efficient algorithm for solving our problem, which we call Rank1Elim. We derive a $O((K + L) (1 / \Delta) \log n)$ upper bound on its $n$-step regret, where $K$ is the number of rows, $L$ is the number of columns, and $\Delta$ is the minimum of the row and column gaps; under the assumption that the mean row and column rewards are bounded away from zero. To the best of our knowledge, we present the first bandit algorithm that finds the maximum entry of a rank-$1$ matrix whose regret is linear in $K + L$, $1 / \Delta$, and $\log n$. We also derive a nearly matching lower bound. Finally, we evaluate Rank1Elim empirically on multiple problems. We observe that it leverages the structure of our problems and can learn near-optimal solutions even if our modeling assumptions are mildly violated. |
| Tasks | |
| Published | 2016-08-10 |
| URL | http://arxiv.org/abs/1608.03023v3 |
| http://arxiv.org/pdf/1608.03023v3.pdf | |
| PWC | https://paperswithcode.com/paper/stochastic-rank-1-bandits |
| Repo | |
| Framework | |
A Feature-Based Prediction Model of Algorithm Selection for Constrained Continuous Optimisation
| Title | A Feature-Based Prediction Model of Algorithm Selection for Constrained Continuous Optimisation |
| Authors | Shayan Poursoltan, Frank Neumann |
| Abstract | With this paper, we contribute to the growing research area of feature-based analysis of bio-inspired computing. In this research area, problem instances are classified according to different features of the underlying problem in terms of their difficulty of being solved by a particular algorithm. We investigate the impact of different sets of evolved instances for building prediction models in the area of algorithm selection. Building on the work of Poursoltan and Neumann [11,10], we consider how evolved instances can be used to predict the best performing algorithm for constrained continuous optimisation from a set of bio-inspired computing methods, namely high performing variants of differential evolution, particle swarm optimization, and evolution strategies. Our experimental results show that instances evolved with a multi-objective approach in combination with random instances of the underlying problem allow to build a model that accurately predicts the best performing algorithm for a wide range of problem instances. |
| Tasks | |
| Published | 2016-02-09 |
| URL | http://arxiv.org/abs/1602.02862v1 |
| http://arxiv.org/pdf/1602.02862v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-feature-based-prediction-model-of-algorithm |
| Repo | |
| Framework | |
High-dimensional Filtering using Nested Sequential Monte Carlo
| Title | High-dimensional Filtering using Nested Sequential Monte Carlo |
| Authors | Christian A. Naesseth, Fredrik Lindsten, Thomas B. Schön |
| Abstract | Sequential Monte Carlo (SMC) methods comprise one of the most successful approaches to approximate Bayesian filtering. However, SMC without good proposal distributions struggle in high dimensions. We propose nested sequential Monte Carlo (NSMC), a methodology that generalises the SMC framework by requiring only approximate, properly weighted, samples from the SMC proposal distribution, while still resulting in a correct SMC algorithm. This way we can exactly approximate the locally optimal proposal, and extend the class of models for which we can perform efficient inference using SMC. We show improved accuracy over other state-of-the-art methods on several spatio-temporal state space models. |
| Tasks | |
| Published | 2016-12-29 |
| URL | http://arxiv.org/abs/1612.09162v1 |
| http://arxiv.org/pdf/1612.09162v1.pdf | |
| PWC | https://paperswithcode.com/paper/high-dimensional-filtering-using-nested |
| Repo | |
| Framework | |
Multi-dimensional signal approximation with sparse structured priors using split Bregman iterations
| Title | Multi-dimensional signal approximation with sparse structured priors using split Bregman iterations |
| Authors | Yoann Isaac, Quentin Barthélemy, Cédric Gouy-Pailler, Michèle Sebag, Jamal Atif |
| Abstract | This paper addresses the structurally-constrained sparse decomposition of multi-dimensional signals onto overcomplete families of vectors, called dictionaries. The contribution of the paper is threefold. Firstly, a generic spatio-temporal regularization term is designed and used together with the standard $\ell_1$ regularization term to enforce a sparse decomposition preserving the spatio-temporal structure of the signal. Secondly, an optimization algorithm based on the split Bregman approach is proposed to handle the associated optimization problem, and its convergence is analyzed. Our well-founded approach yields same accuracy as the other algorithms at the state-of-the-art, with significant gains in terms of convergence speed. Thirdly, the empirical validation of the approach on artificial and real-world problems demonstrates the generality and effectiveness of the method. On artificial problems, the proposed regularization subsumes the Total Variation minimization and recovers the expected decomposition. On the real-world problem of electro-encephalography brainwave decomposition, the approach outperforms similar approaches in terms of P300 evoked potentials detection, using structured spatial priors to guide the decomposition. |
| Tasks | |
| Published | 2016-09-29 |
| URL | http://arxiv.org/abs/1609.09525v1 |
| http://arxiv.org/pdf/1609.09525v1.pdf | |
| PWC | https://paperswithcode.com/paper/multi-dimensional-signal-approximation-with |
| Repo | |
| Framework | |
Basic Reasoning with Tensor Product Representations
| Title | Basic Reasoning with Tensor Product Representations |
| Authors | Paul Smolensky, Moontae Lee, Xiaodong He, Wen-tau Yih, Jianfeng Gao, Li Deng |
| Abstract | In this paper we present the initial development of a general theory for mapping inference in predicate logic to computation over Tensor Product Representations (TPRs; Smolensky (1990), Smolensky & Legendre (2006)). After an initial brief synopsis of TPRs (Section 0), we begin with particular examples of inference with TPRs in the ‘bAbI’ question-answering task of Weston et al. (2015) (Section 1). We then present a simplification of the general analysis that suffices for the bAbI task (Section 2). Finally, we lay out the general treatment of inference over TPRs (Section 3). We also show the simplification in Section 2 derives the inference methods described in Lee et al. (2016); this shows how the simple methods of Lee et al. (2016) can be formally extended to more general reasoning tasks. |
| Tasks | Question Answering |
| Published | 2016-01-12 |
| URL | http://arxiv.org/abs/1601.02745v1 |
| http://arxiv.org/pdf/1601.02745v1.pdf | |
| PWC | https://paperswithcode.com/paper/basic-reasoning-with-tensor-product |
| Repo | |
| Framework | |
Lexis: An Optimization Framework for Discovering the Hierarchical Structure of Sequential Data
| Title | Lexis: An Optimization Framework for Discovering the Hierarchical Structure of Sequential Data |
| Authors | Payam Siyari, Bistra Dilkina, Constantine Dovrolis |
| Abstract | Data represented as strings abounds in biology, linguistics, document mining, web search and many other fields. Such data often have a hierarchical structure, either because they were artificially designed and composed in a hierarchical manner or because there is an underlying evolutionary process that creates repeatedly more complex strings from simpler substrings. We propose a framework, referred to as “Lexis”, that produces an optimized hierarchical representation of a given set of “target” strings. The resulting hierarchy, “Lexis-DAG”, shows how to construct each target through the concatenation of intermediate substrings, minimizing the total number of such concatenations or DAG edges. The Lexis optimization problem is related to the smallest grammar problem. After we prove its NP-Hardness for two cost formulations, we propose an efficient greedy algorithm for the construction of Lexis-DAGs. We also consider the problem of identifying the set of intermediate nodes (substrings) that collectively form the “core” of a Lexis-DAG, which is important in the analysis of Lexis-DAGs. We show that the Lexis framework can be applied in diverse applications such as optimized synthesis of DNA fragments in genomic libraries, hierarchical structure discovery in protein sequences, dictionary-based text compression, and feature extraction from a set of documents. |
| Tasks | |
| Published | 2016-02-17 |
| URL | http://arxiv.org/abs/1602.05561v3 |
| http://arxiv.org/pdf/1602.05561v3.pdf | |
| PWC | https://paperswithcode.com/paper/lexis-an-optimization-framework-for |
| Repo | |
| Framework | |
Commonsense Reasoning, Commonsense Knowledge, and The SP Theory of Intelligence
| Title | Commonsense Reasoning, Commonsense Knowledge, and The SP Theory of Intelligence |
| Authors | J Gerard Wolff |
| Abstract | This paper describes how the “SP Theory of Intelligence” with the “SP Computer Model”, outlined in an Appendix, may throw light on aspects of commonsense reasoning (CSR) and commonsense knowledge (CSK), as discussed in another paper by Ernest Davis and Gary Marcus (DM). In four main sections, the paper describes: 1) The main problems to be solved; 2) Other research on CSR and CSK; 3) Why the SP system may prove useful with CSR and CSK 4) How examples described by DM may be modelled in the SP system. With regard to successes in the automation of CSR described by DM, the SP system’s strengths in simplification and integration may promote seamless integration across these areas, and seamless integration of those area with other aspects of intelligence. In considering challenges in the automation of CSR described by DM, the paper describes in detail, with examples of SP-multiple-alignments. how the SP system may model processes of interpretation and reasoning arising from the horse’s head scene in “The Godfather” film. A solution is presented to the ‘long tail’ problem described by DM. The SP system has some potentially useful things to say about several of DM’s objectives for research in CSR and CSK. |
| Tasks | |
| Published | 2016-09-25 |
| URL | http://arxiv.org/abs/1609.07772v2 |
| http://arxiv.org/pdf/1609.07772v2.pdf | |
| PWC | https://paperswithcode.com/paper/commonsense-reasoning-commonsense-knowledge |
| Repo | |
| Framework | |
Parsing Argumentation Structures in Persuasive Essays
| Title | Parsing Argumentation Structures in Persuasive Essays |
| Authors | Christian Stab, Iryna Gurevych |
| Abstract | In this article, we present a novel approach for parsing argumentation structures. We identify argument components using sequence labeling at the token level and apply a new joint model for detecting argumentation structures. The proposed model globally optimizes argument component types and argumentative relations using integer linear programming. We show that our model considerably improves the performance of base classifiers and significantly outperforms challenging heuristic baselines. Moreover, we introduce a novel corpus of persuasive essays annotated with argumentation structures. We show that our annotation scheme and annotation guidelines successfully guide human annotators to substantial agreement. This corpus and the annotation guidelines are freely available for ensuring reproducibility and to encourage future research in computational argumentation. |
| Tasks | |
| Published | 2016-04-25 |
| URL | http://arxiv.org/abs/1604.07370v2 |
| http://arxiv.org/pdf/1604.07370v2.pdf | |
| PWC | https://paperswithcode.com/paper/parsing-argumentation-structures-in |
| Repo | |
| Framework | |
An Automated System for Essay Scoring of Online Exams in Arabic based on Stemming Techniques and Levenshtein Edit Operations
| Title | An Automated System for Essay Scoring of Online Exams in Arabic based on Stemming Techniques and Levenshtein Edit Operations |
| Authors | Emad Fawzi Al-Shalabi |
| Abstract | In this article, an automated system is proposed for essay scoring in Arabic language for online exams based on stemming techniques and Levenshtein edit operations. An online exam has been developed on the proposed mechanisms, exploiting the capabilities of light and heavy stemming. The implemented online grading system has shown to be an efficient tool for automated scoring of essay questions. |
| Tasks | |
| Published | 2016-11-08 |
| URL | http://arxiv.org/abs/1611.02815v1 |
| http://arxiv.org/pdf/1611.02815v1.pdf | |
| PWC | https://paperswithcode.com/paper/an-automated-system-for-essay-scoring-of |
| Repo | |
| Framework | |
Git4Voc: Git-based Versioning for Collaborative Vocabulary Development
| Title | Git4Voc: Git-based Versioning for Collaborative Vocabulary Development |
| Authors | Lavdim Halilaj, Irlán Grangel-González, Gökhan Coskun, Sören Auer |
| Abstract | Collaborative vocabulary development in the context of data integration is the process of finding consensus between the experts of the different systems and domains. The complexity of this process is increased with the number of involved people, the variety of the systems to be integrated and the dynamics of their domain. In this paper we advocate that the realization of a powerful version control system is the heart of the problem. Driven by this idea and the success of Git in the context of software development, we investigate the applicability of Git for collaborative vocabulary development. Even though vocabulary development and software development have much more similarities than differences there are still important differences. These need to be considered within the development of a successful versioning and collaboration system for vocabulary development. Therefore, this paper starts by presenting the challenges we were faced with during the creation of vocabularies collaboratively and discusses its distinction to software development. Based on these insights we propose Git4Voc which comprises guidelines how Git can be adopted to vocabulary development. Finally, we demonstrate how Git hooks can be implemented to go beyond the plain functionality of Git by realizing vocabulary-specific features like syntactic validation and semantic diffs. |
| Tasks | |
| Published | 2016-01-11 |
| URL | http://arxiv.org/abs/1601.02433v1 |
| http://arxiv.org/pdf/1601.02433v1.pdf | |
| PWC | https://paperswithcode.com/paper/git4voc-git-based-versioning-for |
| Repo | |
| Framework | |
