OpenRaiser/Intern-Atlas huggingface dataset:
An Information-theoretic Framework for the Lossy Compression of Link Streams
Venue: arXiv cs.DS 2018
Year: 2018

Graph compression is a data analysis technique that consists in the replacement of parts of a graph by more general structural patterns in order to reduce its description length. It notably provides interesting exploration tools for the study of real, large-scale, and complex graphs which cannot be grasped at first glance. This article proposes a framework for the compression of temporal graphs, that is for the compression of graphs that evolve with time. This framework first builds on a simple and limited scheme, exploiting structural equivalence for the lossless compression of static graphs, then generalises it to the lossy compression of link streams, a recent formalism for the study of temporal graphs. Such generalisation relies on the natural extension of (bidimensional) relational data by the addition of a third temporal dimension. Moreover, we introduce an information-theoretic measure to quantify and to control the information that is lost during compression, as well as an algebraic characterisation of the space of possible compression patterns to enhance the expressiveness of the initial compression scheme. These contributions lead to the definition of a combinatorial optimisation problem, that is the Lossy Multistream Compression Problem, for which we provide an exact algorithm.
Discrete linear-complexity reinforcement learning in continuous action spaces for Q-learning algorithms
Venue: arXiv cs.LG 2018
Year: 2018

In this article, we sketch an algorithm that extends the Q-learning algorithms to the continuous action space domain. Our method is based on the discretization of the action space. Despite the commonly used discretization methods, our method does not increase the discretized problem dimensionality exponentially. We will show that our proposed method is linear in complexity when the discretization is employed. The variant of the Q-learning algorithm presented in this work, labeled as Finite Step Q-Learning (FSQ), can be deployed to both shallow and deep neural network architectures.
Quantified boolean formula problem
Venue: arXiv cs.DS 2018
Year: 2018

This paper is devoted to the complexity of the quantified boolean formula problem. We describe a simple deterministic algorithm that, for a given quantified boolean formula $F$, stops in time bounded by $O(|F|^4)$ and answers yes if $F$ is true and no otherwise.
Circuits via topoi
Venue: arXiv cs.LO 2018
Year: 2018

Leveraging topos theory a semantics can be given to sequential circuits where time-sensitive gates, such as unit delay, are treated uniformly with combinational gates. Both kinds of gates are functions in a particular topos: the topos of presheaves over the natural ordering of $\mathbb{N}$. This is used to show that sequential circuits validate the equational theory of traced categories.
Towards Explainable and Controllable Open Domain Dialogue Generation with Dialogue Acts
Venue: arXiv cs.CL 2018
Year: 2018

We study open domain dialogue generation with dialogue acts designed to explain how people engage in social chat. To imitate human behavior, we propose managing the flow of human-machine interactions with the dialogue acts as policies. The policies and response generation are jointly learned from human-human conversations, and the former is further optimized with a reinforcement learning approach. With the dialogue acts, we achieve significant improvement over state-of-the-art methods on response quality for given contexts and dialogue length in both machine-machine simulation and human-machine conversation.
Bounded Information Rate Variational Autoencoders
Venue: arXiv cs.LG 2018
Year: 2018

This paper introduces a new member of the family of Variational Autoencoders (VAE) that constrains the rate of information transferred by the latent layer. The latent layer is interpreted as a communication channel, the information rate of which is bound by imposing a pre-set signal-to-noise ratio. The new constraint subsumes the mutual information between the input and latent variables, combining naturally with the likelihood objective of the observed data as used in a conventional VAE. The resulting Bounded-Information-Rate Variational Autoencoder (BIR-VAE) provides a meaningful latent representation with an information resolution that can be specified directly in bits by the system designer. The rate constraint can be used to prevent overtraining, and the method naturally facilitates quantisation of the latent variables at the set rate. Our experiments confirm that the BIR-VAE has a meaningful latent representation and that its performance is at least as good as state-of-the-art competing algorithms, but with lower computational complexity.
Can We Assess Mental Health through Social Media and Smart Devices? Addressing Bias in Methodology and Evaluation
Venue: arXiv cs.CY 2018
Year: 2018

Predicting mental health from smartphone and social media data on a longitudinal basis has recently attracted great interest, with very promising results being reported across many studies. Such approaches have the potential to revolutionise mental health assessment, if their development and evaluation follows a real world deployment setting. In this work we take a closer look at state-of-the-art approaches, using different mental health datasets and indicators, different feature sources and multiple simulations, in order to assess their ability to generalise. We demonstrate that under a pragmatic evaluation framework, none of the approaches deliver or even approach the reported performances. In fact, we show that current state-of-the-art approaches can barely outperform the most naïve baselines in the real-world setting, posing serious questions not only about their deployment ability, but also about the contribution of the derived features for the mental health assessment task and how to make better use of such data in the future.
Speeding up the Hyperparameter Optimization of Deep Convolutional Neural Networks
Venue: arXiv cs.NE 2018
Year: 2018

