May 6, 2019

3430 words 17 mins read

Paper Group ANR 248

Building a Fine-Grained Entity Typing System Overnight for a New X (X = Language, Domain, Genre). Mapping the Similarities of Spectra: Global and Locally-biased Approaches to SDSS Galaxy Data. Hierarchical Bayesian Noise Inference for Robust Real-time Probabilistic Object Classification. Hardware Acceleration for Boolean Satisfiability Solver by Ap …

Building a Fine-Grained Entity Typing System Overnight for a New X (X = Language, Domain, Genre)


Title	Building a Fine-Grained Entity Typing System Overnight for a New X (X = Language, Domain, Genre)
Authors	Lifu Huang, Jonathan May, Xiaoman Pan, Heng Ji
Abstract	Recent research has shown great progress on fine-grained entity typing. Most existing methods require pre-defining a set of types and training a multi-class classifier from a large labeled data set based on multi-level linguistic features. They are thus limited to certain domains, genres and languages. In this paper, we propose a novel unsupervised entity typing framework by combining symbolic and distributional semantics. We start from learning general embeddings for each entity mention, compose the embeddings of specific contexts using linguistic structures, link the mention to knowledge bases and learn its related knowledge representations. Then we develop a novel joint hierarchical clustering and linking algorithm to type all mentions using these representations. This framework doesn’t rely on any annotated data, predefined typing schema, or hand-crafted features, therefore it can be quickly adapted to a new domain, genre and language. Furthermore, it has great flexibility at incorporating linguistic structures (e.g., Abstract Meaning Representation (AMR), dependency relations) to improve specific context representation. Experiments on genres (news and discussion forum) show comparable performance with state-of-the-art supervised typing systems trained from a large amount of labeled data. Results on various languages (English, Chinese, Japanese, Hausa, and Yoruba) and domains (general and biomedical) demonstrate the portability of our framework.
Tasks	Entity Typing
Published	2016-03-10
URL	http://arxiv.org/abs/1603.03112v1
PDF	http://arxiv.org/pdf/1603.03112v1.pdf
PWC	https://paperswithcode.com/paper/building-a-fine-grained-entity-typing-system
Repo
Framework

Mapping the Similarities of Spectra: Global and Locally-biased Approaches to SDSS Galaxy Data


Title	Mapping the Similarities of Spectra: Global and Locally-biased Approaches to SDSS Galaxy Data
Authors	David Lawlor, Tamás Budavári, Michael W. Mahoney
Abstract	We apply a novel spectral graph technique, that of locally-biased semi-supervised eigenvectors, to study the diversity of galaxies. This technique permits us to characterize empirically the natural variations in observed spectra data, and we illustrate how this approach can be used in an exploratory manner to highlight both large-scale global as well as small-scale local structure in Sloan Digital Sky Survey (SDSS) data. We use this method in a way that simultaneously takes into account the measurements of spectral lines as well as the continuum shape. Unlike Principal Component Analysis, this method does not assume that the Euclidean distance between galaxy spectra is a good global measure of similarity between all spectra, but instead it only assumes that local difference information between similar spectra is reliable. Moreover, unlike other nonlinear dimensionality methods, this method can be used to characterize very finely both small-scale local as well as large-scale global properties of realistic noisy data. The power of the method is demonstrated on the SDSS Main Galaxy Sample by illustrating that the derived embeddings of spectra carry an unprecedented amount of information. By using a straightforward global or unsupervised variant, we observe that the main features correlate strongly with star formation rate and that they clearly separate active galactic nuclei. Computed parameters of the method can be used to describe line strengths and their interdependencies. By using a locally-biased or semi-supervised variant, we are able to focus on typical variations around specific objects of astronomical interest. We present several examples illustrating that this approach can enable new discoveries in the data as well as a detailed understanding of very fine local structure that would otherwise be overwhelmed by large-scale noise and global trends in the data.
Tasks
Published	2016-09-13
URL	http://arxiv.org/abs/1609.03932v1
PDF	http://arxiv.org/pdf/1609.03932v1.pdf
PWC	https://paperswithcode.com/paper/mapping-the-similarities-of-spectra-global
Repo
Framework

