OpenRaiser/Intern-Atlas huggingface dataset:
The ALAMO approach to machine learning
Venue: arXiv cs.LG 2017
Year: 2017

ALAMO is a computational methodology for leaning algebraic functions from data. Given a data set, the approach begins by building a low-complexity, linear model composed of explicit non-linear transformations of the independent variables. Linear combinations of these non-linear transformations allow a linear model to better approximate complex behavior observed in real processes. The model is refined, as additional data are obtained in an adaptive fashion through error maximization sampling using derivative-free optimization. Models built using ALAMO can enforce constraints on the response variables to incorporate first-principles knowledge. The ability of ALAMO to generate simple and accurate models for a number of reaction problems is demonstrated. The error maximization sampling is compared with Latin hypercube designs to demonstrate its sampling efficiency. ALAMO's constrained regression methodology is used to further refine concentration models, resulting in models that perform better on validation data and satisfy upper and lower bounds placed on model outputs.
Naturally Combined Shape-Color Moment Invariants under Affine Transformations
Venue: arXiv cs.CV 2017
Year: 2017

We proposed a kind of naturally combined shape-color affine moment invariants (SCAMI), which consider both shape and color affine transformations simultaneously in one single system. In the real scene, color and shape deformations always exist in images simultaneously. Simple shape invariants or color invariants can not be qualified for this situation. The conventional method is just to make a simple linear combination of the two factors. Meanwhile, the manual selection of weights is a complex issue. Our construction method is based on the multiple integration framework. The integral kernel is assigned as the continued product of the shape and color invariant cores. It is the first time to directly derive an invariant to dual affine transformations of shape and color. The manual selection of weights is no longer necessary, and both the shape and color transformations are extended to affine transformation group. With the various of invariant cores, a set of lower-order invariants are constructed and the completeness and independence are discussed detailedly. A set of SCAMIs, which called SCAMI24, are recommended, and the effectiveness and robustness have been evaluated on both synthetic and real datasets.
Analysis of the Effect of Dependency Information on Predicate-Argument Structure Analysis and Zero Anaphora Resolution
Venue: arXiv cs.CL 2017
Year: 2017

This paper investigates and analyzes the effect of dependency information on predicate-argument structure analysis (PASA) and zero anaphora resolution (ZAR) for Japanese, and shows that a straightforward approach of PASA and ZAR works effectively even if dependency information was not available. We constructed an analyzer that directly predicts relationships of predicates and arguments with their semantic roles from a POS-tagged corpus. The features of the system are designed to compensate for the absence of syntactic information by using features used in dependency parsing as a reference. We also constructed analyzers that use the oracle dependency and the real dependency parsing results, and compared with the system that does not use any syntactic information to verify that the improvement provided by dependencies is not crucial.
Time is What Prevents Everything from Happening at Once: Propagation Time-conscious Influence Maximization
Venue: arXiv cs.DB 2017
Year: 2017

The influence maximization (IM) problem as defined in the seminal paper by Kempe et al. has received widespread attention from various research communities, leading to the design of a wide variety of solutions. Unfortunately, this classical IM problem ignores the fact that time taken for influence propagation to reach the largest scope can be significant in realworld social networks, during which the underlying network itself may have evolved. This phenomenon may have considerable adverse impact on the quality of selected seeds and as a result all existing techniques that use this classical definition as their building block generate seeds with suboptimal influence spread. In this paper, we revisit the classical IM problem and propose a more realistic version called PROTEUS-IM (Propagation Time conscious Influence Maximization) to replace it by addressing the aforementioned limitation. Specifically, as influence propagation may take time, we assume that the underlying social network may evolve during influence propagation. Consequently, PROTEUSIM aims to select seeds in the current network to maximize influence spread in the future instance of the network at the end of influence propagation process without assuming complete topological knowledge of the future network. We propose a greedy and a Reverse Reachable (RR) set-based algorithms called PROTEUS-GENIE and PROTEUS-SEER, respectively, to address this problem. Our algorithms utilize the state-of-the-art Forest Fire Model for modeling network evolution during influence propagation to find superior quality seeds. Experimental study on real and synthetic social networks shows that our proposed algorithms consistently outperform state-of-the-art classical IM algorithms with respect to seed set quality.
Implicit Consensus: Blockchain with Unbounded Throughput
Venue: arXiv cs.DC 2017
Year: 2017

