OpenRaiser/Intern-Atlas huggingface dataset:
Fine-Grained Energy Modeling for the Source Code of a Mobile Application
Venue: arXiv cs.OH 2016
Year: 2016

Energy efficiency has a significant influence on user experience of battery-driven devices such as smartphones and tablets. The goal of an energy model for source code is to lay a foundation for the application of energy-saving techniques during software development. The challenge is to relate hardware energy consumption to high-level application code, considering the complex run-time context and software stack. Traditional techniques build the energy model by mapping a hardware energy model onto software constructs; this approach faces obstacles when the software stack consists of a number of abstract layers. Another approach that has been followed is to utilize hardware or operating system features to estimate software energy information at a coarse level of granularity such as blocks, methods or even applications. In this paper, we explain how to construct a fine-grained energy model for the source code, which is based on "energy operations" identified directly from the source code and able to provide more valuable information for code optimization. We apply the approach to a class of applications based on a game-engine, and explain the wider applicability of the method.
Performance Analysis of a Heterogeneous Traffic Scheduler using Large Deviation Principle
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we study the stability of light traffic achieved by a scheduling algorithm which is suitable for heterogeneous traffic networks. Since analyzing a scheduling algorithm is intractable using the conventional mathematical tool, our goal is to minimize the largest queue-overflow probability achieved by the algorithm. In the large deviation setting, this problem is equivalent to maximizing the asymptotic decay rate of the largest queue-overflow probability. We first derive an upper bound on the decay rate of the queue overflow probability as the queue overflow threshold approaches infinity. Then, we study several structural properties of the minimum-cost-path to overflow of the queue with the largest length, which is basically equivalent to the decay rate of the largest queue-overflow probability. Given these properties, we prove that the queue with the largest length follows a sample path with linear increment. For certain parameter value, the scheduling algorithm is asymptotically optimal in reducing the largest queue length. Through numerical results, we have shown the large deviation properties of the queue length typically used in practice while varying one parameter of the algorithm.
A Variational EM Algorithm for the Separation of Time-Varying Convolutive Audio Mixtures
Venue: arXiv cs.SD 2016
Year: 2016

This paper addresses the problem of separating audio sources from time-varying convolutive mixtures. We propose a probabilistic framework based on the local complex-Gaussian model combined with non-negative matrix factorization. The time-varying mixing filters are modeled by a continuous temporal stochastic process. We present a variational expectation-maximization (VEM) algorithm that employs a Kalman smoother to estimate the time-varying mixing matrix, and that jointly estimate the source parameters. The sound sources are then separated by Wiener filters constructed with the estimators provided by the VEM algorithm. Extensive experiments on simulated data show that the proposed method outperforms a block-wise version of a state-of-the-art baseline method.
A Dual Method for Computing Power Transfer Distribution Factors
Venue: arXiv cs.SY 2016
Year: 2016

Power Transfer Distribution Factors (PTDFs) play a crucial role in power grid security analysis, planning, and redispatch. Fast calculation of the PTDFs is therefore of great importance. In this paper, we present a non-approximative dual method of computing PTDFs. It uses power flows along topological cycles of the network but still relies on simple matrix algebra. At the core, our method changes the size of the matrix that needs to be inverted to calculate the PTDFs from $N\times N$, where $N$ is the number of buses, to $(L-N+1)\times (L-N+1)$, where $L$ is the number of lines and $L-N+1$ is the number of independent cycles (closed loops) in the network while remaining mathematically fully equivalent. For power grids containing a relatively small number of cycles, the method can offer a speedup of numerical calculations.
How Good is Multi-Pivot Quicksort?
Venue: arXiv cs.DS 2016
Year: 2016

