OpenRaiser/Intern-Atlas huggingface dataset:
Regularisation Can Mitigate Poisoning Attacks: A Novel Analysis Based on Multiobjective Bilevel Optimisation
Venue: arXiv cs.LG 2020
Year: 2020

Machine Learning (ML) algorithms are vulnerable to poisoning attacks, where a fraction of the training data is manipulated to deliberately degrade the algorithms' performance. Optimal poisoning attacks, which can be formulated as bilevel optimisation problems, help to assess the robustness of learning algorithms in worst-case scenarios. However, current attacks against algorithms with hyperparameters typically assume that these hyperparameters remain constant ignoring the effect the attack has on them. We show that this approach leads to an overly pessimistic view of the robustness of the algorithms. We propose a novel optimal attack formulation that considers the effect of the attack on the hyperparameters by modelling the attack as a multiobjective bilevel optimisation problem. We apply this novel attack formulation to ML classifiers using $L_2$ regularisation and show that, in contrast to results previously reported, $L_2$ regularisation enhances the stability of the learning algorithms and helps to mitigate the attacks. Our empirical evaluation on different datasets confirms the limitations of previous strategies, evidences the benefits of using $L_2$ regularisation to dampen the effect of poisoning attacks and shows how the regularisation hyperparameter increases with the fraction of poisoning points.
Decentralized Multi-player Multi-armed Bandits with No Collision Information
Venue: arXiv cs.LG 2020
Year: 2020

The decentralized stochastic multi-player multi-armed bandit (MP-MAB) problem, where the collision information is not available to the players, is studied in this paper. Building on the seminal work of Boursier and Perchet (2019), we propose error correction synchronization involving communication (EC-SIC), whose regret is shown to approach that of the centralized stochastic MP-MAB with collision information. By recognizing that the communication phase without collision information corresponds to the Z-channel model in information theory, the proposed EC-SIC algorithm applies optimal error correction coding for the communication of reward statistics. A fixed message length, as opposed to the logarithmically growing one in Boursier and Perchet (2019), also plays a crucial role in controlling the communication loss. Experiments with practical Z-channel codes, such as repetition code, flip code and modified Hamming code, demonstrate the superiority of EC-SIC in both synthetic and real-world datasets.
An End-to-End Graph Convolutional Kernel Support Vector Machine
Venue: arXiv cs.LG 2020
Year: 2020

A novel kernel-based support vector machine (SVM) for graph classification is proposed. The SVM feature space mapping consists of a sequence of graph convolutional layers, which generates a vector space representation for each vertex, followed by a pooling layer which generates a reproducing kernel Hilbert space (RKHS) representation for the graph. The use of a RKHS offers the ability to implicitly operate in this space using a kernel function without the computational complexity of explicitly mapping into it. The proposed model is trained in a supervised end-to-end manner whereby the convolutional layers, the kernel function and SVM parameters are jointly optimized with respect to a regularized classification loss. This approach is distinct from existing kernel-based graph classification models which instead either use feature engineering or unsupervised learning to define the kernel function. Experimental results demonstrate that the proposed model outperforms existing deep learning baseline models on a number of datasets.
The Rate Distortion Function of Asynchronously Sampled Memoryless Cyclostationary Gaussian Processes
Venue: arXiv cs.IT 2020
Year: 2020

