Paper Group ANR 675
Estimating the Mixing Time of Ergodic Markov Chains. Simultaneous Translation with Flexible Policy via Restricted Imitation Learning. Blind Visual Motif Removal from a Single Image. Introduction to Multi-Armed Bandits. Quantum Computation with Machine-Learning-Controlled Quantum Stuff. Regularizing Model-Based Planning with Energy-Based Models. Neu …
Estimating the Mixing Time of Ergodic Markov Chains
| Title | Estimating the Mixing Time of Ergodic Markov Chains |
| Authors | Geoffrey Wolfer, Aryeh Kontorovich |
| Abstract | We address the problem of estimating the mixing time $t_{\mathsf{mix}}$ of an arbitrary ergodic finite-state Markov chain from a single trajectory of length $m$. The reversible case was addressed by Hsu et al. [2019], who left the general case as an open problem. In the reversible case, the analysis is greatly facilitated by the fact that the Markov operator is self-adjoint, and Weyl’s inequality allows for a dimension-free perturbation analysis of the empirical eigenvalues. As Hsu et al. point out, in the absence of reversibility (which induces asymmetric pair probabilities matrices), the existing perturbation analysis has a worst-case exponential dependence on the number of states $d$. Furthermore, even if an eigenvalue perturbation analysis with better dependence on $d$ were available, in the non-reversible case the connection between the spectral gap and the mixing time is not nearly as straightforward as in the reversible case. Our key insight is to estimate the pseudo-spectral gap $\gamma_{\mathsf{ps}}$ instead, which allows us to overcome the loss of symmetry and to achieve a polynomial dependence on the minimal stationary probability $\pi_\star$ and $\gamma_{\mathsf{ps}}$. Additionally, in the reversible case, we obtain simultaneous nearly (up to logarithmic factors) minimax rates in $t_{\mathsf{mix}}$ and precision $\varepsilon$, closing a gap in Hsu et al., who treated $\varepsilon$ as constant in the lower bounds. Finally, we construct fully empirical confidence intervals for $\gamma_{\mathsf{ps}}$, which shrink to zero at a rate of roughly $1/\sqrt{m}$, and improve the state of the art in even the reversible case. |
| Tasks | |
| Published | 2019-02-01 |
| URL | https://arxiv.org/abs/1902.01224v3 |
| https://arxiv.org/pdf/1902.01224v3.pdf | |
| PWC | https://paperswithcode.com/paper/estimating-the-mixing-time-of-ergodic-markov |
| Repo | |
| Framework | |
Simultaneous Translation with Flexible Policy via Restricted Imitation Learning
| Title | Simultaneous Translation with Flexible Policy via Restricted Imitation Learning |
| Authors | Baigong Zheng, Renjie Zheng, Mingbo Ma, Liang Huang |
| Abstract | Simultaneous translation is widely useful but remains one of the most difficult tasks in NLP. Previous work either uses fixed-latency policies, or train a complicated two-staged model using reinforcement learning. We propose a much simpler single model that adds a `delay’ token to the target vocabulary, and design a restricted dynamic oracle to greatly simplify training. Experiments on Chinese<->English simultaneous translation show that our work leads to flexible policies that achieve better BLEU scores and lower latencies compared to both fixed and RL-learned policies. | |
| Tasks | Imitation Learning |
| Published | 2019-06-04 |
| URL | https://arxiv.org/abs/1906.01135v2 |
| https://arxiv.org/pdf/1906.01135v2.pdf | |
| PWC | https://paperswithcode.com/paper/simultaneous-translation-with-flexible-policy |
| Repo | |
| Framework | |
Blind Visual Motif Removal from a Single Image
| Title | Blind Visual Motif Removal from a Single Image |
| Authors | Amir Hertz, Sharon Fogel, Rana Hanocka, Raja Giryes, Daniel Cohen-Or |
| Abstract | Many images shared over the web include overlaid objects, or visual motifs, such as text, symbols or drawings, which add a description or decoration to the image. For example, decorative text that specifies where the image was taken, repeatedly appears across a variety of different images. Often, the reoccurring visual motif, is semantically similar, yet, differs in location, style and content (e.g. text placement, font and letters). This work proposes a deep learning based technique for blind removal of such objects. In the blind setting, the location and exact geometry of the motif are unknown. Our approach simultaneously estimates which pixels contain the visual motif, and synthesizes the underlying latent image. It is applied to a single input image, without any user assistance in specifying the location of the motif, achieving state-of-the-art results for blind removal of both opaque and semi-transparent visual motifs. |
| Tasks | |
| Published | 2019-04-04 |
| URL | http://arxiv.org/abs/1904.02756v1 |
| http://arxiv.org/pdf/1904.02756v1.pdf | |
| PWC | https://paperswithcode.com/paper/blind-visual-motif-removal-from-a-single |
| Repo | |
| Framework | |
Introduction to Multi-Armed Bandits
| Title | Introduction to Multi-Armed Bandits |
| Authors | Aleksandrs Slivkins |
| Abstract | Multi-armed bandits a simple but very powerful framework for algorithms that make decisions over time under uncertainty. An enormous body of work has accumulated over the years, covered in several books and surveys. This book provides a more introductory, textbook-like treatment of the subject. Each chapter tackles a particular line of work, providing a self-contained, teachable technical introduction and a brief review of the further developments. The chapters are as follows: stochastic bandits, lower bounds; Bayesian bandits and Thompson Sampling; Lipschitz Bandits; full Feedback and adversarial costs; adversarial bandits; linear costs and semi-bandits; contextual Bandits; bandits and games; bandits with knapsacks; bandits and incentives. |
| Tasks | Multi-Armed Bandits |
| Published | 2019-04-15 |
| URL | https://arxiv.org/abs/1904.07272v5 |
| https://arxiv.org/pdf/1904.07272v5.pdf | |
| PWC | https://paperswithcode.com/paper/introduction-to-multi-armed-bandits |
| Repo | |
| Framework | |
Quantum Computation with Machine-Learning-Controlled Quantum Stuff
| Title | Quantum Computation with Machine-Learning-Controlled Quantum Stuff |
| Authors | Lucien Hardy, Adam G. M. Lewis |
| Abstract | We describe how one may go about performing quantum computation with arbitrary “quantum stuff”, as long as it has some basic physical properties. Imagine a long strip of stuff, equipped with regularly spaced wires to provide input settings and to read off outcomes. After showing how the corresponding map from settings to outcomes can be construed as a quantum circuit, we provide a machine learning algorithm to tomographically “learn” which settings implement the members of a universal gate set. At optimum, arbitrary quantum gates, and thus arbitrary quantum programs, can be implemented using the stuff. |
| Tasks | |
| Published | 2019-11-29 |
| URL | https://arxiv.org/abs/1911.13282v1 |
| https://arxiv.org/pdf/1911.13282v1.pdf | |
| PWC | https://paperswithcode.com/paper/quantum-computation-with-machine-learning |
| Repo | |
| Framework | |
Regularizing Model-Based Planning with Energy-Based Models
| Title | Regularizing Model-Based Planning with Energy-Based Models |
| Authors | Rinu Boney, Juho Kannala, Alexander Ilin |
| Abstract | Model-based reinforcement learning could enable sample-efficient learning by quickly acquiring rich knowledge about the world and using it to improve behaviour without additional data. Learned dynamics models can be directly used for planning actions but this has been challenging because of inaccuracies in the learned models. In this paper, we focus on planning with learned dynamics models and propose to regularize it using energy estimates of state transitions in the environment. We visually demonstrate the effectiveness of the proposed method and show that off-policy training of an energy estimator can be effectively used to regularize planning with pre-trained dynamics models. Further, we demonstrate that the proposed method enables sample-efficient learning to achieve competitive performance in challenging continuous control tasks such as Half-cheetah and Ant in just a few minutes of experience. |
| Tasks | Continuous Control |
| Published | 2019-10-12 |
| URL | https://arxiv.org/abs/1910.05527v1 |
| https://arxiv.org/pdf/1910.05527v1.pdf | |
| PWC | https://paperswithcode.com/paper/regularizing-model-based-planning-with-energy |
| Repo | |
| Framework | |
Neural Machine Translation for Cebuano to Tagalog with Subword Unit Translation
| Title | Neural Machine Translation for Cebuano to Tagalog with Subword Unit Translation |
| Authors | Kristine Mae M. Adlaon, Nelson Marcos |
| Abstract | The Philippines is an archipelago composed of 7, 641 different islands with more than 150 different languages. This linguistic differences and diversity, though may be seen as a beautiful feature, have contributed to the difficulty in the promotion of educational and cultural development of different domains in the country. An effective machine translation system solely dedicated to cater Philippine languages will surely help bridge this gap. In this research work, a never before applied approach for language translation to a Philippine language was used for a Cebuano to Tagalog translator. A Recurrent Neural Network was used to implement the translator using OpenNMT sequence modeling tool in TensorFlow. The performance of the translation was evaluated using the BLEU Score metric. For the Cebuano to Tagalog translation, BLEU produced a score of 20.01. A subword unit translation for verbs and copyable approach was performed where commonly seen mistranslated words from the source to the target were corrected. The BLEU score increased to 22.87. Though slightly higher, this score still indicates that the translation is somehow understandable but is not yet considered as a good translation. |
| Tasks | Machine Translation |
| Published | 2019-02-10 |
| URL | http://arxiv.org/abs/1902.07250v1 |
| http://arxiv.org/pdf/1902.07250v1.pdf | |
| PWC | https://paperswithcode.com/paper/neural-machine-translation-for-cebuano-to |
| Repo | |
| Framework | |
AI-optimized detector design for the future Electron-Ion Collider: the dual-radiator RICH case
| Title | AI-optimized detector design for the future Electron-Ion Collider: the dual-radiator RICH case |
| Authors | E. Cisbani, A. Del Dotto, C. Fanelli, M. Williams, M. Alfred, F. Barbosa, L. Barion, V. Berdnikov, W. Brooks, T. Cao, M. Contalbrigo, S. Danagoulian, A. Datta, M. Demarteau, A. Denisov, M. Diefenthaler, A. Durum, D. Fields, Y. Furletova, C. Gleason, M. Grosse-Perdekamp, M. Hattawy, X. He, H. van Hecke, D. Higinbotham, T. Horn, C. Hyde, Y. Ilieva, G. Kalicy, A. Kebede, B. Kim, M. Liu, J. McKisson, R. Mendez, P. Nadel-Turonski, I. Pegg, D. Romanov, M. Sarsour, C. L. da Silva, J. Stevens, X. Sun, S. Syed, R. Towell, J. Xie, Z. W. Zhao, B. Zihlmann, C. Zorn |
| Abstract | Advanced detector R&D requires performing computationally intensive and detailed simulations as part of the detector-design optimization process. We propose a general approach to this process based on Bayesian optimization and machine learning that encodes detector requirements. As a case study, we focus on the design of the dual-radiator Ring Imaging Cherenkov (dRICH) detector under development as part of the particle-identification system at the future Electron-Ion Collider (EIC). The EIC is a US-led frontier accelerator project for nuclear physics, which has been proposed to further explore the structure and interactions of nuclear matter at the scale of sea quarks and gluons. We show that the detector design obtained with our automated and highly parallelized framework outperforms the baseline dRICH design. Our approach can be applied to any detector R&D, provided that realistic simulations are available. |
| Tasks | |
| Published | 2019-11-13 |
| URL | https://arxiv.org/abs/1911.05797v1 |
| https://arxiv.org/pdf/1911.05797v1.pdf | |
| PWC | https://paperswithcode.com/paper/ai-optimized-detector-design-for-the-future |
| Repo | |
| Framework | |
Robust Logistic Regression against Attribute and Label Outliers via Restricted Minimum Error Entropy Criterion
| Title | Robust Logistic Regression against Attribute and Label Outliers via Restricted Minimum Error Entropy Criterion |
| Authors | Yuanhao Li, Badong Chen, Natsue Yoshimura, Yasuharu Koike |
| Abstract | Minimum Error Entropy (MEE) criterion has been verified as a powerful approach for robust learning in the field of Information Theoretic Learning. The purpose of this study is to demonstrate the great potential of MEE in robust classification, which is a relative vacancy in the literature. Based on the logistic regression model, we analyze the optimal error distribution with outliers, and implement restriction with a specially designed quantization codebook to avoid possible failure caused by the original MEE. The performance of the restricted MEE based logistic regression, called LR-RMEE, is experimentally evaluated on toy examples and public datasets. The results demonstrate that the novel robust variant can outperform existing methods in most cases. Moreover, the proposed restricted MEE criterion can be applied to other classifiers for corresponding robust variants, revealing desirable effectiveness and generality. |
| Tasks | Dimensionality Reduction, Quantization |
| Published | 2019-09-06 |
| URL | https://arxiv.org/abs/1909.02707v3 |
| https://arxiv.org/pdf/1909.02707v3.pdf | |
| PWC | https://paperswithcode.com/paper/robust-logistic-regression-against-attribute |
| Repo | |
| Framework | |
Fusing Vector Space Models for Domain-Specific Applications
| Title | Fusing Vector Space Models for Domain-Specific Applications |
| Authors | Laura Rettig, Julien Audiffren, Philippe Cudré-Mauroux |
| Abstract | We address the problem of tuning word embeddings for specific use cases and domains. We propose a new method that automatically combines multiple domain-specific embeddings, selected from a wide range of pre-trained domain-specific embeddings, to improve their combined expressive power. Our approach relies on two key components: 1) a ranking function, based on a new embedding similarity measure, that selects the most relevant embeddings to use given a domain and 2) a dimensionality reduction method that combines the selected embeddings to produce a more compact and efficient encoding that preserves the expressiveness. We empirically show that our method produces effective domain-specific embeddings that consistently improve the performance of state-of-the-art machine learning algorithms on multiple tasks, compared to generic embeddings trained on large text corpora. |
| Tasks | Dimensionality Reduction, Word Embeddings |
| Published | 2019-09-05 |
| URL | https://arxiv.org/abs/1909.02307v1 |
| https://arxiv.org/pdf/1909.02307v1.pdf | |
| PWC | https://paperswithcode.com/paper/fusing-vector-space-models-for-domain |
| Repo | |
| Framework | |
Engaging in Dialogue about an Agent’s Norms and Behaviors
| Title | Engaging in Dialogue about an Agent’s Norms and Behaviors |
| Authors | Daniel Kasenberg, Antonio Roque, Ravenna Thielstrom, Matthias Scheutz |
| Abstract | We present a set of capabilities allowing an agent planning with moral and social norms represented in temporal logic to respond to queries about its norms and behaviors in natural language, and for the human user to add and remove norms directly in natural language. The user may also pose hypothetical modifications to the agent’s norms and inquire about their effects. |
| Tasks | |
| Published | 2019-11-01 |
| URL | https://arxiv.org/abs/1911.00229v1 |
| https://arxiv.org/pdf/1911.00229v1.pdf | |
| PWC | https://paperswithcode.com/paper/engaging-in-dialogue-about-an-agents-norms |
| Repo | |
| Framework | |
Inverse Graph Learning over Optimization Networks
| Title | Inverse Graph Learning over Optimization Networks |
| Authors | Vincenzo Matta, Augusto Santos, Ali H. Sayed |
| Abstract | Many inferential and learning tasks can be accomplished efficiently by means of distributed optimization algorithms where the network topology plays a critical role in driving the local interactions among neighboring agents. There is a large body of literature examining the effect of the graph structure on the performance of optimization strategies. In this article, we examine the inverse problem and consider the reverse question: How much information does observing the behavior at the nodes convey about the underlying network structure used for optimization? Over large-scale networks, the difficulty of addressing such inverse questions (or problems) is compounded by the fact that usually only a limited portion of nodes can be probed, giving rise to a second important question: Despite the presence of several unobserved nodes, are partial and local observations still sufficient to discover the graph linking the probed nodes? The article surveys recent advances on this inverse learning problem and related questions. Examples of applications are provided to illustrate how the interplay between graph learning and distributed optimization arises in practice, e.g., in cognitive engineered systems such as distributed detection, or in other real-world problems such as the mechanism of opinion formation over social networks and the mechanism of coordination in biological networks. A unifying framework for examining the reconstruction error will be described, which allows to devise and examine various estimation strategies enabling successful graph learning. The relevance of specific network attributes, such as sparsity versus density of connections, and node degree concentration, is discussed in relation to the topology inference goal. It is shown how universal (i.e., data-driven) clustering algorithms can be exploited to solve the graph learning problem. |
| Tasks | Distributed Optimization |
| Published | 2019-12-18 |
| URL | https://arxiv.org/abs/1912.08465v1 |
| https://arxiv.org/pdf/1912.08465v1.pdf | |
| PWC | https://paperswithcode.com/paper/inverse-graph-learning-over-optimization |
| Repo | |
| Framework | |
Image Matters: Scalable Detection of Offensive and Non-Compliant Content / Logo in Product Images
| Title | Image Matters: Scalable Detection of Offensive and Non-Compliant Content / Logo in Product Images |
| Authors | Shreyansh Gandhi, Samrat Kokkula, Abon Chaudhuri, Alessandro Magnani, Theban Stanley, Behzad Ahmadi, Venkatesh Kandaswamy, Omer Ovenc, Shie Mannor |
| Abstract | In e-commerce, product content, especially product images have a significant influence on a customer’s journey from product discovery to evaluation and finally, purchase decision. Since many e-commerce retailers sell items from other third-party marketplace sellers besides their own, the content published by both internal and external content creators needs to be monitored and enriched, wherever possible. Despite guidelines and warnings, product listings that contain offensive and non-compliant images continue to enter catalogs. Offensive and non-compliant content can include a wide range of objects, logos, and banners conveying violent, sexually explicit, racist, or promotional messages. Such images can severely damage the customer experience, lead to legal issues, and erode the company brand. In this paper, we present a computer vision driven offensive and non-compliant image detection system for extremely large image datasets. This paper delves into the unique challenges of applying deep learning to real-world product image data from retail world. We demonstrate how we resolve a number of technical challenges such as lack of training data, severe class imbalance, fine-grained class definitions etc. using a number of practical yet unique technical strategies. Our system combines state-of-the-art image classification and object detection techniques with budgeted crowdsourcing to develop a solution customized for a massive, diverse, and constantly evolving product catalog. |
| Tasks | Image Classification, Object Detection |
| Published | 2019-05-06 |
| URL | https://arxiv.org/abs/1905.02234v2 |
| https://arxiv.org/pdf/1905.02234v2.pdf | |
| PWC | https://paperswithcode.com/paper/image-matters-detecting-offensive-and-non |
| Repo | |
| Framework | |
In Situ Cane Toad Recognition
| Title | In Situ Cane Toad Recognition |
| Authors | Dmitry A. Konovalov, Simindokht Jahangard, Lin Schwarzkopf |
| Abstract | Cane toads are invasive, toxic to native predators, compete with native insectivores, and have a devastating impact on Australian ecosystems, prompting the Australian government to list toads as a key threatening process under the Environment Protection and Biodiversity Conservation Act 1999. Mechanical cane toad traps could be made more native-fauna friendly if they could distinguish invasive cane toads from native species. Here we designed and trained a Convolution Neural Network (CNN) starting from the Xception CNN. The XToadGmp toad-recognition CNN we developed was trained end-to-end using heat-map Gaussian targets. After training, XToadGmp required minimum image pre/post-processing and when tested on 720x1280 shaped images, it achieved 97.1% classification accuracy on 1863 toad and 2892 not-toad test images, which were not used in training. |
| Tasks | |
| Published | 2019-06-09 |
| URL | https://arxiv.org/abs/1906.03547v2 |
| https://arxiv.org/pdf/1906.03547v2.pdf | |
| PWC | https://paperswithcode.com/paper/in-situ-cane-toad-recognition |
| Repo | |
| Framework | |
A Distributed Quasi-Newton Algorithm for Primal and Dual Regularized Empirical Risk Minimization
| Title | A Distributed Quasi-Newton Algorithm for Primal and Dual Regularized Empirical Risk Minimization |
| Authors | Ching-pei Lee, Cong Han Lim, Stephen J. Wright |
| Abstract | We propose a communication- and computation-efficient distributed optimization algorithm using second-order information for solving empirical risk minimization (ERM) problems with a nonsmooth regularization term. Our algorithm is applicable to both the primal and the dual ERM problem. Current second-order and quasi-Newton methods for this problem either do not work well in the distributed setting or work only for specific regularizers. Our algorithm uses successive quadratic approximations of the smooth part, and we describe how to maintain an approximation of the (generalized) Hessian and solve subproblems efficiently in a distributed manner. When applied to the distributed dual ERM problem, unlike state of the art that takes only the block-diagonal part of the Hessian, our approach is able to utilize global curvature information and is thus magnitudes faster. The proposed method enjoys global linear convergence for a broad range of non-strongly convex problems that includes the most commonly used ERMs, thus requiring lower communication complexity. It also converges on non-convex problems, so has the potential to be used on applications such as deep learning. Computational results demonstrate that our method significantly improves on communication cost and running time over the current state-of-the-art methods. |
| Tasks | Distributed Optimization |
| Published | 2019-12-12 |
| URL | https://arxiv.org/abs/1912.06508v1 |
| https://arxiv.org/pdf/1912.06508v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-distributed-quasi-newton-algorithm-for-1 |
| Repo | |
| Framework | |