Multi-Pivot Quicksort refers to variants of classical quicksort where in the partitioning step $k$ pivots are used to split the input into $k + 1$ segments. For many years, multi-pivot quicksort was regarded as impractical, but in 2009 a 2-pivot approach by Yaroslavskiy, Bentley, and Bloch was chosen as the standard sorting algorithm in Sun's Java 7. In 2014 at ALENEX, Kushagra et al. introduced an even faster algorithm that uses three pivots. This paper studies what possible advantages multi-pivot quicksort might offer in general. The contributions are as follows: Natural comparison-optimal algorithms for multi-pivot quicksort are devised and analyzed. The analysis shows that the benefits of using multiple pivots with respect to the average comparison count are marginal and these strategies are inferior to simpler strategies such as the well known median-of-$k$ approach. A substantial part of the partitioning cost is caused by rearranging elements. A rigorous analysis of an algorithm for rearranging elements in the partitioning step is carried out, observing mainly how often array cells are accessed during partitioning. The algorithm behaves best if 3 to 5 pivots are used. Experiments show that this translates into good cache behavior and is closest to predicting observed running times of multi-pivot quicksort algorithms. Finally, it is studied how choosing pivots from a sample affects sorting cost. The study is theoretical in the sense that although the findings motivate design recommendations for multipivot quicksort algorithms that lead to running time improvements over known algorithms in an experimental setting, these improvements are small.
You-Do, I-Learn: Unsupervised Multi-User egocentric Approach Towards Video-Based Guidance
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents an unsupervised approach towards automatically extracting video-based guidance on object usage, from egocentric video and wearable gaze tracking, collected from multiple users while performing tasks. The approach i) discovers task relevant objects, ii) builds a model for each, iii) distinguishes different ways in which each discovered object has been used and iv) discovers the dependencies between object interactions. The work investigates using appearance, position, motion and attention, and presents results using each and a combination of relevant features. Moreover, an online scalable approach is presented and is compared to offline results. The paper proposes a method for selecting a suitable video guide to be displayed to a novice user indicating how to use an object, purely triggered by the user's gaze. The potential assistive mode can also recommend an object to be used next based on the learnt sequence of object interactions. The approach was tested on a variety of daily tasks such as initialising a printer, preparing a coffee and setting up a gym machine.
No Spare Parts: Sharing Part Detectors for Image Categorization
Venue: arXiv cs.CV 2016
Year: 2016

This work aims for image categorization using a representation of distinctive parts. Different from existing part-based work, we argue that parts are naturally shared between image categories and should be modeled as such. We motivate our approach with a quantitative and qualitative analysis by backtracking where selected parts come from. Our analysis shows that in addition to the category parts defining the class, the parts coming from the background context and parts from other image categories improve categorization performance. Part selection should not be done separately for each category, but instead be shared and optimized over all categories. To incorporate part sharing between categories, we present an algorithm based on AdaBoost to jointly optimize part sharing and selection, as well as fusion with the global image representation. We achieve results competitive to the state-of-the-art on object, scene, and action categories, further improving over deep convolutional neural networks.
Discriminative Predicate Path Mining for Fact Checking in Knowledge Graphs
Venue: arXiv cs.DB 2016
Year: 2016

Traditional fact checking by experts and analysts cannot keep pace with the volume of newly created information. It is important and necessary, therefore, to enhance our ability to computationally determine whether some statement of fact is true or false. We view this problem as a link-prediction task in a knowledge graph, and present a discriminative path-based method for fact checking in knowledge graphs that incorporates connectivity, type information, and predicate interactions. Given a statement S of the form (subject, predicate, object), for example, (Chicago, capitalOf, Illinois), our approach mines discriminative paths that alternatively define the generalized statement (U.S. city, predicate, U.S. state) and uses the mined rules to evaluate the veracity of statement S. We evaluate our approach by examining thousands of claims related to history, geography, biology, and politics using a public, million node knowledge graph extracted from Wikipedia and PubMedDB. Not only does our approach significantly outperform related models, we also find that the discriminative predicate path model is easily interpretable and provides sensible reasons for the final determination.
Max-margin Metric Learning for Speaker Recognition
Venue: arXiv cs.SD 2016
Year: 2016

Probabilistic linear discriminant analysis (PLDA) is a popular normalization approach for the i-vector model, and has delivered state-of-the-art performance in speaker recognition. A potential problem of the PLDA model, however, is that it essentially assumes Gaussian distributions over speaker vectors, which is not always true in practice. Additionally, the objective function is not directly related to the goal of the task, e.g., discriminating true speakers and imposters. In this paper, we propose a max-margin metric learning approach to solve the problems. It learns a linear transform with a criterion that the margin between target and imposter trials are maximized. Experiments conducted on the SRE08 core test show that compared to PLDA, the new approach can obtain comparable or even better performance, though the scoring is simply a cosine computation.
Modeling and Analysis for Cache-enabled Cognitive D2D Communications in Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