Man-made communications signals are typically modelled as continuous-time (CT) wide-sense cyclostationary (WSCS) processes. As modern processing is digital, it operates on sampled versions of the CT signals. When sampling is applied to a CT WSCS process, the statistics of the resulting discrete-time (DT) process depends on the relationship between the sampling interval and the period of the statistics of the CT process: When these two parameters have a common integer factor, then the DT process is WSCS. This situation is referred to as synchronous sampling. When this is not the case, which is referred to as asynchronous sampling, the resulting DT process is wide-sense almost cyclostationary (WSACS). In this work, we study the fundamental tradeoff of sources codes applied to sampled CT WSCS processes, namely, their rate-distortion function (RDF). We note that RDF characterization for the case of synchronous sampling directly follows from classic information-theoretic tools utilizing ergodicity and the law of large numbers; however, when sampling is asynchronous, the resulting process is not information stable. In such cases, commonly used information-theoretic tools are inapplicable to RDF analysis, which poses a major challenge. Using the information spectrum framework, we show that the RDF for asynchronous sampling in the low distortion regime can be expressed as the limit superior of a sequence of RDFs in which each element corresponds to the RDF of a synchronously sampled WSCS process (but their limit is not guaranteed to exist). The resulting characterization allows us to introduce novel insights on the relationship between sampling synchronization and RDF. For example, we demonstrate that, differently from stationary processes, small differences in the sampling rate and the sampling time offset can notably affect the RDF of sampled CT WSCS processes.
Representations, Metrics and Statistics For Shape Analysis of Elastic Graphs
Venue: arXiv cs.CV 2020
Year: 2020

Past approaches for statistical shape analysis of objects have focused mainly on objects within the same topological classes, e.g., scalar functions, Euclidean curves, or surfaces, etc. For objects that differ in more complex ways, the current literature offers only topological methods. This paper introduces a far-reaching geometric approach for analyzing shapes of graphical objects, such as road networks, blood vessels, brain fiber tracts, etc. It represents such objects, exhibiting differences in both geometries and topologies, as graphs made of curves with arbitrary shapes (edges) and connected at arbitrary junctions (nodes). To perform statistical analyses, one needs mathematical representations, metrics and other geometrical tools, such as geodesics, means, and covariances. This paper utilizes a quotient structure to develop efficient algorithms for computing these quantities, leading to useful statistical tools, including principal component analysis and analytical statistical testing and modeling of graphical shapes. The efficacy of this framework is demonstrated using various simulated as well as the real data from neurons and brain arterial networks.
Enumerating Hardware-Software Splits with Program Rewriting
Venue: arXiv cs.DC 2020
Year: 2020

A core problem in hardware-software codesign is in the sheer size of the design space. Without a set ISA to constrain the hardware-software interface, the design space explodes. This work presents a strategy for managing the massive hardware-software design space within the domain of machine learning inference workloads and accelerators. We first propose EngineIR, a new language for representing machine learning hardware and software in a single program. Then, using equality graphs -- a data structure from the compilers literature -- we suggest a method for efficiently enumerating the design space by performing rewrites over our representation.
Unsupervised Dictionary Learning for Anomaly Detection
Venue: arXiv cs.LG 2020
Year: 2020

We investigate the possibilities of employing dictionary learning to address the requirements of most anomaly detection applications, such as absence of supervision, online formulations, low false positive rates. We present new results of our recent semi-supervised online algorithm, TODDLeR, on a anti-money laundering application. We also introduce a novel unsupervised method of using the performance of the learning algorithm as indication of the nature of the samples.
Improving Sustainability of Cryptocurrency Payment Networks for IoT Applications
Venue: arXiv cs.CR 2020
Year: 2020

Blockchain-based cryptocurrencies received a lot of attention recently for their applications in many domains. IoT domain is one of such applications, which can utilize cryptocur-rencies for micro payments without compromising their payment privacy. However, long confirmation times of transactions and relatively high fees hinder the adoption of cryptoccurency based micro-payments. The payment channel networks is one of the proposed solutions to address these issue where nodes establish payment channels among themselves without writing on blockchain. IoT devices can benefit from such payment networks as long as they are capable of sustaining their overhead. Payment channel networks pose unique characteristics as far as the routing problem is concerned. Specifically, they should stay balanced to have a sustainable network for maintaining payments for longer times, which is crucial for IoT devices once they are deployed.In this paper, we present a payment channel network design that aims to keep the channels balanced by using a common weight policy across the network. We additionally propose using multi-point connections to nodes for each IoT device for unbalanced payment scenarios. The experiment results show that we can keep the channels in the network more equally balanced compared to the minimal fee approach. In addition, multiple connections from IoT devices to nodes increase the success ratio significantly.
Three-dimensional matching is NP-Hard
Venue: arXiv cs.CC 2020
Year: 2020

