OpenRaiser/Intern-Atlas huggingface dataset:
Approximate Voronoi cells for lattices, revisited
Venue: arXiv cs.DS 2019
Year: 2019

We revisit the approximate Voronoi cells approach for solving the closest vector problem with preprocessing (CVPP) on high-dimensional lattices, and settle the open problem of Doulgerakis-Laarhoven-De Weger [PQCrypto, 2019] of determining exact asymptotics on the volume of these Voronoi cells under the Gaussian heuristic. As a result, we obtain improved upper bounds on the time complexity of the randomized iterative slicer when using less than $2^{0.076d + o(d)}$ memory, and we show how to obtain time-memory trade-offs even when using less than $2^{0.048d + o(d)}$ memory. We also settle the open problem of obtaining a continuous trade-off between the size of the advice and the query time complexity, as the time complexity with subexponential advice in our approach scales as $d^{d/2 + o(d)}$, matching worst-case enumeration bounds, and achieving the same asymptotic scaling as average-case enumeration algorithms for the closest vector problem.
Video Action Recognition Via Neural Architecture Searching
Venue: arXiv cs.CV 2019
Year: 2019

Deep neural networks have achieved great success for video analysis and understanding. However, designing a high-performance neural architecture requires substantial efforts and expertise. In this paper, we make the first attempt to let algorithm automatically design neural networks for video action recognition tasks. Specifically, a spatio-temporal network is developed in a differentiable space modeled by a directed acyclic graph, thus a gradient-based strategy can be performed to search an optimal architecture. Nonetheless, it is computationally expensive, since the computational burden to evaluate each architecture candidate is still heavy. To alleviate this issue, we, for the video input, introduce a temporal segment approach to reduce the computational cost without losing global video information. For the architecture, we explore in an efficient search space by introducing pseudo 3D operators. Experiments show that, our architecture outperforms popular neural architectures, under the training from scratch protocol, on the challenging UCF101 dataset, surprisingly, with only around one percentage of parameters of its manual-design counterparts.
Incrementally Learning Functions of the Return
Venue: arXiv cs.LG 2019
Year: 2019

Temporal difference methods enable efficient estimation of value functions in reinforcement learning in an incremental fashion, and are of broader interest because they correspond learning as observed in biological systems. Standard value functions correspond to the expected value of a sum of discounted returns. While this formulation is often sufficient for many purposes, it would often be useful to be able to represent functions of the return as well. Unfortunately, most such functions cannot be estimated directly using TD methods. We propose a means of estimating functions of the return using its moments, which can be learned online using a modified TD algorithm. The moments of the return are then used as part of a Taylor expansion to approximate analytic functions of the return.
Optimal Explanations of Linear Models
Venue: arXiv cs.LG 2019
Year: 2019

When predictive models are used to support complex and important decisions, the ability to explain a model's reasoning can increase trust, expose hidden biases, and reduce vulnerability to adversarial attacks. However, attempts at interpreting models are often ad hoc and application-specific, and the concept of interpretability itself is not well-defined. We propose a general optimization framework to create explanations for linear models. Our methodology decomposes a linear model into a sequence of models of increasing complexity using coordinate updates on the coefficients. Computing this decomposition optimally is a difficult optimization problem for which we propose exact algorithms and scalable heuristics. By solving this problem, we can derive a parametrized family of interpretability metrics for linear models that generalizes typical proxies, and study the tradeoff between interpretability and predictive accuracy.
A Projectional Ansatz to Reconstruction
Venue: arXiv cs.LG 2019
Year: 2019

Recently the field of inverse problems has seen a growing usage of mathematically only partially understood learned and non-learned priors. Based on first principles, we develop a projectional approach to inverse problems that addresses the incorporation of these priors, while still guaranteeing data consistency. We implement this projectional method (PM) on the one hand via very general Plug-and-Play priors and on the other hand, via an end-to-end training approach. To this end, we introduce a novel alternating neural architecture, allowing for the incorporation of highly customized priors from data in a principled manner. We also show how the recent success of Regularization by Denoising (RED) can, at least to some extent, be explained as an approximation of the PM. Furthermore, we demonstrate how the idea can be applied to stop the degradation of Deep Image Prior (DIP) reconstructions over time.
Learning a Behavior Model of Hybrid Systems Through Combining Model-Based Testing and Machine Learning (Full Version)
Venue: arXiv cs.LG 2019
Year: 2019

Models play an essential role in the design process of cyber-physical systems. They form the basis for simulation and analysis and help in identifying design problems as early as possible. However, the construction of models that comprise physical and digital behavior is challenging. Therefore, there is considerable interest in learning such hybrid behavior by means of machine learning which requires sufficient and representative training data covering the behavior of the physical system adequately. In this work, we exploit a combination of automata learning and model-based testing to generate sufficient training data fully automatically. Experimental results on a platooning scenario show that recurrent neural networks learned with this data achieved significantly better results compared to models learned from randomly generated data. In particular, the classification error for crash detection is reduced by a factor of five and a similar F1-score is obtained with up to three orders of magnitude fewer training samples.
Integrating Visualization Literacy into Computer Graphics Education Using the Example of Dear Data
Venue: arXiv cs.HC 2019
Year: 2019

