OpenRaiser/Intern-Atlas huggingface dataset:
Conversational Recommendation System with Unsupervised Learning
Venue: arXiv cs.CL 2016
Year: 2016

We will demonstrate a conversational products recommendation agent. This system shows how we combine research in personalized recommendation systems with research in dialogue systems to build a virtual sales agent. Based on new deep learning technologies we developed, the virtual agent is capable of learning how to interact with users, how to answer user questions, what is the next question to ask, and what to recommend when chatting with a human user. Normally a descent conversational agent for a particular domain requires tens of thousands of hand labeled conversational data or hand written rules. This is a major barrier when launching a conversation agent for a new domain. We will explore and demonstrate the effectiveness of the learning solution even when there is no hand written rules or hand labeled training data.
Learning How to Communicate in the Internet of Things: Finite Resources and Heterogeneity
Venue: arXiv cs.IT 2016
Year: 2016

For a seamless deployment of the Internet of Things (IoT), there is a need for self-organizing solutions to overcome key IoT challenges that include data processing, resource management, coexistence with existing wireless networks, and improved IoT-wide event detection. One of the most promising solutions to address these challenges is via the use of innovative learning frameworks that will enable the IoT devices to operate autonomously in a dynamic environment. However, developing learning mechanisms for the IoT requires coping with unique IoT properties in terms of resource constraints, heterogeneity, and strict quality-of-service requirements. In this paper, a number of emerging learning frameworks suitable for IoT applications are presented. In particular, the advantages, limitations, IoT applications, and key results pertaining to machine learning, sequential learning, and reinforcement learning are studied. For each type of learning, the computational complexity, required information, and learning performance are discussed. Then, to handle the heterogeneity of the IoT, a new framework based on the powerful tools of cognitive hierarchy theory is introduced. This framework is shown to efficiently capture the different IoT device types and varying levels of available resources among the IoT devices. In particular, the different resource capabilities of IoT devices are mapped to different levels of rationality in cognitive hierarchy theory, thus enabling the IoT devices to use different learning frameworks depending on their available resources. Finally, key results on the use of cognitive hierarchy theory in the IoT are presented.
A Survey and Measurement Study of GPU DVFS on Energy Conservation
Venue: arXiv cs.DC 2016
Year: 2016

Energy efficiency has become one of the top design criteria for current computing systems. The dynamic voltage and frequency scaling (DVFS) has been widely adopted by laptop computers, servers, and mobile devices to conserve energy, while the GPU DVFS is still at a certain early age. This paper aims at exploring the impact of GPU DVFS on the application performance and power consumption, and furthermore, on energy conservation. We survey the state-of-the-art GPU DVFS characterizations, and then summarize recent research works on GPU power and performance models. We also conduct real GPU DVFS experiments on NVIDIA Fermi and Maxwell GPUs. According to our experimental results, GPU DVFS has significant potential for energy saving. The effect of scaling core voltage/frequency and memory voltage/frequency depends on not only the GPU architectures, but also the characteristic of GPU applications.
Active exploration in parameterized reinforcement learning
Venue: arXiv cs.LG 2016
Year: 2016

Online model-free reinforcement learning (RL) methods with continuous actions are playing a prominent role when dealing with real-world applications such as Robotics. However, when confronted to non-stationary environments, these methods crucially rely on an exploration-exploitation trade-off which is rarely dynamically and automatically adjusted to changes in the environment. Here we propose an active exploration algorithm for RL in structured (parameterized) continuous action space. This framework deals with a set of discrete actions, each of which is parameterized with continuous variables. Discrete exploration is controlled through a Boltzmann softmax function with an inverse temperature $β$ parameter. In parallel, a Gaussian exploration is applied to the continuous action parameters. We apply a meta-learning algorithm based on the comparison between variations of short-term and long-term reward running averages to simultaneously tune $β$ and the width of the Gaussian distribution from which continuous action parameters are drawn. When applied to a simple virtual human-robot interaction task, we show that this algorithm outperforms continuous parameterized RL both without active exploration and with active exploration based on uncertainty variations measured by a Kalman-Q-learning algorithm.
After Sandy Hook Elementary: A Year in the Gun Control Debate on Twitter
Venue: arXiv cs.SI 2016
Year: 2016

The mass shooting at Sandy Hook elementary school on December 14, 2012 catalyzed a year of active debate and legislation on gun control in the United States. Social media hosted an active public discussion where people expressed their support and opposition to a variety of issues surrounding gun legislation. In this paper, we show how a content-based analysis of Twitter data can provide insights and understanding into this debate. We estimate the relative support and opposition to gun control measures, along with a topic analysis of each camp by analyzing over 70 million gun-related tweets from 2013. We focus on spikes in conversation surrounding major events related to guns throughout the year. Our general approach can be applied to other important public health and political issues to analyze the prevalence and nature of public opinion.
Prospect Theory for Enhanced Smart Grid Resilience Using Distributed Energy Storage
Venue: arXiv cs.GT 2016
Year: 2016

