OpenRaiser/Intern-Atlas huggingface dataset:
A Very Low Resource Language Speech Corpus for Computational Language Documentation Experiments
Venue: arXiv cs.CL 2018
Year: 2018

Most speech and language technologies are trained with massive amounts of speech and text information. However, most of the world languages do not have such resources or stable orthography. Systems constructed under these almost zero resource conditions are not only promising for speech technology but also for computational language documentation. The goal of computational language documentation is to help field linguists to (semi-)automatically analyze and annotate audio recordings of endangered and unwritten languages. Example tasks are automatic phoneme discovery or lexicon discovery from the speech signal. This paper presents a speech corpus collected during a realistic language documentation process. It is made up of 5k speech utterances in Mboshi (Bantu C25) aligned to French text translations. Speech transcriptions are also made available: they correspond to a non-standard graphemic form close to the language phonology. We present how the data was collected, cleaned and processed and we illustrate its use through a zero-resource task: spoken term discovery. The dataset is made available to the community for reproducible computational language documentation experiments and their evaluation.
Optimized Frameless ALOHA for Cooperative Base Stations with Overlapped Coverage Areas
Venue: arXiv cs.IT 2018
Year: 2018

Herein, we consider the problem of cooperative multi-access in the presence of overlapped coverage areas. Assuming a frameless ALOHA transmission scheme, we derive exact analytical throughput expressions for throughput in the aforementioned scenarios as a function of the frame length of the system and for arbitrary average numbers of users transmitting in each slot (target degree). After obtaining these original expressions, we then formulate a utility function whose maximization (obtained, e.g., through genetic algorithms) yields unequal and optimum target degrees to be employed by users in each group in order to maximize the peak throughput of the whole system, while satisfying a given prescribed outage. A comparison of the resulting cooperative multiple base station (BS) multi-access scheme against optimized single-BS frameless ALOHA systems - which presume the perfect isolation of users at each BS and an equal optimum target degree for all users - indicates a significant gain in overall throughput, thereby revealing that a multi-access diversity gain can be reaped by allowing groups of users from different BSs to overlap.
Automatic Salient Object Detection for Panoramic Images Using Region Growing and Fixation Prediction Model
Venue: arXiv cs.CV 2018
Year: 2018

Almost all previous works on saliency detection have been dedicated to conventional images, however, with the outbreak of panoramic images due to the rapid development of VR or AR technology, it is becoming more challenging, meanwhile valuable for extracting salient contents in panoramic images. In this paper, we propose a novel bottom-up salient object detection framework for panoramic images. First, we employ a spatial density estimation method to roughly extract object proposal regions, with the help of region growing algorithm. Meanwhile, an eye fixation model is utilized to predict visually attractive parts in the image from the perspective of the human visual search mechanism. Then, the previous results are combined by the maxima normalization to get the coarse saliency map. Finally, a refinement step based on geodesic distance is utilized for post-processing to derive the final saliency map. To fairly evaluate the performance of the proposed approach, we propose a high-quality dataset of panoramic images (SalPan). Extensive evaluations demonstrate the effectiveness of our proposed method on panoramic images and the superiority of the proposed method against other methods.
Distributed Hybrid Simulation of the Internet of Things and Smart Territories
Venue: arXiv cs.CY 2018
Year: 2018

This paper deals with the use of hybrid simulation to build and compose heterogeneous simulation scenarios that can be proficiently exploited to model and represent the Internet of Things (IoT). Hybrid simulation is a methodology that combines multiple modalities of modeling/simulation. Complex scenarios are decomposed into simpler ones, each one being simulated through a specific simulation strategy. All these simulation building blocks are then synchronized and coordinated. This simulation methodology is an ideal one to represent IoT setups, which are usually very demanding, due to the heterogeneity of possible scenarios arising from the massive deployment of an enormous amount of sensors and devices. We present a use case concerned with the distributed simulation of smart territories, a novel view of decentralized geographical spaces that, thanks to the use of IoT, builds ICT services to manage resources in a way that is sustainable and not harmful to the environment. Three different simulation models are combined together, namely, an adaptive agent-based parallel and distributed simulator, an OMNeT++ based discrete event simulator and a script-language simulator based on MATLAB. Results from a performance analysis confirm the viability of using hybrid simulation to model complex IoT scenarios.
Sum-Product-Quotient Networks
Venue: arXiv cs.LG 2018
Year: 2018