The standard proof of NP-Hardness of 3DM provides a power-$4$ reduction of 3SAT to 3DM. In this note, we provide a linear-time reduction. Under the exponential time hypothesis, this reduction improves the runtime lower bound from $2^{o(\sqrt[4]{m})}$ (under the standard reduction) to $2^{o(m)}$.
Calibrated Prediction with Covariate Shift via Unsupervised Domain Adaptation
Venue: arXiv cs.LG 2020
Year: 2020

Reliable uncertainty estimates are an important tool for helping autonomous agents or human decision makers understand and leverage predictive models. However, existing approaches to estimating uncertainty largely ignore the possibility of covariate shift--i.e., where the real-world data distribution may differ from the training distribution. As a consequence, existing algorithms can overestimate certainty, possibly yielding a false sense of confidence in the predictive model. We propose an algorithm for calibrating predictions that accounts for the possibility of covariate shift, given labeled examples from the training distribution and unlabeled examples from the real-world distribution. Our algorithm uses importance weighting to correct for the shift from the training to the real-world distribution. However, importance weighting relies on the training and real-world distributions to be sufficiently close. Building on ideas from domain adaptation, we additionally learn a feature map that tries to equalize these two distributions. In an empirical evaluation, we show that our proposed approach outperforms existing approaches to calibrated prediction when there is covariate shift.
Clinical Text Summarization with Syntax-Based Negation and Semantic Concept Identification
Venue: arXiv cs.CL 2020
Year: 2020

In the era of clinical information explosion, a good strategy for clinical text summarization is helpful to improve the clinical workflow. The ideal summarization strategy can preserve important information in the informative but less organized, ill-structured clinical narrative texts. Instead of using pure statistical learning approaches, which are difficult to interpret and explain, we utilized knowledge of computational linguistics with human experts-curated biomedical knowledge base to achieve the interpretable and meaningful clinical text summarization. Our research objective is to use the biomedical ontology with semantic information, and take the advantage from the language hierarchical structure, the constituency tree, in order to identify the correct clinical concepts and the corresponding negation information, which is critical for summarizing clinical concepts from narrative text. We achieved the clinically acceptable performance for both negation detection and concept identification, and the clinical concepts with common negated patterns can be identified and negated by the proposed method.
Deep Reinforcement Learning for Fresh Data Collection in UAV-assisted IoT Networks
Venue: arXiv cs.IT 2020
Year: 2020

Due to the flexibility and low operational cost, dispatching unmanned aerial vehicles (UAVs) to collect information from distributed sensors is expected to be a promising solution in Internet of Things (IoT), especially for time-critical applications. How to maintain the information freshness is a challenging issue. In this paper, we investigate the fresh data collection problem in UAV-assisted IoT networks. Particularly, the UAV flies towards the sensors to collect status update packets within a given duration while maintaining a non-negative residual energy. We formulate a Markov Decision Process (MDP) to find the optimal flight trajectory of the UAV and transmission scheduling of the sensors that minimizes the weighted sum of the age of information (AoI). A UAV-assisted data collection algorithm based on deep reinforcement learning (DRL) is further proposed to overcome the curse of dimensionality. Extensive simulation results demonstrate that the proposed DRL-based algorithm can significantly reduce the weighted sum of the AoI compared to other baseline algorithms.
The cross cyclomatic complexity: a bi-dimensional measure for program complexity on graphs
Venue: arXiv cs.SE 2020
Year: 2020