Recently, the blockchain technique was put in the spotlight as it introduced a systematic approach for multiple parties to reach consensus without needing trust. However, the application of this technique in practice is severely restricted due to its limitations in throughput. In this paper, we propose a novel consensus model, namely the implicit consensus, with a distinctive blockchain-based distributed ledger in which each node holds its individual blockchain. In our system, the consensus is not on the transactions, but on a special type of blocks called Check Points that are used to validate individual transactions. Our system exploits the ideas of self-interest and spontaneous sharding and achieves unbounded throughput with the transaction reliability that equivalent to traditional Byzantine fault tolerance schemes.
LRSE: A Lightweight Efficient Searchable Encryption Scheme using Local and Global Representations
Venue: arXiv cs.IR 2017
Year: 2017

Cloud computing is emerging as a revolutionary computing paradigm, while security and privacy become major concerns in the cloud scenario. For which Searchable Encryption (SE) technology is proposed to support efficient retrieval of encrypted data. However, the absence of lightweight ranked search with higher search quality in a harsh adversary model is still a typical shortage in existing SE schemes. In this paper, we propose a novel SE scheme called LRSE which firstly integrates machine learning methods into the framework of SE and combines local and global representations of encrypted cloud data to achieve the above design goals. In LRSE, we employ an improved secure kNN scheme to guarantee sufficient privacy protection. Our detailed security analysis shows that LRSE satisfies our formulated privacy requirements. Extensive experiments performed on benchmark datasets demonstrate that LRSE indeed achieves state-of-the-art search quality with lowest system cost.
Generalised Precoded Spatial Modulation for Integrated Wireless Information and Power Transfer
Venue: arXiv cs.IT 2017
Year: 2017

Conventional wireless information transfer by modulating the amplitude, phase or frequency leads to an inevitable Rate-Energy (RE) trade-off in the presence of simultaneous Wireless Power Transfer (WPT). In echoing Varshney's seminal concept of jointly transmitting both information and energy, we propose the so-called Generalised Precoded Spatial Modulation (GPSM) aided Integrated Wireless Information and Power Transfer (IWIPT) concept employing a power-split receiver. The principle of GPSM is that a particular subset of Receive Antennas (RA) is activated and the activation pattern itself conveys useful information. Hence, the novelty of our GPSM aided IWIPT concept is that RA pattern-based information transfer is used in addition to the conventional waveform-based information carried by the classic M-ary modulation. Following the Radio Frequency (RF) to Direct Current (DC) power conversion invoked for WPT at the power-split receiver, the non-coherent detector simply compares the remaining received power accumulated by each legitimate RA pattern for the sake of identifying the most likely RA. This operation is then followed by down-conversion and conventional Base Band (BB) M-ary detection. Both our analysis and simulations show that the RA pattern based information transfer represented in the Spatial Domain (SD) exhibits a beneficial immunity to any potential power conversion induced performance degradation and hence improves the overall RE trade-off when additionally the waveform-based information transfer is also taken into account. Moreover, we investigate the impact of realistic imperfect Channel State Information at the Transmitter (CSIT) as well as that of the antenna correlations encountered. Finally, the system's asymptotic performance is characterised in the context of large-scale Multiple Input Multiple Output (MIMO) systems.
A Logic for Non-Deterministic Parallel Abstract State Machines
Venue: arXiv cs.LO 2017
Year: 2017

We develop a logic which enables reasoning about single steps of non-deterministic parallel Abstract State Machines (ASMs). Our logic builds upon the unifying logic introduced by Nanchen and Stärk for reasoning about hierarchical (parallel) ASMs. Our main contribution to this regard is the handling of non-determinism (both bounded and unbounded) within the logical formalism. Moreover, we do this without sacrificing the completeness of the logic for statements about single steps of non-deterministic parallel ASMs, such as invariants of rules, consistency conditions for rules, or step-by-step equivalence of rules.
Identification of points using disks
Venue: arXiv cs.DM 2017
Year: 2017