Hierarchical Bayesian Noise Inference for Robust Real-time Probabilistic Object Classification


Title	Hierarchical Bayesian Noise Inference for Robust Real-time Probabilistic Object Classification
Authors	Shayegan Omidshafiei, Brett T. Lopez, Jonathan P. How, John Vian
Abstract	Robust environment perception is essential for decision-making on robots operating in complex domains. Principled treatment of uncertainty sources in a robot’s observation model is necessary for accurate mapping and object detection. This is important not only for low-level observations (e.g., accelerometer data), but for high-level observations such as semantic object labels as well. This paper presents an approach for filtering sequences of object classification probabilities using online modeling of the noise characteristics of the classifier outputs. A hierarchical Bayesian approach is used to model per-class noise distributions, while simultaneously allowing sharing of high-level noise characteristics between classes. The proposed filtering scheme, called Hierarchical Bayesian Noise Inference (HBNI), is shown to outperform classification accuracy of existing methods. The paper also presents real-time filtered classification hardware experiments running fully onboard a moving quadrotor, where the proposed approach is demonstrated to work in a challenging domain where noise-agnostic filtering fails.
Tasks	Decision Making, Object Classification, Object Detection
Published	2016-05-03
URL	http://arxiv.org/abs/1605.01042v2
PDF	http://arxiv.org/pdf/1605.01042v2.pdf
PWC	https://paperswithcode.com/paper/hierarchical-bayesian-noise-inference-for
Repo
Framework

Hardware Acceleration for Boolean Satisfiability Solver by Applying Belief Propagation Algorithm


Title	Hardware Acceleration for Boolean Satisfiability Solver by Applying Belief Propagation Algorithm
Authors	Te-Hsuan Chen, Ju-Yi Lu
Abstract	Boolean satisfiability (SAT) has an extensive application domain in computer science, especially in electronic design automation applications. Circuit synthesis, optimization, and verification problems can be solved by transforming original problems to SAT problems. However, the SAT problem is known as NP-complete, which means there is no efficient method to solve it. Therefore, an efficient SAT solver to enhance the performance is always desired. We propose a hardware acceleration method for SAT problems. By surveying the properties of SAT problems and the decoding of low-density parity-check (LDPC) codes, a special class of error-correcting codes, we discover that both of them are constraint satisfaction problems. The belief propagation algorithm has been successfully applied to the decoding of LDPC, and the corresponding decoder hardware designs are extensively studied. Therefore, we proposed a belief propagation based algorithm to solve SAT problems. With this algorithm, the SAT solver can be accelerated by hardware. A software simulator is implemented to verify the proposed algorithm and the performance improvement is estimated. Our experiment results show that time complexity does not increase with the size of SAT problems and the proposed method can achieve at least 30x speedup compared to MiniSat.
Tasks
Published	2016-03-16
URL	http://arxiv.org/abs/1603.05314v1
PDF	http://arxiv.org/pdf/1603.05314v1.pdf
PWC	https://paperswithcode.com/paper/hardware-acceleration-for-boolean
Repo
Framework

Attribute Extraction from Product Titles in eCommerce


Title	Attribute Extraction from Product Titles in eCommerce
Authors	Ajinkya More
Abstract	This paper presents a named entity extraction system for detecting attributes in product titles of eCommerce retailers like Walmart. The absence of syntactic structure in such short pieces of text makes extracting attribute values a challenging problem. We find that combining sequence labeling algorithms such as Conditional Random Fields and Structured Perceptron with a curated normalization scheme produces an effective system for the task of extracting product attribute values from titles. To keep the discussion concrete, we will illustrate the mechanics of the system from the point of view of a particular attribute - brand. We also discuss the importance of an attribute extraction system in the context of retail websites with large product catalogs, compare our approach to other potential approaches to this problem and end the paper with a discussion of the performance of our system for extracting attributes.
Tasks	Entity Extraction
Published	2016-08-15
URL	http://arxiv.org/abs/1608.04670v1
PDF	http://arxiv.org/pdf/1608.04670v1.pdf
PWC	https://paperswithcode.com/paper/attribute-extraction-from-product-titles-in
Repo
Framework