The amount of visual communication we are facing is rapidly increasing, and skills to process, understand, and generate visual representations are in high demand. Especially students focusing on computer graphics and visualization can benefit from a more diverse education on visual literacy, as they often have to work on graphical representations for broad masses after their graduation. Our proposed teaching approach incorporates basic design thinking principles into traditional visualization and graphics education. Our course was inspired by the book Dear Data that was the subject of a lively discussion at the closing capstone of IEEE VIS 2017. The paper outlines our 12-week teaching experiment and summarizes the results extracted from accompanying questionnaires and interviews. In particular, we provide insights into the creation process and pain points of visualization novices, discuss the observed interplay between visualization tasks and design thinking, and finally draw design implications for visual literacy education in general.
Constant-Time Dynamic $(Δ+1)$-Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing
Venue: arXiv cs.DS 2019
Year: 2019

With few exceptions (namely, algorithms for maximal matching, $2$-approximate vertex cover, and certain constant-stretch spanners), all known fully dynamic algorithms in general graphs require (amortized) $Ω(\log n)$ update/query time. Showing for the first time that techniques from property testing can lead to constant-time fully dynamic graph algorithms we prove the following results: (1) We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper $(Δ+1)$-vertex coloring of a graph with maximum degree at most $Δ$. This improves upon the previous $O(\log Δ)$-time algorithm by Bhattacharya et al. (SODA 2018). We show that our result does not only have optimal running time, but is also optimal in the sense that already deciding whether a $Δ$-coloring exists in a dynamically changing graph with maximum degree at most $Δ$ takes $Ω(\log n)$ time per operation. (2) We give two fully dynamic algorithms that maintain a $(1+\varepsilon)$-approximation of the weight $M$ of the minimum spanning forest of a graph $G$ with edges weights in $[1,W]$. Our deterministic algorithm takes $O({W^2 \log W}/{\varepsilon^3})$ worst-case time, which is constant if both $W$ and $\varepsilon$ are constant. This is somewhat surprising as a lower bound by Patrascu and Demaine (SIAM J. Comput. 2006) shows that it takes $Ω(\log n)$ time per operation to maintain the exact weight of the MSF that holds even for $W=1$. Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case $O(\frac{1}{\varepsilon^4}\log^2(\frac{1}{\varepsilon}))$ time if $W= O({(m^*)^{1/3}}/{\log^3 n})$, where $m^*$ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary.
Dense Peelable Random Uniform Hypergraphs
Venue: arXiv cs.DS 2019
Year: 2019

We describe a new family of $k$-uniform hypergraphs with independent random edges. The hypergraphs have a high probability of being peelable, i.e. to admit no sub-hypergraph of minimum degree $2$, even when the edge density (number of edges over vertices) is close to $1$. In our construction, the vertex set is partitioned into linearly arranged segments and each edge is incident to random vertices of $k$ consecutive segments. Quite surprisingly, the linear geometry allows our graphs to be peeled "from the outside in". The density thresholds $f_k$ for peelability of our hypergraphs ($f_3 \approx 0.918$, $f_4 \approx 0.977$, $f_5 \approx 0.992$, ...) are well beyond the corresponding thresholds ($c_3 \approx 0.818$, $c_4 \approx 0.772$, $c_5 \approx 0.702$, ...) of standard $k$-uniform random hypergraphs. To get a grip on $f_k$, we analyse an idealised peeling process on the random weak limit of our hypergraph family. The process can be described in terms of an operator on functions and $f_k$ can be linked to thresholds relating to the operator. These thresholds are then tractable with numerical methods. Random hypergraphs underlie the construction of various data structures based on hashing. These data structures frequently rely on peelability of the hypergraph or peelability allows for simple linear time algorithms. To demonstrate the usefulness of our construction, we used our $3$-uniform hypergraphs as a drop-in replacement for the standard $3$-uniform hypergraphs in a retrieval data structure by Botelho et al. This reduces memory usage from $1.23m$ bits to $1.12m$ bits ($m$ being the input size) with almost no change in running time.
Toward a Procedural Fruit Tree Rendering Framework for Image Analysis
Venue: arXiv cs.CV 2019
Year: 2019