We consider the problem of identifying n points in the plane using disks, i.e., minimizing the number of disks so that each point is contained in a disk and no two points are in exactly the same set of disks. This problem can be seen as an instance of the test covering problem with geometric constraints on the tests. We give tight lower and upper bounds on the number of disks needed to identify any set of n points of the plane. In particular, we prove that if there are no three colinear points nor four cocyclic points, then roughly n/3 disks are enough, improving the known bound of (n+1)/2 when we only require that no three points are colinear. We also consider complexity issues when the radius of the disks is fixed, proving that this problem is NP-complete. In contrast, we give a linear-time algorithm computing the exact number of disks if the points are colinear.
Improved Algorithms for MST and Metric-TSP Interdiction
Venue: arXiv cs.DS 2017
Year: 2017

We consider the {\em MST-interdiction} problem: given a multigraph $G = (V, E)$, edge weights $\{w_e\geq 0\}_{e \in E}$, interdiction costs $\{c_e\geq 0\}_{e \in E}$, and an interdiction budget $B\geq 0$, the goal is to remove a set $R\subseteq E$ of edges of total interdiction cost at most $B$ so as to maximize the $w$-weight of an MST of $G-R:=(V,E\setminus R)$. Our main result is a $4$-approximation algorithm for this problem. This improves upon the previous-best $14$-approximation~\cite{Zenklusen15}. Notably, our analysis is also significantly simpler and cleaner than the one in~\cite{Zenklusen15}. Whereas~\cite{Zenklusen15} uses a greedy algorithm with an involved analysis to extract a good interdiction set from an over-budget set, we utilize a generalization of knapsack called the {\em tree knapsack problem} that nicely captures the key combinatorial aspects of this "extraction problem." We prove a simple, yet strong, LP-relative approximation bound for tree knapsack, which leads to our improved guarantees for MST interdiction. Our algorithm and analysis are nearly tight, as we show that one cannot achieve an approximation ratio better than 3 relative to the upper bound used in our analysis (and the one in~\cite{Zenklusen15}). Our guarantee for MST-interdiction yields an $8$-approximation for {\em metric-TSP interdiction} (improving over the $28$-approximation in~\cite{Zenklusen15}). We also show that the {\em maximum-spanning-tree interdiction} problem is at least as hard to approximate as the minimization version of densest-$k$-subgraph.
A Diversified Multi-Start Algorithm for Unconstrained Binary Quadratic Problems Leveraging the Graphics Processor Unit
Venue: arXiv cs.AI 2017
Year: 2017

Multi-start algorithms are a common and effective tool for metaheuristic searches. In this paper we amplify multi-start capabilities by employing the parallel processing power of the graphics processer unit (GPU) to quickly generate a diverse starting set of solutions for the Unconstrained Binary Quadratic Optimization Problem which are evaluated and used to implement screening methods to select solutions for further optimization. This method is implemented as an initial high quality solution generation phase prior to a secondary steepest ascent search and a comparison of results to best known approaches on benchmark unconstrained binary quadratic problems demonstrates that GPU-enabled diversified multi-start with screening quickly yields very good results.
Interference Modeling for Cellular Networks under Beamforming Transmission
Venue: arXiv cs.IT 2017
Year: 2017

We propose analytical models for the interference power distribution in a cellular system employing MIMO beamforming in rich and limited scattering environments, which capture non line-of-sight signal propagation in the microwave and mmWave bands, respectively. Two candidate models are considered: the Inverse Gaussian and the Inverse Weibull, both are two-parameter heavy tail distributions. We further propose a mixture of these two distributions as a model with three parameters. To estimate the parameters of these distributions, three approaches are used: moment matching, individual distribution maximum likelihood estimation (MLE), and mixture distribution MLE with a designed expectation maximization algorithm. We then introduce simple fitted functions for the mixture model parameters as polynomials of the channel path loss exponent and shadowing variance. To measure the goodness of these models, the information-theoretic metric relative entropy is used to capture the distance from the model distribution to a reference one. The interference models are tested against data obtained by simulating a cellular network based on stochastic geometry. The results show that the three-parameter mixture model offers remarkably good fit to simulated interference power. The mixture model is further used to analyze the capacity of a cellular network employing joint transmit and receive beamforming and confirms a good fit with simulation.
Deep Generative Adversarial Networks for Compressed Sensing Automates MRI
Venue: arXiv cs.CV 2017
Year: 2017