On the Theoretical Capacity of Evolution Strategies to Statistically Learn the Landscape Hessian


Title	On the Theoretical Capacity of Evolution Strategies to Statistically Learn the Landscape Hessian
Authors	Ofer M. Shir, Jonathan Roslund, Amir Yehudayoff
Abstract	We study the theoretical capacity to statistically learn local landscape information by Evolution Strategies (ESs). Specifically, we investigate the covariance matrix when constructed by ESs operating with the selection operator alone. We model continuous generation of candidate solutions about quadratic basins of attraction, with deterministic selection of the decision vectors that minimize the objective function values. Our goal is to rigorously show that accumulation of winning individuals carries the potential to reveal valuable information about the search landscape, e.g., as already practically utilized by derandomized ES variants. We first show that the statistically-constructed covariance matrix over such winning decision vectors shares the same eigenvectors with the Hessian matrix about the optimum. We then provide an analytic approximation of this covariance matrix for a non-elitist multi-child $(1,\lambda)$-strategy, which holds for a large population size $\lambda$. Finally, we also numerically corroborate our results.
Tasks
Published	2016-06-23
URL	http://arxiv.org/abs/1606.07262v1
PDF	http://arxiv.org/pdf/1606.07262v1.pdf
PWC	https://paperswithcode.com/paper/on-the-theoretical-capacity-of-evolution
Repo
Framework

Improving historical spelling normalization with bi-directional LSTMs and multi-task learning


Title	Improving historical spelling normalization with bi-directional LSTMs and multi-task learning
Authors	Marcel Bollmann, Anders Søgaard
Abstract	Natural-language processing of historical documents is complicated by the abundance of variant spellings and lack of annotated data. A common approach is to normalize the spelling of historical words to modern forms. We explore the suitability of a deep neural network architecture for this task, particularly a deep bi-LSTM network applied on a character level. Our model compares well to previously established normalization algorithms when evaluated on a diverse set of texts from Early New High German. We show that multi-task learning with additional normalization data can improve our model’s performance further.
Tasks	Multi-Task Learning
Published	2016-10-25
URL	http://arxiv.org/abs/1610.07844v1
PDF	http://arxiv.org/pdf/1610.07844v1.pdf
PWC	https://paperswithcode.com/paper/improving-historical-spelling-normalization
Repo
Framework

Dense Captioning with Joint Inference and Visual Context


Title	Dense Captioning with Joint Inference and Visual Context
Authors	Linjie Yang, Kevin Tang, Jianchao Yang, Li-Jia Li
Abstract	Dense captioning is a newly emerging computer vision topic for understanding images with dense language descriptions. The goal is to densely detect visual concepts (e.g., objects, object parts, and interactions between them) from images, labeling each with a short descriptive phrase. We identify two key challenges of dense captioning that need to be properly addressed when tackling the problem. First, dense visual concept annotations in each image are associated with highly overlapping target regions, making accurate localization of each visual concept challenging. Second, the large amount of visual concepts makes it hard to recognize each of them by appearance alone. We propose a new model pipeline based on two novel ideas, joint inference and context fusion, to alleviate these two challenges. We design our model architecture in a methodical manner and thoroughly evaluate the variations in architecture. Our final model, compact and efficient, achieves state-of-the-art accuracy on Visual Genome for dense captioning with a relative gain of 73% compared to the previous best algorithm. Qualitative experiments also reveal the semantic capabilities of our model in dense captioning.
Tasks
Published	2016-11-21
URL	http://arxiv.org/abs/1611.06949v2
PDF	http://arxiv.org/pdf/1611.06949v2.pdf
PWC	https://paperswithcode.com/paper/dense-captioning-with-joint-inference-and
Repo
Framework

