OpenRaiser/Intern-Atlas huggingface dataset:
Computational Soundness for Dalvik Bytecode
Venue: arXiv cs.CR 2016
Year: 2016

Automatically analyzing information flow within Android applications that rely on cryptographic operations with their computational security guarantees imposes formidable challenges that existing approaches for understanding an app's behavior struggle to meet. These approaches do not distinguish cryptographic and non-cryptographic operations, and hence do not account for cryptographic protections: f(m) is considered sensitive for a sensitive message m irrespective of potential secrecy properties offered by a cryptographic operation f. These approaches consequently provide a safe approximation of the app's behavior, but they mistakenly classify a large fraction of apps as potentially insecure and consequently yield overly pessimistic results. In this paper, we show how cryptographic operations can be faithfully included into existing approaches for automated app analysis. To this end, we first show how cryptographic operations can be expressed as symbolic abstractions within the comprehensive Dalvik bytecode language. These abstractions are accessible to automated analysis, and they can be conveniently added to existing app analysis tools using minor changes in their semantics. Second, we show that our abstractions are faithful by providing the first computational soundness result for Dalvik bytecode, i.e., the absence of attacks against our symbolically abstracted program entails the absence of any attacks against a suitable cryptographic program realization. We cast our computational soundness result in the CoSP framework, which makes the result modular and composable.
TerpreT: A Probabilistic Programming Language for Program Induction
Venue: arXiv cs.LG 2016
Year: 2016

We study machine learning formulations of inductive program synthesis; given input-output examples, we try to synthesize source code that maps inputs to corresponding outputs. Our aims are to develop new machine learning approaches based on neural networks and graphical models, and to understand the capabilities of machine learning techniques relative to traditional alternatives, such as those based on constraint solving from the programming languages community. Our key contribution is the proposal of TerpreT, a domain-specific language for expressing program synthesis problems. TerpreT is similar to a probabilistic programming language: a model is composed of a specification of a program representation (declarations of random variables) and an interpreter describing how programs map inputs to outputs (a model connecting unknowns to observations). The inference task is to observe a set of input-output examples and infer the underlying program. TerpreT has two main benefits. First, it enables rapid exploration of a range of domains, program representations, and interpreter models. Second, it separates the model specification from the inference algorithm, allowing like-to-like comparisons between different approaches to inference. From a single TerpreT specification we automatically perform inference using four different back-ends. These are based on gradient descent, linear program (LP) relaxations for graphical models, discrete satisfiability solving, and the Sketch program synthesis system. We illustrate the value of TerpreT by developing several interpreter models and performing an empirical comparison between alternative inference algorithms. Our key empirical finding is that constraint solvers dominate the gradient descent and LP-based formulations. We conclude with suggestions for the machine learning community to make progress on program synthesis.
Natural Language Processing using Hadoop and KOSHIK
Venue: arXiv cs.CL 2016
Year: 2016

Natural language processing, as a data analytics related technology, is used widely in many research areas such as artificial intelligence, human language processing, and translation. At present, due to explosive growth of data, there are many challenges for natural language processing. Hadoop is one of the platforms that can process the large amount of data required for natural language processing. KOSHIK is one of the natural language processing architectures, and utilizes Hadoop and contains language processing components such as Stanford CoreNLP and OpenNLP. This study describes how to build a KOSHIK platform with the relevant tools, and provides the steps to analyze wiki data. Finally, it evaluates and discusses the advantages and disadvantages of the KOSHIK architecture, and gives recommendations on improving the processing performance.
Distributed Charging Control in Broadband Wireless Power Transfer Networks
Venue: arXiv cs.NI 2016
Year: 2016

Wireless power transfer (WPT) technology provides a cost-effective solution to achieve sustainable energy supply in wireless networks, where WPT-enabled energy nodes (ENs) can charge wireless devices (WDs) remotely without interruption to the use. However, in a heterogeneous WPT network with distributed ENs and WDs, some WDs may quickly deplete their batteries due to the lack of timely wireless power supply by the ENs, thus resulting in short network operating lifetime. In this paper, we exploit frequency diversity in a broadband WPT network and study the distributed charging control by ENs to maximize network lifetime. In particular, we propose a practical voting-based distributed charging control framework where each WD simply estimates the broadband channel, casts its vote(s) for some strong sub-channel(s) and sends to the ENs along with its battery state information, based on which the ENs independently allocate their transmit power over the sub-channels without the need of centralized control. Under this framework, we aim to design lifetime-maximizing power allocation and efficient voting-based feedback methods. Towards this end, we first derive the general expression of the expected lifetime of a WPT network and draw the general design principles for lifetime-maximizing charging control. Based on the analysis, we then propose a distributed charging control protocol with voting-based feedback, where the power allocated to sub-channels at each EN is a function of the weighted sum vote received from all WDs. Besides, the number of votes cast by a WD and the weight of each vote are related to its current battery state. Simulation results show that the proposed distributed charging control protocol could significantly increase the network lifetime under stringent transmit power constraint in a broadband WPT network.
Unbiased Learning-to-Rank with Biased Feedback
Venue: arXiv cs.IR 2016
Year: 2016