We present a novel tractable generative model that extends Sum-Product Networks (SPNs) and significantly boosts their power. We call it Sum-Product-Quotient Networks (SPQNs), whose core concept is to incorporate conditional distributions into the model by direct computation using quotient nodes, e.g. $P(A|B) = \frac{P(A,B)}{P(B)}$. We provide sufficient conditions for the tractability of SPQNs that generalize and relax the decomposable and complete tractability conditions of SPNs. These relaxed conditions give rise to an exponential boost to the expressive efficiency of our model, i.e. we prove that there are distributions which SPQNs can compute efficiently but require SPNs to be of exponential size. Thus, we narrow the gap in expressivity between tractable graphical models and other Neural Network-based generative models.
Optical Network Virtualisation using Multi-technology Monitoring and SDN-enabled Optical Transceiver
Venue: arXiv cs.NI 2018
Year: 2018

We introduce the real-time multi-technology transport layer monitoring to facilitate the coordinated virtualisation of optical and Ethernet networks supported by optical virtualise-able transceivers (V-BVT). A monitoring and network resource configuration scheme is proposed to include the hardware monitoring in both Ethernet and Optical layers. The scheme depicts the data and control interactions among multiple network layers under the software defined network (SDN) background, as well as the application that analyses the monitored data obtained from the database. We also present a re-configuration algorithm to adaptively modify the composition of virtual optical networks based on two criteria. The proposed monitoring scheme is experimentally demonstrated with OpenFlow (OF) extensions for a holistic (re-)configuration across both layers in Ethernet switches and V-BVTs.
Recomputation Enabled Efficient Checkpointing
Venue: arXiv cs.DC 2018
Year: 2018

Systematic checkpointing of the machine state makes restart of execution from a safe state possible upon detection of an error. The time and energy overhead of checkpointing, however, grows with the frequency of checkpointing. Amortizing this overhead becomes especially challenging, considering the growth of expected error rates, as checkpointing frequency tends to increase with increasing error rates. Based on the observation that due to imbalanced technology scaling, recomputing a data value can be more energy efficient than retrieving (i.e., loading) a stored copy, this paper explores how recomputation of data values (which otherwise would be read from a checkpoint from memory or secondary storage) can reduce the machine state to be checkpointed, and thereby reduce the checkpointing overhead. Specifically, the resulting amnesic checkpointing framework AmnesiCHK can reduce the storage overhead by up to 23.91%; time overhead, by 11.92%; and energy overhead, by 12.53%, respectively, even in a relatively small scale system.
Average Age of Information with Hybrid ARQ under a Resource Constraint
Venue: arXiv cs.IT 2018
Year: 2018

Scheduling of the transmission of status updates over an error-prone communication channel is studied in order to minimize the long-term average age of information (AoI) at the destination, under an average resource constraint at the source node, which limits the average number of transmissions. After each transmission, the source receives an instantaneous ACK/NACK feedback, and decides on the next update, without a priori knowledge on the success of the future transmissions. The optimal scheduling policy is studied under different feedback mechanisms; in particular, standard automatic repeat request (ARQ) and hybrid ARQ (HARQ) protocols are considered. Average-cost reinforcement learning algorithms are proposed when the error probabilities for the HARQ system are unknown.
Learners that Use Little Information
Venue: arXiv cs.LG 2018
Year: 2018