Scalable Algorithms for Tractable Schatten Quasi-Norm Minimization


Title	Scalable Algorithms for Tractable Schatten Quasi-Norm Minimization
Authors	Fanhua Shang, Yuanyuan Liu, James Cheng
Abstract	The Schatten-p quasi-norm $(0<p<1)$ is usually used to replace the standard nuclear norm in order to approximate the rank function more accurately. However, existing Schatten-p quasi-norm minimization algorithms involve singular value decomposition (SVD) or eigenvalue decomposition (EVD) in each iteration, and thus may become very slow and impractical for large-scale problems. In this paper, we first define two tractable Schatten quasi-norms, i.e., the Frobenius/nuclear hybrid and bi-nuclear quasi-norms, and then prove that they are in essence the Schatten-2/3 and 1/2 quasi-norms, respectively, which lead to the design of very efficient algorithms that only need to update two much smaller factor matrices. We also design two efficient proximal alternating linearized minimization algorithms for solving representative matrix completion problems. Finally, we provide the global convergence and performance guarantees for our algorithms, which have better convergence properties than existing algorithms. Experimental results on synthetic and real-world data show that our algorithms are more accurate than the state-of-the-art methods, and are orders of magnitude faster.
Tasks	Matrix Completion
Published	2016-06-04
URL	http://arxiv.org/abs/1606.01245v1
PDF	http://arxiv.org/pdf/1606.01245v1.pdf
PWC	https://paperswithcode.com/paper/scalable-algorithms-for-tractable-schatten
Repo
Framework

Joint Target Detection and Tracking in Multipath Environment: A Variational Bayesian Approach


Title	Joint Target Detection and Tracking in Multipath Environment: A Variational Bayesian Approach
Authors	Hua Lan, Shuai Sun, Zengfu Wang, Quan Pan, Zhishan Zhang
Abstract	We consider multitarget detection and tracking problem for a class of multipath detection system where one target may generate multiple measurements via multiple propagation paths, and the association relationship among targets, measurements and propagation paths is unknown. In order to effectively utilize multipath measurements from one target to improve detection and tracking performance, a tracker has to handle high-dimensional estimation of latent variables including target active/dormant meta-state, target kinematic state, and multipath data association. Based on variational Bayesian inference, we propose a novel joint detection and tracking algorithm that incorporates multipath data association, target detection and target state estimation in a unified Bayesian framework. The posterior probabilities of these latent variables are derived in a closed-form iterative manner, which is effective for reducing the performance deterioration caused by the coupling between estimation errors and identification errors. Loopy belief propagation is exploited to approximately calculate the probability of multipath data association, saving the computational cost significantly. Simulation results of over-the-horizon radar multitarget tracking show that the proposed algorithm outperforms multihypothesis multipath track fusion and multi-detection (hypothesis-oriented) multiple hypothesis tracker, especially under low signal-to-noise ratio circumstance.
Tasks	Bayesian Inference
Published	2016-10-27
URL	http://arxiv.org/abs/1610.08616v2
PDF	http://arxiv.org/pdf/1610.08616v2.pdf
PWC	https://paperswithcode.com/paper/joint-target-detection-and-tracking-in
Repo
Framework

Data Science in Service of Performing Arts: Applying Machine Learning to Predicting Audience Preferences


