OpenRaiser/Intern-Atlas huggingface dataset:
Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm
Venue: arXiv cs.DS 2018
Year: 2018

Blomer and Naewe[BN09] modified the randomized sieving algorithm of Ajtai, Kumar and Sivakumar[AKS01] to solve the shortest vector problem (SVP). The algorithm starts with $N = 2^{O(n)}$ randomly chosen vectors in the lattice and employs a sieving procedure to iteratively obtain shorter vectors in the lattice. The running time of the sieving procedure is quadratic in $N$. We study this problem for the special but important case of the $\ell_\infty$ norm. We give a new sieving procedure that runs in time linear in $N$, thereby significantly improving the running time of the algorithm for SVP in the $\ell_\infty$ norm. As in [AKS02,BN09], we also extend this algorithm to obtain significantly faster algorithms for approximate versions of the shortest vector problem and the closest vector problem (CVP) in the $\ell_\infty$ norm. We also show that the heuristic sieving algorithms of Nguyen and Vidick[NV08] and Wang et al.[WLTB11] can also be analyzed in the $\ell_{\infty}$ norm. The main technical contribution in this part is to calculate the expected volume of intersection of a unit ball centred at origin and another ball of a different radius centred at a uniformly random point on the boundary of the unit ball. This might be of independent interest.
Deciding and Interpolating Algebraic Data Types by Reduction (Technical Report)
Venue: arXiv cs.LO 2018
Year: 2018

Recursive algebraic data types (term algebras, ADTs) are one of the most well-studied theories in logic, and find application in contexts including functional programming, modelling languages, proof assistants, and verification. At this point, several state-of-the-art theorem provers and SMT solvers include tailor-made decision procedures for ADTs, and version 2.6 of the SMT-LIB standard includes support for ADTs. We study an extremely simple approach to decide satisfiability of ADT constraints, the reduction of ADT constraints to equisatisfiable constraints over uninterpreted functions (EUF) and linear integer arithmetic (LIA). We show that the reduction approach gives rise to both decision and Craig interpolation procedures in (extensions of) ADTs.
Cumulant Generating Function of Codeword Lengths in Variable-Length Lossy Compression Allowing Positive Excess Distortion Probability
Venue: arXiv cs.IT 2018
Year: 2018

This paper considers the problem of variable-length lossy source coding. The performance criteria are the excess distortion probability and the cumulant generating function of codeword lengths. We derive a non-asymptotic fundamental limit of the cumulant generating function of codeword lengths allowing positive excess distortion probability. It is shown that the achievability and converse bounds are characterized by the Rényi entropy-based quantity. In the proof of the achievability result, the explicit code construction is provided. Further, we investigate an asymptotic single-letter characterization of the fundamental limit for a stationary memoryless source.
Gaussian 1-2-1 Networks: Capacity Results for mmWave Communications
Venue: arXiv cs.IT 2018
Year: 2018

This paper proposes a new model for wireless relay networks referred to as "1-2-1 network", where two nodes can communicate only if they point "beams" at each other, while if they do not point beams at each other, no signal can be exchanged or interference can be generated. This model is motivated by millimeter wave communications where, due to the high path loss, a link between two nodes can exist only if beamforming gain at both sides is established, while in the absence of beamforming gain the signal is received well below the thermal noise floor. The main result in this paper is that the 1-2-1 network capacity can be approximated by routing information along at most $2N+2$ paths, where $N$ is the number of relays connecting a source and a destination through an arbitrary topology.
On Division Polynomial PIT and Supersingularity
Venue: arXiv cs.SC 2018
Year: 2018

For an elliptic curve $E$ over a finite field $\F_q$, where $q$ is a prime power, we propose new algorithms for testing the supersingularity of $E$. Our algorithms are based on the Polynomial Identity Testing (PIT) problem for the $p$-th division polynomial of $E$. In particular, an efficient algorithm using points of high order on $E$ is given.
Violable Contracts and Governance for Blockchain Applications
Venue: arXiv cs.CY 2018
Year: 2018