Most learning algorithms require the practitioner to manually set the values of many hyperparameters before the learning process can begin. However, with modern algorithms, the evaluation of a given hyperparameter setting can take a considerable amount of time and the search space is often very high-dimensional. We suggest using a lower-dimensional representation of the original data to quickly identify promising areas in the hyperparameter space. This information can then be used to initialize the optimization algorithm for the original, higher-dimensional data. We compare this approach with the standard procedure of optimizing the hyperparameters only on the original input. We perform experiments with various state-of-the-art hyperparameter optimization algorithms such as random search, the tree of parzen estimators (TPEs), sequential model-based algorithm configuration (SMAC), and a genetic algorithm (GA). Our experiments indicate that it is possible to speed up the optimization process by using lower-dimensional data representations at the beginning, while increasing the dimensionality of the input later in the optimization process. This is independent of the underlying optimization procedure, making the approach promising for many existing hyperparameter optimization algorithms.
Image Reconstruction via Variational Network for Real-Time Hand-Held Sound-Speed Imaging
Venue: arXiv cs.CV 2018
Year: 2018

Speed-of-sound is a biomechanical property for quantitative tissue differentiation, with great potential as a new ultrasound-based image modality. A conventional ultrasound array transducer can be used together with an acoustic mirror, or so-called reflector, to reconstruct sound-speed images from time-of-flight measurements to the reflector collected between transducer element pairs, which constitutes a challenging problem of limited-angle computed tomography. For this problem, we herein present a variational network based image reconstruction architecture that is based on optimization loop unrolling, and provide an efficient training protocol of this network architecture on fully synthetic inclusion data. Our results indicate that the learned model presents good generalization ability, being able to reconstruct images with significantly different statistics compared to the training set. Complex inclusion geometries were shown to be successfully reconstructed, also improving over the prior-art by 23% in reconstruction error and by 10% in contrast on synthetic data. In a phantom study, we demonstrated the detection of multiple inclusions that were not distinguishable by prior-art reconstruction, meanwhile improving the contrast by 27% for a stiff inclusion and by 219% for a soft inclusion. Our reconstruction algorithm takes approximately 10ms, enabling its use as a real-time imaging method on an ultrasound machine, for which we are demonstrating an example preliminary setup herein.
Real-Time Stereo Vision for Road Surface 3-D Reconstruction
Venue: arXiv cs.CV 2018
Year: 2018

Stereo vision techniques have been widely used in civil engineering to acquire 3-D road data. The two important factors of stereo vision are accuracy and speed. However, it is very challenging to achieve both of them simultaneously and therefore the main aim of developing a stereo vision system is to improve the trade-off between these two factors. In this paper, we present a real-time stereo vision system used for road surface 3-D reconstruction. The proposed system is developed from our previously published 3-D reconstruction algorithm where the perspective view of the target image is first transformed into the reference view, which not only increases the disparity accuracy but also improves the processing speed. Then, the correlation cost between each pair of blocks is computed and stored in two 3-D cost volumes. To adaptively aggregate the matching costs from neighbourhood systems, bilateral filtering is performed on the cost volumes. This greatly reduces the ambiguities during stereo matching and further improves the precision of the estimated disparities. Finally, the subpixel resolution is achieved by conducting a parabola interpolation and the subpixel disparity map is used to reconstruct the 3-D road surface. The proposed algorithm is implemented on an NVIDIA GTX 1080 GPU for the real-time purpose. The experimental results illustrate that the reconstruction accuracy is around 3 mm.
A Strategy of MR Brain Tissue Images' Suggestive Annotation Based on Modified U-Net
Venue: arXiv cs.CV 2018
Year: 2018

Accurate segmentation of MR brain tissue is a crucial step for diagnosis,surgical planning, and treatment of brain abnormalities. However,it is a time-consuming task to be performed by medical experts. So, automatic and reliable segmentation methods are required. How to choose appropriate training dataset from limited labeled dataset rather than the whole also has great significance in saving training time. In addition, medical data labeled is too rare and expensive to obtain extensively, so choosing appropriate unlabeled dataset instead of all the datasets to annotate, which can attain at least same performance, is also very meaningful. To solve the problem above, we design an automatic segmentation method based on U-shaped deep convolutional network and obtain excellent result with average DSC metric of 0.8610, 0.9131, 0.9003 for Cerebrospinal Fluid (CSF), Gray Matter (GM) and White Matter (WM) respectively on the well-known IBSR18 dataset. We use bootstrapping algorithm for selecting the most effective training data and get more state-of-the-art segmentation performance by using only 50% of training data. Moreover, we propose a strategy of MR brain tissue images' suggestive annotation for unlabeled medical data based on the modified U-net. The proposed method performs fast and can be used in clinical.
Bio-Measurements Estimation and Support in Knee Recovery through Machine Learning
Venue: arXiv cs.CV 2018
Year: 2018