Implicit feedback (e.g., clicks, dwell times, etc.) is an abundant source of data in human-interactive systems. While implicit feedback has many advantages (e.g., it is inexpensive to collect, user centric, and timely), its inherent biases are a key obstacle to its effective use. For example, position bias in search rankings strongly influences how many clicks a result receives, so that directly using click data as a training signal in Learning-to-Rank (LTR) methods yields sub-optimal results. To overcome this bias problem, we present a counterfactual inference framework that provides the theoretical basis for unbiased LTR via Empirical Risk Minimization despite biased data. Using this framework, we derive a Propensity-Weighted Ranking SVM for discriminative learning from implicit feedback, where click models take the role of the propensity estimator. In contrast to most conventional approaches to de-bias the data using click models, this allows training of ranking functions even in settings where queries do not repeat. Beyond the theoretical support, we show empirically that the proposed learning method is highly effective in dealing with biases, that it is robust to noise and propensity model misspecification, and that it scales efficiently. We also demonstrate the real-world applicability of our approach on an operational search engine, where it substantially improves retrieval performance.
Observer Placement for Source Localization: The Effect of Budgets and Transmission Variance
Venue: arXiv cs.SI 2016
Year: 2016

When an epidemic spreads in a network, a key question is where was its source, i.e., the node that started the epidemic. If we know the time at which various nodes were infected, we can attempt to use this information in order to identify the source. However, maintaining observer nodes that can provide their infection time may be costly, and we may have a budget $k$ on the number of observer nodes we can maintain. Moreover, some nodes are more informative than others due to their location in the network. Hence, a pertinent question arises: Which nodes should we select as observers in order to maximize the probability that we can accurately identify the source? Inspired by the simple setting in which the node-to-node delays in the transmission of the epidemic are deterministic, we develop a principled approach for addressing the problem even when transmission delays are random. We show that the optimal observer-placement differs depending on the variance of the transmission delays and propose approaches in both low- and high-variance settings. We validate our methods by comparing them against state-of-the-art observer-placements and show that, in both settings, our approach identifies the source with higher accuracy.
Higher-Order Kullback-Leibler Aggregation of Markov Chains
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of reducing a first-order Markov chain on a large alphabet to a higher-order Markov chain on a small alphabet. We present information-theoretic cost functions that are related to predictability and lumpability, show relations between these cost functions, and discuss heuristics to minimize them. Our experiments suggest that the generalization to higher orders is useful for model reduction in reliability analysis and natural language processing.
The Generalized Metastable Switch Memristor Model
Venue: arXiv cs.ET 2016
Year: 2016

Memristor device modeling is currently a heavily researched topic and is becoming ever more important as memristor devices make their way into CMOS circuit designs, necessitating accurate and efficient memristor circuit simulations. In this paper, the Generalized Metastable Switch (MSS) memristor model is presented. The Generalized MSS model consists of a voltage-dependent stochastic component and a voltage-dependent exponential diode current component and is designed to be easy to implement, computationally efficient, and amenable to modeling a wide range of different memristor devices.
Informal Physical Reasoning Processes
Venue: arXiv cs.AI 2016
Year: 2016

A fundamental question is whether Turing machines can model all reasoning processes. We introduce an existence principle stating that the perception of the physical existence of any Turing program can serve as a physical causation for the application of any Turing-computable function to this Turing program. The existence principle overcomes the limitation of the outputs of Turing machines to lists, that is, recursively enumerable sets. The principle is illustrated by productive partial functions for productive sets such as the set of the Goedel numbers of the Turing-computable total functions. The existence principle and productive functions imply the existence of physical systems whose reasoning processes cannot be modeled by Turing machines. These systems are called creative. Creative systems can prove the undecidable formula in Goedel's theorem in another formal system which is constructed at a later point in time. A hypothesis about creative systems, which is based on computer experiments, is introduced.
A Note on Relaxation and Rounding in Algorithmic Mechanism Design
Venue: arXiv cs.GT 2016
Year: 2016