Magnetic resonance image (MRI) reconstruction is a severely ill-posed linear inverse task demanding time and resource intensive computations that can substantially trade off {\it accuracy} for {\it speed} in real-time imaging. In addition, state-of-the-art compressed sensing (CS) analytics are not cognizant of the image {\it diagnostic quality}. To cope with these challenges we put forth a novel CS framework that permeates benefits from generative adversarial networks (GAN) to train a (low-dimensional) manifold of diagnostic-quality MR images from historical patients. Leveraging a mixture of least-squares (LS) GANs and pixel-wise $\ell_1$ cost, a deep residual network with skip connections is trained as the generator that learns to remove the {\it aliasing} artifacts by projecting onto the manifold. LSGAN learns the texture details, while $\ell_1$ controls the high-frequency noise. A multilayer convolutional neural network is then jointly trained based on diagnostic quality images to discriminate the projection quality. The test phase performs feed-forward propagation over the generator network that demands a very low computational overhead. Extensive evaluations are performed on a large contrast-enhanced MR dataset of pediatric patients. In particular, images rated based on expert radiologists corroborate that GANCS retrieves high contrast images with detailed texture relative to conventional CS, and pixel-wise schemes. In addition, it offers reconstruction under a few milliseconds, two orders of magnitude faster than state-of-the-art CS-MRI schemes.
Recognizing Handwritten Source Code
Venue: arXiv cs.HC 2017
Year: 2017

Supporting programming on touchscreen devices requires effective text input and editing methods. Unfortunately, the virtual keyboard can be inefficient and uses valuable screen space on already small devices. Recent advances in stylus input make handwriting a potentially viable text input solution for programming on touchscreen devices. The primary barrier, however, is that handwriting recognition systems are built to take advantage of the rules of natural language, not those of a programming language. In this paper, we explore this particular problem of handwriting recognition for source code. We collect and make publicly available a dataset of handwritten Python code samples from 15 participants and we characterize the typical recognition errors for this handwritten Python source code when using a state-of-the-art handwriting recognition tool. We present an approach to improve the recognition accuracy by augmenting a handwriting recognizer with the programming language grammar rules. Our experiment on the collected dataset shows an 8.6% word error rate and a 3.6% character error rate which outperforms standard handwriting recognition systems and compares favorably to typing source code on virtual keyboards.
Free energy-based reinforcement learning using a quantum processor
Venue: arXiv cs.LG 2017
Year: 2017

Recent theoretical and experimental results suggest the possibility of using current and near-future quantum hardware in challenging sampling tasks. In this paper, we introduce free energy-based reinforcement learning (FERL) as an application of quantum hardware. We propose a method for processing a quantum annealer's measured qubit spin configurations in approximating the free energy of a quantum Boltzmann machine (QBM). We then apply this method to perform reinforcement learning on the grid-world problem using the D-Wave 2000Q quantum annealer. The experimental results show that our technique is a promising method for harnessing the power of quantum sampling in reinforcement learning tasks.
The Constant of Proportionality in Lower Bound Constructions of Point-Line Incidences
Venue: arXiv cs.CG 2017
Year: 2017

