OpenRaiser/Intern-Atlas huggingface dataset:
BayesDB: A probabilistic programming system for querying the probable implications of data
Venue: arXiv cs.AI 2015
Year: 2015

Is it possible to make statistical inference broadly accessible to non-statisticians without sacrificing mathematical rigor or inference quality? This paper describes BayesDB, a probabilistic programming platform that aims to enable users to query the probable implications of their data as directly as SQL databases enable them to query the data itself. This paper focuses on four aspects of BayesDB: (i) BQL, an SQL-like query language for Bayesian data analysis, that answers queries by averaging over an implicit space of probabilistic models; (ii) techniques for implementing BQL using a broad class of multivariate probabilistic models; (iii) a semi-parametric Bayesian model-builder that auomatically builds ensembles of factorial mixture models to serve as baselines; and (iv) MML, a "meta-modeling" language for imposing qualitative constraints on the model-builder and combining baseline models with custom algorithmic and statistical models that can be implemented in external software. BayesDB is illustrated using three applications: cleaning and exploring a public database of Earth satellites; assessing the evidence for temporal dependence between macroeconomic indicators; and analyzing a salary survey.
Likelihood of Cyber Data Injection Attacks to Power Systems
Venue: arXiv cs.SY 2015
Year: 2015

Cyber data attacks are the worst-case interacting bad data to power system state estimation and cannot be detected by existing bad data detectors. In this paper, we for the first time analyze the likelihood of cyber data attacks by characterizing the actions of a malicious intruder. We propose to use Markov decision process to model an intruder's strategy, where the objective is to maximize the cumulative reward across time. Linear programming method is employed to find the optimal attack policy from the intruder's perspective. Numerical experiments are conducted to study the intruder's attack strategy in test power systems.
Reality Mining with Mobile Big Data: Understanding the Impact of Network Structure on Propagation Dynamics
Venue: arXiv cs.SI 2015
Year: 2015

Information and epidemic propagation dynamics in complex networks is truly important to discover and control terrorist attack and disease spread. How to track, recognize and model such dynamics is a big challenge. With the popularity of intellectualization and the rapid development of Internet of Things (IoT), massive mobile data is automatically collected by millions of wireless devices (e.g., smart phone and tablet). In this article, as a typical use case, the impact of network structure on epidemic propagation dynamics is investigated by using the mobile data collected from the smart phones carried by the volunteers of Ebola outbreak areas. On this basis, we propose a model to recognize the dynamic structure of a network. Then, we introduce and discuss the open issues and future work for developing the proposed recognition model.
Transfer functions in consensus systems with higher-order dynamics and external inputs
Venue: arXiv cs.SY 2015
Year: 2015

This paper considers transfer functions in consensus systems where agents have identical SISO dynamics of arbitrary order. The interconnecting structure is a directed graph. The transfer functions for various inputs and outputs are presented in simple product forms with a similar structure of the numerator and the denominator. This structure combines the network properties and the agent model in an explicit way. The link between a higher-order and a single-integrator dynamics is shown and the polynomials of the transfer function in the single-integrator system are related to the graph properties. These properties also allow to generalize a result on the minimal dimension of the controllable subspace to the directed graphs.
A Note on "Efficient Algorithms for Secure Outsourcing of Bilinear Pairings"
Venue: arXiv cs.CR 2015
Year: 2015

We show that the verifying equations in the scheme [Theoretical Computer Science, 562 (2015), 112-121] cannot filter out some malformed values returned by the malicious servers. We also remark that the two untrusted programs model adopted in the scheme is somewhat artificial, and discuss some reasonable scenarios for outsourcing computations.
Deep-Spying: Spying using Smartwatch and Deep Learning
Venue: arXiv cs.CR 2015
Year: 2015