Reduce and control complexity is an essential practice in software design. Cyclomatic complexity (CC) is one of the most popular software metrics, applied for more than 40 years. Despite CC is an interesting metric to highlight the number of branches in a program, it clearly not sufficient to represent the complexity in a piece of software. In this paper, we introduce the cross cyclomatic complexity (CCC), a new bi-dimensional complexity measure on graphs that combines the cyclomatic complexity and the weight of a minimum-weight cycle basis in as pair on the Cartesian plan to characterize program complexity using control flow graphs. Our postulates open a new venue to represent program complexity, and we discuss its implications and opportunities.
Optimal codes with small constant weight in $\ell_1$-metric
Venue: arXiv cs.IT 2020
Year: 2020

Motivated by the duplication-correcting problem for data storage in live DNA, we study the construction of constant-weight codes in $\ell_1$-metric. By using packings and group divisible designs in combinatorial design theory, we give constructions of optimal codes over non-negative integers and optimal ternary codes with $\ell_1$-weight $w\leq 4$ for all possible distances. In general, we derive the size of the largest ternary code with constant weight $w$ and distance $2w-2$ for sufficiently large length $n$ satisfying $n\equiv 1,w,-w+2,-2w+3\pmod{w(w-1)}$.
Mitigation of Civilian-to-Military Interference in DSRC for Urban Operations
Venue: arXiv cs.NI 2020
Year: 2020

Dedicated short-range communications (DSRC) attracts popularity in the military applications thanks to its easiness in establishment, no need for paid subscription, and wide compatibility with any other IEEE 802.11 standards. The main challenge in DSRC is congestion due to existence of only 7 channels, which may not be enough to accommodate the increased number of transmitters expected to be deployed in the near future. Recently, there are a myriad of urban operation scenarios for the military including urban warfare and humanitarian assistance/disaster relief (HA/DR). The key challenge is that the communications among the military vehicles can be interfered by civilian users. It is the desire that the messages transmitted by the military vehicles hold a higher significance so that they can avoid the interference coming from the civilian users, which is not supported in the current version of DSRC. As a remedy, this paper proposes a protocol that prioritizes the military DSRC users while muffling the civilian DSRC users. Our results show that this prioritization method achieves higher communications performances for the military DSRC users.
Differentially Private Deep Learning with Smooth Sensitivity
Venue: arXiv cs.LG 2020
Year: 2020

Ensuring the privacy of sensitive data used to train modern machine learning models is of paramount importance in many areas of practice. One approach to study these concerns is through the lens of differential privacy. In this framework, privacy guarantees are generally obtained by perturbing models in such a way that specifics of data used to train the model are made ambiguous. A particular instance of this approach is through a "teacher-student" framework, wherein the teacher, who owns the sensitive data, provides the student with useful, but noisy, information, hopefully allowing the student model to perform well on a given task without access to particular features of the sensitive data. Because stronger privacy guarantees generally involve more significant perturbation on the part of the teacher, deploying existing frameworks fundamentally involves a trade-off between student's performance and privacy guarantee. One of the most important techniques used in previous works involves an ensemble of teacher models, which return information to a student based on a noisy voting procedure. In this work, we propose a novel voting mechanism with smooth sensitivity, which we call Immutable Noisy ArgMax, that, under certain conditions, can bear very large random noising from the teacher without affecting the useful information transferred to the student. Compared with previous work, our approach improves over the state-of-the-art methods on all measures, and scale to larger tasks with both better performance and stronger privacy ($ε\approx 0$). This new proposed framework can be applied with any machine learning models, and provides an appealing solution for tasks that requires training on a large amount of data.
High Performance Code Generation in MLIR: An Early Case Study with GEMM
Venue: arXiv cs.PF 2020
Year: 2020

This article is primarily meant to present an early case study on using MLIR, a new compiler intermediate representation infrastructure, for high-performance code generation. Aspects of MLIR covered in particular include memrefs, the affine dialect, and polyhedral utilities and pass infrastructure surrounding those. This article is also aimed at showing the role compiler infrastructure could play in generating code that is competitive with highly tuned manually developed libraries, albeit in a more modular, reusable, and automatable way.
User profiling using smartphone network traffic analysis
Venue: arXiv cs.CR 2020
Year: 2020