Title	Data Science in Service of Performing Arts: Applying Machine Learning to Predicting Audience Preferences
Authors	Jacob Abernethy, Cyrus Anderson, Alex Chojnacki, Chengyu Dai, John Dryden, Eric Schwartz, Wenbo Shen, Jonathan Stroud, Laura Wendlandt, Sheng Yang, Daniel Zhang
Abstract	Performing arts organizations aim to enrich their communities through the arts. To do this, they strive to match their performance offerings to the taste of those communities. Success relies on understanding audience preference and predicting their behavior. Similar to most e-commerce or digital entertainment firms, arts presenters need to recommend the right performance to the right customer at the right time. As part of the Michigan Data Science Team (MDST), we partnered with the University Musical Society (UMS), a non-profit performing arts presenter housed in the University of Michigan, Ann Arbor. We are providing UMS with analysis and business intelligence, utilizing historical individual-level sales data. We built a recommendation system based on collaborative filtering, gaining insights into the artistic preferences of customers, along with the similarities between performances. To better understand audience behavior, we used statistical methods from customer-base analysis. We characterized customer heterogeneity via segmentation, and we modeled customer cohorts to understand and predict ticket purchasing patterns. Finally, we combined statistical modeling with natural language processing (NLP) to explore the impact of wording in program descriptions. These ongoing efforts provide a platform to launch targeted marketing campaigns, helping UMS carry out its mission by allocating its resources more efficiently. Celebrating its 138th season, UMS is a 2014 recipient of the National Medal of Arts, and it continues to enrich communities by connecting world-renowned artists with diverse audiences, especially students in their formative years. We aim to contribute to that mission through data science and customer analytics.
Tasks
Published	2016-09-30
URL	http://arxiv.org/abs/1611.05788v1
PDF	http://arxiv.org/pdf/1611.05788v1.pdf
PWC	https://paperswithcode.com/paper/data-science-in-service-of-performing-arts
Repo
Framework

Low-Complexity Stochastic Generalized Belief Propagation


Title	Low-Complexity Stochastic Generalized Belief Propagation
Authors	Farzin Haddadpour, Mahdi Jafari Siavoshani, Morteza Noshad
Abstract	The generalized belief propagation (GBP), introduced by Yedidia et al., is an extension of the belief propagation (BP) algorithm, which is widely used in different problems involved in calculating exact or approximate marginals of probability distributions. In many problems, it has been observed that the accuracy of GBP considerably outperforms that of BP. However, because in general the computational complexity of GBP is higher than BP, its application is limited in practice. In this paper, we introduce a stochastic version of GBP called stochastic generalized belief propagation (SGBP) that can be considered as an extension to the stochastic BP (SBP) algorithm introduced by Noorshams et al. They have shown that SBP reduces the complexity per iteration of BP by an order of magnitude in alphabet size. In contrast to SBP, SGBP can reduce the computation complexity if certain topological conditions are met by the region graph associated to a graphical model. However, this reduction can be larger than only one order of magnitude in alphabet size. In this paper, we characterize these conditions and the amount of computation gain that we can obtain by using SGBP. Finally, using similar proof techniques employed by Noorshams et al., for general graphical models satisfy contraction conditions, we prove the asymptotic convergence of SGBP to the unique GBP fixed point, as well as providing non-asymptotic upper bounds on the mean square error and on the high probability error.
Tasks
Published	2016-05-06
URL	http://arxiv.org/abs/1605.02046v1
PDF	http://arxiv.org/pdf/1605.02046v1.pdf
PWC	https://paperswithcode.com/paper/low-complexity-stochastic-generalized-belief
Repo
Framework

Parallel Bayesian Global Optimization of Expensive Functions