We propose a procedural fruit tree rendering framework, based on Blender and Python scripts allowing to generate quickly labeled dataset (i.e. including ground truth semantic segmentation). It is designed to train image analysis deep learning methods (e.g. in a robotic fruit harvesting context), where real labeled training datasets are usually scarce and existing synthetic ones are too specialized. Moreover, the framework includes the possibility to introduce parametrized variations in the model (e.g. lightning conditions, background), producing a dataset with embedded Domain Randomization aspect.
Barnes-Hut Approximation for Point SetGeodesic Shooting
Venue: arXiv cs.CV 2019
Year: 2019

Geodesic shooting has been successfully applied to diffeo-morphic registration of point sets. Exact computation of the geodesicshooting between point sets, however, requiresO(N2) calculations each time step on the number of points in the point set. We proposean approximation approach based on the Barnes-Hut algorithm to speedup point set geodesic shooting. This approximation can reduce the al-gorithm complexity toO(N b+N logN). The evaluation of the proposedmethod in both simulated images and the medial temporal lobe thick-ness analysis demonstrates a comparable accuracy to the exact point set geodesic shooting while offering up to 3-fold speed up. This improvementopens up a range of clinical research studies and practical problems towhich the method can be effectively applied.
LakhNES: Improving multi-instrumental music generation with cross-domain pre-training
Venue: arXiv cs.SD 2019
Year: 2019

We are interested in the task of generating multi-instrumental music scores. The Transformer architecture has recently shown great promise for the task of piano score generation; here we adapt it to the multi-instrumental setting. Transformers are complex, high-dimensional language models which are capable of capturing long-term structure in sequence data, but require large amounts of data to fit. Their success on piano score generation is partially explained by the large volumes of symbolic data readily available for that domain. We leverage the recently-introduced NES-MDB dataset of four-instrument scores from an early video game sound synthesis chip (the NES), which we find to be well-suited to training with the Transformer architecture. To further improve the performance of our model, we propose a pre-training technique to leverage the information in a large collection of heterogeneous music, namely the Lakh MIDI dataset. Despite differences between the two corpora, we find that this transfer learning procedure improves both quantitative and qualitative performance for our primary task.
Productization Challenges of Contextual Multi-Armed Bandits
Venue: arXiv cs.IR 2019
Year: 2019

Contextual Multi-Armed Bandits is a well-known and accepted online optimization algorithm, that is used in many Web experiences to tailor content or presentation to users' traffic. Much has been published on theoretical guarantees (e.g. regret bounds) of proposed algorithmic variants, but relatively little attention has been devoted to the challenges encountered while productizing contextual bandits schemes in large scale settings. This work enumerates several productization challenges we encountered while leveraging contextual bandits for two concrete use cases at scale. We discuss how to (1) determine the context (engineer the features) that model the bandit arms; (2) sanity check the health of the optimization process; (3) evaluate the process in an offline manner; (4) add potential actions (arms) on the fly to a running process; (5) subject the decision process to constraints; and (6) iteratively improve the online learning algorithm. For each such challenge, we explain the issue, provide our approach, and relate to prior art where applicable.
Object Detection in Video with Spatial-temporal Context Aggregation
Venue: arXiv cs.CV 2019
Year: 2019

Recent cutting-edge feature aggregation paradigms for video object detection rely on inferring feature correspondence. The feature correspondence estimation problem is fundamentally difficult due to poor image quality, motion blur, etc, and the results of feature correspondence estimation are unstable. To avoid the problem, we propose a simple but effective feature aggregation framework which operates on the object proposal-level. It learns to enhance each proposal's feature via modeling semantic and spatio-temporal relationships among object proposals from both within a frame and across adjacent frames. Experiments are carried out on the ImageNet VID dataset. Without any bells and whistles, our method obtains 80.3\% mAP on the ImageNet VID dataset, which is superior over the previous state-of-the-arts. The proposed feature aggregation mechanism improves the single frame Faster RCNN baseline by 5.8% mAP. Besides, under the setting of no temporal post-processing, our method outperforms the previous state-of-the-art by 1.4% mAP.
Profiling based Out-of-core Hybrid Method for Large Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

GPUs are widely used to accelerate deep learning with NNs (NNs). On the other hand, since GPU memory capacity is limited, it is difficult to implement efficient programs that compute large NNs on GPU. To compute NNs exceeding GPU memory capacity, data-swapping method and recomputing method have been proposed in existing work. However, in these methods, performance overhead occurs due to data movement or increase of computation. In order to reduce the overhead, it is important to consider characteristics of each layer such as sizes and cost for recomputation. Based on this direction, we proposed Profiling based out-of-core Hybrid method (PoocH). PoocH determines target layers of swapping or recomputing based on runtime profiling. We implemented PoocH by extending a deep learning framework, Chainer, and we evaluated its performance. With PoocH, we successfully computed an NN requiring 50 GB memory on a single GPU with 16 GB memory. Compared with in-core cases, performance degradation was 38 \% on x86 machine and 28 \% on POWER9 machine.
Evidential positive opinion influence measures for viral marketing
Venue: arXiv cs.SI 2019
Year: 2019

