OpenRaiser/Intern-Atlas huggingface dataset:
Ring Learning With Errors: A crossroads between postquantum cryptography, machine learning and number theory
Venue: arXiv cs.CR 2020
Year: 2020

The present survey reports on the state of the art of the different cryptographic functionalities built upon the ring learning with errors problem and its interplay with several classical problems in algebraic number theory. The survey is based to a certain extent on an invited course given by the author at the Basque Center for Applied Mathematics in September 2018.
Succinct Data Structures for Families of Interval Graphs
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of designing succinct data structures for interval graphs with $n$ vertices while supporting degree, adjacency, neighborhood and shortest path queries in optimal time in the $Θ(\log n)$-bit word RAM model. The degree query reports the number of incident edges to a given vertex in constant time, the adjacency query returns true if there is an edge between two vertices in constant time, the neighborhood query reports the set of all adjacent vertices in time proportional to the degree of the queried vertex, and the shortest path query returns a shortest path in time proportional to its length, thus the running times of these queries are optimal. Towards showing succinctness, we first show that at least $n\log{n} - 2n\log\log n - O(n)$ bits are necessary to represent any unlabeled interval graph $G$ with $n$ vertices, answering an open problem of Yang and Pippenger [Proc. Amer. Math. Soc. 2017]. This is augmented by a data structure of size $n\log{n} +O(n)$ bits while supporting not only the aforementioned queries optimally but also capable of executing various combinatorial algorithms (like proper coloring, maximum independent set etc.) on the input interval graph efficiently. Finally, we extend our ideas to other variants of interval graphs, for example, proper/unit interval graphs, k-proper and k-improper interval graphs, and circular-arc graphs, and design succinct/compact data structures for these graph classes as well along with supporting queries on them efficiently.
Long-Range Indoor Navigation with PRM-RL
Venue: arXiv cs.RO 2020
Year: 2020

Long-range indoor navigation requires guiding robots with noisy sensors and controls through cluttered environments along paths that span a variety of buildings. We achieve this with PRM-RL, a hierarchical robot navigation method in which reinforcement learning agents that map noisy sensors to robot controls learn to solve short-range obstacle avoidance tasks, and then sampling-based planners map where these agents can reliably navigate in simulation; these roadmaps and agents are then deployed on robots, guiding them along the shortest path where the agents are likely to succeed. Here we use Probabilistic Roadmaps (PRMs) as the sampling-based planner, and AutoRL as the reinforcement learning method in the indoor navigation context. We evaluate the method in simulation for kinematic differential drive and kinodynamic car-like robots in several environments, and on differential-drive robots at three physical sites. Our results show PRM-RL with AutoRL is more successful than several baselines, is robust to noise, and can guide robots over hundreds of meters in the face of noise and obstacles in both simulation and on robots, including over 5.8 kilometers of physical robot navigation. Video: https://youtu.be/xN-OWX5gKvQ
Middleware Implementation in Cloud-MANET Mobility Model for Internet of Smart Devices
Venue: arXiv cs.NI 2020
Year: 2020

The smart devices are extremely useful devices that are making our lives easier than before. A smart device is facilitated us to establish a connection with another smart device in a wireless network with a decentralized approach. The mobile ad hoc network (MANET) is a novel methodology that discovers neighborhood devices and establishes connection among them without centralized infrastructure. Cloud provides service to the MANET users to access cloud and communicates with another MANET users. In this article, I integrated MANET and cloud together and formed a new mobility model named Cloud-MANET. In this Mobility model, if one smart device of MANET is able to connect to the internet then all smart devices are enabled to use cloud service and can be interacted with another smart device in the Cloud-MANET framework. A middleware acts as an interface between MANET and cloud. The objective of this article is to implement a middleware in Cloud-MANET mobility model for communication on internet of smart devices.
Anonymity Preserving Byzantine Vector Consensus
Venue: arXiv cs.DC 2020
Year: 2020

Collecting anonymous opinions finds various applications ranging from simple whistleblowing, releasing secretive information, to complex forms of voting, where participants rank candidates by order of preferences. Unfortunately, as far as we know there is no efficient distributed solution to this problem. Previously, participants had to trust third parties, run expensive cryptographic protocols or sacrifice anonymity. In this paper, we propose a resilient-optimal solution to this problem called AVCP, which tolerates up to a third of Byzantine participants. AVCP combines traceable ring signatures to detect double votes with a reduction from vector consensus to binary consensus to ensure all valid votes are taken into account. We prove our algorithm correct and show that it preserves anonymity with at most a linear communication overhead and constant message overhead when compared to a recent consensus baseline. Finally, we demonstrate empirically that the protocol is practical by deploying it on 100 machines geo-distributed in 3 continents: America, Asia and Europe. Anonymous decisions are reached within 10 seconds with a conservative choice of traceable ring signatures.
Learning Dynamic-Objective Policies from a Class of Optimal Trajectories
Venue: arXiv cs.SY 2020
Year: 2020