Exploiting cognition to the cache-enabled device-to-device (D2D) communication underlaying the multi-channel cellular network is the main focus of this paper. D2D pairs perform direct communications via sensing the available cellular channels, bypassing the base station (BS). Dynamic service is considered and the network performance is evaluated with the stochastic geometry. Node locations are first modeled as mutually independent Poisson Point Processes, and the service queueing process is formulated. Then the corresponding tier association and cognitive access protocol are developed. The delay and the length for the queue at the BS and D2D transmitter are further elaborated, with modeling the traffic dynamics of request arrivals and departures as the discrete-time multiserver queue with priorities. Moreover, impacts of the physical layer and content-centric features on the system performance are jointly investigated to provide a valuable insight.
Triangular Alignment (TAME): A Tensor-based Approach for Higher-order Network Alignment
Venue: arXiv cs.CE 2016
Year: 2016

Network alignment has extensive applications in comparative interactomics. Traditional approaches aim to simultaneously maximize the number of conserved edges and the underlying similarity of aligned entities. We propose a novel formulation of the network alignment problem that extends topological similarity to higher-order structures and provides a new objective function that maximizes the number of aligned substructures. This objective function corresponds to an integer programming problem, which is NP-hard. Consequently, we identify a closely related surrogate function whose maximization results in a tensor eigenvector problem. Based on this formulation, we present an algorithm called Triangular AlignMEnt (TAME), which attempts to maximize the number of aligned triangles across networks. Using a case study on the NAPAbench dataset, we show that triangular alignment is capable of producing mappings with high node correctness. We further evaluate our method by aligning yeast and human interactomes. Our results indicate that TAME outperforms the state-of-art alignment methods in terms of conserved triangles. In addition, we show that the number of conserved triangles is more significantly correlated, compared to the conserved edge, with node correctness and co-expression of edges. Our formulation and resulting algorithms can be easily extended to arbitrary motifs.
Observability analysis and state estimation of lithium-ion batteries in the presence of sensor biases
Venue: arXiv cs.SY 2016
Year: 2016

This paper investigates the observability of one of the most commonly used equivalent circuit models (ECMs) for lithium-ion batteries and presents a method to estimate the state of charge (SOC) in the presence of sensor biases, highlighting the importance of observability analysis for choosing appropriate state estimation algorithms. Using a differential geometric approach, necessary and sufficient conditions for the nonlinear ECM to be observable are derived and are shown to be different from the conditions for the observability of the linearised model. It is then demonstrated that biases in the measurements, due to sensor ageing or calibration errors, can be estimated by applying a nonlinear Kalman filter to an augmented model where the biases are incorporated into the state vector. Experiments are carried out on a lithium-ion pouch cell and three types of nonlinear filters, the first-order extended Kalman filter (EKF), the second-order EKF and the unscented Kalman filter (UKF) are applied using experimental data. The different performances of the filters are explained from the point of view of observability.
Approximating Strategic Abilities under Imperfect Information: a Naive Approach
Venue: arXiv cs.MA 2016
Year: 2016

Alternating-time temporal logic (ATL) allows to specify requirements on abilities that different agents should (or should not) possess in a multi-agent system. However, model checking ATL specifications in realistic systems is computationally hard. In particular, if the agents have imperfect information about the global state of the system, the complexity ranges from Delta2P to undecidable, depending on the syntactic and semantic details. The problem is also hard in practice, as evidenced by several recent attempts to tackle it. On the other hand, model checking of alternating epistemic mu-calculus can have a distinctly lower computational complexity. In this work, we look at the idea of approximating the former problem by the verification of its "naive" translations to the latter. In other words, we look at what happens when one uses the (incorrect) fixpoint algorithm to verify formulae of ATL with imperfect information.
Parallel Tensor Compression for Large-Scale Scientific Data
Venue: arXiv cs.NA 2016
Year: 2016

As parallel computing trends towards the exascale, scientific data produced by high-fidelity simulations are growing increasingly massive. For instance, a simulation on a three-dimensional spatial grid with 512 points per dimension that tracks 64 variables per grid point for 128 time steps yields 8~TB of data, assuming double precision. By viewing the data as a dense five-way tensor, we can compute a Tucker decomposition to find inherent low-dimensional multilinear structure, achieving compression ratios of up to 5000 on real-world data sets with negligible loss in accuracy. So that we can operate on such massive data, we present the first-ever distributed-memory parallel implementation for the Tucker decomposition, whose key computations correspond to parallel linear algebra operations, albeit with nonstandard data layouts. Our approach specifies a data distribution for tensors that avoids any tensor data redistribution, either locally or in parallel. We provide accompanying analysis of the computation and communication costs of the algorithms. To demonstrate the compression and accuracy of the method, we apply our approach to real-world data sets from combustion science simulations. We also provide detailed performance results, including parallel performance in both weak and strong scaling experiments.
Freshman or Fresher? Quantifying the Geographic Variation of Internet Language
Venue: arXiv cs.CL 2016
Year: 2016

