OpenRaiser/Intern-Atlas huggingface dataset:
A Machine Learning Approach to Air Traffic Route Choice Modelling
Venue: arXiv cs.AI 2018
Year: 2018

Air Traffic Flow and Capacity Management (ATFCM) is one of the constituent parts of Air Traffic Management (ATM). The goal of ATFCM is to make airport and airspace capacity meet traffic demand and, when capacity opportunities are exhausted, optimise traffic flows to meet the available capacity. One of the key enablers of ATFCM is the accurate estimation of future traffic demand. The available information (schedules, flight plans, etc.) and its associated level of uncertainty differ across the different ATFCM planning phases, leading to qualitative differences between the types of forecasting that are feasible at each time horizon. While abundant research has been conducted on tactical trajectory prediction (i.e., during the day of operations), trajectory prediction in the pre-tactical phase, when few or no flight plans are available, has received much less attention. As a consequence, the methods currently in use for pre-tactical traffic forecast are still rather rudimentary, often resulting in suboptimal ATFCM decision making. This paper proposes a machine learning approach for the prediction of airlines route choices between two airports as a function of route characteristics, such as flight efficiency, air navigation charges and expected level of congestion. Different predictive models based on multinomial logistic regression and decision trees are formulated and calibrated with historical traffic data, and a critical evaluation of each model is conducted. We analyse the predictive power of each model in terms of its ability to forecast traffic volumes at the level of charging zones, proving significant potential to enhance pre-tactical traffic forecast. We conclude by discussing the limitations and room for improvement of the proposed approach, as well as the future developments required to produce reliable traffic forecasts at a higher spatial and temporal resolution.
Robustness of Rotation-Equivariant Networks to Adversarial Perturbations
Venue: arXiv cs.CV 2018
Year: 2018

Deep neural networks have been shown to be vulnerable to adversarial examples: very small perturbations of the input having a dramatic impact on the predictions. A wealth of adversarial attacks and distance metrics to quantify the similarity between natural and adversarial images have been proposed, recently enlarging the scope of adversarial examples with geometric transformations beyond pixel-wise attacks. In this context, we investigate the robustness to adversarial attacks of new Convolutional Neural Network architectures providing equivariance to rotations. We found that rotation-equivariant networks are significantly less vulnerable to geometric-based attacks than regular networks on the MNIST, CIFAR-10, and ImageNet datasets.
Maximal Exploration of Trees with Energy-Constrained Agents
Venue: arXiv cs.DS 2018
Year: 2018

We consider the problem of exploring an unknown tree with a team of $k$ initially colocated mobile agents. Each agent has limited energy and cannot, as a result, traverse more than $B$ edges. The goal is to maximize the number of nodes collectively visited by all agents during the execution. Initially, the agents have no knowledge about the structure of the tree, but they gradually discover the topology as they traverse new edges. We assume that the agents can communicate with each other at arbitrary distances. Therefore the knowledge obtained by one agent after traversing an edge is instantaneously transmitted to the other agents. We propose an algorithm that divides the tree into subtrees during the exploration process and makes a careful trade-off between breadth-first and depth-first exploration. We show that our algorithm is 3-competitive compared to an optimal solution that we could obtain if we knew the map of the tree in advance. While it is easy to see that no algorithm can be better than 2-competitive, we give a non-trivial lower bound of 2.17 on the competitive ratio of any online algorithm.
Matrix Exponential Learning Schemes with Low Informational Exchange
Venue: arXiv cs.IT 2018
Year: 2018

We consider a distributed resource allocation problem in networks where each transmitter-receiver pair aims at maximizing its local utility function by adjusting its action matrix, which belongs to a given feasible set. This problem has been addressed recently by applying a matrix exponential learning (MXL) algorithm which has a very appealing convergence rate. In this learning algorithm, however, each transmitter must know an estimate of the gradient matrix of the local utility. The knowledge of the gradient matrix at the transmitters incurs a high signaling overhead especially that the matrix size increases with the dimension of the action matrix. In this paper, we therefore investigate two strategies in order to decrease the informational exchange per iteration of the algorithm. In the first strategy, each receiver sends at each iteration part of the elements of the gradient matrix with respect to a certain probability. In the second strategy, each receiver feeds back sporadically the whole gradient matrix. We focus on the analysis of the convergence of the MXL algorithm to optimum under these two strategies. We prove that the algorithm can still converge to optimum almost surely. Upper bounds of the average convergence rate are also derived in both situations with general step-size setting, from which we can clearly see the impact of the incompleteness of the feedback information. The proposed algorithms are applied to solve the energy efficiency maximization problem in a multicarrier multi-user MIMO network. Simulation results further corroborate our claim.
(Arc-disjoint) cycle packing in tournament: classical and parameterized complexity
Venue: arXiv cs.DM 2018
Year: 2018