The Viral Marketing is a relatively new form of marketing that exploits social networks to promote a brand, a product, etc. The idea behind it is to find a set of influencers on the network that can trigger a large cascade of propagation and adoptions. In this paper, we will introduce an evidential opinion-based influence maximization model for viral marketing. Besides, our approach tackles three opinions based scenarios for viral marketing in the real world. The first scenario concerns influencers who have a positive opinion about the product. The second scenario deals with influencers who have a positive opinion about the product and produce effects on users who also have a positive opinion. The third scenario involves influence users who have a positive opinion about the product and produce effects on the negative opinion of other users concerning the product in question. Next, we proposed six influence measures, two for each scenario. We also use an influence maximization model that the set of detected influencers for each scenario. Finally, we show the performance of the proposed model with each influence measure through some experiments conducted on a generated dataset and a real world dataset collected from Twitter.
The Keys to Decidable HyperLTL Satisfiability: Small Models or Very Simple Formulas
Venue: arXiv cs.LO 2019
Year: 2019

HyperLTL, the extension of Linear Temporal Logic by trace quantifiers, is a uniform framework for expressing information flow policies by relating multiple traces of a security-critical system. HyperLTL has been successfully applied to express fundamental security policies like noninterference and observational determinism, but has also found applications beyond security, e.g., distributed protocols and coding theory. However, HyperLTL satisfiability is undecidable as soon as there are existential quantifiers in the scope of a universal one. To overcome this severe limitation to applicability, we investigate here restricted variants of the satisfiability problem to pinpoint the decidability border. First, we restrict the space of admissible models and show decidability when restricting the search space to models of bounded size or to finitely representable ones. Second, we consider formulas with restricted nesting of temporal operators and show that nesting depth one yields decidability for a slightly larger class of quantifier prefixes. We provide tight complexity bounds in almost all cases.
Spatiotemporal Local Propagation
Venue: arXiv cs.LG 2019
Year: 2019

This paper proposes an in-depth re-thinking of neural computation that parallels apparently unrelated laws of physics, that are formulated in the variational framework of the least action principle. The theory holds for neural networks that are also based on any digraph, and the resulting computational scheme exhibits the intriguing property of being truly biologically plausible. The scheme, which is referred to as SpatioTemporal Local Propagation (STLP), is local in both space and time. Space locality comes from the expression of the network connections by an appropriate Lagrangian term, so as the corresponding computational scheme does not need the backpropagation (BP) of the error, while temporal locality is the outcome of the variational formulation of the problem. Overall, in addition to conquering the often invoked biological plausibility missed by BP, the locality in both space and time that arises from the proposed theory can neither be exhibited by Backpropagation Through Time (BPTT) nor by Real-Time Recurrent Learning (RTRL).
Image-Based Size Analysis of Agglomerated and Partially Sintered Particles via Convolutional Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

There is a high demand for fully automated methods for the analysis of primary particle size distributions of agglomerated, sintered or occluded primary particles, due to their impact on material properties. Therefore, a novel, deep learning-based, method for the detection of such primary particles was proposed and tested, which renders a manual tuning of analysis parameters unnecessary. As a specialty, the training of the utilized convolutional neural networks was carried out using only synthetic images, thereby avoiding the laborious task of manual annotation and increasing the ground truth quality. Nevertheless, the proposed method performs excellent on real world samples of sintered silica nanoparticles with various sintering degrees and varying image conditions. In a direct comparison, the proposed method clearly outperforms two state-of-the-art methods for automated image-based particle size analysis (Hough transformation and the ImageJ ParticleSizer plug-in), thereby attaining human-like performance.
Forecasting remaining useful life: Interpretable deep learning approach via variational Bayesian inferences
Venue: arXiv cs.LG 2019
Year: 2019

Predicting the remaining useful life of machinery, infrastructure, or other equipment can facilitate preemptive maintenance decisions, whereby a failure is prevented through timely repair or replacement. This allows for a better decision support by considering the anticipated time-to-failure and thus promises to reduce costs. Here a common baseline may be derived by fitting a probability density function to past lifetimes and then utilizing the (conditional) expected remaining useful life as a prognostic. This approach finds widespread use in practice because of its high explanatory power. A more accurate alternative is promised by machine learning, where forecasts incorporate deterioration processes and environmental variables through sensor data. However, machine learning largely functions as a black-box method and its forecasts thus forfeit most of the desired interpretability. As our primary contribution, we propose a structured-effect neural network for predicting the remaining useful life which combines the favorable properties of both approaches: its key innovation is that it offers both a high accountability and the flexibility of deep learning. The parameters are estimated via variational Bayesian inferences. The different approaches are compared based on the actual time-to-failure for aircraft engines. This demonstrates the performance and superior interpretability of our method, while we finally discuss implications for decision support.