OpenRaiser/Intern-Atlas huggingface dataset:
Greed is Still Good: Maximizing Monotone Submodular+Supermodular Functions
Venue: arXiv cs.DM 2018
Year: 2018

We analyze the performance of the greedy algorithm, and also a discrete semi-gradient based algorithm, for maximizing the sum of a suBmodular and suPermodular (BP) function (both of which are non-negative monotone non-decreasing) under two types of constraints, either a cardinality constraint or $p\geq 1$ matroid independence constraints. These problems occur naturally in several real-world applications in data science, machine learning, and artificial intelligence. The problems are ordinarily inapproximable to any factor (as we show). Using the curvature $κ_f$ of the submodular term, and introducing $κ^g$ for the supermodular term (a natural dual curvature for supermodular functions), however, both of which are computable in linear time, we show that BP maximization can be efficiently approximated by both the greedy and the semi-gradient based algorithm. The algorithms yield multiplicative guarantees of $\frac{1}{κ_f}\left[1-e^{-(1-κ^g)κ_f}\right]$ and $\frac{1-κ^g}{(1-κ^g)κ_f + p}$ for the two types of constraints respectively. For pure monotone supermodular constrained maximization, these yield $1-κ^g$ and $(1-κ^g)/p$ for the two types of constraints respectively. We also analyze the hardness of BP maximization and show that our guarantees match hardness by a constant factor and by $O(\ln(p))$ respectively. Computational experiments are also provided supporting our analysis.
Protograph-based Quasi-Cyclic MDPC Codes for McEliece Cryptosystems
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, ensembles of quasi-cyclic moderate-density parity-check (MDPC) codes based on protographs are introduced and analyzed in the context of a McEliece-like cryptosystem. The proposed ensembles significantly improve the error correction capability of the regular MDPC code ensembles that are currently considered for post-quantum cryptosystems without increasing the public key size. The proposed ensembles are analyzed in the asymptotic setting via density evolution, both under the sum-product algorithm and a low-complexity (error-and-erasure) message passing algorithm. The asymptotic analysis is complemented at finite block lengths by Monte Carlo simulations. The enhanced error correction capability remarkably improves the scheme robustness with respect to (known) decoding attacks.
An Efficient Primal-Dual Algorithm for Fair Combinatorial Optimization Problems
Venue: arXiv cs.DS 2018
Year: 2018