Given a tournament $T$, the problem MaxCT consists of finding a maximum (arc-disjoint) cycle packing of $T$. In the same way, MaxTT corresponds to the specific case where the collection of cycles are triangles (i.e. directed 3-cycles). Although MaxCT can be seen as the LP dual of minimum feedback arc set in tournaments which have been widely studied, surprisingly no algorithmic results seem to exist concerning the former. In this paper, we prove the NP-hardness of both MaxCT and MaxTT. We also show that deciding if a tournament has a cycle packing and a feedback arc set with the same size is an NP-complete problem. In light of this, we show that MaxTT admits a vertex linear-kernel when parameterized with the size of the solution. Finally, we provide polynomial algorithms for MaxTT and MaxCT when the tournament is sparse, that is when it admits a FAS which is a matching.
Integration of Carrier Aggregation and Dual Connectivity for the ns-3 mmWave Module
Venue: arXiv cs.NI 2018
Year: 2018

Thanks to the wide availability of bandwidth, the millimeter wave (mmWave) frequencies will provide very high data rates to mobile users in next generation 5G cellular networks. However, mmWave links suffer from high isotropic pathloss and blockage from common materials, and are subject to an intermittent channel quality. Therefore, protocols and solutions at different layers in the cellular network and the TCP/IP protocol stack have been proposed and studied. A valuable tool for the end-to-end performance analysis of mmWave cellular networks is the ns-3 mmWave module, which already models in detail the channel, Physical (PHY) and Medium Access Control (MAC) layers, and extends the Long Term Evolution (LTE) stack for the higher layers. In this paper we present an implementation for the ns-3 mmWave module of multi connectivity techniques for 3GPP New Radio (NR) at mmWave frequencies, namely Carrier Aggregation (CA) and Dual Connectivity (DC), and discuss how they can be integrated to increase the functionalities offered by the ns-3 mmWave module.
On Learning the $cμ$ Rule in Single and Parallel Server Networks
Venue: arXiv cs.PF 2018
Year: 2018

We consider learning-based variants of the $c μ$ rule for scheduling in single and parallel server settings of multi-class queueing systems. In the single server setting, the $c μ$ rule is known to minimize the expected holding-cost (weighted queue-lengths summed over classes and a fixed time horizon). We focus on the problem where the service rates $μ$ are unknown with the holding-cost regret (regret against the $c μ$ rule with known $μ$) as our objective. We show that the greedy algorithm that uses empirically learned service rates results in a constant holding-cost regret (the regret is independent of the time horizon). This free exploration can be explained in the single server setting by the fact that any work-conserving policy obtains the same number of samples in a busy cycle. In the parallel server setting, we show that the $c μ$ rule may result in unstable queues, even for arrival rates within the capacity region. We then present sufficient conditions for geometric ergodicity under the $c μ$ rule. Using these results, we propose an almost greedy algorithm that explores only when the number of samples falls below a threshold. We show that this algorithm delivers constant holding-cost regret because a free exploration condition is eventually satisfied.
Design and software implementation of subsystems for creating and using the ontological base of a research scientist
Venue: arXiv cs.AI 2018
Year: 2018

Creation of the information systems and tools for scientific research and development support has always been one of the central directions of the development of computer science. The main features of the modern evolution of scientific research and development are the transdisciplinary approach and the deep intellectualisation of all stages of the life cycle of formulation and solution of scientific problems. The theoretical and practical aspects of the development of perspective complex knowledge-oriented information systems and their components are considered in the paper. The analysis of existing scientific information systems (or current research information systems, CRIS) and synthesis of general principles of design of the research and development workstation environment of a researcher and its components are carried out in the work. The functional components of knowledge-oriented information system research and development workstation environment of a researcher are designed. Designed and developed functional components of knowledge-oriented information system developing research and development workstation environment,including functional models and software implementation of the software subsystem for creation and use of ontological knowledge base for research fellow publications, as part of personalized knowledge base of scientific researcher. Research in modern conditions of e-Science paradigm requires pooling scientific community and intensive exchange of research results that may be achieved through the use of scientific information systems. research and development workstation environment allows to solve problems of contructivisation and formalisation of knowledge representation, obtained during the research process and collective accomplices interaction.
Technique for designing a domain ontology
Venue: arXiv cs.AI 2018
Year: 2018

The article describes the technique for designing a domain ontology, shows the flowchart of algorithm design and example of constructing a fragment of the ontology of the subject area of Computer Science is considered.
Mining Density Contrast Subgraphs
Venue: arXiv cs.SI 2018
Year: 2018