We study learning algorithms that are restricted to using a small amount of information from their input sample. We introduce a category of learning algorithms we term $d$-bit information learners, which are algorithms whose output conveys at most $d$ bits of information of their input. A central theme in this work is that such algorithms generalize. We focus on the learning capacity of these algorithms, and prove sample complexity bounds with tight dependencies on the confidence and error parameters. We also observe connections with well studied notions such as sample compression schemes, Occam's razor, PAC-Bayes and differential privacy. We discuss an approach that allows us to prove upper bounds on the amount of information that algorithms reveal about their inputs, and also provide a lower bound by showing a simple concept class for which every (possibly randomized) empirical risk minimizer must reveal a lot of information. On the other hand, we show that in the distribution-dependent setting every VC class has empirical risk minimizers that do not reveal a lot of information.
Human-centered transparency of grasping via a robot-assisted minimally invasive surgery system
Venue: arXiv cs.HC 2018
Year: 2018

We investigate grasping of rigid objects in unilateral robot-assisted minimally invasive surgery (RAMIS) in this paper. We define a human-centered transparency that quantifies natural action and perception in RAMIS. We demonstrate this human-centered transparency analysis for different values of gripper scaling - the scaling between the grasp aperture of the surgeon-side manipulator and the aperture of the surgical instrument grasper. Thirty-one participants performed teleoperated grasping and perceptual assessment of rigid objects in one of three gripper scaling conditions (fine, normal, and quick, trading off precision and responsiveness). Psychophysical analysis of the variability of maximal grasping aperture during prehension and of the reported size of the object revealed that in normal and quick (but not in the fine) gripper scaling conditions, teleoperated grasping with our system was similar to natural grasping, and therefore, human-centered transparent. We anticipate that using motor control and psychophysics for human-centered optimizing of teleoperation control will eventually improve the usability of RAMIS.
A systematic study of the class imbalance problem in convolutional neural networks
Venue: arXiv cs.CV 2018
Year: 2018

In this study, we systematically investigate the impact of class imbalance on classification performance of convolutional neural networks (CNNs) and compare frequently used methods to address the issue. Class imbalance is a common problem that has been comprehensively studied in classical machine learning, yet very limited systematic research is available in the context of deep learning. In our study, we use three benchmark datasets of increasing complexity, MNIST, CIFAR-10 and ImageNet, to investigate the effects of imbalance on classification and perform an extensive comparison of several methods to address the issue: oversampling, undersampling, two-phase training, and thresholding that compensates for prior class probabilities. Our main evaluation metric is area under the receiver operating characteristic curve (ROC AUC) adjusted to multi-class tasks since overall accuracy metric is associated with notable difficulties in the context of imbalanced data. Based on results from our experiments we conclude that (i) the effect of class imbalance on classification performance is detrimental; (ii) the method of addressing class imbalance that emerged as dominant in almost all analyzed scenarios was oversampling; (iii) oversampling should be applied to the level that completely eliminates the imbalance, whereas the optimal undersampling ratio depends on the extent of imbalance; (iv) as opposed to some classical machine learning models, oversampling does not cause overfitting of CNNs; (v) thresholding should be applied to compensate for prior class probabilities when overall number of properly classified cases is of interest.
Robust Structure-based Shape Correspondence
Venue: arXiv cs.GR 2018
Year: 2018

We present a robust method to find region-level correspondences between shapes, which are invariant to changes in geometry and applicable across multiple shape representations. We generate simplified shape graphs by jointly decomposing the shapes, and devise an adapted graph-matching technique, from which we infer correspondences between shape regions. The simplified shape graphs are designed to primarily capture the overall structure of the shapes, without reflecting precise information about the geometry of each region, which enables us to find correspondences between shapes that might have significant geometric differences. Moreover, due to the special care we take to ensure the robustness of each part of our pipeline, our method can find correspondences between shapes with different representations, such as triangular meshes and point clouds. We demonstrate that the region-wise matching that we obtain can be used to find correspondences between feature points, reveal the intrinsic self-similarities of each shape, and even construct point-to-point maps across shapes. Our method is both time and space efficient, leading to a pipeline that is significantly faster than comparable approaches. We demonstrate the performance of our approach through an extensive quantitative and qualitative evaluation on several benchmarks where we achieve comparable or superior performance to existing methods.
Fast Deployment of UAV Networks for Optimal Wireless Coverage
Venue: arXiv cs.NI 2018
Year: 2018