Wearable technologies are today on the rise, becoming more common and broadly available to mainstream users. In fact, wristband and armband devices such as smartwatches and fitness trackers already took an important place in the consumer electronics market and are becoming ubiquitous. By their very nature of being wearable, these devices, however, provide a new pervasive attack surface threatening users privacy, among others. In the meantime, advances in machine learning are providing unprecedented possibilities to process complex data efficiently. Allowing patterns to emerge from high dimensional unavoidably noisy data. The goal of this work is to raise awareness about the potential risks related to motion sensors built-in wearable devices and to demonstrate abuse opportunities leveraged by advanced neural network architectures. The LSTM-based implementation presented in this research can perform touchlogging and keylogging on 12-keys keypads with above-average accuracy even when confronted with raw unprocessed data. Thus demonstrating that deep neural networks are capable of making keystroke inference attacks based on motion sensors easier to achieve by removing the need for non-trivial pre-processing pipelines and carefully engineered feature extraction strategies. Our results suggest that the complete technological ecosystem of a user can be compromised when a wearable wristband device is worn.
General Framework for Evaluating Password Complexity and Strength
Venue: arXiv cs.CR 2015
Year: 2015

Although it is common for users to select bad passwords that can be easily cracked by attackers, password-based authentication remains the most widely-used method. To encourage users to select good passwords, enterprises often enforce policies. Such policies have been proven to be ineffectual in practice. Accurate assessment of a password's resistance to cracking attacks is still an unsolved problem, and our work addresses this challenge. Although the best way to determine how difficult it may be to crack a user-selected password is to check its resistance to cracking attacks employed by attackers in the wild, implementing such a strategy at an enterprise would be infeasible in practice. We first formalize the concepts of password complexity and strength with concrete definitions emphasizing their differences. Our framework captures human biases and many known techniques attackers use to recover stolen credentials in real life, such as brute-force attacks. Building on our definitions, we develop a general framework for calculating password complexity and strength that could be used in practice. Our approach is based on the key insight that an attacker's success at cracking a password must be defined by its available computational resources, time, function used to store that password, as well as the topology that bounds that attacker's search space based on that attacker's available inputs, transformations it can use to tweak and explore its inputs, and the path of exploration which can be based on the attacker's perceived probability of success. We also provide a general framework for assessing the accuracy of password complexity and strength estimators that can be used to compare other tools available in the wild.
Learning the Preferences of Ignorant, Inconsistent Agents
Venue: arXiv cs.AI 2015
Year: 2015

An important use of machine learning is to learn what people value. What posts or photos should a user be shown? Which jobs or activities would a person find rewarding? In each case, observations of people's past choices can inform our inferences about their likes and preferences. If we assume that choices are approximately optimal according to some utility function, we can treat preference inference as Bayesian inverse planning. That is, given a prior on utility functions and some observed choices, we invert an optimal decision-making process to infer a posterior distribution on utility functions. However, people often deviate from approximate optimality. They have false beliefs, their planning is sub-optimal, and their choices may be temporally inconsistent due to hyperbolic discounting and other biases. We demonstrate how to incorporate these deviations into algorithms for preference inference by constructing generative models of planning for agents who are subject to false beliefs and time inconsistency. We explore the inferences these models make about preferences, beliefs, and biases. We present a behavioral experiment in which human subjects perform preference inference given the same observations of choices as our model. Results show that human subjects (like our model) explain choices in terms of systematic deviations from optimal behavior and suggest that they take such deviations into account when inferring preferences.
A faster fixed parameter algorithm for two-layer crossing minimization
Venue: arXiv cs.DS 2015
Year: 2015

We give an algorithm that decides whether the bipartite crossing number of a given graph is at most $k$. The running time of the algorithm is upper bounded by $2^{O(k)} + n^{O(1)}$, where $n$ is the number of vertices of the input graph, which improves the previously known algorithm due to Kobayashi et al. (TCS 2014) that runs in $2^{O(k \log k)} + n^{O(1)}$ time. This result is based on a combinatorial upper bound on the number of two-layer drawings of a connected bipartite graph with a bounded crossing number.
Random Generation and Enumeration of Accessible Determinisitic Real-time Pushdown Automata
Venue: arXiv cs.FL 2015
Year: 2015