We examine blockchain technologies, especially smart contracts, as a platform for decentralized applications. By providing a basis for consensus, blockchain promises to upend business models that presuppose a central authority. However, blockchain suffers from major shortcomings arising from an over-regimented way of organizing computation that limits its prospects. We propose a sociotechnical, yet computational, perspective that avoids those shortcomings. A centerpiece of our vision is the notion of a declarative, violable contract in contradistinction to smart contracts. This new way of thinking enables flexible governance, by formalizing organizational structures; verification of correctness without obstructing autonomy; and a meaningful basis for trust.
Near Maximum Likelihood Decoding with Deep Learning
Venue: arXiv cs.IT 2018
Year: 2018

A novel and efficient neural decoder algorithm is proposed. The proposed decoder is based on the neural Belief Propagation algorithm and the Automorphism Group. By combining neural belief propagation with permutations from the Automorphism Group we achieve near maximum likelihood performance for High Density Parity Check codes. Moreover, the proposed decoder significantly improves the decoding complexity, compared to our earlier work on the topic. We also investigate the training process and show how it can be accelerated. Simulations of the hessian and the condition number show why the learning process is accelerated. We demonstrate the decoding algorithm for various linear block codes of length up to 63 bits.
Structural Results and Improved Upper Bounds on the Capacity of the Discrete-Time Poisson Channel
Venue: arXiv cs.IT 2018
Year: 2018

New capacity upper bounds are presented for the discrete-time Poisson channel with no dark current and an average-power constraint. These bounds are a simple consequence of techniques developed for the seemingly unrelated problem of upper bounding the capacity of binary deletion and repetition channels. Previously, the best known capacity upper bound in the regime where the average-power constraint does not approach zero was due to Martinez (JOSA B, 2007), which is re-derived as a special case of the framework developed in this paper. Furthermore, this framework is carefully instantiated in order to obtain a closed-form bound that noticeably improves the result of Martinez everywhere. Finally, capacity-achieving distributions for the discrete-time Poisson channel are studied under an average-power constraint and/or a peak-power constraint and arbitrary dark current. In particular, it is shown that the support of the capacity-achieving distribution under an average-power constraint only must be countably infinite. This settles a conjecture of Shamai (IEE Proceedings I, 1990) in the affirmative. Previously, it was only known that the support must be unbounded.
Compressing Deep Neural Networks: A New Hashing Pipeline Using Kac's Random Walk Matrices
Venue: arXiv cs.LG 2018
Year: 2018

The popularity of deep learning is increasing by the day. However, despite the recent advancements in hardware, deep neural networks remain computationally intensive. Recent work has shown that by preserving the angular distance between vectors, random feature maps are able to reduce dimensionality without introducing bias to the estimator. We test a variety of established hashing pipelines as well as a new approach using Kac's random walk matrices. We demonstrate that this method achieves similar accuracy to existing pipelines.
Novel Methods for Enhancing the Performance of Genetic Algorithms
Venue: arXiv cs.NE 2018
Year: 2018

In this thesis we propose new methods for crossover operator namely: cut on worst gene (COWGC), cut on worst L+R gene (COWLRGC) and Collision Crossovers. And also we propose several types of mutation operator such as: worst gene with random gene mutation (WGWRGM) , worst LR gene with random gene mutation (WLRGWRGM), worst gene with worst gene mutation (WGWWGM), worst gene with nearest neighbour mutation (WGWNNM), worst gene with the worst around the nearest neighbour mutation (WGWWNNM), worst gene inserted beside nearest neighbour mutation (WGIBNNM), random gene inserted beside nearest neighbour mutation (RGIBNNM), Swap worst gene locally mutation (SWGLM), Insert best random gene before worst gene mutation (IBRGBWGM) and Insert best random gene before random gene mutation (IBRGBRGM). In addition to proposing four selection strategies, namely: select any crossover (SAC), select any mutation (SAM), select best crossover (SBC) and select best mutation (SBM). The first two are based on selection of the best crossover and mutation operator respectively, and the other two strategies randomly select any operator. So we investigate the use of more than one crossover/mutation operator (based on the proposed strategies) to enhance the performance of genetic algorithms. Our experiments, conducted on several Travelling Salesman Problems (TSP), show the superiority of some of the proposed methods in crossover and mutation over some of the well-known crossover and mutation operators described in the literature. In addition, using any of the four strategies (SAC, SAM, SBC and SBM), found to be better than using one crossover/mutation operator in general, because those allow the GA to avoid local optima, or the so-called premature convergence. Keywords: GAs, Collision crossover, Multi crossovers, Multi mutations, TSP.
Malware detection techniques for mobile devices
Venue: arXiv cs.CR 2018
Year: 2018

