OpenRaiser/Intern-Atlas huggingface dataset:
Sentiment Classification with Word Attention based on Weakly Supervised Learning with a Convolutional Neural Network
Venue: arXiv cs.CL 2017
Year: 2017

In order to maximize the applicability of sentiment analysis results, it is necessary to not only classify the overall sentiment (positive/negative) of a given document but also to identify the main words that contribute to the classification. However, most datasets for sentiment analysis only have the sentiment label for each document or sentence. In other words, there is no information about which words play an important role in sentiment classification. In this paper, we propose a method for identifying key words discriminating positive and negative sentences by using a weakly supervised learning method based on a convolutional neural network (CNN). In our model, each word is represented as a continuous-valued vector and each sentence is represented as a matrix whose rows correspond to the word vector used in the sentence. Then, the CNN model is trained using these sentence matrices as inputs and the sentiment labels as the output. Once the CNN model is trained, we implement the word attention mechanism that identifies high-contributing words to classification results with a class activation map, using the weights from the fully connected layer at the end of the learned CNN model. In order to verify the proposed methodology, we evaluated the classification accuracy and inclusion rate of polarity words using two movie review datasets. Experimental result show that the proposed model can not only correctly classify the sentence polarity but also successfully identify the corresponding words with high polarity scores.
Communicating Finite-State Machines and Two-Variable Logic
Venue: arXiv cs.LO 2017
Year: 2017

Communicating finite-state machines are a fundamental, well-studied model of finite-state processes that communicate via unbounded first-in first-out channels. We show that they are expressively equivalent to existential MSO logic with two first-order variables and the order relation.
Distributed Robust Set-Invariance for Interconnected Linear Systems
Venue: arXiv cs.SY 2017
Year: 2017

We introduce a class of distributed control policies for networks of discrete-time linear systems with polytopic additive disturbances. The objective is to restrict the network-level state and controls to user-specified polyhedral sets for all times. This problem arises in many safety-critical applications. We consider two problems. First, given a communication graph characterizing the structure of the information flow in the network, we find the optimal distributed control policy by solving a single linear program. Second, we find the sparsest communication graph required for the existence of a distributed invariance-inducing control policy. Illustrative examples, including one on platooning, are presented.
An Extended Analytic Model for the Heating of Bondwires
Venue: arXiv cs.CE 2017
Year: 2017

We present an extended analytic formula for the calculation of the temperature profile along a bondwire embedded in a package. The resulting closed formula is built by coupling the heat transfer equations of the bondwire and the surrounding moulding compound by means of auxiliary variables that stem from an \emph{ad-hoc} linearisation and mediate the wire-mould thermal interaction. The model, which corrects typical simplifications in previously introduced analytic models, is also optimised against carefully taken experimental samples representing fusing events of bondwires within real packages.
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
Venue: arXiv cs.CC 2017
Year: 2017

We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called $k$-LCIS: Given $k$ integer sequences $X_1,\dots,X_k$ of length at most $n$, the task is to determine the length of the longest common subsequence of $X_1,\dots,X_k$ that is also strictly increasing. Especially for the case of $k=2$ (called LCIS for short), several algorithms have been proposed that require quadratic time in the worst case. Assuming the Strong Exponential Time Hypothesis (SETH), we prove a tight lower bound, specifically, that no algorithm solves LCIS in (strongly) subquadratic time. Interestingly, the proof makes no use of normalization tricks common to hardness proofs for similar problems such as LCS. We further strengthen this lower bound (1) to rule out $O((nL)^{1-\varepsilon})$ time algorithms for LCIS, where $L$ denotes the solution size, (2) to rule out $O(n^{k-\varepsilon})$ time algorithms for $k$-LCIS, and (3) to follow already from weaker variants of SETH. We obtain the same conditional lower bounds for the related Longest Common Weakly Increasing Subsequence problem.
Recognition of feature curves on 3D shapes using an algebraic approach to Hough transforms
Venue: arXiv cs.CV 2017
Year: 2017

Feature curves are largely adopted to highlight shape features, such as sharp lines, or to divide surfaces into meaningful segments, like convex or concave regions. Extracting these curves is not sufficient to convey prominent and meaningful information about a shape. We have first to separate the curves belonging to features from those caused by noise and then to select the lines, which describe non-trivial portions of a surface. The automatic detection of such features is crucial for the identification and/or annotation of relevant parts of a given shape. To do this, the Hough transform (HT) is a feature extraction technique widely used in image analysis, computer vision and digital image processing, while, for 3D shapes, the extraction of salient feature curves is still an open problem. Thanks to algebraic geometry concepts, the HT technique has been recently extended to include a vast class of algebraic curves, thus proving to be a competitive tool for yielding an explicit representation of the diverse feature lines equations. In the paper, for the first time we apply this novel extension of the HT technique to the realm of 3D shapes in order to identify and localize semantic features like patterns, decorations or anatomical details on 3D objects (both complete and fragments), even in the case of features partially damaged or incomplete. The method recognizes various features, possibly compound, and it selects the most suitable feature profiles among families of algebraic curves.
Reservoir Computing using Stochastic p-Bits
Venue: arXiv cs.ET 2017
Year: 2017