This papers presents a general framework for the uniform random generation of deterministic real-time accessible pushdown automata. A polynomial time algorithm to randomly generate a pushdown automaton having a fixed stack operations total size is proposed. The influence of the accepting condition (empty stack, final state) on the reachability of the generated automata is investigated.
Can Pretrained Neural Networks Detect Anatomy?
Venue: arXiv cs.CV 2015
Year: 2015

Convolutional neural networks demonstrated outstanding empirical results in computer vision and speech recognition tasks where labeled training data is abundant. In medical imaging, there is a huge variety of possible imaging modalities and contrasts, where annotated data is usually very scarce. We present two approaches to deal with this challenge. A network pretrained in a different domain with abundant data is used as a feature extractor, while a subsequent classifier is trained on a small target dataset; and a deep architecture trained with heavy augmentation and equipped with sophisticated regularization methods. We test the approaches on a corpus of X-ray images to design an anatomy detection system.
On Locally Recoverable (LRC) Codes
Venue: arXiv cs.IT 2015
Year: 2015

We present simple constructions of optimal erasure-correcting LRC codes by exhibiting their parity-check matrices. When the number of local parities in a parity group plus the number of global parities is smaller than the size of the parity group, the constructed codes are optimal with a field of size at least the length of the code. We can reduce the size of the field to at least the size of the parity groups when the number of global parities equals the number of local parities in a parity group plus one.
A Stackelberg Game Model for Overlay D2D Transmission with Heterogeneous Rate Requirements
Venue: arXiv cs.GT 2015
Year: 2015

This paper studies the performance of overlay device-to-device (D2D) communication links via carrier sense multiple access (CSMA) protocols. We assume that the D2D links have heterogeneous rate requirements and different willingness to pay, and each of them acts non-altruistically to achieve its target rate while maximizing its own payoff. Spatial reuse is allowed if the links are not interfering with each other. A non-cooperative game model is used to address the resource allocation among the D2D links, at the same time leveraging on the ideal CSMA network (ICN) model to address the physical channel access issue. We propose a Stackelberg game in which the base station in the cellular network acts as a Stackelberg leader to regulate the individual payoff by modifying the unit service price so that the total D2D throughput is maximized. The problem is shown to be quasi-convex and can be solved by a sequence of equivalent convex optimization problems. The pricing strategies are designed so that the network always operates within the feasible throughput region. The results are verified by simulations.
Combining patch-based strategies and non-rigid registration-based label fusion methods
Venue: arXiv cs.CV 2015
Year: 2015

The objective of this study is to develop a patch-based labeling method that cooperates with a label fusion using non-rigid registrations. We present a novel patch-based label fusion method, whose selected patches and their weights are calculated from a combination of similarity measures between patches using intensity-based distances and labeling-based distances, where a previous labeling of the target image is inferred through a label fusion method using non-rigid registrations. These combined similarity measures result in better selection of the patches, and their weights are more robust, which improves the segmentation results compared to other label fusion methods, including the conventional patch-based labeling method. To evaluate the performance and the robustness of the proposed label fusion method, we employ two available databases of T1-weighted (T1W) magnetic resonance imaging (MRI) of human brains. We compare our approach with other label fusion methods in the automatic hippocampal segmentation from T1W-MRI. Our label fusion method yields mean Dice coefficients of 0.847 and 0.798 for the two databases used with mean times of approximately 180 and 320 seconds, respectively. The collaboration between the patch-based labeling method and the label fusion using non-rigid registrations is given in the several levels: (a) The pre-selection of the patches in the atlases are improved, (b) The weights of our selected patches are also more robust, (c) our approach imposes geometrical restrictions, such as shape priors, and (d) the work-flow is very efficient. We show that the proposed approach is very competitive with respect to recently reported methods.
Process Realizability
Venue: arXiv cs.LO 2015
Year: 2015