Let $I(n,l)$ denote the maximum possible number of incidences between $n$ points and $l$ lines. It is well known that $I(n,l) = Θ(n^{2/3}l^{2/3} + n + l)$. Let $c_{\mathrm{SzTr}}$ denote the lower bound on the constant of proportionality of the $n^{2/3}l^{2/3}$ term. The known lower bound, due to Elekes, is $c_{\mathrm{SzTr}} \ge 2^{-2/3} = 0.63$. With a slight modification of Elekes' construction, we show that it can give a better lower bound of $c_{\mathrm{SzTr}} \ge 1$, i.e., $I(n,l) \ge n^{2/3}l^{2/3}$. Furthermore, we analyze a different construction given by Erd{\H o}s, and show its constant of proportionality to be even better, $c_{\mathrm{SzTr}} \ge 3/(2^{1/3}π^{2/3}) \approx 1.11$.
Using GPI-2 for Distributed Memory Paralleliziation of the Caffe Toolbox to Speed up Deep Neural Network Training
Venue: arXiv cs.LG 2017
Year: 2017

Deep Neural Network (DNN) are currently of great inter- est in research and application. The training of these net- works is a compute intensive and time consuming task. To reduce training times to a bearable amount at reasonable cost we extend the popular Caffe toolbox for DNN with an efficient distributed memory communication pattern. To achieve good scalability we emphasize the overlap of computation and communication and prefer fine granu- lar synchronization patterns over global barriers. To im- plement these communication patterns we rely on the the Global address space Programming Interface version 2 (GPI-2) communication library. This interface provides a light-weight set of asynchronous one-sided communica- tion primitives supplemented by non-blocking fine gran- ular data synchronization mechanisms. Therefore, Caf- feGPI is the name of our parallel version of Caffe. First benchmarks demonstrate better scaling behavior com- pared with other extensions, e.g., the Intel TM Caffe. Even within a single symmetric multiprocessing machine with four graphics processing units, the CaffeGPI scales bet- ter than the standard Caffe toolbox. These first results demonstrate that the use of standard High Performance Computing (HPC) hardware is a valid cost saving ap- proach to train large DDNs. I/O is an other bottleneck to work with DDNs in a standard parallel HPC setting, which we will consider in more detail in a forthcoming paper.
A graph model of message passing processes
Venue: arXiv cs.LO 2017
Year: 2017

In the paper we consider a graph model of message passing processes and present a method verification of message passing processes. The method is illustrated by an example of a verification of sliding window protocol.
One button machine for automating feature engineering in relational databases
Venue: arXiv cs.DB 2017
Year: 2017

Feature engineering is one of the most important and time consuming tasks in predictive analytics projects. It involves understanding domain knowledge and data exploration to discover relevant hand-crafted features from raw data. In this paper, we introduce a system called One Button Machine, or OneBM for short, which automates feature discovery in relational databases. OneBM automatically performs a key activity of data scientists, namely, joining of database tables and applying advanced data transformations to extract useful features from data. We validated OneBM in Kaggle competitions in which OneBM achieved performance as good as top 16% to 24% data scientists in three Kaggle competitions. More importantly, OneBM outperformed the state-of-the-art system in a Kaggle competition in terms of prediction accuracy and ranking on Kaggle leaderboard. The results show that OneBM can be useful for both data scientists and non-experts. It helps data scientists reduce data exploration time allowing them to try and error many ideas in short time. On the other hand, it enables non-experts, who are not familiar with data science, to quickly extract value from their data with a little effort, time and cost.
Optimal Slotted ALOHA under Delivery Deadline Constraint for Multiple-Packet Reception
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the slotted ALOHA protocol in a communication channel shared by N users. It is assumed that the channel has the multiple-packet reception (MPR) capability that allows the correct reception of up to M ($1 \leq M < N$) time-overlapping packets. To evaluate the reliability in the scenario that a packet needs to be transmitted within a strict delivery deadline D ($D \geq 1$) (in unit of slot) since its arrival at the head of queue, we consider the successful delivery probability (SDP) of a packet as performance metric of interest. We derive the optimal transmission probability that maximizes the SDP for any $1 \leq M < N$ and any $D \geq 1$, and show it can be computed by a fixed-point iteration. In particular, the case for D = 1 (i.e., throughput maximization) is first completely addressed in this paper. Based on these theoretical results, for real-life scenarios where N may be unknown and changing, we develop a distributed algorithm that enables each user to tune its transmission probability at runtime according to the estimate of N. Simulation results show that the proposed algorithm is effective in dynamic scenarios, with near-optimal performance.