We present a general hardware framework for building networks that directly implement Reservoir Computing, a popular software method for implementing and training Recurrent Neural Networks and are particularly suited for temporal inferencing and pattern recognition. We provide a specific example of a candidate hardware unit based on a combination of soft-magnets, spin-orbit materials and CMOS transistors that can implement these networks. Efficient non von-Neumann hardware implementation of reservoir computers can open up a pathway for integration of temporal Neural Networks in a wide variety of emerging systems such as Internet of Things (IoTs), industrial controls, bio- and photo-sensors, and self-driving automotives.
Intelligence Quotient and Intelligence Grade of Artificial Intelligence
Venue: arXiv cs.AI 2017
Year: 2017

Although artificial intelligence is currently one of the most interesting areas in scientific research, the potential threats posed by emerging AI systems remain a source of persistent controversy. To address the issue of AI threat, this study proposes a standard intelligence model that unifies AI and human characteristics in terms of four aspects of knowledge, i.e., input, output, mastery, and creation. Using this model, we observe three challenges, namely, expanding of the von Neumann architecture; testing and ranking the intelligence quotient of naturally and artificially intelligent systems, including humans, Google, Bing, Baidu, and Siri; and finally, the dividing of artificially intelligent systems into seven grades from robots to Google Brain. Based on this, we conclude that AlphaGo belongs to the third grade.
Explainable Planning
Venue: arXiv cs.AI 2017
Year: 2017

As AI is increasingly being adopted into application solutions, the challenge of supporting interaction with humans is becoming more apparent. Partly this is to support integrated working styles, in which humans and intelligent systems cooperate in problem-solving, but also it is a necessary step in the process of building trust as humans migrate greater responsibility to such systems. The challenge is to find effective ways to communicate the foundations of AI-driven behaviour, when the algorithms that drive it are far from transparent to humans. In this paper we consider the opportunities that arise in AI planning, exploiting the model-based representations that form a familiar and common basis for communication with users, while acknowledging the gap between planning algorithms and human problem-solving.
Non-parametric Message Important Measure: Storage Code Design and Transmission Planning for Big Data
Venue: arXiv cs.IT 2017
Year: 2017

Storage and transmission in big data are discussed in this paper, where message importance is taken into account. Similar to Shannon Entropy and Renyi Entropy, we define non-parametric message important measure (NMIM) as a measure for the message importance in the scenario of big data, which can characterize the uncertainty of random events. It is proved that the proposed NMIM can sufficiently describe two key characters of big data: rare events finding and large diversities of events. Based on NMIM, we first propose an effective compressed encoding mode for data storage, and then discuss the channel transmission over some typical channel models. Numerical simulation results show that using our proposed strategy occupies less storage space without losing too much message importance, and there are growth region and saturation region for the maximum transmission, which contributes to designing of better practical communication system.
MobInsight: A Framework Using Semantic Neighborhood Features for Localized Interpretations of Urban Mobility
Venue: arXiv cs.HC 2017
Year: 2017

Collective urban mobility embodies the residents' local insights on the city. Mobility practices of the residents are produced from their spatial choices, which involve various considerations such as the atmosphere of destinations, distance, past experiences, and preferences. The advances in mobile computing and the rise of geo-social platforms have provided the means for capturing the mobility practices; however, interpreting the residents' insights is challenging due to the scale and complexity of an urban environment, and its unique context. In this paper, we present MobInsight, a framework for making localized interpretations of urban mobility that reflect various aspects of the urbanism. MobInsight extracts a rich set of neighborhood features through holistic semantic aggregation, and models the mobility between all-pairs of neighborhoods. We evaluate MobInsight with the mobility data of Barcelona and demonstrate diverse localized and semantically-rich interpretations.
Optimal Reserve Price for Online Ads Trading Based on Inventory Identification
Venue: arXiv cs.GT 2017
Year: 2017