We consider a general class of combinatorial optimization problems including among others allocation, multiple knapsack, matching or travelling salesman problems. The standard version of those problems is the maximum weight optimization problem where a sum of values is optimized. However, the sum is not a good aggregation function when the fairness of the distribution of those values (corresponding for example to different agents' utilities or criteria) is important. In this paper, using the generalized Gini index (GGI), a well-known inequality measure, instead of the sum to model fairness, we formulate a new general problem, that we call fair combinatorial optimization. Although GGI is a non-linear aggregating function, a $0,1$-linear program (IP) can be formulated for finding a GGI-optimal solution by exploiting a linearization of GGI proposed by Ogryczak and Sliwinski. However, the time spent by commercial solvers (e.g., CPLEX, Gurobi...) for solving (IP) increases very quickly with instances' size and can reach hours even for relatively small-sized ones. As a faster alternative, we propose a heuristic for solving (IP) based on a primal-dual approach using Lagrangian decomposition. %We experimentally evaluate our methods against the exact solution of (IP) by CPLEX on several fair optimization problems related to matching to demonstrate the efficiency of our proposition. We demonstrate the efficiency of our method by evaluating it against the exact solution of (IP) by CPLEX on several fair optimization problems related to matching. The numerical results show that our method outputs in a very short time efficient solutions giving lower bounds that CPLEX may take several orders of magnitude longer to obtain. Moreover, for instances for which we know the optimal value, these solutions are quasi-optimal with optimality gap less than 0.3%.
Energy sustainable paradigms and methods for future mobile networks: A survey
Venue: arXiv cs.NI 2018
Year: 2018

In this survey, we discuss the role of energy in the design of future mobile networks and, in particular, we advocate and elaborate on the use of energy harvesting (EH) hardware as a means to decrease the environmental footprint of 5G technology. To take full advantage of the harvested (renewable) energy, while still meeting the quality of service required by dense 5G deployments, suitable management techniques are here reviewed, highlighting the open issues that are still to be solved to provide eco-friendly and cost-effective mobile architectures. Several solutions have recently been proposed to tackle capacity, coverage and efficiency problems, including: C-RAN, Software Defined Networking (SDN) and fog computing, among others. However, these are not explicitly tailored to increase the energy efficiency of networks featuring renewable energy sources, and have the following limitations: (i) their energy savings are in many cases still insufficient and (ii) they do not consider network elements possessing energy harvesting capabilities. In this paper, we systematically review existing energy sustainable paradigms and methods to address points (i) and (ii), discussing how these can be exploited to obtain highly efficient, energy self-sufficient and high capacity networks. Several open issues have emerged from our review, ranging from the need for accurate energy, transmission and consumption models, to the lack of accurate data traffic profiles, to the use of power transfer, energy cooperation and energy trading techniques. These challenges are here discussed along with some research directions to follow for achieving sustainable 5G systems.
A Multi-layer Recursive Residue Number System
Venue: arXiv cs.CR 2018
Year: 2018

We present a method to increase the dynamical range of a Residue Number System (RNS) by adding virtual RNS layers on top of the original RNS, where the required modular arithmetic for a modulus on any non-bottom layer is implemented by means of an RNS Montgomery multiplication algorithm that uses the RNS on the layer below. As a result, the actual arithmetic is deferred to the bottom layer. The multiplication algorithm that we use is based on an algorithm by Bajard and Imbert, extended to work with pseudo-residues (remainders with a larger range than the modulus). The resulting Recursive Residue Number System (RRNS) can be used to implement modular addition, multiplication, and multiply-and-accumulate for very large (2000+ bits) moduli, using only modular operations for small (for example 8-bits) moduli. A hardware implementation of this method allows for massive parallelization. Our method can be applied in cryptographic algorithms such as RSA to realize modular exponentiation with a large (2048-bit, or even 4096-bit) modulus. Due to the use of full RNS Montgomery algorithms, the system does not involve any carries, therefore cryptographic attacks that exploit carries cannot be applied.
On $\mathcal{L}_{\infty}$ string stability of nonlinear bidirectional asymmetric heterogeneous platoon systems
Venue: arXiv cs.SY 2018
Year: 2018

This paper is concerned with the study of bidirectionally coupled platoon systems. The case considered is when the vehicles are heterogeneous and the coupling can be nonlinear and asymmetric. For such systems, a sufficient condition for $\mathcal{L}_{\infty}$ string stability is presented. The effectiveness of our approach is illustrated via a numerical example, where it is shown how our result can be recast as an optimization problem, allowing to design the control protocol for each vehicle independently on the other vehicles and hence leading to a bottom-up approach for the design of string stable systems able to track a time-varying reference speed.
A Work Zone Simulation Model for Travel Time Prediction in a Connected Vehicle Environment
Venue: arXiv cs.MA 2018
Year: 2018

A work zone bottleneck in a roadway network can cause traffic delays, emissions and safety issues. Accurate measurement and prediction of work zone travel time can help travelers make better routing decisions and therefore mitigate its impact. Historically, data used for travel time analyses comes from fixed loop detectors, which are expensive to install and maintain. With connected vehicle technology, such as Vehicle-to-Infrastructure, portable roadside unit (RSU) can be located in and around a work zone segment to communicate with the vehicles and collect traffic data. A PARAMICS simulation model for a prototypical freeway work zone in a connected vehicle environment was built to test this idea using traffic demand data from NY State Route 104. For the simulation, twelve RSUs were placed along the work zone segment and sixteen variables were extracted from the simulation results to explore travel time estimation and prediction. For the travel time analysis, four types of models were constructed, including linear regression, multivariate adaptive regression splines (MARS), stepwise regression and elastic net. The results show that the modeling approaches under consideration have similar performance in terms of the Root of Mean Square Error (RMSE), which provides an opportunity for model selection based on additional factors including the number and locations of the RSUs according to the significant variables identified in the various models. Among the four approaches, the stepwise regression model only needs variables from two RSUs: one placed sufficiently upstream of the work zone and one at the end of the work zone.
Internal Universes in Models of Homotopy Type Theory
Venue: arXiv cs.LO 2018
Year: 2018

We begin by recalling the essentially global character of universes in various models of homotopy type theory, which prevents a straightforward axiomatization of their properties using the internal language of the presheaf toposes from which these model are constructed. We get around this problem by extending the internal language with a modal operator for expressing properties of global elements. In this setting we show how to construct a universe that classifies the Cohen-Coquand-Huber-Mörtberg (CCHM) notion of fibration from their cubical sets model, starting from the assumption that the interval is tiny - a property that the interval in cubical sets does indeed have. This leads to an elementary axiomatization of that and related models of homotopy type theory within what we call crisp type theory.
Pruning Techniques for Mixed Ensembles of Genetic Programming Models
Venue: arXiv cs.NE 2018
Year: 2018

The objective of this paper is to define an effective strategy for building an ensemble of Genetic Programming (GP) models. Ensemble methods are widely used in machine learning due to their features: they average out biases, they reduce the variance and they usually generalize better than single models. Despite these advantages, building ensemble of GP models is not a well-developed topic in the evolutionary computation community. To fill this gap, we propose a strategy that blends individuals produced by standard syntax-based GP and individuals produced by geometric semantic genetic programming, one of the newest semantics-based method developed in GP. In fact, recent literature showed that combining syntax and semantics could improve the generalization ability of a GP model. Additionally, to improve the diversity of the GP models used to build up the ensemble, we propose different pruning criteria that are based on correlation and entropy, a commonly used measure in information theory. Experimental results,obtained over different complex problems, suggest that the pruning criteria based on correlation and entropy could be effective in improving the generalization ability of the ensemble model and in reducing the computational burden required to build it.
Bayesian Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

This paper describes and discusses Bayesian Neural Network (BNN). The paper showcases a few different applications of them for classification and regression problems. BNNs are comprised of a Probabilistic Model and a Neural Network. The intent of such a design is to combine the strengths of Neural Networks and Stochastic modeling. Neural Networks exhibit continuous function approximator capabilities. Stochastic models allow direct specification of a model with known interaction between parameters to generate data. During the prediction phase, stochastic models generate a complete posterior distribution and produce probabilistic guarantees on the predictions. Thus BNNs are a unique combination of neural network and stochastic models with the stochastic model forming the core of this integration. BNNs can then produce probabilistic guarantees on it's predictions and also generate the distribution of parameters that it has learnt from the observations. That means, in the parameter space, one can deduce the nature and shape of the neural network's learnt parameters. These two characteristics makes them highly attractive to theoreticians as well as practitioners. Recently there has been a lot of activity in this area, with the advent of numerous probabilistic programming libraries such as: PyMC3, Edward, Stan etc. Further this area is rapidly gaining ground as a standard machine learning approach for numerous problems
Markov Chain Monitoring
Venue: arXiv cs.SI 2018
Year: 2018

In networking applications, one often wishes to obtain estimates about the number of objects at different parts of the network (e.g., the number of cars at an intersection of a road network or the number of packets expected to reach a node in a computer network) by monitoring the traffic in a small number of network nodes or edges. We formalize this task by defining the 'Markov Chain Monitoring' problem. Given an initial distribution of items over the nodes of a Markov chain, we wish to estimate the distribution of items at subsequent times. We do this by asking a limited number of queries that retrieve, for example, how many items transitioned to a specific node or over a specific edge at a particular time. We consider different types of queries, each defining a different variant of the Markov chain monitoring. For each variant, we design efficient algorithms for choosing the queries that make our estimates as accurate as possible. In our experiments with synthetic and real datasets we demonstrate the efficiency and the efficacy of our algorithms in a variety of settings.
Estimation of Variance and Spatial Correlation Width for Fine-scale Measurement Error in Digital Elevation Model
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we borrow from blind noise parameter estimation (BNPE) methodology early developed in the image processing field an original and innovative no-reference approach to estimate Digital Elevation Model (DEM) vertical error parameters without resorting to a reference DEM. The challenges associated with the proposed approach related to the physical nature of the error and its multifactor structure in DEM are discussed in detail. A suitable multivariate method is then developed for estimating the error in gridded DEM. It is built on a recently proposed vectorial BNPE method for estimating spatially correlated noise using Noise Informative areas and Fractal Brownian Motion. The newly multivariate method is derived to estimate the effect of the stacking procedure and that of the epipolar line error on local (fine-scale) standard deviation and autocorrelation function width of photogrammetric DEM measurement error. Applying the new estimator to ASTER GDEM2 and ALOS World 3D DEMs, good agreement of derived estimates with results available in the literature is evidenced. In future works, the proposed no-reference method for analyzing DEM error can be extended to a larger number of predictors for accounting for other factors influencing remote sensing (RS) DEM accuracy.
Evaluating Layers of Representation in Neural Machine Translation on Part-of-Speech and Semantic Tagging Tasks
Venue: arXiv cs.CL 2018
Year: 2018

While neural machine translation (NMT) models provide improved translation quality in an elegant, end-to-end framework, it is less clear what they learn about language. Recent work has started evaluating the quality of vector representations learned by NMT models on morphological and syntactic tasks. In this paper, we investigate the representations learned at different layers of NMT encoders. We train NMT systems on parallel data and use the trained models to extract features for training a classifier on two tasks: part-of-speech and semantic tagging. We then measure the performance of the classifier as a proxy to the quality of the original NMT model for the given task. Our quantitative analysis yields interesting insights regarding representation learning in NMT models. For instance, we find that higher layers are better at learning semantics while lower layers tend to be better for part-of-speech tagging. We also observe little effect of the target language on source-side representations, especially with higher quality NMT models.
On The Reliability Function of Discrete Memoryless Multiple-Access Channel with Feedback
Venue: arXiv cs.IT 2018
Year: 2018

We derive a lower and upper bound on the reliability function of discrete memoryless multiple-access channel (MAC) with noiseless feedback and variable-length codes (VLCs). For the upper-bound, we use proof techniques of Burnashev for the point-to-point case. Also, we adopt the techniques used to prove the converse for the feedback-capacity of MAC. For the lower-bound on the error exponent, we present a coding scheme consisting of a data and a confirmation stage. In the data stage, any arbitrary feedback capacity-achieving code is used. In the confirmation stage, each transmitter sends one bit of information to the receiver using a pair of codebooks of size two, one for each transmitter. The codewords at this stage are selected randomly according to an appropriately optimized joint probability distribution. The bounds increase linearly with respect to a specific Euclidean distance measure defined between the transmission rate pair and the capacity boundary. The lower and upper bounds match for a class of MACs.
Data is the Fuel of Organizations: Opportunities and Challenges in Afghanistan
Venue: arXiv cs.CY 2018
Year: 2018

In this paper, the author at first briefly outlines the value of data in organizations and the opportunities and challenges in Afghanistan. Then the author takes the Kankor (National University Entrance Exam) data, particularly names of participants, locations, high schools and higher education institutions into account and explains how these data, that organizations in Afghanistan do not use for anything, can be useful in several cases and areas. The application of these data is shown through cases such as Auto filling missing values, identifying names of people, locations, and institutions from unstructured text, generating fake data to benchmark the database and web application performance and appearance, comparing and matching high school data with Kankor data, producing the top-n male and female names very common in Afghanistan or province-wise, and the data mining application in education and higher education institutions.
qrypt0 - encrypted short messages exchanged between offline computers
Venue: arXiv cs.CR 2018
Year: 2018

A system is described for exchanging encrypted short messages between computers which remain permanently isolated from any network accessible to the attacker. The main advantage is effective protection of these computers from malware which could circumvent the encryption. For transmission, the ciphertext is passed between isolated and connected computers in the form of a QR code, which is displayed on and scanned from a screen. The security of qrypt0 therefore rests on the cryptography and the computer's physical isolation rather than on the computer security of the encrypting device.
Scalable and accurate deep learning for electronic health records
Venue: arXiv cs.CY 2018
Year: 2018

Predictive modeling with electronic health record (EHR) data is anticipated to drive personalized medicine and improve healthcare quality. Constructing predictive statistical models typically requires extraction of curated predictor variables from normalized EHR data, a labor-intensive process that discards the vast majority of information in each patient's record. We propose a representation of patients' entire, raw EHR records based on the Fast Healthcare Interoperability Resources (FHIR) format. We demonstrate that deep learning methods using this representation are capable of accurately predicting multiple medical events from multiple centers without site-specific data harmonization. We validated our approach using de-identified EHR data from two U.S. academic medical centers with 216,221 adult patients hospitalized for at least 24 hours. In the sequential format we propose, this volume of EHR data unrolled into a total of 46,864,534,945 data points, including clinical notes. Deep learning models achieved high accuracy for tasks such as predicting in-hospital mortality (AUROC across sites 0.93-0.94), 30-day unplanned readmission (AUROC 0.75-0.76), prolonged length of stay (AUROC 0.85-0.86), and all of a patient's final discharge diagnoses (frequency-weighted AUROC 0.90). These models outperformed state-of-the-art traditional predictive models in all cases. We also present a case-study of a neural-network attribution system, which illustrates how clinicians can gain some transparency into the predictions. We believe that this approach can be used to create accurate and scalable predictions for a variety of clinical scenarios, complete with explanations that directly highlight evidence in the patient's chart.
Downlink Power Control in Massive MIMO Networks with Distributed Antenna Arrays
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we investigate downlink power control in massive multiple-input multiple-output (MIMO) networks with distributed antenna arrays. The base station (BS) in each cell consists of multiple antenna arrays, which are deployed in arbitrary locations within the cell. Due to the spatial separation between antenna arrays, the large-scale propagation effect is different from a user to different antenna arrays in a cell, which makes power control a challenging problem as compared to conventional massive MIMO. We assume that the BS in each cell obtains the channel estimates via uplink pilots. Based on the channel estimates, the BSs perform maximum ratio transmission for the downlink. We then derive a closed-form spectral efficiency (SE) expression, where the channels are subject to correlated fading. Utilizing the derived expression, we propose a max-min power control algorithm to ensure that each user in the network receives a uniform quality of service. Numerical results demonstrate that, for the network considered in this work, optimizing for max-min SE through the max-min power control improves the sum SE of the network as compared to equal power allocation.