Mobile devices have become very popular nowadays, due to its portability and high performance, a mobile device became a must device for persons using information and communication technologies. In addition to hardware rapid evolution, mobile applications are also increasing in their complexity and performance to cover most needs of their users. Both software and hardware design focused on increasing performance and the working hours of a mobile device. Different mobile operating systems are being used today with different platforms and different market shares. Like all information systems, mobile systems are prone to malware attacks. Due to the personality feature of mobile devices, malware detection is very important and is a must tool in each device to protect private data and mitigate attacks. In this paper, analysis of different malware detection techniques used for mobile operating systems is provides. The focus of the analysis will be on the to two competing mobile operating systems - Android and iOS. Finally, an assessment of each technique and a summary of its advantages and disadvantages is provided. The aim of the work is to establish a basis for developing a mobile malware detection tool based on user profiling.
Less is More: Culling the Training Set to Improve Robustness of Deep Neural Networks
Venue: arXiv cs.CR 2018
Year: 2018

Deep neural networks are vulnerable to adversarial examples. Prior defenses attempted to make deep networks more robust by either changing the network architecture or augmenting the training set with adversarial examples, but both have inherent limitations. Motivated by recent research that shows outliers in the training set have a high negative influence on the trained model, we studied the relationship between model robustness and the quality of the training set. We first show that outliers give the model better generalization ability but weaker robustness. Next, we propose an adversarial example detection framework, in which we design two methods for removing outliers from training set to obtain the sanitized model and then detect adversarial example by calculating the difference of outputs between the original and the sanitized model. We evaluated the framework on both MNIST and SVHN. Based on the difference measured by Kullback-Leibler divergence, we could detect adversarial examples with accuracy between 94.67% to 99.89%.
A Survey among Network Operators on BGP Prefix Hijacking
Venue: arXiv cs.NI 2018
Year: 2018

BGP prefix hijacking is a threat to Internet operators and users. Several mechanisms or modifications to BGP that protect the Internet against it have been proposed. However, the reality is that most operators have not deployed them and are reluctant to do so in the near future. Instead, they rely on basic - and often inefficient - proactive defenses to reduce the impact of hijacking events, or on detection based on third party services and reactive approaches that might take up to several hours. In this work, we present the results of a survey we conducted among 75 network operators to study: (a) the operators' awareness of BGP prefix hijacking attacks, (b) presently used defenses (if any) against BGP prefix hijacking, (c) the willingness to adopt new defense mechanisms, and (d) reasons that may hinder the deployment of BGP prefix hijacking defenses. We expect the findings of this survey to increase the understanding of existing BGP hijacking defenses and the needs of network operators, as well as contribute towards designing new defense mechanisms that satisfy the requirements of the operators.
Data Augmentation by Pairing Samples for Images Classification
Venue: arXiv cs.LG 2018
Year: 2018