The online ads trading platform plays a crucial role in connecting publishers and advertisers and generates tremendous value in facilitating the convenience of our lives. It has been evolving into a more and more complicated structure. In this paper, we consider the problem of maximizing the revenue for the seller side via utilizing proper reserve price for the auctions in a dynamical way. Predicting the optimal reserve price for each auction in the repeated auction marketplaces is a non-trivial problem. However, we were able to come up with an efficient method of improving the seller revenue by mainly focusing on adjusting the reserve price for those high-value inventories. Previously, no dedicated work has been performed from this perspective. Inspired by Paul and Michael, our model first identifies the value of the inventory by predicting the top bid price bucket using a cascade of classifiers. The cascade is essential in significantly reducing the false positive rate of a single classifier. Based on the output of the first step, we build another cluster of classifiers to predict the price separations between the top two bids. We showed that although the high-value auctions are only a small portion of all the traffic, successfully identifying them and setting correct reserve price would result in a significant revenue lift. Moreover, our optimization is compatible with all other reserve price models in the system and does not impact their performance. In other words, when combined with other models, the enhancement on exchange revenue will be aggregated. Simulations on randomly sampled Yahoo ads exchange (YAXR) data showed stable and expected lift after applying our model.
Runtime Distributions and Criteria for Restarts
Venue: arXiv cs.DS 2017
Year: 2017

Randomized algorithms sometimes employ a restart strategy. After a certain number of steps, the current computation is aborted and restarted with a new, independent random seed. In some cases, this results in an improved overall expected runtime. This work introduces properties of the underlying runtime distribution which determine whether restarts are advantageous. The most commonly used probability distributions admit the use of a scale and a location parameter. Location parameters shift the density function to the right, while scale parameters affect the spread of the distribution. It is shown that for all distributions scale parameters do not influence the usefulness of restarts and that location parameters only have a limited influence. This result simplifies the analysis of the usefulness of restarts. The most important runtime probability distributions are the log-normal, the Weibull, and the Pareto distribution. In this work, these distributions are analyzed for the usefulness of restarts. Secondly, a condition for the optimal restart time (if it exists) is provided. The log-normal, the Weibull, and the generalized Pareto distribution are analyzed in this respect. Moreover, it is shown that the optimal restart time is also not influenced by scale parameters and that the influence of location parameters is only linear.
Dynamic Conflict-Free Colorings in the Plane
Venue: arXiv cs.CG 2017
Year: 2017

We study dynamic conflict-free colorings in the plane, where the goal is to maintain a conflict-free coloring (CF-coloring for short) under insertions and deletions. - First we consider CF-colorings of a set $S$ of unit squares with respect to points. Our method maintains a CF-coloring that uses $O(\log n)$ colors at any time, where $n$ is the current number of squares in $S$, at the cost of only $O(\log n)$ recolorings per insertion or deletion of a square. We generalize the method to rectangles whose sides have lengths in the range $[1,c]$, where $c$ is a fixed constant. Here the number of used colors becomes $O(\log^2 n)$. The method also extends to arbitrary rectangles whose coordinates come from a fixed universe of size $N$, yielding $O(\log^2 N \log^2 n)$ colors. The number of recolorings for both methods stays in $O(\log n)$. - We then present a general framework to maintain a CF-coloring under insertions for sets of objects that admit a unimax coloring with a small number of colors in the static case. As an application we show how to maintain a CF-coloring with $O(\log^3 n)$ colors for disks (or other objects with linear union complexity) with respect to points at the cost of $O(\log n)$ recolorings per insertion. We extend the framework to the fully-dynamic case when the static unimax coloring admits weak deletions. As an application we show how to maintain a CF-coloring with $O(\sqrt{n} \log^2 n)$ colors for points with respect to rectangles, at the cost of $O(\log n)$ recolorings per insertion and $O(1)$ recolorings per deletion. These are the first results on fully-dynamic CF-colorings in the plane, and the first results for semi-dynamic CF-colorings for non-congruent objects.
Foresight: Rapid Data Exploration Through Guideposts
Venue: arXiv cs.HC 2017
Year: 2017

Current tools for exploratory data analysis (EDA) require users to manually select data attributes, statistical computations and visual encodings. This can be daunting for large-scale, complex data. We introduce Foresight, a visualization recommender system that helps the user rapidly explore large high-dimensional datasets through "guideposts." A guidepost is a visualization corresponding to a pronounced instance of a statistical descriptor of the underlying data, such as a strong linear correlation between two attributes, high skewness or concentration about the mean of a single attribute, or a strong clustering of values. For each descriptor, Foresight initially presents visualizations of the "strongest" instances, based on an appropriate ranking metric. Given these initial guideposts, the user can then look at "nearby" guideposts by issuing "guidepost queries" containing constraints on metric type, metric strength, data attributes, and data values. Thus, the user can directly explore the network of guideposts, rather than the overwhelming space of data attributes and visual encodings. Foresight also provides for each descriptor a global visualization of ranking-metric values to both help orient the user and ensure a thorough exploration process. Foresight facilitates interactive exploration of large datasets using fast, approximate sketching to compute ranking metrics. We also contribute insights on EDA practices of data scientists, summarizing results from an interview study we conducted to inform the design of Foresight.
Unsupervised Domain Adaptation with Copula Models
Venue: arXiv cs.LG 2017
Year: 2017