Unmanned Aerial Vehicle (UAV) networks have emerged as a promising technique to rapidly provide wireless coverage to a geographical area, where a flying UAV can be fast deployed to serve as cell site. Existing work on UAV-enabled wireless networks overlook the fast UAV deployment for wireless coverage, and such deployment problems have only been studied recently in sensor networks. Unlike sensors, UAVs should be deployed to the air and they are generally different in flying speed, operating altitude and wireless coverage radius. By considering such UAV heterogeneity to cover the whole target area, this paper studies two fast UAV deployment problems: one is to minimize the maximum deployment delay among all UAVs (min-max) for fairness consideration, and the other is to minimize the total deployment delay (min-sum) for efficiency consideration. We prove both min-max and min-sum problems are NP-complete in general. When dispatching UAVs from the same location, we present an optimal algorithm of low computational complexity $O(n^2)$ for the min-max problem. When UAVs are dispatched from different locations, we propose to preserve their location order during deployment and successfully design a fully polynomial time approximation scheme (FPTAS) of computation complexity $O(n^2 \log \frac{1}ε)$ to arbitrarily approach the global optimum with relative error $ε$. The min-sum problem is more challenging. When UAVs are dispatched from the same initial location, we present an approximation algorithm of linear time. As for the general case, we further reformulate it as a dynamic program and propose a pseudo polynomial-time algorithm to solve it optimally.
Compressed Sensing, ASBSR-method of image sampling and reconstruction and the problem of digital image acquisition with the lowest possible sampling rate
Venue: arXiv cs.CV 2018
Year: 2018

The problem of minimization of the number of measurements needed for digital image acquisition and reconstruction with a given accuracy is addressed. Basics of the sampling theory are outlined to show that the lower bound of signal sampling rate sufficient for signal reconstruction with a given accuracy is equal to the spectrum sparsity of the signal sparse approximation that has this accuracy. It is revealed that the compressed sensing approach, which was advanced as a solution to the sampling rate minimization problem, is far from reaching the sampling rate theoretical minimum. Potentials and limitations of compressed sensing are demystified using a simple and intutive model, A method of image Arbitrary Sampling and Bounded Spectrum Reconstruction (ASBSR-method) is described that allows to draw near the image sampling rate theoretical minimum. Presented and discussed are also results of experimental verification of the ASBSR-method and its possible applicability extensions to solving various underdetermined inverse problems such as color image demosaicing, image in-painting, image reconstruction from their sparsely sampled or decimated projections, image reconstruction from the modulus of its Fourier spectrum, and image reconstruction from its sparse samples in Fourier domain
State Complexity of Overlap Assembly
Venue: arXiv cs.FL 2018
Year: 2018

The \emph{state complexity} of a regular language $L_m$ is the number $m$ of states in a minimal deterministic finite automaton (DFA) accepting $L_m$. The state complexity of a regularity-preserving binary operation on regular languages is defined as the maximal state complexity of the result of the operation where the two operands range over all languages of state complexities $\le m$ and $\le n$, respectively. We find a tight upper bound on the state complexity of the binary operation \emph{overlap assembly} on regular languages. This operation was introduced by Csuhaj-Varjú, Petre, and Vaszil to model the process of self-assembly of two linear DNA strands into a longer DNA strand, provided that their ends "overlap". We prove that the state complexity of the overlap assembly of languages $L_m$ and $L_n$, where $m\ge 2$ and $n\ge1$, is at most $2 (m-1) 3^{n-1} + 2^n$. Moreover, for $m \ge 2$ and $n \ge 3$ there exist languages $L_m$ and $L_n$ over an alphabet of size $n$ whose overlap assembly meets the upper bound and this bound cannot be met with smaller alphabets. Finally, we prove that $m+n$ is a tight upper bound on the overlap assembly of unary languages, and that there are binary languages whose overlap assembly has exponential state complexity at least $m(2^{n-1}-2)+2$.
Convolutional Recurrent Neural Networks for Electrocardiogram Classification
Venue: arXiv cs.LG 2018
Year: 2018