Title	Parallel Bayesian Global Optimization of Expensive Functions
Authors	Jialei Wang, Scott C. Clark, Eric Liu, Peter I. Frazier
Abstract	We consider parallel global optimization of derivative-free expensive-to-evaluate functions, and propose an efficient method based on stochastic approximation for implementing a conceptual Bayesian optimization algorithm proposed by Ginsbourger et al. (2007). At the heart of this algorithm is maximizing the information criterion called the “multi-points expected improvement’', or the q-EI. To accomplish this, we use infinitessimal perturbation analysis (IPA) to construct a stochastic gradient estimator and show that this estimator is unbiased. We also show that the stochastic gradient ascent algorithm using the constructed gradient estimator converges to a stationary point of the q-EI surface, and therefore, as the number of multiple starts of the gradient ascent algorithm and the number of steps for each start grow large, the one-step Bayes optimal set of points is recovered. We show in numerical experiments that our method for maximizing the q-EI is faster than methods based on closed-form evaluation using high-dimensional integration, when considering many parallel function evaluations, and is comparable in speed when considering few. We also show that the resulting one-step Bayes optimal algorithm for parallel global optimization finds high-quality solutions with fewer evaluations than a heuristic based on approximately maximizing the q-EI. A high-quality open source implementation of this algorithm is available in the open source Metrics Optimization Engine (MOE).
Tasks
Published	2016-02-16
URL	https://arxiv.org/abs/1602.05149v4
PDF	https://arxiv.org/pdf/1602.05149v4.pdf
PWC	https://paperswithcode.com/paper/parallel-bayesian-global-optimization-of
Repo
Framework

GTApprox: surrogate modeling for industrial design


Title	GTApprox: surrogate modeling for industrial design
Authors	Mikhail Belyaev, Evgeny Burnaev, Ermek Kapushev, Maxim Panov, Pavel Prikhodko, Dmitry Vetrov, Dmitry Yarotsky
Abstract	We describe GTApprox - a new tool for medium-scale surrogate modeling in industrial design. Compared to existing software, GTApprox brings several innovations: a few novel approximation algorithms, several advanced methods of automated model selection, novel options in the form of hints. We demonstrate the efficiency of GTApprox on a large collection of test problems. In addition, we describe several applications of GTApprox to real engineering problems.
Tasks	Model Selection
Published	2016-09-05
URL	http://arxiv.org/abs/1609.01088v1
PDF	http://arxiv.org/pdf/1609.01088v1.pdf
PWC	https://paperswithcode.com/paper/gtapprox-surrogate-modeling-for-industrial
Repo
Framework

Acquisition of Visual Features Through Probabilistic Spike-Timing-Dependent Plasticity


Title	Acquisition of Visual Features Through Probabilistic Spike-Timing-Dependent Plasticity
Authors	Amirhossein Tavanaei, Timothee Masquelier, Anthony S Maida
Abstract	The final version of this paper has been published in IEEEXplore available at http://ieeexplore.ieee.org/document/7727213. Please cite this paper as: Amirhossein Tavanaei, Timothee Masquelier, and Anthony Maida, Acquisition of visual features through probabilistic spike-timing-dependent plasticity. IEEE International Joint Conference on Neural Networks. pp. 307-314, IJCNN 2016. This paper explores modifications to a feedforward five-layer spiking convolutional network (SCN) of the ventral visual stream [Masquelier, T., Thorpe, S., Unsupervised learning of visual features through spike timing dependent plasticity. PLoS Computational Biology, 3(2), 247-257]. The original model showed that a spike-timing-dependent plasticity (STDP) learning algorithm embedded in an appropriately selected SCN could perform unsupervised feature discovery. The discovered features where interpretable and could effectively be used to perform rapid binary decisions in a classifier. In order to study the robustness of the previous results, the present research examines the effects of modifying some of the components of the original model. For improved biological realism, we replace the original non-leaky integrate-and-fire neurons with Izhikevich-like neurons. We also replace the original STDP rule with a novel rule that has a probabilistic interpretation. The probabilistic STDP slightly but significantly improves the performance for both types of model neurons. Use of the Izhikevich-like neuron was not found to improve performance although performance was still comparable to the IF neuron. This shows that the model is robust enough to handle more biologically realistic neurons. We also conclude that the underlying reasons for stable performance in the model are preserved despite the overt changes to the explicit components of the model.
Tasks
Published	2016-06-03
URL	http://arxiv.org/abs/1606.01102v2
PDF	http://arxiv.org/pdf/1606.01102v2.pdf
PWC	https://paperswithcode.com/paper/acquisition-of-visual-features-through
Repo
Framework