OpenRaiser/Intern-Atlas huggingface dataset:
Deterministic Heavy Hitters with Sublinear Query Time
Venue: arXiv cs.DS 2018
Year: 2018

This paper studies the classic problem of finding heavy hitters in the turnstile streaming model. We give the first deterministic linear sketch that has $O(ε^{-2} \log n \cdot \log^*(ε^{-1}))$ rows and answers queries in sublinear time. The number of rows is only a factor of $\log^*(ε^{-1})$ more than that used by the state-of-the-art algorithm prior to our paper due to Nelson, Nguyen and Woodruff (RANDOM'12). Their algorithm runs in time at least linear in the universe size $n$, which is highly undesirable in streaming applications. Our approach is based on an iterative procedure, where most unrecovered heavy hitters are identified in each iteration. Although this technique has been extensively employed in the related problem of sparse recovery, this is the first time, to the best of our knowledge, that it has been used in the context of $\ell_1$ heavy hitters. Along the way, we also give sublinear time algorithms for the closely related problems of combinatorial group testing and $\ell_1/\ell_1$ compressed sensing, matching the space usage of previous (super-)linear time algorithms.
A family of constacyclic codes over $\mathbb{F}_{2^{m}}+u\mathbb{F}_{2^{m}}$ and its application to quantum codes
Venue: arXiv cs.IT 2018
Year: 2018

We introduce a Gray map from $\mathbb{F}_{2^{m}}+u\mathbb{F}_{2^{m}}$ to $\mathbb{F}_{2}^{2m}$ and study $(1+u)$-constacyclic codes over $\mathbb{F}_{2^{m}}+u\mathbb{F}_{2^{m}},$ where $u^{2}=0.$ It is proved that the image of a $(1+u)$-constacyclic code length $n$ over $\mathbb{F}_{2^{m}}+u\mathbb{F}_{2^{m}}$ under the Gray map is a distance-invariant quasi-cyclic code of index $m$ and length $2mn$ over $\mathbb{F}_{2}.$ We also prove that every code of length $2mn$ which is the Gray image of cyclic codes over $\mathbb{F}_{2^{m}}+u\mathbb{F}_{2^{m}}$ of length $n$ is permutation equivalent to a binary quasi-cyclic code of index $m.$ Furthermore, a family of quantum error-correcting codes obtained from the Calderbank-Shor-Steane (CSS) construction applied to $(1+u)$-constacyclic codes over $\mathbb{F}_{2^{m}}+u\mathbb{F}_{2^{m}}.$
Secure Directional Modulation to Enhance Physical Layer Security in IoT Networks
Venue: arXiv cs.IT 2018
Year: 2018

In this work, an adaptive and robust null-space projection (AR-NSP) scheme is proposed for secure transmission with artificial noise (AN)-aided directional modulation (DM) in wireless networks. The proposed scheme is carried out in three steps. Firstly, the directions of arrival (DOAs) of the signals from the desired user and eavesdropper are estimated by the Root Multiple Signal Classificaiton (Root-MUSIC) algorithm and the related signal-to-noise ratios (SNRs) are estimated based on the ratio of the corresponding eigenvalue to the minimum eigenvalue of the covariance matrix of the received signals. In the second step, the value intervals of DOA estimation errors are predicted based on the DOA and SNR estimations. Finally, a robust NSP beamforming DM system is designed according to the afore-obtained estimations and predictions. Our examination shows that the proposed scheme can significantly outperform the conventional non-adaptive robust scheme and non-robust NSP scheme in terms of achieving a much lower bit error rate (BER) at the desired user and a much higher secrecy rate (SR). In addition, the BER and SR performance gains achieved by the proposed scheme relative to other schemes increase with the value range of DOA estimation error.
Normalization of zero-inflated data: An empirical analysis of a new indicator family and its use with altmetrics data
Venue: arXiv cs.DL 2018
Year: 2018

Recently, two new indicators (Equalized Mean-based Normalized Proportion Cited, EMNPC; Mean-based Normalized Proportion Cited, MNPC) were proposed which are intended for sparse scientometrics data. The indicators compare the proportion of mentioned papers (e.g. on Facebook) of a unit (e.g., a researcher or institution) with the proportion of mentioned papers in the corresponding fields and publication years (the expected values). In this study, we propose a third indicator (Mantel-Haenszel quotient, MHq) belonging to the same indicator family. The MHq is based on the MH analysis - an established method in statistics for the comparison of proportions. We test (using citations and assessments by peers, i.e. F1000Prime recommendations) if the three indicators can distinguish between different quality levels as defined on the basis of the assessments by peers. Thus, we test their convergent validity. We find that the indicator MHq is able to distinguish between the quality levels in most cases while MNPC and EMNPC are not. Since the MHq is shown in this study to be a valid indicator, we apply it to six types of zero-inflated altmetrics data and test whether different altmetrics sources are related to quality. The results for the various altmetrics demonstrate that the relationship between altmetrics (Wikipedia, Facebook, blogs, and news data) and assessments by peers is not as strong as the relationship between citations and assessments by peers. Actually, the relationship between citations and peer assessments is about two to three times stronger than the association between altmetrics and assessments by peers.
Stretching Domain Adaptation: How far is too far?
Venue: arXiv cs.CV 2018
Year: 2018

While deep learning has led to significant advances in visual recognition over the past few years, such advances often require a lot of annotated data. Unsupervised domain adaptation has emerged as an alternative approach that does not require as much annotated data, prior evaluations of domain adaptation approaches have been limited to relatively similar datasets, e.g source and target domains are samples captured by different cameras. A new data suite is proposed that comprehensively evaluates cross-modality domain adaptation problems. This work pushes the limit of unsupervised domain adaptation through an in-depth evaluation of several state of the art methods on benchmark datasets and the new dataset suite. We also propose a new domain adaptation network called "Deep MagNet" that effectively transfers knowledge for cross-modality domain adaptation problems. Deep Magnet achieves state of the art performance on two benchmark datasets. More importantly, the proposed method shows consistent improvements in performance on the newly proposed dataset suite.
Differential Flatness of Quadrotor Dynamics Subject to Rotor Drag for Accurate Tracking of High-Speed Trajectories
Venue: arXiv cs.RO 2018
Year: 2018

In this paper, we prove that the dynamical model of a quadrotor subject to linear rotor drag effects is differentially flat in its position and heading. We use this property to compute feed-forward control terms directly from a reference trajectory to be tracked. The obtained feed-forward terms are then used in a cascaded, nonlinear feedback control law that enables accurate agile flight with quadrotors. Compared to state-of-the-art control methods, which treat the rotor drag as an unknown disturbance, our method reduces the trajectory tracking error significantly. Finally, we present a method based on a gradient-free optimization to identify the rotor drag coefficients, which are required to compute the feed-forward control terms. The new theoretical results are thoroughly validated trough extensive comparative experiments.
Hungarian Layer: Logics Empowered Neural Architecture
Venue: arXiv cs.CL 2018
Year: 2018

Neural architecture is a purely numeric framework, which fits the data as a continuous function. However, lacking of logic flow (e.g. \textit{if, for, while}), traditional algorithms (e.g. \textit{Hungarian algorithm, A$^*$ searching, decision tress algorithm}) could not be embedded into this paradigm, which limits the theories and applications. In this paper, we reform the calculus graph as a dynamic process, which is guided by logic flow. Within our novel methodology, traditional algorithms could empower numerical neural network. Specifically, regarding the subject of sentence matching, we reformulate this issue as the form of task-assignment, which is solved by Hungarian algorithm. First, our model applies BiLSTM to parse the sentences. Then Hungarian layer aligns the matching positions. Last, we transform the matching results for soft-max regression by another BiLSTM. Extensive experiments show that our model outperforms other state-of-the-art baselines substantially.
Generalised primal-dual grids for unstructured co-volume schemes
Venue: arXiv cs.CG 2018
Year: 2018

The generation of high-quality staggered unstructured grids is considered, leading to the development of a new optimisation-based strategy designed to construct weighted `Regular-Power' tessellations appropriate for co-volume type numerical discretisation techniques. This new framework aims to extend the conventional Delaunay-Voronoi primal-dual structure; seeking to assemble generalised orthogonal tessellations with enhanced geometric quality. The construction of these grids is motivated by the desire to improve the performance and accuracy of numerical methods based on unstructured co-volume type schemes, including various staggered grid techniques for the simulation of fluid dynamics and hyperbolic transport. In this study, a new hybrid optimisation strategy is proposed; seeking to optimise the geometry, topology and weights associated with general, two-dimensional Regular-Power tessellations using a combination of gradient-ascent and energy-based techniques. The performance of this new method is tested experimentally, with a range of complex, multi-resolution primal-dual grids generated for various coastal and regional ocean modelling applications.
A Classification of Functions in Multiterminal Distributed Computing
Venue: arXiv cs.IT 2018
Year: 2018

In the distributed function computation problem, dichotomy theorems, initiated by Han-Kobayashi, seek to classify functions by whether the rate regions for function computation improve on the Slepian-Wolf regions or not. In this paper, we develop a general approach to derive converse bounds on the distributed function computation problem. By using this approach, we recover the sufficiency part, i.e. the conditions such that the Slepian-Wolf regions become optimal, of the known dichotomy theorems in the two-terminal distributed computing. Furthermore, we derive an improved sufficient condition on the dichotomy theorem in the multiterminal distributed computing for the class of i.i.d. sources with positivity condition. Finally, we derive the matching sufficient and necessary condition on the dichotomy theorem in the multiterminal distributed computing for the class of smooth sources.
Shrewd Selection Speeds Surfing: Use Smart EXP3!
Venue: arXiv cs.GT 2018
Year: 2018

In this paper, we explore the use of multi-armed bandit online learning techniques to solve distributed resource selection problems. As an example, we focus on the problem of network selection. Mobile devices often have several wireless networks at their disposal. While choosing the right network is vital for good performance, a decentralized solution remains a challenge. The impressive theoretical properties of multi-armed bandit algorithms, like EXP3, suggest that it should work well for this type of problem. Yet, its real-word performance lags far behind. The main reasons are the hidden cost of switching networks and its slow rate of convergence. We propose Smart EXP3, a novel bandit-style algorithm that (a) retains the good theoretical properties of EXP3, (b) bounds the number of switches, and (c) yields significantly better performance in practice. We evaluate Smart EXP3 using simulations, controlled experiments, and real-world experiments. Results show that it stabilizes at the optimal state, achieves fairness among devices and gracefully deals with transient behaviors. In real world experiments, it can achieve 18% faster download over alternate strategies. We conclude that multi-armed bandit algorithms can play an important role in distributed resource selection problems, when practical concerns, such as switching costs and convergence time, are addressed.
A Heuristic Search Algorithm Using the Stability of Learning Algorithms in Certain Scenarios as the Fitness Function: An Artificial General Intelligence Engineering Approach
Venue: arXiv cs.AI 2018
Year: 2018

This paper presents a non-manual design engineering method based on heuristic search algorithm to search for candidate agents in the solution space which formed by artificial intelligence agents modeled on the base of bionics.Compared with the artificial design method represented by meta-learning and the bionics method represented by the neural architecture chip,this method is more feasible for realizing artificial general intelligence,and it has a much better interaction with cognitive neuroscience;at the same time,the engineering method is based on the theoretical hypothesis that the final learning algorithm is stable in certain scenarios,and has generalization ability in various scenarios.The paper discusses the theory preliminarily and proposes the possible correlation between the theory and the fixed-point theorem in the field of mathematics.Limited by the author's knowledge level,this correlation is proposed only as a kind of conjecture.
A path to AI
Venue: arXiv cs.CY 2018
Year: 2018

To build a safe system that would replicate and perhaps transcend human-level intelligence, three basic modules: objective, agent, and perception are proposed for development. The objective module would ensure that the system acts in humanity's interest, not against it. It would have two components: a network of machine learning agents to address the problem of value alignment and a distributed ledger to propose a mechanism to mitigate the existential threat. The agent module would further develop the Dyna concept and benefit from a treatise in sociology to build the missing link of artificial general intelligence - a world simulator. The perception module would estimate the state of the world and benefit from existing machine learning algorithms enhanced by a new paradigm in hardware design - a quantum computer. This paper describes a way in which such a system could be built, analyzing the current state of the art and providing alternative directions for research rather than concrete, industry-ready solutions.
Image Inpainting for High-Resolution Textures using CNN Texture Synthesis
Venue: arXiv cs.CV 2018
Year: 2018

Deep neural networks have been successfully applied to problems such as image segmentation, image super-resolution, coloration and image inpainting. In this work we propose the use of convolutional neural networks (CNN) for image inpainting of large regions in high-resolution textures. Due to limited computational resources processing high-resolution images with neural networks is still an open problem. Existing methods separate inpainting of global structure and the transfer of details, which leads to blurry results and loss of global coherence in the detail transfer step. Based on advances in texture synthesis using CNNs we propose patch-based image inpainting by a CNN that is able to optimize for global as well as detail texture statistics. Our method is capable of filling large inpainting regions, oftentimes exceeding the quality of comparable methods for high-resolution images. For reference patch look-up we propose to use the same summary statistics that are used in the inpainting process.
Control of a nonlinear continuous stirred tank reactor via event triggered sliding modes
Venue: arXiv cs.SY 2018
Year: 2018

Continuous Stirred Tank Reactors (CSTR) are the most important and central equipment in many chemical and biochemical industry that exhibit second order complex nonlinear dynamics. The nonlinear dynamics of CSTR poses many design and control challenges. The proposed controller guarantees a stable closed loop behavior over multiple operating points even in presence of disturbances and parametric uncertainties. An event driven sliding mode control is presented in this work to regulate the temperature and concentration very close to the equilibrium points of CSTR. The control is executed only when a predefined condition gets violated and hence the controller is relaxed when the system is operating under tolerable limits in terms of closed loop performance. A novel dynamic event triggering rule is presented to maintain desired performance with minimum computational cost. The inter event execution time is shown to be lower bounded by a finite positive quantity to exclude Zeno behavior. Sliding mode control (SMC) combined with event triggering scheme retains the inherent robustness of traditional SMC and aids in reducing computational load on the controller involved. Simulation results validate the efficiency of the proposed controller.
Overcoming Endurance Issue: UAV-Enabled Communications with Proactive Caching
Venue: arXiv cs.IT 2018
Year: 2018

Wireless communication enabled by unmanned aerial vehicles (UAVs) has emerged as an appealing technology for many application scenarios in future wireless systems. However, the limited endurance of UAVs greatly hinders the practical implementation of UAV-enabled communications. To overcome this issue, this paper proposes a novel scheme for UAV-enabled communications by utilizing the promising technique of proactive caching at the users. Specifically, we focus on content-centric communication systems, where a UAV is dispatched to serve a group of ground nodes (GNs) with random and asynchronous requests for files drawn from a given set. With the proposed scheme, at the beginning of each operation period, the UAV pro-actively transmits the files to a subset of selected GNs that cooperatively cache all the files in the set. As a result, when requested, a file can be retrieved by each GN either directly from its local cache or from its nearest neighbor that has cached the file via device-to-device (D2D) communications. It is revealed that there exists a fundamental trade-off between the file caching cost, which is the total time required for the UAV to transmit the files to their designated caching GNs, and the file retrieval cost, which is the average time required for serving one file request. To characterize this trade-off, we formulate an optimization problem to minimize the weighted sum of the two costs, via jointly designing the file caching policy, the UAV trajectory and communication scheduling. As the formulated problem is NP-hard in general, we propose efficient algorithms to find high-quality approximate solutions for it. Numerical results are provided to corroborate our study and show the great potential of proactive caching for overcoming the limited endurance issue in UAV-enabled communications.
On Stochastic Orders and Fast Fading Multiuser Channels with Statistical CSIT
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, fading Gaussian multiuser channels are considered. If the channel is perfectly known to the transmitter, capacity has been established for many cases in which the channels may satisfy certain information theoretic orders such as degradedness or strong/very strong interference. Here, we study the case when only the statistics of the channels are known at the transmitter which is an open problem in general. The main contribution of this paper is the following: First, we introduce a framework to classify random fading channels based on their joint distributions by leveraging three schemes: maximal coupling, coupling, and copulas. The underlying spirit of all scheme is, we obtain an equivalent channel by changing the joint distribution in such a way that it now satisfies a certain information theoretic order while ensuring that the marginal distributions of the channels to the different users are not changed. The construction of this equivalent multi-user channel allows us to directly make use of existing capacity results, which includes Gaussian interference channels, Gaussian broadcast channels, and Gaussian wiretap channels. We also extend the framework to channels with a specific memory structure, namely, channels with finite-state, wherein the Markov fading broadcast channel is discussed as a special case. Several practical examples such as Rayleigh fading and Nakagami-\textit{m} fading illustrate the applicability of the derived results.
Attack Vulnerability of Complex Networks in Center-Based Strategies
Venue: arXiv cs.SI 2018
Year: 2018

Central nodes are critical in establishing structural connectivity in a complex network. Attacking such nodes can create real havoc in a complex system. We propose attack strategies based on four types of centers, namely betweenness center, degree center, median, and center. We study the vulnerability of synthetic as well as real-world networks in these center-based attacks. These attacks are node-removal attacks which involve identifying the central node set and removing them from the network. We observed that the attacks based on recalculated network information are more efficient than ones based on initial network information. This work shows that the median-based attack, which is a novel strategy proposed in this work, is highly destructive in real as well as synthetic networks.
Temporal Stability in Predictive Process Monitoring
Venue: arXiv cs.LG 2018
Year: 2018

Predictive process monitoring is concerned with the analysis of events produced during the execution of a business process in order to predict as early as possible the final outcome of an ongoing case. Traditionally, predictive process monitoring methods are optimized with respect to accuracy. However, in environments where users make decisions and take actions in response to the predictions they receive, it is equally important to optimize the stability of the successive predictions made for each case. To this end, this paper defines a notion of temporal stability for binary classification tasks in predictive process monitoring and evaluates existing methods with respect to both temporal stability and accuracy. We find that methods based on XGBoost and LSTM neural networks exhibit the highest temporal stability. We then show that temporal stability can be enhanced by hyperparameter-optimizing random forests and XGBoost classifiers with respect to inter-run stability. Finally, we show that time series smoothing techniques can further enhance temporal stability at the expense of slightly lower accuracy.
Computational Complexity of the Interleaving Distance
Venue: arXiv cs.CG 2018
Year: 2018

The interleaving distance is arguably the most prominent distance measure in topological data analysis. In this paper, we provide bounds on the computational complexity of determining the interleaving distance in several settings. We show that the interleaving distance is NP-hard to compute for persistence modules valued in the category of vector spaces. In the specific setting of multidimensional persistent homology we show that the problem is at least as hard as a matrix invertibility problem. Furthermore, this allows us to conclude that the interleaving distance of interval decomposable modules depends on the characteristic of the field. Persistence modules valued in the category of sets are also studied. As a corollary, we obtain that the isomorphism problem for Reeb graphs is graph isomorphism complete.