The proliferation of distributed generation and storage units is leading to the development of local, small-scale distribution grids, known as microgrids (MGs). In this paper, the problem of optimizing the energy trading decisions of MG operators (MGOs) is studied using game theory. In the formulated game, each MGO chooses the amount of energy that must be sold immediately or stored for future emergencies, given the prospective market prices which are influenced by other MGOs' decisions. The problem is modeled using a Bayesian game to account for the incomplete information that MGOs have about each others' levels of surplus. The proposed game explicitly accounts for each MGO's subjective decision when faced with the uncertainty of its opponents' energy surplus. In particular, the so-called framing effect, from the framework of prospect theory (PT), is used to account for each MGO's valuation of its gains and losses with respect to an individual utility reference point. The reference point is typically different for each individual and originates from its past experiences and future aspirations. A closed-form expression for the Bayesian Nash equilibrium is derived for the standard game formulation. Under PT, a best response algorithm is proposed to find the equilibrium. Simulation results show that, depending on their individual reference points, MGOs can tend to store more or less energy under PT compared to classical game theory. In addition, the impact of the reference point is found to be more prominent as the emergency price set by the power company increases.
An Algebraic Approach to a Class of Rank-Constrained Semi-Definite Programs With Applications
Venue: arXiv cs.IT 2016
Year: 2016

A new approach to solving a class of rankconstrained semi-definite programming (SDP) problems, which appear in many signal processing applications such as transmit beamspace design in multiple-input multiple-output (MIMO) radar, downlink beamforming design in MIMO communications, generalized sidelobe canceller design, phase retrieval, etc., is presented. The essence of the approach is the use of underlying algebraic structure enforced in such problems by other practical constraints such as, for example, null shaping constraint. According to this approach, instead of relaxing the non-convex rankconstrained SDP problem to a feasible set of positive semidefinite matrices, we restrict it to a space of polynomials whose dimension is equal to the desired rank. The resulting optimization problem is then convex as its solution is required to be full rank, and can be efficiently and exactly solved. A simple matrix decomposition is needed to recover the solution of the original problem from the solution of the restricted one. We show how this approach can be applied to solving some important signal processing problems that contain null-shaping constraints. As a byproduct of our study, the conjugacy of beamfoming and parameter estimation problems leads us to formulation of a new and rigorous criterion for signal/noise subspace identification. Simulation results are performed for the problem of rank-constrained beamforming design and show an exact agreement of the solution with the proposed algebraic structure, as well as significant performance improvements in terms of sidelobe suppression compared to the existing methods.
Performance analysis of multi-dimensional ESPRIT-type algorithms for arbitrary and strictly non-circular sources with spatial smoothing
Venue: arXiv cs.IT 2016
Year: 2016

Spatial smoothing is a widely used preprocessing scheme to improve the performance of high-resolution parameter estimation algorithms in case of coherent signals or if only a small number of snapshots is available. In this paper, we present a first-order performance analysis of the spatially smoothed versions of R-D Standard ESPRIT and R-D Unitary ESPRIT for sources with arbitrary signal constellations as well as R-D NC Standard ESPRIT and R-D NC Unitary ESPRIT for strictly second-order (SO) non-circular (NC) sources. The derived expressions are asymptotic in the effective signal-to-noise ratio (SNR), i.e., the approximations become exact for either high SNRs or a large sample size. Moreover, no assumptions on the noise statistics are required apart from a zero-mean and finite SO moments. We show that both R-D NC ESPRIT-type algorithms with spatial smoothing perform asymptotically identical in the high effective SNR regime. Generally, the performance of spatial smoothing based algorithms depends on the number of subarrays, which is a design parameter and needs to be chosen beforehand. In order to gain more insights into the optimal choice of the number of subarrays, we simplify the derived analytical R-D mean square error (MSE) expressions for the special case of a single source. The obtained MSE expression explicitly depends on the number of subarrays in each dimension, which allows us to analytically find the optimal number of subarrays for spatial smoothing. Based on this result, we additionally derive the maximum asymptotic gain from spatial smoothing and explicitly compute the asymptotic efficiency for this special case. All the analytical results are verified by simulations.
Energy-efficient Delivery by Heterogeneous Mobile Agents
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of delivering $m$ messages between specified source-target pairs in a weighted undirected graph, by $k$ mobile agents initially located at distinct nodes of the graph. Each agent consumes energy proportional to the distance it travels in the graph and we are interested in optimizing the total energy consumption for the team of agents. Unlike previous related work, we consider heterogeneous agents with different rates of energy consumption (weights~$w_i$). To solve the delivery problem, agents face three major challenges: \emph{Collaboration} (how to work together on each message), \emph{Planning} (which route to take) and \emph{Coordination} (how to assign agents to messages). We first show that the delivery problem can be 2-approximated \emph{without} collaborating and that this is best possible, i.e., we show that the \emph{benefit of collaboration} is 2 in general. We also show that the benefit of collaboration for a single message is~$1/\ln 2 \approx 1.44$. Planning turns out to be \NP-hard to approximate even for a single agent, but can be 2-approximated in polynomial time if agents have unit capacities and do not collaborate. We further show that coordination is \NP-hard even for agents with unit capacity, but can be efficiently solved exactly if they have uniform weights. Finally, we give a polynomial-time $(4\max\tfrac{w_i}{w_j})$-approximation for message delivery with unit capacities.
Step Timing Adjustment: A Step toward Generating Robust Gaits
Venue: arXiv cs.RO 2016
Year: 2016