In this note, we revisit the \emph{relaxation and rounding} technique employed several times in algorithmic mechanism design. We try to introduce a general framework which covers the most significant algorithms in mechanism design that use the relaxation and rounding technique. We believe that this framework is not only a generalization of the existing algorithms but also can be leveraged for further results in algorithmic mechanism design. Before presenting the framework, we briefly define algorithmic mechanism design, its connections to game theory and computer science, and the challenges in the field.
Non-Uniform Linear Antenna Array Design and Optimization for Millimeter Wave Communications
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we investigate the optimization of non-uniform linear antenna arrays (NULAs) for millimeter wave (mmWave) line-of-sight (LoS) multiple-input multiple-output (MIMO) channels. Our focus is on the maximization of the system effective multiplexing gain (EMG), by optimizing the individual antenna positions in the transmit/receive NULAs. Here the EMG is defined as the number of signal streams that are practically supported by the channel at a finite SNR. We first derive analytical expressions for the asymptotic channel eigenvalues with arbitrarily deployed NULAs when, asymptotically, the end-to-end distance is sufficiently large compared to the aperture sizes of the transmit/receive NULAs. Based on the derived expressions, we prove that, the asymptotically optimal NULA deployment that maximizes the achievable EMG should follow the groupwise Fekete-point distribution. Specifically, the antennas should be physically grouped into K separate uniform linear antenna arrays (ULAs) with the minimum feasible antenna spacing within each ULA, where K is the target EMG to be achieved; in addition, the centers of these K ULAs follow the Fekete-point distribution. We numerically verify the asymptotic optimality of such an NULA deployment and extend it to a groupwise projected arch type (PAT) NULA deployment, which provides a more practical option for mmWave LoS MIMO systems with realistic non-asymptotic configurations. Numerical examples are provided to demonstrate a significant capacity gain of the optimized NULAs over traditional ULAs.
Application of multiview techniques to NHANES dataset
Venue: arXiv cs.LG 2016
Year: 2016

Disease prediction or classification using health datasets involve using well-known predictors associated with the disease as features for the models. This study considers multiple data components of an individual's health, using the relationship between variables to generate features that may improve the performance of disease classification models. In order to capture information from different aspects of the data, this project uses a multiview learning approach, using Canonical Correlation Analysis (CCA), a technique that finds projections with maximum correlations between two data views. Data categories collected from the NHANES survey (1999-2014) are used as views to learn the multiview representations. The usefulness of the representations is demonstrated by applying them as features in a Diabetes classification task.
Quicksort with median of medians is considered practical
Venue: arXiv cs.DS 2016
Year: 2016

The linear pivot selection algorithm, known as median-of-medians, makes the worst case complexity of quicksort be $\mathrm{O}(n\ln n)$. Nevertheless, it has often been said that this algorithm is too expensive to use in quicksort. In this article, we show that we can make the quicksort with this kind of pivot selection approach be efficient.
Demystifying Competition and Cooperation Dynamics of the Aerial mmWave Access Market
Venue: arXiv cs.GT 2016
Year: 2016

Cellular has always relied on static deployments for providing wireless access. However, even the emerging fifth-generation (5G) networks may face difficulty in supporting the increased traffic demand with rigid, fixed infrastructure without substantial over-provisioning. This is particularly true for spontaneous large-scale events that require service providers to augment capacity of their networks quickly. Today, the use of aerial devices equipped with high-rate radio access capabilities has the potential to offer the much needed "on-demand" capacity boost. Conversely, it also threatens to rattle the long-standing business strategies of wireless operators, especially as the "gold rush" for cheaper millimeter wave (mmWave) spectrum lowers the market entry barriers. However, the intricate structure of this new market presently remains a mystery. This paper sheds light on competition and cooperation behavior of dissimilar aerial mmWave access suppliers, concurrently employing licensed and license-exempt frequency bands, by modeling it as a vertically differentiated market where customers have varying preferences in price and quality. To understand viable service provider strategies, we begin with constructing the Nash equilibrium for the initial market competition by employing the Bertrand and Cournot games. We then conduct a unique assessment of short-term market dynamics, where two licensed-band service providers may cooperate to improve their competition positions against the unlicensed-band counterpart intruding the market. Our unprecedented analysis studies the effects of various market interactions, price-driven demand evolution, and dynamic profit balance in this novel type of ecosystem.
Frame- and Segment-Level Features and Candidate Pool Evaluation for Video Caption Generation
Venue: arXiv cs.CV 2016
Year: 2016