The recent decade has witnessed phenomenal growth in communication technology. Development of user-friendly software platforms, such as Facebook, WhatsApp etc. have facilitated ease of communication and thereby people have started freely sharing messages and multimedia over the Internet. Further, there is a shift in trends with services being accessed from smartphones over personal computers. To protect the security and privacy of the smartphone users, most of the applications use encryption that encapsulates communications over the Internet. However, research has shown that the statistical information present in a traffic can be used to identify the application, and further, the activity performed by the user inside that application. In this paper, we extend the scope of analysis by proposing a learning framework to leverage application and activity data to profile smartphone users in terms of their gender, profession age group etc. This will greatly help the authoritative agencies to conduct their investigations related to national security and other purposes.
On the Area Requirements of Planar Greedy Drawings of Triconnected Planar Graphs
Venue: arXiv cs.CG 2020
Year: 2020

In this paper we study the area requirements of planar greedy drawings of triconnected planar graphs. Cao, Strelzoff, and Sun exhibited a family $\cal H$ of subdivisions of triconnected plane graphs and claimed that every planar greedy drawing of the graphs in $\mathcal H$ respecting the prescribed plane embedding requires exponential area. However, we show that every $n$-vertex graph in $\cal H$ actually has a planar greedy drawing respecting the prescribed plane embedding on an $O(n)\times O(n)$ grid. This reopens the question whether triconnected planar graphs admit planar greedy drawings on a polynomial-size grid. Further, we provide evidence for a positive answer to the above question by proving that every $n$-vertex Halin graph admits a planar greedy drawing on an $O(n)\times O(n)$ grid. Both such results are obtained by actually constructing drawings that are convex and angle-monotone. Finally, we consider $α$-Schnyder drawings, which are angle-monotone and hence greedy if $α\leq 30^\circ$, and show that there exist planar triangulations for which every $α$-Schnyder drawing with a fixed $α<60^\circ$ requires exponential area for any resolution rule.
Change Point Detection in Software Performance Testing
Venue: arXiv cs.SE 2020
Year: 2020

We describe our process for automatic detection of performance changes for a software product in the presence of noise. A large collection of tests run periodically as changes to our software product are committed to our source repository, and we would like to identify the commits responsible for performance regressions. Previously, we relied on manual inspection of time series graphs to identify significant changes. That was later replaced with a threshold-based detection system, but neither system was sufficient for finding changes in performance in a timely manner. This work describes our recent implementation of a change point detection system built upon the E-Divisive means algorithm. The algorithm produces a list of change points representing significant changes from a given history of performance results. A human reviews the list of change points for actionable changes, which are then triaged for further inspection. Using change point detection has had a dramatic impact on our ability to detect performance changes. Quantitatively, it has dramatically dropped our false positive rate for performance changes, while qualitatively it has made the entire performance evaluation process easier, more productive (ex. catching smaller regressions), and more timely.
A Reconfigurable Hybrid Actuator with Rigid and Soft Components
Venue: arXiv cs.RO 2020
Year: 2020

Classical rigid-bodied robotic systems are presented with proven success in theoretical development and industrial applications, are recently challenged by the emergence of soft robotics due to a growing need in physical human-robot interactions (pHRI), such as wearable devices, medical robots, personal robots, etc. In this paper, we present the design and fabrication of a robust, hybrid bending actuator build from both rigid and soft components inspired by crustaceans, where its bending radius and axis can be mechanically programmed through the selective activation of the rigid exterior joints, actuated by the soft actuators inside. The hybrid actuator was experimentally measured in terms of bending and force tests to demonstrate the utility of this design. Finally, a case study was presented to demonstrate its capacity to adapt to specific objects geometry, anticipating its potential application in situations where compliance is the priority.