Step adjustment for humanoid robots has been shown to improve robustness in gaits. However, step duration adaptation is often neglected in control strategies. In this paper, we propose an approach that combines both step location and timing adjustment for generating robust gaits. In this approach, step location and step timing are decided, based on feedback from the current state of the robot. The proposed approach is comprised of two stages. In the first stage, the nominal step location and step duration for the next step or a previewed number of steps are specified. In this stage which is done at the start of each step, the main goal is to specify the best step length and step duration for a desired walking speed. The second stage deals with finding the best landing point and landing time of the swing foot at each control cycle. In this stage, stability of the gaits is preserved by specifying a desired offset between the swing foot landing point and the Divergent Component of Motion (DCM) at the end of current step. After specifying the landing point of the swing foot at a desired time, the swing foot trajectory is regenerated at each control cycle to realize desired landing properties. Simulation on different scenarios shows the robustness of the generated gaits from our proposed approach compared to the case where no timing adjustment is employed.
Indoor Space Recognition using Deep Convolutional Neural Network: A Case Study at MIT Campus
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose a robust and parsimonious approach using Deep Convolutional Neural Network (DCNN) to recognize and interpret interior space. DCNN has achieved incredible success in object and scene recognition. In this study we design and train a DCNN to classify a pre-zoning indoor space, and from a single phone photo to recognize the learned space features, with no need of additional assistive technology. We collect more than 600,000 images inside MIT campus buildings to train our DCNN model, and achieved 97.9% accuracy in validation dataset and 81.7% accuracy in test dataset based on spatial-scale fixed model. Furthermore, the recognition accuracy and spatial resolution can be potentially improved through multiscale classification model. We identify the discriminative image regions through Class Activating Mapping (CAM) technique, to observe the model's behavior in how to recognize space and interpret it in an abstract way. By evaluating the results with misclassification matrix, we investigate the visual spatial feature of interior space by looking into its visual similarity and visual distinctiveness, giving insights into interior design and human indoor perception and wayfinding research. The contribution of this paper is threefold. First, we propose a robust and parsimonious approach for indoor navigation using DCNN. Second, we demonstrate that DCNN also has a potential capability in space feature learning and recognition, even under severe appearance changes. Third, we introduce a DCNN based approach to look into the visual similarity and visual distinctiveness of interior space.
Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)
Venue: arXiv cs.DB 2016
Year: 2016

Approximate Nearest neighbor search (ANNS) is fundamental and essential operation in applications from many domains, such as databases, machine learning, multimedia, and computer vision. Although many algorithms have been continuously proposed in the literature in the above domains each year, there is no comprehensive evaluation and analysis of their performances. In this paper, we conduct a comprehensive experimental evaluation of many state-of-the-art methods for approximate nearest neighbor search. Our study (1) is cross-disciplinary (i.e., including 16 algorithms in different domains, and from practitioners) and (2) has evaluated a diverse range of settings, including 20 datasets, several evaluation metrics, and different query workloads. The experimental results are carefully reported and analyzed to understand the performance results. Furthermore, we propose a new method that achieves both high query efficiency and high recall empirically on majority of the datasets under a wide range of settings.
Bi-Fuzzy Discrete Event Systems and Their Supervisory Control Theory
Venue: arXiv cs.SY 2016
Year: 2016