We study the task of unsupervised domain adaptation, where no labeled data from the target domain is provided during training time. To deal with the potential discrepancy between the source and target distributions, both in features and labels, we exploit a copula-based regression framework. The benefits of this approach are two-fold: (a) it allows us to model a broader range of conditional predictive densities beyond the common exponential family, (b) we show how to leverage Sklar's theorem, the essence of the copula formulation relating the joint density to the copula dependency functions, to find effective feature mappings that mitigate the domain mismatch. By transforming the data to a copula domain, we show on a number of benchmark datasets (including human emotion estimation), and using different regression models for prediction, that we can achieve a more robust and accurate estimation of target labels, compared to recently proposed feature transformation (adaptation) methods.
Learning the Exact Topology of Undirected Consensus Networks
Venue: arXiv cs.SY 2017
Year: 2017

In this article, we present a method to learn the interaction topology of a network of agents undergoing linear consensus updates in a non invasive manner. Our approach is based on multivariate Wiener filtering, which is known to recover spurious edges apart from the true edges in the topology. The main contribution of this work is to show that in the case of undirected consensus networks, all spurious links obtained using Wiener filtering can be identified using frequency response of the Wiener filters. Thus, the exact interaction topology of the agents is unveiled. The method presented requires time series measurements of the state of the agents and does not require any knowledge of link weights. To the best of our knowledge this is the first approach that provably reconstructs the structure of undirected consensus networks with correlated noise. We illustrate the effectiveness of the method developed through numerical simulations as well as experiments on a five node network of Raspberry Pis.
HEPCloud, a New Paradigm for HEP Facilities: CMS Amazon Web Services Investigation
Venue: arXiv cs.DC 2017
Year: 2017

Historically, high energy physics computing has been performed on large purpose-built computing systems. These began as single-site compute facilities, but have evolved into the distributed computing grids used today. Recently, there has been an exponential increase in the capacity and capability of commercial clouds. Cloud resources are highly virtualized and intended to be able to be flexibly deployed for a variety of computing tasks. There is a growing nterest among the cloud providers to demonstrate the capability to perform large-scale scientific computing. In this paper, we discuss results from the CMS experiment using the Fermilab HEPCloud facility, which utilized both local Fermilab resources and virtual machines in the Amazon Web Services Elastic Compute Cloud. We discuss the planning, technical challenges, and lessons learned involved in performing physics workflows on a large-scale set of virtualized resources. In addition, we will discuss the economics and operational efficiencies when executing workflows both in the cloud and on dedicated resources.
Two-Way Energy Trading and Online Planning for Fifth-Generation Communications with Renewables
Venue: arXiv cs.SY 2017
Year: 2017

Future fifth-generation (5G) cellular networks, equipped with energy harvesting devices, are uniquely positioned to closely interoperate with smart grid. New interoperable functionalities are discussed in stochastic two-way energy trading and online planning to improve efficiency and productivity. Challenges lie in the unavailability of a-priori knowledge on future wireless channels, energy pricing and harvesting. Lyapunov optimization techniques are utilized to address the challenges and stochastically optimize energy trading and planning. Particularly, it is able to decouple the optimization of energy trading and planning during individual time slots, hence eliminating the need for joint optimization across a large number of slots.
Automated Program Analysis for Novice Programmers
Venue: arXiv cs.SE 2017
Year: 2017

This paper describes how to adapt a static code analyzer to help novice programmers. Current analyzers have been built to give feedback to experienced programmers who build new applications or systems. The type of feedback and the type of analysis of these tools focusses on mistakes that are relevant within that context, and help with debugging the system. When teaching novice programmers this type of advice is often not particularly useful. It would be instead more useful to use these techniques to find problem in the understanding of students of important programming concepts. This paper first explores in what respect static analyzers support the learning and teaching of programming can be implemented based on existing static analysis technology. It presents an extension to static analyzer PMD was made so that feedback messages appear which are easier to understand for novice programmers. To answer the question if these techniques are able to find conceptual mistakes that are characteristic for novice programmers make, we ran it over a number of student projects, and compared these results with publicly available mature software projects.