Optimal state-feedback controllers, capable of changing between different objective functions, are advantageous to systems in which unexpected situations may arise. However, synthesising such controllers, even for a single objective, is a demanding process. In this paper, we present a novel and straightforward approach to synthesising these policies through a combination of trajectory optimisation, homotopy continuation, and imitation learning. We use numerical continuation to efficiently generate optimal demonstrations across several objectives and boundary conditions, and use these to train our policies. Additionally, we demonstrate the ability of our policies to effectively learn families of optimal state-feedback controllers, which can be used to change objective functions online. We illustrate this approach across two trajectory optimisation problems, an inverted pendulum swingup and a spacecraft orbit transfer, and show that the synthesised policies, when evaluated in simulation, produce trajectories that are near-optimal. These results indicate the benefit of trajectory optimisation and homotopy continuation to the synthesis of controllers in dynamic-objective contexts.
Shallow Water Bathymetry Mapping from UAV Imagery based on Machine Learning
Venue: arXiv cs.CV 2020
Year: 2020

The determination of accurate bathymetric information is a key element for near offshore activities, hydrological studies such as coastal engineering applications, sedimentary processes, hydrographic surveying as well as archaeological mapping and biological research. UAV imagery processed with Structure from Motion (SfM) and Multi View Stereo (MVS) techniques can provide a low-cost alternative to established shallow seabed mapping techniques offering as well the important visual information. Nevertheless, water refraction poses significant challenges on depth determination. Till now, this problem has been addressed through customized image-based refraction correction algorithms or by modifying the collinearity equation. In this paper, in order to overcome the water refraction errors, we employ machine learning tools that are able to learn the systematic underestimation of the estimated depths. In the proposed approach, based on known depth observations from bathymetric LiDAR surveys, an SVR model was developed able to estimate more accurately the real depths of point clouds derived from SfM-MVS procedures. Experimental results over two test sites along with the performed quantitative validation indicated the high potential of the developed approach.
Unsupervised Segmentation Algorithms' Implementation in ITK for Tissue Classification via Human Head MRI Scans
Venue: arXiv cs.CV 2020
Year: 2020

Tissue classification is one of the significant tasks in the field of biomedical image analysis. Magnetic Resonance Imaging (MRI) is of great importance in tissue classification especially in the areas of brain tissue classification which is able to recognize anatomical areas of interest such as surgical planning, monitoring therapy, clinical drug trials, image registration, stereotactic neurosurgery, radiotherapy etc. The task of this paper is to implement different unsupervised classification algorithms in ITK and perform tissue classification (white matter, gray matter, cerebrospinal fluid (CSF) and background of the human brain). For this purpose, 5 grayscale head MRI scans are provided. In order of classifying brain tissues, three algorithms are used. These are: Otsu thresholding, Bayesian classification and Bayesian classification with Gaussian smoothing. The obtained classification results are analyzed in the results and discussion section.
Covariance-Aided CSI Acquisition with Non-Orthogonal Pilots in Massive MIMO: A Large-System Performance Analysis
Venue: arXiv cs.IT 2020
Year: 2020

Massive multiple-input multiple-output (MIMO) systems use antenna arrays with a large number of antenna elements to serve many different users simultaneously. The large number of antennas in the system makes, however, the channel state information (CSI) acquisition strategy design critical and particularly challenging. Interestingly, in the context of massive MIMO systems, channels exhibit a large degree of spatial correlation which results in strongly rank-deficient spatial covariance matrices at the base station (BS). With the final objective of analyzing the benefits of covariance-aided uplink multi-user CSI acquisition in massive MIMO systems, here we compare the channel estimation mean-square error (MSE) for (i) conventional CSI acquisition, which does not assume any knowledge on the user spatial covariance matrices and uses orthogonal pilot sequences; and (ii) covariance-aided CSI acquisition, which exploits the individual covariance matrices for channel estimation and enables the use of non-orthogonal pilot sequences. We apply a large-system analysis to the latter case, for which new asymptotic MSE expressions are established under various assumptions on the distributions of the pilot sequences and on the covariance matrices. We link these expressions to those describing the estimation MSE of conventional CSI acquisition with orthogonal pilot sequences of some equivalent length. This analysis provides insights on how much training overhead can be reduced with respect to the conventional strategy when a covariance-aided approach is adopted.
Transformation Consistent Self-ensembling Model for Semi-supervised Medical Image Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