We propose two deep neural network architectures for classification of arbitrary-length electrocardiogram (ECG) recordings and evaluate them on the atrial fibrillation (AF) classification data set provided by the PhysioNet/CinC Challenge 2017. The first architecture is a deep convolutional neural network (CNN) with averaging-based feature aggregation across time. The second architecture combines convolutional layers for feature extraction with long-short term memory (LSTM) layers for temporal aggregation of features. As a key ingredient of our training procedure we introduce a simple data augmentation scheme for ECG data and demonstrate its effectiveness in the AF classification task at hand. The second architecture was found to outperform the first one, obtaining an $F_1$ score of $82.1$% on the hidden challenge testing set.
A Bayesian Perspective on Generalization and Stochastic Gradient Descent
Venue: arXiv cs.LG 2018
Year: 2018

We consider two questions at the heart of machine learning; how can we predict if a minimum will generalize to the test set, and why does stochastic gradient descent find minima that generalize well? Our work responds to Zhang et al. (2016), who showed deep neural networks can easily memorize randomly labeled training data, despite generalizing well on real labels of the same inputs. We show that the same phenomenon occurs in small linear models. These observations are explained by the Bayesian evidence, which penalizes sharp minima but is invariant to model parameterization. We also demonstrate that, when one holds the learning rate fixed, there is an optimum batch size which maximizes the test set accuracy. We propose that the noise introduced by small mini-batches drives the parameters towards minima whose evidence is large. Interpreting stochastic gradient descent as a stochastic differential equation, we identify the "noise scale" $g = ε(\frac{N}{B} - 1) \approx εN/B$, where $ε$ is the learning rate, $N$ the training set size and $B$ the batch size. Consequently the optimum batch size is proportional to both the learning rate and the size of the training set, $B_{opt} \propto εN$. We verify these predictions empirically.
Superpixels Based Marker Tracking Vs. Hue Thresholding In Rodent Biomechanics Application
Venue: arXiv cs.CV 2018
Year: 2018

Examining locomotion has improved our basic understanding of motor control and aided in treating motor impairment. Mice and rats are premier models of human disease and increasingly the model systems of choice for basic neuroscience. High frame rates (250 Hz) are needed to quantify the kinematics of these running rodents. Manual tracking, especially for multiple markers, becomes time-consuming and impossible for large sample sizes. Therefore, the need for automatic segmentation of these markers has grown in recent years. We propose two methods to segment and track these markers: first, using SLIC superpixels segmentation with a tracker based on position, speed, shape, and color information of the segmented region in the previous frame; second, using a thresholding on hue channel following up with the same tracker. The comparison showed that the SLIC superpixels method was superior because the segmentation was more reliable and based on both color and spatial information.
Enhancing Inductive Entailment Proofs in Separation Logic with Lemma Synthesis
Venue: arXiv cs.PL 2018
Year: 2018

This paper presents an approach to lemma synthesis to support advanced inductive entailment procedures based on separation logic. We first propose a mechanism where lemmas are automatically proven and systematically applied. The lemmas may include universal guard and/or unknown predicate. While the former is critical for expressivity, the latter is essential for supporting relationships between multiple predicates. We further introduce lemma synthesis to support (i) automated inductive reasoning together with frame inference and (ii) theorem exploration. For (i) we automatically discover and prove auxiliary lemmas during an inductive proof; and for (ii) we automatically generate a useful set of lemmas to relate user-defined or system-generated predicates. We have implemented our proposed approach into an existing verification system and tested its capability in inductive reasoning and theorem exploration. The experimental results show that the enhanced system can automatically synthesize useful lemmas to facilitate reasoning on a broad range of non-trivial inductive proofs.