Knee injuries are frequent, varied and often require the patient to undergo intensive rehabilitation for several months. Treatment protocols usually contemplate some recurrent measurements in order to assess progress, such as goniometry. The need for specific equipment or the complexity and duration of these tasks cause them to often be neglected. A novel deep learning based solution is presented, supported by the generation of a synthetic image dataset. A 3D human-body model was used for this purpose, simulating a recovering patient. For each image, the coordinates of three key points were registered: the centers of the thigh, the knee and the lower leg. These values are sufficient to estimate the flexion angle. Convolutional neural networks were then trained for predicting these six coordinates. Transfer learning was used with the VGG16 and InceptionV3 models pre-trained on the ImageNet dataset, being an additional custom model trained from scratch. All models were tested with different combinations of data augmentation techniques applied on the training sets. InceptionV3 achieved the best overall results, producing considerably good predictions even on real unedited pictures.
Optimal Las Vegas Approximate Near Neighbors in $\ell_p$
Venue: arXiv cs.DS 2018
Year: 2018

We show that approximate near neighbor search in high dimensions can be solved in a Las Vegas fashion (i.e., without false negatives) for $\ell_p$ ($1\le p\le 2$) while matching the performance of optimal locality-sensitive hashing. Specifically, we construct a data-independent Las Vegas data structure with query time $O(dn^ρ)$ and space usage $O(dn^{1+ρ})$ for $(r, c r)$-approximate near neighbors in $\mathbb{R}^{d}$ under the $\ell_p$ norm, where $ρ= 1/c^p + o(1)$. Furthermore, we give a Las Vegas locality-sensitive filter construction for the unit sphere that can be used with the data-dependent data structure of Andoni et al. (SODA 2017) to achieve optimal space-time tradeoffs in the data-dependent setting. For the symmetric case, this gives us a data-dependent Las Vegas data structure with query time $O(dn^ρ)$ and space usage $O(dn^{1+ρ})$ for $(r, c r)$-approximate near neighbors in $\mathbb{R}^{d}$ under the $\ell_p$ norm, where $ρ= 1/(2c^p - 1) + o(1)$. Our data-independent construction improves on the recent Las Vegas data structure of Ahle (FOCS 2017) for $\ell_p$ when $1 < p\le 2$. Our data-dependent construction does even better for $\ell_p$ for all $p\in [1, 2]$ and is the first Las Vegas approximate near neighbors data structure to make use of data-dependent approaches. We also answer open questions of Indyk (SODA 2000), Pagh (SODA 2016), and Ahle by showing that for approximate near neighbors, Las Vegas data structures can match state-of-the-art Monte Carlo data structures in performance for both the data-independent and data-dependent settings and across space-time tradeoffs.
Rearranging the Familiar: Testing Compositional Generalization in Recurrent Networks
Venue: arXiv cs.CL 2018
Year: 2018

Systematic compositionality is the ability to recombine meaningful units with regular and predictable outcomes, and it's seen as key to humans' capacity for generalization in language. Recent work has studied systematic compositionality in modern seq2seq models using generalization to novel navigation instructions in a grounded environment as a probing tool, requiring models to quickly bootstrap the meaning of new words. We extend this framework here to settings where the model needs only to recombine well-trained functional words (such as "around" and "right") in novel contexts. Our findings confirm and strengthen the earlier ones: seq2seq models can be impressively good at generalizing to novel combinations of previously-seen input, but only when they receive extensive training on the specific pattern to be generalized (e.g., generalizing from many examples of "X around right" to "jump around right"), while failing when generalization requires novel application of compositional rules (e.g., inferring the meaning of "around right" from those of "right" and "around").
Capsule Networks against Medical Imaging Data Challenges
Venue: arXiv cs.CV 2018
Year: 2018

A key component to the success of deep learning is the availability of massive amounts of training data. Building and annotating large datasets for solving medical image classification problems is today a bottleneck for many applications. Recently, capsule networks were proposed to deal with shortcomings of Convolutional Neural Networks (ConvNets). In this work, we compare the behavior of capsule networks against ConvNets under typical datasets constraints of medical image analysis, namely, small amounts of annotated data and class-imbalance. We evaluate our experiments on MNIST, Fashion-MNIST and medical (histological and retina images) publicly available datasets. Our results suggest that capsule networks can be trained with less amount of data for the same or better performance and are more robust to an imbalanced class distribution, which makes our approach very promising for the medical imaging community.
Universalizing science: alternative indices to direct research
Venue: arXiv cs.DL 2018
Year: 2018