Deep convolutional neural networks have achieved remarkable progress on a variety of medical image computing tasks. A common problem when applying supervised deep learning methods to medical images is the lack of labeled data, which is very expensive and time-consuming to be collected. In this paper, we present a novel semi-supervised method for medical image segmentation, where the network is optimized by the weighted combination of a common supervised loss for labeled inputs only and a regularization loss for both labeled and unlabeled data. To utilize the unlabeled data, our method encourages the consistent predictions of the network-in-training for the same input under different regularizations. Aiming for the semi-supervised segmentation problem, we enhance the effect of regularization for pixel-level predictions by introducing a transformation, including rotation and flipping, consistent scheme in our self-ensembling model. With the aim of semi-supervised segmentation tasks, we introduce a transformation consistent strategy in our self-ensembling model to enhance the regularization effect for pixel-level predictions. We have extensively validated the proposed semi-supervised method on three typical yet challenging medical image segmentation tasks: (i) skin lesion segmentation from dermoscopy images on International Skin Imaging Collaboration (ISIC) 2017 dataset, (ii) optic disc segmentation from fundus images on Retinal Fundus Glaucoma Challenge (REFUGE) dataset, and (iii) liver segmentation from volumetric CT scans on Liver Tumor Segmentation Challenge (LiTS) dataset. Compared to the state-of-the-arts, our proposed method shows superior segmentation performance on challenging 2D/3D medical images, demonstrating the effectiveness of our semi-supervised method for medical image segmentation.
Combinatorial Bandits with Relative Feedback
Venue: arXiv cs.LG 2020
Year: 2020

We consider combinatorial online learning with subset choices when only relative feedback information from subsets is available, instead of bandit or semi-bandit feedback which is absolute. Specifically, we study two regret minimisation problems over subsets of a finite ground set $[n]$, with subset-wise relative preference information feedback according to the Multinomial logit choice model. In the first setting, the learner can play subsets of size bounded by a maximum size and receives top-$m$ rank-ordered feedback, while in the second setting the learner can play subsets of a fixed size $k$ with a full subset ranking observed as feedback. For both settings, we devise instance-dependent and order-optimal regret algorithms with regret $O(\frac{n}{m} \ln T)$ and $O(\frac{n}{k} \ln T)$, respectively. We derive fundamental limits on the regret performance of online learning with subset-wise preferences, proving the tightness of our regret guarantees. Our results also show the value of eliciting more general top-$m$ rank-ordered feedback over single winner feedback ($m=1$). Our theoretical results are corroborated with empirical evaluations.
Robot Learning via Human Adversarial Games
Venue: arXiv cs.RO 2020
Year: 2020

Much work in robotics has focused on "human-in-the-loop" learning techniques that improve the efficiency of the learning process. However, these algorithms have made the strong assumption of a cooperating human supervisor that assists the robot. In reality, human observers tend to also act in an adversarial manner towards deployed robotic systems. We show that this can in fact improve the robustness of the learned models by proposing a physical framework that leverages perturbations applied by a human adversary, guiding the robot towards more robust models. In a manipulation task, we show that grasping success improves significantly when the robot trains with a human adversary as compared to training in a self-supervised manner.
Robot-to-Robot Relative Pose Estimation using Humans as Markers
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we propose a method to determine the 3D relative pose of pairs of communicating robots by using human pose-based key-points as correspondences. We adopt a 'leader-follower' framework, where at first, the leader robot visually detects and triangulates the key-points using the state-of-the-art pose detector named OpenPose. Afterward, the follower robots match the corresponding 2D projections on their respective calibrated cameras and find their relative poses by solving the perspective-n-point (PnP) problem. In the proposed method, we design an efficient person re-identification technique for associating the mutually visible humans in the scene. Additionally, we present an iterative optimization algorithm to refine the associated key-points based on their local structural properties in the image space. We demonstrate that these refinement processes are essential to establish accurate key-point correspondences across viewpoints. Furthermore, we evaluate the performance of the proposed relative pose estimation system through several experiments conducted in terrestrial and underwater environments. Finally, we discuss the relevant operational challenges of this approach and analyze its feasibility for multi-robot cooperative systems in human-dominated social settings and feature-deprived environments such as underwater.
User Review-Based Change File Localization for Mobile Applications
Venue: arXiv cs.SE 2020
Year: 2020