Data augmentation is a widely used technique in many machine learning tasks, such as image classification, to virtually enlarge the training dataset size and avoid overfitting. Traditional data augmentation techniques for image classification tasks create new samples from the original training data by, for example, flipping, distorting, adding a small amount of noise to, or cropping a patch from an original image. In this paper, we introduce a simple but surprisingly effective data augmentation technique for image classification tasks. With our technique, named SamplePairing, we synthesize a new sample from one image by overlaying another image randomly chosen from the training data (i.e., taking an average of two images for each pixel). By using two images randomly selected from the training set, we can generate $N^2$ new samples from $N$ training samples. This simple data augmentation technique significantly improved classification accuracy for all the tested datasets; for example, the top-1 error rate was reduced from 33.5% to 29.0% for the ILSVRC 2012 dataset with GoogLeNet and from 8.22% to 6.93% in the CIFAR-10 dataset. We also show that our SamplePairing technique largely improved accuracy when the number of samples in the training set was very small. Therefore, our technique is more valuable for tasks with a limited amount of training data, such as medical imaging tasks.
An Ontology for Satellite Databases
Venue: arXiv cs.AI 2018
Year: 2018

This paper demonstrates the development of ontology for satellite databases. First, I create a computational ontology for the Union of Concerned Scientists (UCS) Satellite Database (UCSSD for short), called the UCS Satellite Ontology (or UCSSO). Second, in developing UCSSO I show that The Space Situational Awareness Ontology (SSAO) (Rovetto and Kelso 2016)--an existing space domain reference ontology--and related ontology work by the author (Rovetto 2015, 2016) can be used either (i) with a database-specific local ontology such as UCSSO, or (ii) in its stead. In case (i), local ontologies such as UCSSO can reuse SSAO terms, perform term mappings, or extend it. In case (ii), the author's orbital space ontology work, such as the SSAO, is usable by the UCSSD and organizations with other space object catalogs, as a reference ontology suite providing a common semantically-rich domain model. The SSAO, UCSSO, and the broader Orbital Space Environment Domain Ontology project is online at http://purl.org/space-ontology and GitHub. This ontology effort aims, in part, to provide accurate formal representations of the domain for various applications. Ontology engineering has the potential to facilitate the sharing and integration of satellite data from federated databases and sensors for safer spaceflight.
Iterative Learning Economic Model Predictive Control
Venue: arXiv cs.SY 2018
Year: 2018

An iterative learning based economic model predictive controller (ILEMPC) is proposed for repetitive tasks in this paper. Compared with existing works, the initial feasible trajectory of the proposed ILEMPC is not restricted to be convergent to an equilibrium so it can handle various types of control objectives: stabilization, tracking a periodic trajectory and even pure economic optimization. The controller can learn from the previous closed-loop trajectory, resulting in a performance which is guaranteed to be no worse than the previous one. Under some standard assumptions in model predictive control, we show that recursive feasibility is ensured. Furthermore, for stabilization problem, the convergence of each learned trajectory and the learning process are established provided the initial trajectory is convergent. Numerical examples show that the proposed control strategy works well for different types of control tasks and systems.
Multiplexing Analysis of Millimeter-Wave Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

This paper is concerned with spatial multiplexing analysis for millimeter-wave (mmWave) massive MIMO systems. For a single-user mmWave system employing distributed antenna subarray architecture in which the transmitter and receiver consist of Kt and Kr subarrays, respectively, an asymptotic multiplexing gain formula is firstly derived when the numbers of antennas at subarrays go to infinity. Specifically, assuming that all subchannels have the same average number of propagation paths L, the formula implies that by employing such a distributed antenna-subarray architecture, an exact average maximum multiplexing gain of KrKtL can be achieved. This result means that compared to the co-located antenna architecture, using the distributed antenna-subarray architecture can scale up the maximum multiplexing gain proportionally to KrKt. In order to further reveal the relation between diversity gain and multiplexing gain, a simple characterization of the diversity-multiplexing tradeoff is also given. The multiplexing gain analysis is then extended to the multiuser scenario. Moreover, simulation results obtained with the hybrid analog/digital processing corroborate the analysis results.
Predict Forex Trend via Convolutional Neural Networks
Venue: arXiv cs.CE 2018
Year: 2018