Measurement is a complicated but very necessary task. Many indices have been created in an effort to define the quality of knowledge produced but they have attracted strong criticism, having become synonymous with individualism, competition and mere productivity and, furthermore, they fail to head science towards addressing local demands or towards producing international knowledge by means of collaboration. Institutions, countries, publishers, governments and authors have a latent need to create quality and productivity indices because they can serve as filters that influence far-reaching decision making and even decisions on the professional promotion of university teachers. Even so, in the present-day context, the very creators of those indices admit that they were not designed for that purpose, given that different research areas, the age of the researcher, the country and the language spoken all have an influence on the index calculations. Accordingly, this research sets out three indices designed to head science towards its universal objective by valuing collaboration and the dissemination of knowledge. It is hoped that the proposed indices may provoke new discussions and the proposal of new, more assertive indicators for the analysis of scientific research quality.
Adaptive Variational Particle Filtering in Non-stationary Environments
Venue: arXiv cs.LG 2018
Year: 2018

Online convex optimization is a sequential prediction framework with the goal to track and adapt to the environment through evaluating proper convex loss functions. We study efficient particle filtering methods from the perspective of such a framework. We formulate an efficient particle filtering methods for the non-stationary environment by making connections with the online mirror descent algorithm which is known to be a universal online convex optimization algorithm. As a result of this connection, our proposed particle filtering algorithm proves to achieve optimal particle efficiency.
Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
Venue: arXiv cs.DS 2018
Year: 2018

We consider two optimization problems in planar graphs. In Maximum Weight Independent Set of Objects we are given a graph $G$ and a family $\mathcal{D}$ of objects, each being a connected subgraph of $G$ with a prescribed weight, and the task is to find a maximum-weight subfamily of $\mathcal{D}$ consisting of pairwise disjoint objects. In Minimum Weight Distance Set Cover we are given an edge-weighted graph $G$, two sets $\mathcal{D},\mathcal{C}$ of vertices of $G$, where vertices of $\mathcal{D}$ have prescribed weights, and a nonnegative radius $r$. The task is to find a minimum-weight subset of $\mathcal{D}$ such that every vertex of $\mathcal{C}$ is at distance at most $r$ from some selected vertex. Via simple reductions, these two problems generalize a number of geometric optimization tasks, notably Maximum Weight Independent Set for polygons in the plane and Weighted Geometric Set Cover for unit disks and unit squares. We present quasi-polynomial time approximation schemes (QPTASs) for both of the above problems in planar graphs: given an accuracy parameter $ε>0$ we can compute a solution whose weight is within multiplicative factor of $(1+ε)$ from the optimum in time $2^{\mathrm{poly}(1/ε,\log |\mathcal{D}|)}\cdot n^{\mathcal{O}(1)}$, where $n$ is the number of vertices of the input graph. Our main technical contribution is to transfer the techniques used for recursive approximation schemes for geometric problems due to Adamaszek, Har-Peled, and Wiese to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods.
Physical-type correctness in scientific Python
Venue: arXiv cs.MS 2018
Year: 2018

The representation of units and dimensions in informatics systems is barely codified and often ignored. For instance, the major languages used in scientific computing (Fortran, C and Python), have no type for dimension or unit, and so physical quantities are represented in a program by variables of type real, resulting in the possibility of unit or dimensional errors. In view of this danger, many authors have proposed language schemes for unit-checking and conversion. However, since many physical quantities have the same units, it is possible for a block of code to be unit-compatible, but still physically meaningless. We demonstrate the limitations of three Python unit-libraries and present a justification and method for checking kind-of-quantity.
Loud and Interactive Paper Prototyping in Requirements Elicitation: What is it Good for?
Venue: arXiv cs.SE 2018
Year: 2018

Requirements Engineering is a multidisciplinary and a human-centered process, therefore, the artifacts produced from RE are always error-prone. The most significant of these errors are missing or misunderstanding requirements. Information loss in RE could result in omitted logic in the software, which will be onerous to correct at the later stages of development. In this paper, we demonstrate and investigate how interactive and Loud Paper Prototyping (LPP) can be integrated to collect stakeholders' needs and expectations than interactive prototyping or face-to-face meetings alone. To this end, we conducted a case study of (1) 31 mobile application (App) development teams who applied either of interactive or loud prototyping and (2) 19 mobile App development teams who applied only the face-to-face meetings. From this study, we found that while using Silent Paper Prototyping (SPP) rather than No Paper Prototyping (NPP) is a more efficient technique to capture Non-Functional Requirements (NFRs), User Interface (UI) requirements, and existing requirements, LPP is more applicable to manage NFRs, UI requirements, as well as adding new requirements and removing/modifying the existing requirements. We also found that among LPP and SPP, LPP is more efficient to capture and influence Functional Requirements (FRs).