In the current mobile app development, novel and emerging DevOps practices (e.g., Continuous Delivery, Integration, and user feedback analysis) and tools are becoming more widespread. For instance, the integration of user feedback (provided in the form of user reviews) in the software release cycle represents a valuable asset for the maintenance and evolution of mobile apps. To fully make use of these assets, it is highly desirable for developers to establish semantic links between the user reviews and the software artefacts to be changed (e.g., source code and documentation), and thus to localize the potential files to change for addressing the user feedback. In this paper, we propose RISING (Review Integration via claSsification, clusterIng, and linkiNG), an automated approach to support the continuous integration of user feedback via classification, clustering, and linking of user reviews. RISING leverages domain-specific constraint information and semi-supervised learning to group user reviews into multiple fine-grained clusters concerning similar users' requests. Then, by combining the textual information from both commit messages and source code, it automatically localizes potential change files to accommodate the users' requests. Our empirical studies demonstrate that the proposed approach outperforms the state-of-the-art baseline work in terms of clustering and localization accuracy, and thus produces more reliable results.
State-Continuity Approximation of Markov Decision Processes via Finite Element Methods for Autonomous System Planning
Venue: arXiv cs.RO 2020
Year: 2020

Motion planning under uncertainty for an autonomous system can be formulated as a Markov Decision Process with a continuous state space. In this paper, we propose a novel solution to this decision-theoretic planning problem that directly obtains the continuous value function with only the first and second moments of the transition probabilities, alleviating the requirement for an explicit transition model in the literature. We achieve this by expressing the value function as a linear combination of basis functions and approximating the Bellman equation by a partial differential equation, where the value function can be naturally constructed using a finite element method. We have validated our approach via extensive simulations, and the evaluations reveal that to baseline methods, our solution leads to in terms of path smoothness, travel distance, and time costs.
Deterministic Sparse Fourier Transform with an ell_infty Guarantee
Venue: arXiv cs.DS 2020
Year: 2020

In this paper we revisit the deterministic version of the Sparse Fourier Transform problem, which asks to read only a few entries of $x \in \mathbb{C}^n$ and design a recovery algorithm such that the output of the algorithm approximates $\hat x$, the Discrete Fourier Transform (DFT) of $x$. The randomized case has been well-understood, while the main work in the deterministic case is that of Merhi et al.\@ (J Fourier Anal Appl 2018), which obtains $O(k^2 \log^{-1}k \cdot \log^{5.5}n)$ samples and a similar runtime with the $\ell_2/\ell_1$ guarantee. We focus on the stronger $\ell_{\infty}/\ell_1$ guarantee and the closely related problem of incoherent matrices. We list our contributions as follows. 1. We find a deterministic collection of $O(k^2 \log n)$ samples for the $\ell_\infty/\ell_1$ recovery in time $O(nk \log^2 n)$, and a deterministic collection of $O(k^2 \log^2 n)$ samples for the $\ell_\infty/\ell_1$ sparse recovery in time $O(k^2 \log^3n)$. 2. We give new deterministic constructions of incoherent matrices that are row-sampled submatrices of the DFT matrix, via a derandomization of Bernstein's inequality and bounds on exponential sums considered in analytic number theory. Our first construction matches a previous randomized construction of Nelson, Nguyen and Woodruff (RANDOM'12), where there was no constraint on the form of the incoherent matrix. Our algorithms are nearly sample-optimal, since a lower bound of $Ω(k^2 + k \log n)$ is known, even for the case where the sensing matrix can be arbitrarily designed. A similar lower bound of $Ω(k^2 \log n/ \log k)$ is known for incoherent matrices.
SECNLP: A Survey of Embeddings in Clinical Natural Language Processing
Venue: arXiv cs.CL 2020
Year: 2020

Traditional representations like Bag of words are high dimensional, sparse and ignore the order as well as syntactic and semantic information. Distributed vector representations or embeddings map variable length text to dense fixed length vectors as well as capture the prior knowledge which can transferred to downstream tasks. Even though embedding has become de facto standard for representations in deep learning based NLP tasks in both general and clinical domains, there is no survey paper which presents a detailed review of embeddings in Clinical Natural Language Processing. In this survey paper, we discuss various medical corpora and their characteristics, medical codes and present a brief overview as well as comparison of popular embeddings models. We classify clinical embeddings into nine types and discuss each embedding type in detail. We discuss various evaluation methods followed by possible solutions to various challenges in clinical embeddings. Finally, we conclude with some of the future directions which will advance the research in clinical embeddings.
Learning Sensory-Motor Associations from Demonstration
Venue: arXiv cs.RO 2020
Year: 2020

We propose a method which generates reactive robot behavior learned from human demonstration. In order to do so, we use the Playful programming language which is based on the reactive programming paradigm. This allows us to represent the learned behavior as a set of associations between sensor and motor primitives in a human readable script. Distinguishing between sensor and motor primitives introduces a supplementary level of granularity and more importantly enforces feedback, increasing adaptability and robustness. As the experimental section shows, useful behaviors may be learned from a single demonstration covering a very limited portion of the task space.