Deep learning is an effective approach to solving image recognition problems. People draw intuitive conclusions from trading charts; this study uses the characteristics of deep learning to train computers in imitating this kind of intuition in the context of trading charts. The three steps involved are as follows: 1. Before training, we pre-process the input data from quantitative data to images. 2. We use a convolutional neural network (CNN), a type of deep learning, to train our trading model. 3. We evaluate the model's performance in terms of the accuracy of classification. A trading model is obtained with this approach to help devise trading strategies. The main application is designed to help clients automatically obtain personalized trading strategies.
Topical Stance Detection for Twitter: A Two-Phase LSTM Model Using Attention
Venue: arXiv cs.CL 2018
Year: 2018

The topical stance detection problem addresses detecting the stance of the text content with respect to a given topic: whether the sentiment of the given text content is in FAVOR of (positive), is AGAINST (negative), or is NONE (neutral) towards the given topic. Using the concept of attention, we develop a two-phase solution. In the first phase, we classify subjectivity - whether a given tweet is neutral or subjective with respect to the given topic. In the second phase, we classify sentiment of the subjective tweets (ignoring the neutral tweets) - whether a given subjective tweet has a FAVOR or AGAINST stance towards the topic. We propose a Long Short-Term memory (LSTM) based deep neural network for each phase, and embed attention at each of the phases. On the SemEval 2016 stance detection Twitter task dataset, we obtain a best-case macro F-score of 68.84% and a best-case accuracy of 60.2%, outperforming the existing deep learning based solutions. Our framework, T-PAN, is the first in the topical stance detection literature, that uses deep learning within a two-phase architecture.
Abstract: Probabilistic Prognostic Estimates of Survival in Metastatic Cancer Patients
Venue: arXiv cs.AI 2018
Year: 2018

We propose a deep learning model - Probabilistic Prognostic Estimates of Survival in Metastatic Cancer Patients (PPES-Met) for estimating short-term life expectancy (3 months) of the patients by analyzing free-text clinical notes in the electronic medical record, while maintaining the temporal visit sequence. In a single framework, we integrated semantic data mapping and neural embedding technique to produce a text processing method that extracts relevant information from heterogeneous types of clinical notes in an unsupervised manner, and we designed a recurrent neural network to model the temporal dependency of the patient visits. The model was trained on a large dataset (10,293 patients) and validated on a separated dataset (1818 patients). Our method achieved an area under the ROC curve (AUC) of 0.89. To provide explain-ability, we developed an interactive graphical tool that may improve physician understanding of the basis for the model's predictions. The high accuracy and explain-ability of the PPES-Met model may enable our model to be used as a decision support tool to personalize metastatic cancer treatment and provide valuable assistance to the physicians.
Why informatics and general science need a conjoint basic definition of information
Venue: arXiv cs.DL 2018
Year: 2018

First the basic definition of information as a selection from a set of possibilities resp. domain is recalled. This also applies to digital information. The bits of digital information are parts of number sequences which represent a selection from a set of possibilities resp. domain. For faultless conversation sender and receiver of information must have the same definition of the domain (e.g. of language vocabulary). Up to now the definition of the domain and of its elements is derived from context and knowledge. The internet provides an additional important possibility: A link to a conjoint uniform definition of the domain at unique location on the internet. The associated basic information structure is called "Domain Vector" (DV) and has the structure "UL (of the domain definition) plus sequence of numbers". The "UL" is not only "Uniform Locator" of the domain definition. It also identifies a certain kind of information for later comparison and search. It can be a Uniform Resource Locator (URL) or an abbreviated equivalent, e.g. a hierarchic numeric pointer or a short local pointer to a table with global internet pointers. The DV structure can be used as general carrier of information which is language independent and more precise than language. A domain which contains DVs is called "Domain Space" (DS) and is defined as metric space. This allows similarity search according to user defined criteria, so that any kind of definable information can be made comparable and searchable according to user selected (relevant) and objectifiable (globally uniform) criteria. DS definitions can be reused in new DS definitions. Their elements, the DVs, are automatically globally uniformly identified and defined. Obviously such conjoint definition of comparable information has great potential. It also can avoid interoperability problems and redundant programming and so save high costs.