Paper Group ANR 450
Diversified Top-k Partial MaxSAT Solving. Distributed Vector Representation Of Shopping Items, The Customer And Shopping Cart To Build A Three Fold Recommendation System. SILVar: Single Index Latent Variable Models. Quaternion Based Camera Pose Estimation From Matched Feature Points. FWDA: a Fast Wishart Discriminant Analysis with its Application t …
Diversified Top-k Partial MaxSAT Solving
| Title | Diversified Top-k Partial MaxSAT Solving |
| Authors | Junping Zhou, Huanyao Sun, Feifei Ma, Jian Gao, Ke Xu, Minghao Yin |
| Abstract | We introduce a diversified top-k partial MaxSAT problem, a combination of partial MaxSAT problem and enumeration problem. Given a partial MaxSAT formula F and a positive integer k, the diversified top-k partial MaxSAT is to find k maximal solutions for F such that the k maximal solutions satisfy the maximum number of soft clauses of F. This problem can be widely used in many applications including community detection, sensor place, motif discovery, and combinatorial testing. We prove the problem is NP-hard and propose an approach for solving the problem. The concrete idea of the approach is to design an encoding EE which reduces diversified top-k partial MaxSAT problem into partial MaxSAT problem, and then solve the resulting problem with state-of-art solvers. In addition, we present an algorithm MEMKC exactly solving the diversified top-k partial MaxSAT. Through several experiments we show that our approach can be successfully applied to the interesting problem. |
| Tasks | Community Detection |
| Published | 2017-05-31 |
| URL | http://arxiv.org/abs/1706.00123v1 |
| http://arxiv.org/pdf/1706.00123v1.pdf | |
| PWC | https://paperswithcode.com/paper/diversified-top-k-partial-maxsat-solving |
| Repo | |
| Framework | |
Distributed Vector Representation Of Shopping Items, The Customer And Shopping Cart To Build A Three Fold Recommendation System
| Title | Distributed Vector Representation Of Shopping Items, The Customer And Shopping Cart To Build A Three Fold Recommendation System |
| Authors | Bibek Behera, Manoj Joshi, Abhilash KK, Mohammad Ansari Ismail |
| Abstract | The main idea of this paper is to represent shopping items through vectors because these vectors act as the base for building em- beddings for customers and shopping carts. Also, these vectors are input to the mathematical models that act as either a recommendation engine or help in targeting potential customers. We have used exponential family embeddings as the tool to construct two basic vectors - product embeddings and context vectors. Using the basic vectors, we build combined embeddings, trip embeddings and customer embeddings. Combined embeddings mix linguistic properties of product names with their shopping patterns. The customer embeddings establish an understand- ing of the buying pattern of customers in a group and help in building customer profile. For example a customer profile can represent customers frequently buying pet-food. Identifying such profiles can help us bring out offers and discounts. Similarly, trip embeddings are used to build trip profiles. People happen to buy similar set of products in a trip and hence their trip embeddings can be used to predict the next product they would like to buy. This is a novel technique and the first of its kind to make recommendation using product, trip and customer embeddings. |
| Tasks | |
| Published | 2017-05-17 |
| URL | http://arxiv.org/abs/1705.06338v1 |
| http://arxiv.org/pdf/1705.06338v1.pdf | |
| PWC | https://paperswithcode.com/paper/distributed-vector-representation-of-shopping |
| Repo | |
| Framework | |
SILVar: Single Index Latent Variable Models
| Title | SILVar: Single Index Latent Variable Models |
| Authors | Jonathan Mei, Jose’ M. F. Moura |
| Abstract | A semi-parametric, non-linear regression model in the presence of latent variables is introduced. These latent variables can correspond to unmodeled phenomena or unmeasured agents in a complex networked system. This new formulation allows joint estimation of certain non-linearities in the system, the direct interactions between measured variables, and the effects of unmodeled elements on the observed system. The particular form of the model adopted is justified, and learning is posed as a regularized empirical risk minimization. This leads to classes of structured convex optimization problems with a “sparse plus low-rank” flavor. Relations between the proposed model and several common model paradigms, such as those of Robust Principal Component Analysis (PCA) and Vector Autoregression (VAR), are established. Particularly in the VAR setting, the low-rank contributions can come from broad trends exhibited in the time series. Details of the algorithm for learning the model are presented. Experiments demonstrate the performance of the model and the estimation algorithm on simulated and real data. |
| Tasks | Latent Variable Models, Time Series |
| Published | 2017-05-09 |
| URL | http://arxiv.org/abs/1705.03536v3 |
| http://arxiv.org/pdf/1705.03536v3.pdf | |
| PWC | https://paperswithcode.com/paper/silvar-single-index-latent-variable-models |
| Repo | |
| Framework | |
Quaternion Based Camera Pose Estimation From Matched Feature Points
| Title | Quaternion Based Camera Pose Estimation From Matched Feature Points |
| Authors | Kaveh Fathian, J. Pablo Ramirez-Paredes, Emily A. Doucette, J. Willard Curtis, Nicholas R. Gans |
| Abstract | We present a novel solution to the camera pose estimation problem, where rotation and translation of a camera between two views are estimated from matched feature points in the images. The camera pose estimation problem is traditionally solved via algorithms that are based on the essential matrix or the Euclidean homography. With six or more feature points in general positions in the space, essential matrix based algorithms can recover a unique solution. However, such algorithms fail when points are on critical surfaces (e.g., coplanar points) and homography should be used instead. By formulating the problem in quaternions and decoupling the rotation and translation estimation, our proposed algorithm works for all point configurations. Using both simulated and real world images, we compare the estimation accuracy of our algorithm with some of the most commonly used algorithms. Our method is shown to be more robust to noise and outliers. For the benefit of community, we have made the implementation of our algorithm available online and free. |
| Tasks | Pose Estimation |
| Published | 2017-04-09 |
| URL | http://arxiv.org/abs/1704.02672v2 |
| http://arxiv.org/pdf/1704.02672v2.pdf | |
| PWC | https://paperswithcode.com/paper/quaternion-based-camera-pose-estimation-from |
| Repo | |
| Framework | |
FWDA: a Fast Wishart Discriminant Analysis with its Application to Electronic Health Records Data Classification
| Title | FWDA: a Fast Wishart Discriminant Analysis with its Application to Electronic Health Records Data Classification |
| Authors | Haoyi Xiong, Wei Cheng, Wenqing Hu, Jiang Bian, Zhishan Guo |
| Abstract | Linear Discriminant Analysis (LDA) on Electronic Health Records (EHR) data is widely-used for early detection of diseases. Classical LDA for EHR data classification, however, suffers from two handicaps: the ill-posed estimation of LDA parameters (e.g., covariance matrix), and the “linear inseparability” of EHR data. To handle these two issues, in this paper, we propose a novel classifier FWDA – Fast Wishart Discriminant Analysis, that makes predictions in an ensemble way. Specifically, FWDA first surrogates the distribution of inverse covariance matrices using a Wishart distribution estimated from the training data, then “weighted-averages” the classification results of multiple LDA classifiers parameterized by the sampled inverse covariance matrices via a Bayesian Voting scheme. The weights for voting are optimally updated to adapt each new input data, so as to enable the nonlinear classification. Theoretical analysis indicates that FWDA possesses a fast convergence rate and a robust performance on high dimensional data. Extensive experiments on large-scale EHR dataset show that our approach outperforms state-of-the-art algorithms by a large margin. |
| Tasks | |
| Published | 2017-04-25 |
| URL | http://arxiv.org/abs/1704.07790v1 |
| http://arxiv.org/pdf/1704.07790v1.pdf | |
| PWC | https://paperswithcode.com/paper/fwda-a-fast-wishart-discriminant-analysis |
| Repo | |
| Framework | |
Learning Agents in Black-Scholes Financial Markets: Consensus Dynamics and Volatility Smiles
| Title | Learning Agents in Black-Scholes Financial Markets: Consensus Dynamics and Volatility Smiles |
| Authors | Tushar Vaidya, Carlos Murguia, Georgios Piliouras |
| Abstract | Black-Scholes (BS) is the standard mathematical model for option pricing in financial markets. Option prices are calculated using an analytical formula whose main inputs are strike (at which price to exercise) and volatility. The BS framework assumes that volatility remains constant across all strikes, however, in practice it varies. How do traders come to learn these parameters? We introduce natural models of learning agents, in which they update their beliefs about the true implied volatility based on the opinions of other traders. We prove convergence of these opinion dynamics using techniques from control theory and leader-follower models, thus providing a resolution between theory and market practices. We allow for two different models, one with feedback and one with an unknown leader. |
| Tasks | |
| Published | 2017-04-25 |
| URL | http://arxiv.org/abs/1704.07597v2 |
| http://arxiv.org/pdf/1704.07597v2.pdf | |
| PWC | https://paperswithcode.com/paper/learning-agents-in-black-scholes-financial |
| Repo | |
| Framework | |
GA-PSO-Optimized Neural-Based Control Scheme for Adaptive Congestion Control to Improve Performance in Multimedia Applications
| Title | GA-PSO-Optimized Neural-Based Control Scheme for Adaptive Congestion Control to Improve Performance in Multimedia Applications |
| Authors | Mansour Sheikhan, Ehsan Hemmati, Reza Shahnazi |
| Abstract | Active queue control aims to improve the overall communication network throughput while providing lower delay and small packet loss rate. The basic idea is to actively trigger packet dropping (or marking provided by explicit congestion notification (ECN)) before buffer overflow. In this paper, two artificial neural networks (ANN)-based control schemes are proposed for adaptive queue control in TCP communication networks. The structure of these controllers is optimized using genetic algorithm (GA) and the output weights of ANNs are optimized using particle swarm optimization (PSO) algorithm. The controllers are radial bias function (RBF)-based, but to improve the robustness of RBF controller, an error-integral term is added to RBF equation in the second scheme. Experimental results show that GA- PSO-optimized improved RBF (I-RBF) model controls network congestion effectively in terms of link utilization with a low packet loss rate and outperform Drop Tail, proportional-integral (PI), random exponential marking (REM), and adaptive random early detection (ARED) controllers. |
| Tasks | |
| Published | 2017-11-16 |
| URL | http://arxiv.org/abs/1711.06317v1 |
| http://arxiv.org/pdf/1711.06317v1.pdf | |
| PWC | https://paperswithcode.com/paper/ga-pso-optimized-neural-based-control-scheme |
| Repo | |
| Framework | |
The Landscape of Deep Learning Algorithms
| Title | The Landscape of Deep Learning Algorithms |
| Authors | Pan Zhou, Jiashi Feng |
| Abstract | This paper studies the landscape of empirical risk of deep neural networks by theoretically analyzing its convergence behavior to the population risk as well as its stationary points and properties. For an $l$-layer linear neural network, we prove its empirical risk uniformly converges to its population risk at the rate of $\mathcal{O}(r^{2l}\sqrt{d\log(l)}/\sqrt{n})$ with training sample size of $n$, the total weight dimension of $d$ and the magnitude bound $r$ of weight of each layer. We then derive the stability and generalization bounds for the empirical risk based on this result. Besides, we establish the uniform convergence of gradient of the empirical risk to its population counterpart. We prove the one-to-one correspondence of the non-degenerate stationary points between the empirical and population risks with convergence guarantees, which describes the landscape of deep neural networks. In addition, we analyze these properties for deep nonlinear neural networks with sigmoid activation functions. We prove similar results for convergence behavior of their empirical risks as well as the gradients and analyze properties of their non-degenerate stationary points. To our best knowledge, this work is the first one theoretically characterizing landscapes of deep learning algorithms. Besides, our results provide the sample complexity of training a good deep neural network. We also provide theoretical understanding on how the neural network depth $l$, the layer width, the network size $d$ and parameter magnitude determine the neural network landscapes. |
| Tasks | |
| Published | 2017-05-19 |
| URL | http://arxiv.org/abs/1705.07038v2 |
| http://arxiv.org/pdf/1705.07038v2.pdf | |
| PWC | https://paperswithcode.com/paper/the-landscape-of-deep-learning-algorithms |
| Repo | |
| Framework | |
Truthful Facility Location with Additive Errors
| Title | Truthful Facility Location with Additive Errors |
| Authors | Iddan Golomb, Christos Tzamos |
| Abstract | We address the problem of locating facilities on the $[0,1]$ interval based on reports from strategic agents. The cost of each agent is her distance to the closest facility, and the global objective is to minimize either the maximum cost of an agent or the social cost. As opposed to the extensive literature on facility location which considers the multiplicative error, we focus on minimizing the worst-case additive error. Minimizing the additive error incentivizes mechanisms to adapt to the size of the instance. I.e., mechanisms can sacrifice little efficiency in small instances (location profiles in which all agents are relatively close to one another), in order to gain more [absolute] efficiency in large instances. We argue that this measure is better suited for many manifestations of the facility location problem in various domains. We present tight bounds for mechanisms locating a single facility in both deterministic and randomized cases. We further provide several extensions for locating multiple facilities. |
| Tasks | |
| Published | 2017-01-02 |
| URL | http://arxiv.org/abs/1701.00529v1 |
| http://arxiv.org/pdf/1701.00529v1.pdf | |
| PWC | https://paperswithcode.com/paper/truthful-facility-location-with-additive |
| Repo | |
| Framework | |
Fair prediction with disparate impact: A study of bias in recidivism prediction instruments
| Title | Fair prediction with disparate impact: A study of bias in recidivism prediction instruments |
| Authors | Alexandra Chouldechova |
| Abstract | Recidivism prediction instruments (RPI’s) provide decision makers with an assessment of the likelihood that a criminal defendant will reoffend at a future point in time. While such instruments are gaining increasing popularity across the country, their use is attracting tremendous controversy. Much of the controversy concerns potential discriminatory bias in the risk assessments that are produced. This paper discusses several fairness criteria that have recently been applied to assess the fairness of recidivism prediction instruments. We demonstrate that the criteria cannot all be simultaneously satisfied when recidivism prevalence differs across groups. We then show how disparate impact can arise when a recidivism prediction instrument fails to satisfy the criterion of error rate balance. |
| Tasks | |
| Published | 2017-02-28 |
| URL | http://arxiv.org/abs/1703.00056v1 |
| http://arxiv.org/pdf/1703.00056v1.pdf | |
| PWC | https://paperswithcode.com/paper/fair-prediction-with-disparate-impact-a-study-1 |
| Repo | |
| Framework | |
Question Asking as Program Generation
| Title | Question Asking as Program Generation |
| Authors | Anselm Rothe, Brenden M. Lake, Todd M. Gureckis |
| Abstract | A hallmark of human intelligence is the ability to ask rich, creative, and revealing questions. Here we introduce a cognitive model capable of constructing human-like questions. Our approach treats questions as formal programs that, when executed on the state of the world, output an answer. The model specifies a probability distribution over a complex, compositional space of programs, favoring concise programs that help the agent learn in the current context. We evaluate our approach by modeling the types of open-ended questions generated by humans who were attempting to learn about an ambiguous situation in a game. We find that our model predicts what questions people will ask, and can creatively produce novel questions that were not present in the training set. In addition, we compare a number of model variants, finding that both question informativeness and complexity are important for producing human-like questions. |
| Tasks | |
| Published | 2017-11-16 |
| URL | http://arxiv.org/abs/1711.06351v1 |
| http://arxiv.org/pdf/1711.06351v1.pdf | |
| PWC | https://paperswithcode.com/paper/question-asking-as-program-generation |
| Repo | |
| Framework | |
Text Summarization using Abstract Meaning Representation
| Title | Text Summarization using Abstract Meaning Representation |
| Authors | Shibhansh Dohare, Harish Karnick, Vivek Gupta |
| Abstract | With an ever increasing size of text present on the Internet, automatic summary generation remains an important problem for natural language understanding. In this work we explore a novel full-fledged pipeline for text summarization with an intermediate step of Abstract Meaning Representation (AMR). The pipeline proposed by us first generates an AMR graph of an input story, through which it extracts a summary graph and finally, generate summary sentences from this summary graph. Our proposed method achieves state-of-the-art results compared to the other text summarization routines based on AMR. We also point out some significant problems in the existing evaluation methods, which make them unsuitable for evaluating summary quality. |
| Tasks | Text Summarization |
| Published | 2017-06-06 |
| URL | http://arxiv.org/abs/1706.01678v3 |
| http://arxiv.org/pdf/1706.01678v3.pdf | |
| PWC | https://paperswithcode.com/paper/text-summarization-using-abstract-meaning |
| Repo | |
| Framework | |
Using a new parsimonious AHP methodology combined with the Choquet integral: An application for evaluating social housing initiatives
| Title | Using a new parsimonious AHP methodology combined with the Choquet integral: An application for evaluating social housing initiatives |
| Authors | Francesca Abastante, Salvatore Corrente, Salvatore Greco, Alessio Ishizaka, Isabella Lami |
| Abstract | We propose a development of the Analytic Hierarchy Process (AHP) permitting to use the methodology also in cases of decision problems with a very large number of alternatives evaluated with respect to several criteria. While the application of the original AHP method involves many pairwise comparisons between alternatives and criteria, our proposal is composed of three steps: (i) direct evaluation of the alternatives at hand on the considered criteria, (ii) selection of some reference evaluations; (iii) application of the original AHP method to reference evaluations; (iv) revision of the direct evaluation on the basis of the prioritization supplied by AHP on reference evaluations. The new proposal has been tested and validated in an experiment conducted on a sample of university students. The new methodology has been therefore applied to a real world problem involving the evaluation of 21 Social Housing initiatives sited in the Piedmont region (Italy). To take into account interaction between criteria, the Choquet integral preference model has been considered within a Non Additive Robust Ordinal Regression approach. |
| Tasks | |
| Published | 2017-04-24 |
| URL | http://arxiv.org/abs/1704.08119v1 |
| http://arxiv.org/pdf/1704.08119v1.pdf | |
| PWC | https://paperswithcode.com/paper/using-a-new-parsimonious-ahp-methodology |
| Repo | |
| Framework | |
Interpretable Categorization of Heterogeneous Time Series Data
| Title | Interpretable Categorization of Heterogeneous Time Series Data |
| Authors | Ritchie Lee, Mykel J. Kochenderfer, Ole J. Mengshoel, Joshua Silbermann |
| Abstract | Understanding heterogeneous multivariate time series data is important in many applications ranging from smart homes to aviation. Learning models of heterogeneous multivariate time series that are also human-interpretable is challenging and not adequately addressed by the existing literature. We propose grammar-based decision trees (GBDTs) and an algorithm for learning them. GBDTs extend decision trees with a grammar framework. Logical expressions derived from a context-free grammar are used for branching in place of simple thresholds on attributes. The added expressivity enables support for a wide range of data types while retaining the interpretability of decision trees. In particular, when a grammar based on temporal logic is used, we show that GBDTs can be used for the interpretable classi cation of high-dimensional and heterogeneous time series data. Furthermore, we show how GBDTs can also be used for categorization, which is a combination of clustering and generating interpretable explanations for each cluster. We apply GBDTs to analyze the classic Australian Sign Language dataset as well as data on near mid-air collisions (NMACs). The NMAC data comes from aircraft simulations used in the development of the next-generation Airborne Collision Avoidance System (ACAS X). |
| Tasks | Time Series |
| Published | 2017-08-30 |
| URL | http://arxiv.org/abs/1708.09121v2 |
| http://arxiv.org/pdf/1708.09121v2.pdf | |
| PWC | https://paperswithcode.com/paper/interpretable-categorization-of-heterogeneous |
| Repo | |
| Framework | |
Identification and Off-Policy Learning of Multiple Objectives Using Adaptive Clustering
| Title | Identification and Off-Policy Learning of Multiple Objectives Using Adaptive Clustering |
| Authors | Thommen George Karimpanal, Erik Wilhelm |
| Abstract | In this work, we present a methodology that enables an agent to make efficient use of its exploratory actions by autonomously identifying possible objectives in its environment and learning them in parallel. The identification of objectives is achieved using an online and unsupervised adaptive clustering algorithm. The identified objectives are learned (at least partially) in parallel using Q-learning. Using a simulated agent and environment, it is shown that the converged or partially converged value function weights resulting from off-policy learning can be used to accumulate knowledge about multiple objectives without any additional exploration. We claim that the proposed approach could be useful in scenarios where the objectives are initially unknown or in real world scenarios where exploration is typically a time and energy intensive process. The implications and possible extensions of this work are also briefly discussed. |
| Tasks | Q-Learning |
| Published | 2017-05-17 |
| URL | http://arxiv.org/abs/1705.06342v1 |
| http://arxiv.org/pdf/1705.06342v1.pdf | |
| PWC | https://paperswithcode.com/paper/identification-and-off-policy-learning-of |
| Repo | |
| Framework | |