We present our submission to the Microsoft Video to Language Challenge of generating short captions describing videos in the challenge dataset. Our model is based on the encoder--decoder pipeline, popular in image and video captioning systems. We propose to utilize two different kinds of video features, one to capture the video content in terms of objects and attributes, and the other to capture the motion and action information. Using these diverse features we train models specializing in two separate input sub-domains. We then train an evaluator model which is used to pick the best caption from the pool of candidates generated by these domain expert models. We argue that this approach is better suited for the current video captioning task, compared to using a single model, due to the diversity in the dataset. Efficacy of our method is proven by the fact that it was rated best in MSR Video to Language Challenge, as per human evaluation. Additionally, we were ranked second in the automatic evaluation metrics based table.
The BioDynaMo Project: Creating a Platform for Large-Scale Reproducible Biological Simulations
Venue: arXiv cs.DC 2016
Year: 2016

Computer simulations have become a very powerful tool for scientific research. In order to facilitate research in computational biology, the BioDynaMo project aims at a general platform for biological computer simulations, which should be executable on hybrid cloud computing systems. This paper describes challenges and lessons learnt during the early stages of the software development process, in the context of implementation issues and the international nature of the collaboration.
A Unified Finite Element Method for Fluid-Structure Interaction
Venue: arXiv cs.CE 2016
Year: 2016

In this article, we present a new unified finite element method (UFEM) for simulation of general Fluid-Structure interaction (FSI) which has the same generality and robustness as monolithic methods but is significantly more computationally efficient and easier to implement. Our proposed approach has similarities with classical immersed finite element methods (IFEMs), by approximating a single velocity and pressure field in the entire domain (i.e. occupied by fluid and solid) on a single mesh, but differs by treating the corrections due to the solid deformation on the left-hand side of the modified fluid flow equations (i.e. implicitly). The method is described in detail, followed by the presentation of multiple computational examples in order to validate it across a wide range of fluid and solid parameters and interactions.
A Fast Pseudo-Stochastic Sequential Cipher Generator Based on RBMs
Venue: arXiv cs.CR 2016
Year: 2016

Based on Restricted Boltzmann Machines (RBMs), an improved pseudo-stochastic sequential cipher generator is proposed. It is effective and efficient because of the two advantages: this generator includes a stochastic neural network that can perform the calculation in parallel, that is to say, all elements are calculated simultaneously; unlimited number of sequential ciphers can be generated simultaneously for multiple encryption schemas. The periodicity and the correlation of the output sequential ciphers meet the requirements for the design of encrypting sequential data. In the experiment, the generated sequential cipher is used to encrypt the image, and better performance is achieved in terms of the key space analysis, the correlation analysis, the sensitivity analysis and the differential attack. The experimental result is promising that could promote the development of image protection in computer security.
Introduction to the Case Management Model and Notation (CMMN)
Venue: arXiv cs.SE 2016
Year: 2016

This is a short tutorial of the Case Management Model and Notation (CMMN) version 1.0. It is targeted to readers with knowledge of basic process or workflow modeling, and it covers the complete CMMN notation. A simple complaints process is used to demonstrate the notation. At the end of the tutorial the reader will be able to understand and create CMMN models. An appendix summarizing the notation is included for reference purposes.
Path-based vs. Distributional Information in Recognizing Lexical Semantic Relations
Venue: arXiv cs.CL 2016
Year: 2016

Recognizing various semantic relations between terms is beneficial for many NLP tasks. While path-based and distributional information sources are considered complementary for this task, the superior results the latter showed recently suggested that the former's contribution might have become obsolete. We follow the recent success of an integrated neural method for hypernymy detection (Shwartz et al., 2016) and extend it to recognize multiple relations. The empirical results show that this method is effective in the multiclass setting as well. We further show that the path-based information source always contributes to the classification, and analyze the cases in which it mostly complements the distributional information.
Females' Enrollment and Completion in Science, Technology, Engineering, and Mathematics Massive Open Online Courses
Venue: arXiv cs.CY 2016
Year: 2016

Massive Open Online Courses (MOOCs) have the potential to democratize education by providing learners with access to rich sources of information. However, evidence supporting this democratization across countries is limited. We explored the question of democratization by investigating whether females from different countries were more likely to enroll in and complete STEM MOOCs compared with males. We found that whereas females were less likely to enroll in STEM MOOCs, they were equally likely to complete them. We found smaller gender gaps in STEM MOOC enrollment in less economically developed countries. Further, females were more likely than males to complete STEM MOOCs in countries identified as having a high potential to become the largest economies in the 21st century.