We develop a notion of realizability for Classical Linear Logic based on a concurrent process calculus.
Streaming Data Transmission in the Moderate Deviations and Central Limit Regimes
Venue: arXiv cs.IT 2015
Year: 2015

We consider streaming data transmission over a discrete memoryless channel. A new message is given to the encoder at the beginning of each block and the decoder decodes each message sequentially, after a delay of $T$ blocks. In this streaming setup, we study the fundamental interplay between the rate and error probability in the central limit and moderate deviations regimes and show that i) in the moderate deviations regime, the moderate deviations constant improves over the block coding or non-streaming setup by a factor of $T$ and ii) in the central limit regime, the second-order coding rate improves by a factor of approximately $\sqrt{T}$ for a wide range of channel parameters. For both regimes, we propose coding techniques that incorporate a joint encoding of fresh and previous messages. In particular, for the central limit regime, we propose a coding technique with truncated memory to ensure that a summation of constants, which arises as a result of applications of the central limit theorem, does not diverge in the error analysis. Furthermore, we explore interesting variants of the basic streaming setup in the moderate deviations regime. We first consider a scenario with an erasure option at the decoder and show that both the exponents of the total error and the undetected error probabilities improve by factors of $T$. Next, by utilizing the erasure option, we show that the exponent of the total error probability can be improved to that of the undetected error probability (in the order sense) at the expense of a variable decoding delay. Finally, we also extend our results to the case where the message rate is not fixed but alternates between two values.
Maximizing diversity in biology and beyond
Venue: arXiv cs.IT 2015
Year: 2015

Entropy, under a variety of names, has long been used as a measure of diversity in ecology, as well as in genetics, economics and other fields. There is a spectrum of viewpoints on diversity, indexed by a real parameter q giving greater or lesser importance to rare species. Leinster and Cobbold proposed a one-parameter family of diversity measures taking into account both this variation and the varying similarities between species. Because of this latter feature, diversity is not maximized by the uniform distribution on species. So it is natural to ask: which distributions maximize diversity, and what is its maximum value? In principle, both answers depend on q, but our main theorem is that neither does. Thus, there is a single distribution that maximizes diversity from all viewpoints simultaneously, and any list of species has an unambiguous maximum diversity value. Furthermore, the maximizing distribution(s) can be computed in finite time, and any distribution maximizing diversity from some particular viewpoint q > 0 actually maximizes diversity for all q. Although we phrase our results in ecological terms, they apply very widely, with applications in graph theory and metric geometry.
Collaborative Filtering for Predicting User Preferences for Organizing Objects
Venue: arXiv cs.RO 2015
Year: 2015

As service robots become more and more capable of performing useful tasks for us, there is a growing need to teach robots how we expect them to carry out these tasks. However, different users typically have their own preferences, for example with respect to arranging objects on different shelves. As many of these preferences depend on a variety of factors including personal taste, cultural background, or common sense, it is challenging for an expert to pre-program a robot in order to accommodate all potential users. At the same time, it is impractical for robots to constantly query users about how they should perform individual tasks. In this work, we present an approach to learn patterns in user preferences for the task of tidying up objects in containers, e.g., shelves or boxes. Our method builds upon the paradigm of collaborative filtering for making personalized recommendations and relies on data from different users that we gather using crowdsourcing. To deal with novel objects for which we have no data, we propose a method that compliments standard collaborative filtering by leveraging information mined from the Web. When solving a tidy-up task, we first predict pairwise object preferences of the user. Then, we subdivide the objects in containers by modeling a spectral clustering problem. Our solution is easy to update, does not require complex modeling, and improves with the amount of user data. We evaluate our approach using crowdsourcing data from over 1,200 users and demonstrate its effectiveness for two tidy-up scenarios. Additionally, we show that a real robot can reliably predict user preferences using our approach.
On-the fly AES Decryption/Encryption for Cloud SQL Databases
Venue: arXiv cs.DB 2015
Year: 2015