Dense subgraph discovery is a key primitive in many graph mining applications, such as detecting communities in social networks and mining gene correlation from biological data. Most studies on dense subgraph mining only deal with one graph. However, in many applications, we have more than one graph describing relations among a same group of entities. In this paper, given two graphs sharing the same set of vertices, we investigate the problem of detecting subgraphs that contrast the most with respect to density. We call such subgraphs Density Contrast Subgraphs, or DCS in short. Two widely used graph density measures, average degree and graph affinity, are considered. For both density measures, mining DCS is equivalent to mining the densest subgraph from a "difference" graph, which may have both positive and negative edge weights. Due to the existence of negative edge weights, existing dense subgraph detection algorithms cannot identify the subgraph we need. We prove the computational hardness of mining DCS under the two graph density measures and develop efficient algorithms to find DCS. We also conduct extensive experiments on several real-world datasets to evaluate our algorithms. The experimental results show that our algorithms are both effective and efficient.
Be-Educated: Multimedia Learning through 3D Animation
Venue: arXiv cs.GR 2018
Year: 2018

Multimedia learning tools and techniques are placing its importance with large scale in education sector. With the help of multimedia learning, various complex phenomenon and theories can be explained and taught easily and conveniently. This project aims to teach and spread the importance of education and respecting the tools of education: pen, paper, pencil, rubber. To achieve this cognitive learning, a 3D animated movie has been developed using principles of multimedia learning with 3D cartoon characters resembling the actual educational objects, where the buildings have also been modelled to resemble real books and diaries. For modelling and animation of these characters, polygon mesh tools are used in 3D Studio Max. Additionally, the final composition of video and audio is performed in adobe premiere. This 3D animated video aims to highlight a message of importance for education and stationary. The Moral of movie is that do not waste your stationary material, use your Pen and Paper for the purpose they are made for. To be a good citizen you have to Be-Educated yourself and for that you need to give value to Pen. The final rendered and composited 3D animated video reflects this moral and portrays the intended message with very vibrant visuals
Population Protocols Are Fast
Venue: arXiv cs.DC 2018
Year: 2018

A population protocol describes a set of state change rules for a population of $n$ indistinguishable finite-state agents (automata), undergoing random pairwise interactions. Within this very basic framework, it is possible to resolve a number of fundamental tasks in distributed computing, including: leader election, aggregate and threshold functions on the population, such as majority computation, and plurality consensus. For the first time, we show that solutions to all of these problems can be obtained \emph{quickly} using finite-state protocols. For any input, the designed finite-state protocols converge under a fair random scheduler to an output which is correct with high probability in expected $O(\mathrm{poly} \log n)$ parallel time. In the same setting, we also show protocols which always reach a valid solution, in expected parallel time $O(n^\varepsilon)$, where the number of states of the interacting automata depends only on the choice of $\varepsilon>0$. The stated time bounds hold for \emph{any} semi-linear predicate computable in the population protocol framework. The key ingredient of our result is the decentralized design of a hierarchy of phase-clocks, which tick at different rates, with the rates of adjacent clocks separated by a factor of $Θ(\log n)$. The construction of this clock hierarchy relies on a new protocol composition technique, combined with an adapted analysis of a self-organizing process of oscillatory dynamics. This clock hierarchy is used to provide nested synchronization primitives, which allow us to view the population in a global manner and design protocols using a high-level imperative programming language with a (limited) capacity for loops and branching instructions.
Learning Word Vectors for 157 Languages
Venue: arXiv cs.CL 2018
Year: 2018

Distributed word representations, or word vectors, have recently been applied to many tasks in natural language processing, leading to state-of-the-art performance. A key ingredient to the successful application of these representations is to train them on very large corpora, and use these pre-trained models in downstream tasks. In this paper, we describe how we trained such high quality word representations for 157 languages. We used two sources of data to train these models: the free online encyclopedia Wikipedia and data from the common crawl project. We also introduce three new word analogy datasets to evaluate these word vectors, for French, Hindi and Polish. Finally, we evaluate our pre-trained word vectors on 10 languages for which evaluation datasets exists, showing very strong performance compared to previous models.
Hierarchical Expertise-Level Modeling for User Specific Robot-Behavior Explanations
Venue: arXiv cs.AI 2018
Year: 2018

There is a growing interest within the AI research community to develop autonomous systems capable of explaining their behavior to users. One aspect of the explanation generation problem that has yet to receive much attention is the task of explaining plans to users whose level of expertise differ from that of the explainer. We propose an approach for addressing this problem by representing the user's model as an abstraction of the domain model that the planner uses. We present algorithms for generating minimal explanations in cases where this abstract human model is not known. We reduce the problem of generating explanation to a search over the space of abstract models and investigate possible greedy approximations for minimal explanations. We also empirically show that our approach can efficiently compute explanations for a variety of problems.
Scale Optimization for Full-Image-CNN Vehicle Detection
Venue: arXiv cs.CV 2018
Year: 2018