It is well known that type-1 fuzzy sets (T1 FSs) have limited capabilities to handle some data uncertainties directly, and type-2 fuzzy sets (T2 FSs) can cover the shortcoming of T1 FSs to a certain extent. Fuzzy discrete event systems (FDESs) were proposed based on T1 FSs theory. Hence, FDES may not be a satisfactory model to characterize some high-uncertainty systems. In this paper, we propose a new model, called as bi-fuzzy discrete event systems (BFDESs), by combining classical DESs theory and T2 FSs theory. Then, we consider the supervisory control problem of BFDESs. The bi-fuzzy controllability theorem and nonblocking bi-fuzzy controllability theorem are demonstrated. Also, an algorithm for checking the bi-fuzzy controllability condition is presented. In addition, two controllable approximations to an uncontrollable language are investigated in detail. An illustrative example is provided to show the applicability and the advantages of BFDESs model.
A Semantic Analyzer for the Comprehension of the Spontaneous Arabic Speech
Venue: arXiv cs.CL 2016
Year: 2016

This work is part of a large research project entitled "Oréodule" aimed at developing tools for automatic speech recognition, translation, and synthesis for Arabic language. Our attention has mainly been focused on an attempt to improve the probabilistic model on which our semantic decoder is based. To achieve this goal, we have decided to test the influence of the pertinent context use, and of the contextual data integration of different types, on the effectiveness of the semantic decoder. The findings are quite satisfactory.
SaberLDA: Sparsity-Aware Learning of Topic Models on GPUs
Venue: arXiv cs.DC 2016
Year: 2016

Latent Dirichlet Allocation (LDA) is a popular tool for analyzing discrete count data such as text and images. Applications require LDA to handle both large datasets and a large number of topics. Though distributed CPU systems have been used, GPU-based systems have emerged as a promising alternative because of the high computational power and memory bandwidth of GPUs. However, existing GPU-based LDA systems cannot support a large number of topics because they use algorithms on dense data structures whose time and space complexity is linear to the number of topics. In this paper, we propose SaberLDA, a GPU-based LDA system that implements a sparsity-aware algorithm to achieve sublinear time complexity and scales well to learn a large number of topics. To address the challenges introduced by sparsity, we propose a novel data layout, a new warp-based sampling kernel, and an efficient sparse count matrix updating algorithm that improves locality, makes efficient utilization of GPU warps, and reduces memory consumption. Experiments show that SaberLDA can learn from billions-token-scale data with up to 10,000 topics, which is almost two orders of magnitude larger than that of the previous GPU-based systems. With a single GPU card, SaberLDA is able to learn 10,000 topics from a dataset of billions of tokens in a few hours, which is only achievable with clusters with tens of machines before.
Multiuser Diversity Gain from Superposition of Infinite Users over Block-Fading MAC
Venue: arXiv cs.IT 2016
Year: 2016

In uplink block-fading multiple access channel (BF-MAC), the advantage of multiuser diversity (MUD) can be taken to achieve higher system throughput. In this letter, with rate constraints for all users and only channel state information available at the receiver assumed, we demonstrate that non-orthogonal multiple access (NOMA) outperforms the counterpart of orthogonal multiple access (OMA) via exploiting the MUD from the superposition of multiple users. The MUD gain achieved by NOMA compared with OMA is quantitatively analyzed for finite users, and the closed-form upper bound of MUD gain from the superposition of infinite users is also derived. Numerical results show that the potential MUD gain from superposition of infinite users can be well approached with limited superposed users, which indicates that multiple access schemes with limited superposed users can provide a good tradeoff between system performance and decoding complexity.
Dynamic Trade-Off Prediction in Multi-Stage Retrieval Systems
Venue: arXiv cs.IR 2016
Year: 2016

Modern multi-stage retrieval systems are comprised of a candidate generation stage followed by one or more reranking stages. In such an architecture, the quality of the final ranked list may not be sensitive to the quality of initial candidate pool, especially in terms of early precision. This provides several opportunities to increase retrieval efficiency without significantly sacrificing effectiveness. In this paper, we explore a new approach to dynamically predicting two different parameters in the candidate generation stage which can directly affect the overall efficiency and effectiveness of the entire system. Previous work exploring this tradeoff has focused on global parameter settings that apply to all queries, even though optimal settings vary across queries. In contrast, we propose a technique which makes a parameter prediction that maximizes efficiency within a effectiveness envelope on a per query basis, using only static pre-retrieval features. The query-specific tradeoff point between effectiveness and efficiency is decided using a classifier cascade that weighs possible efficiency gains against effectiveness losses over a range of possible parameter cutoffs to make the prediction. The interesting twist in our new approach is to train classifiers without requiring explicit relevance judgments. We show that our framework is generalizable by applying it to two different retrieval parameters - selecting k in common top-k query retrieval algorithms, and setting a quality threshold, $ρ$, for score-at-a-time approximate query evaluation algorithms. Experimental results show that substantial efficiency gains are achievable depending on the dynamic parameter choice. In addition, our framework provides a versatile tool that can be used to estimate the effectiveness-efficiency tradeoffs that are possible before selecting and tuning algorithms to make machine learned predictions.