We propose the client-side AES256 encryption for a cloud SQL DB. A column ciphertext is deterministic or probabilistic. We trust the cloud DBMS for security of its run-time values, e.g., through a moving target defense. The client may send AES key(s) with the query. These serve the on-the-fly decryption of selected ciphertext into plaintext for query evaluation. The DBMS clears the key(s) and the plaintext at the query end at latest. It may deliver ciphertext to decryption enabled clients or plaintext otherwise, e.g., to browsers/navigators. The scheme functionally offers to a cloud DBMS capabilities of a plaintext SQL DBMS. AES processing overhead appears negligible for a modern CPU, e.g., a popular Intel I5. The determin-istic encryption may have no storage overhead. The probabilistic one doubles the DB storage. The scheme seems the first generally practical for an outsourced encrypted SQL DB. An implementation sufficient to practice with appears easy. An existing cloud SQL DBMS with UDF support should do.
Towards Integrated Glance To Restructuring in Combinatorial Optimization
Venue: arXiv cs.AI 2015
Year: 2015

The paper focuses on a new class of combinatorial problems which consists in restructuring of solutions (as sets/structures) in combinatorial optimization. Two main features of the restructuring process are examined: (i) a cost of the restructuring, (ii) a closeness to a goal solution. Three types of the restructuring problems are under study: (a) one-stage structuring, (b) multi-stage structuring, and (c) structuring over changed element set. One-criterion and multicriteria problem formulations can be considered. The restructuring problems correspond to redesign (improvement, upgrade) of modular systems or solutions. The restructuring approach is described and illustrated (problem statements, solving schemes, examples) for the following combinatorial optimization problems: knapsack problem, multiple choice problem, assignment problem, spanning tree problems, clustering problem, multicriteria ranking (sorting) problem, morphological clique problem. Numerical examples illustrate the restructuring problems and solving schemes.
Behavioral Modeling for Churn Prediction: Early Indicators and Accurate Predictors of Custom Defection and Loyalty
Venue: arXiv cs.LG 2015
Year: 2015

Churn prediction, or the task of identifying customers who are likely to discontinue use of a service, is an important and lucrative concern of firms in many different industries. As these firms collect an increasing amount of large-scale, heterogeneous data on the characteristics and behaviors of customers, new methods become possible for predicting churn. In this paper, we present a unified analytic framework for detecting the early warning signs of churn, and assigning a "Churn Score" to each customer that indicates the likelihood that the particular individual will churn within a predefined amount of time. This framework employs a brute force approach to feature engineering, then winnows the set of relevant attributes via feature selection, before feeding the final feature-set into a suite of supervised learning algorithms. Using several terabytes of data from a large mobile phone network, our method identifies several intuitive - and a few surprising - early warning signs of churn, and our best model predicts whether a subscriber will churn with 89.4% accuracy.
Geometry-covering Jammer Localization based on Distance Comprehension in Wireless Sensor Networks
Venue: arXiv cs.NI 2015
Year: 2015

Jamming attacks could cause severe damage to Wireless Sensor Networks (WSNs). Once jamming attack occurs, the most urgent work is to get the position information of the jammer. Then safety measures to eliminate the jamming effects can be devised. In this paper, the jammer localization is conducted by geometric covering method to achieve a low energy consumption. And utilizing the power of the jamming signal received by the boundary nodes, a compensating method is composed to reduce the estimating error of the jamming area. At last the localization is conducted by extracting the minimum covering circle of the compensated victim area. Simulations are conducted to test the localization accuracy with the impact of node density, jamming region and radius. Results show that this localization method achieves both good precision and low energy consumption.