Many state-of-the-art general object detection methods make use of shared full-image convolutional features (as in Faster R-CNN). This achieves a reasonable test-phase computation time while enjoys the discriminative power provided by large Convolutional Neural Network (CNN) models. Such designs excel on benchmarks which contain natural images but which have very unnatural distributions, i.e. they have an unnaturally high-frequency of the target classes and a bias towards a "friendly" or "dominant" object scale. In this paper we present further study of the use and adaptation of the Faster R-CNN object detection method for datasets presenting natural scale distribution and unbiased real-world object frequency. In particular, we show that better alignment of the detector scale sensitivity to the extant distribution improves vehicle detection performance. We do this by modifying both the selection of Region Proposals, and through using more scale-appropriate full-image convolution features within the CNN model. By selecting better scales in the region proposal input and by combining feature maps through careful design of the convolutional neural network, we improve performance on smaller objects. We significantly increase detection AP for the KITTI dataset car class from 76.3% on our baseline Faster R-CNN detector to 83.6% in our improved detector.
On Lyapunov exponents and adversarial perturbation
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we would like to disseminate a serendipitous discovery involving Lyapunov exponents of a 1-D time series and their use in serving as a filtering defense tool against a specific kind of deep adversarial perturbation. To this end, we use the state-of-the-art CleverHans library to generate adversarial perturbations against a standard Convolutional Neural Network (CNN) architecture trained on the MNIST as well as the Fashion-MNIST datasets. We empirically demonstrate how the Lyapunov exponents computed on the flattened 1-D vector representations of the images served as highly discriminative features that could be to pre-classify images as adversarial or legitimate before feeding the image into the CNN for classification. We also explore the issue of possible false-alarms when the input images are noisy in a non-adversarial sense.
AMC and HARQ: How to Increase the Throughput
Venue: arXiv cs.IT 2018
Year: 2018

In this work, we consider transmissions over block fading channels and assume that adaptive modulation and coding (AMC) and hybrid automatic repeat request (HARQ) are implemented. Knowing that in high signal-to-noise ratio, the conventional combination of HARQ with AMC is counterproductive from the throughput point of view, we adopt the so-called layer-coded HARQ (L-HARQ). L-HARQ allows consecutive packets to share the channel and preserves a great degree of separation between AMC and HARQ; this makes the encoding and decoding very simple and allows us to use the available/optimized codes. Numerical examples shown in the paper indicate that L-HARQ can provide significant throughput gains compared to the conventional HARQ. The L-HARQ is also implemented using turbo codes indicating that the throughput gains also materialize in practice.
Using Automatic Generation of Relaxation Constraints to Improve the Preimage Attack on 39-step MD4
Venue: arXiv cs.AI 2018
Year: 2018

In this paper we construct preimage attack on the truncated variant of the MD4 hash function. Specifically, we study the MD4-39 function defined by the first 39 steps of the MD4 algorithm. We suggest a new attack on MD4-39, which develops the ideas proposed by H. Dobbertin in 1998. Namely, the special relaxation constraints are introduced in order to simplify the equations corresponding to the problem of finding a preimage for an arbitrary MD4-39 hash value. The equations supplemented with the relaxation constraints are then reduced to the Boolean Satisfiability Problem (SAT) and solved using the state-of-the-art SAT solvers. We show that the effectiveness of a set of relaxation constraints can be evaluated using the black-box function of a special kind. Thus, we suggest automatic method of relaxation constraints generation by applying the black-box optimization to this function. The proposed method made it possible to find new relaxation constraints that contribute to a SAT-based preimage attack on MD4-39 which significantly outperforms the competition.
Coupon Advertising in Online Social Systems: Algorithms and Sampling Techniques
Venue: arXiv cs.SI 2018
Year: 2018

Online social systems have become important platforms for viral marketing where the advertising of products is carried out with the communication of users. After adopting the product, the seed buyers may spread the information to their friends via online messages e.g. posts and tweets. In another issue, electronic coupon system is one of the relevant promotion vehicles that help manufacturers and retailers attract more potential customers. By offering coupons to seed buyers, there is a chance to convince the influential users who are, however, at first not very interested in the product. In this paper, we propose a coupon based online influence model and consider the problem that how to maximize the profit by selecting appropriate seed buyers. The considered problem herein is markedly different from other influence related problems as its objective function is not monotone. We provide an algorithmic analysis and give several algorithms designed with different sampling techniques. In particular, we propose the RA-T and RA-S algorithms which are not only provably effective but also scalable on large datasets. The proposed theoretical results are evaluated by extensive experiments done on large-scale real-world social networks. The analysis of this paper also provides an algorithmic framework for non-monotone submodular maximization problems in social networks.