We present a new computational technique to detect and analyze statistically significant geographic variation in language. Our meta-analysis approach captures statistical properties of word usage across geographical regions and uses statistical methods to identify significant changes specific to regions. While previous approaches have primarily focused on lexical variation between regions, our method identifies words that demonstrate semantic and syntactic variation as well. We extend recently developed techniques for neural language models to learn word representations which capture differing semantics across geographical regions. In order to quantify this variation and ensure robust detection of true regional differences, we formulate a null model to determine whether observed changes are statistically significant. Our method is the first such approach to explicitly account for random variation due to chance while detecting regional variation in word meaning. To validate our model, we study and analyze two different massive online data sets: millions of tweets from Twitter spanning not only four different countries but also fifty states, as well as millions of phrases contained in the Google Book Ngrams. Our analysis reveals interesting facets of language change at multiple scales of geographic resolution -- from neighboring states to distant continents. Finally, using our model, we propose a measure of semantic distance between languages. Our analysis of British and American English over a period of 100 years reveals that semantic variation between these dialects is shrinking.
Emotions, Demographics and Sociability in Twitter Interactions
Venue: arXiv cs.CY 2016
Year: 2016

The social connections people form online affect the quality of information they receive and their online experience. Although a host of socioeconomic and cognitive factors were implicated in the formation of offline social ties, few of them have been empirically validated, particularly in an online setting. In this study, we analyze a large corpus of geo-referenced messages, or tweets, posted by social media users from a major US metropolitan area. We linked these tweets to US Census data through their locations. This allowed us to measure emotions expressed in the tweets posted from an area, the structure of social connections, and also use that area's socioeconomic characteristics in analysis. %We extracted the structure of online social interactions from the people mentioned in tweets from that area. We find that at an aggregate level, places where social media users engage more deeply with less diverse social contacts are those where they express more negative emotions, like sadness and anger. Demographics also has an impact: these places have residents with lower household income and education levels. Conversely, places where people engage less frequently but with diverse contacts have happier, more positive messages posted from them and also have better educated, younger, more affluent residents. Results suggest that cognitive factors and offline characteristics affect the quality of online interactions. Our work highlights the value of linking social media data to traditional data sources, such as US Census, to drive novel analysis of online behavior.
Reviewer Integration and Performance Measurement for Malware Detection
Venue: arXiv cs.CR 2016
Year: 2016

We present and evaluate a large-scale malware detection system integrating machine learning with expert reviewers, treating reviewers as a limited labeling resource. We demonstrate that even in small numbers, reviewers can vastly improve the system's ability to keep pace with evolving threats. We conduct our evaluation on a sample of VirusTotal submissions spanning 2.5 years and containing 1.1 million binaries with 778GB of raw feature data. Without reviewer assistance, we achieve 72% detection at a 0.5% false positive rate, performing comparable to the best vendors on VirusTotal. Given a budget of 80 accurate reviews daily, we improve detection to 89% and are able to detect 42% of malicious binaries undetected upon initial submission to VirusTotal. Additionally, we identify a previously unnoticed temporal inconsistency in the labeling of training datasets. We compare the impact of training labels obtained at the same time training data is first seen with training labels obtained months later. We find that using training labels obtained well after samples appear, and thus unavailable in practice for current training data, inflates measured detection by almost 20 percentage points. We release our cluster-based implementation, as well as a list of all hashes in our evaluation and 3% of our entire dataset.
Location-Enhanced Authenticated Key Exchange
Venue: arXiv cs.CR 2016
Year: 2016

We introduce LOCATHE (Location-Enhanced Authenticated Key Exchange), a generic protocol that pools location, user attributes, access policy and desired services into a multi-factor authentication, allowing two peers to establish a secure, encrypted session and perform mutual authentication with pre-shared keys, passwords and other authentication factors. LOCATHE contributes to: (1) forward secrecy through ephemeral session keys; (2) security through zero-knowledge password proofs (ZKPP), such that no passwords can be learned from the exchange; (3) the ability to use not only location, but also multiple authentication factors from a user to a service; (4) providing a two-tiered privacy authentication scheme, in which a user may be authenticated either based on her attributes (hiding her unique identification), or with a full individual authentication; (5) employing the expressiveness and flexibility of Decentralized or Multi-Authority Ciphertext-Policy Attribute-Based Encryption, allowing multiple service providers to control their respective key generation and attributes.