OpenRaiser/Intern-Atlas huggingface dataset:
A Trust Architecture for Blockchain in IoT
Venue: arXiv cs.CR 2019
Year: 2019

Blockchain is a promising technology for establishing trust in IoT networks, where network nodes do not necessarily trust each other. Cryptographic hash links and distributed consensus mechanisms ensure that the data stored on an immutable blockchain can not be altered or deleted. However, blockchain mechanisms do not guarantee the trustworthiness of data at the origin. We propose a layered architecture for improving the end-to-end trust that can be applied to a diverse range of blockchain-based IoT applications. Our architecture evaluates the trustworthiness of sensor observations at the data layer and adapts block verification at the blockchain layer through the proposed data trust and gateway reputation modules. We present the performance evaluation of the data trust module using a simulated indoor target localization and the gateway reputation module using an end-to-end blockchain implementation, together with a qualitative security analysis for the architecture.
Automatic Colon Polyp Detection using Region based Deep CNN and Post Learning Approaches
Venue: arXiv cs.CV 2019
Year: 2019

Automatic detection of colonic polyps is still an unsolved problem due to the large variation of polyps in terms of shape, texture, size, and color, and the existence of various polyp-like mimics during colonoscopy. In this study, we apply a recent region based convolutional neural network (CNN) approach for the automatic detection of polyps in images and videos obtained from colonoscopy examinations. We use a deep-CNN model (Inception Resnet) as a transfer learning scheme in the detection system. To overcome the polyp detection obstacles and the small number of polyp images, we examine image augmentation strategies for training deep networks. We further propose two efficient post-learning methods such as, automatic false positive learning and off-line learning, both of which can be incorporated with the region based detection system for reliable polyp detection. Using the large size of colonoscopy databases, experimental results demonstrate that the suggested detection systems show better performance compared to other systems in the literature. Furthermore, we show improved detection performance using the proposed post-learning schemes for colonoscopy videos.
Automatically Extract the Semi-transparent Motion-blurred Hand from a Single Image
Venue: arXiv cs.CV 2019
Year: 2019

When we use video chat, video game, or other video applications, motion-blurred hands often appear. Accurately extracting these hands is very useful for video editing and behavior analysis. However, existing motion-blurred object extraction methods either need user interactions, such as user supplied trimaps and scribbles, or need additional information, such as background images. In this paper, a novel method which can automatically extract the semi-transparent motion-blurred hand just according to the original RGB image is proposed. The proposed method separates the extraction task into two subtasks: alpha matte prediction and foreground prediction. These two subtasks are implemented by Xception based encoder-decoder networks. The extracted motion-blurred hand images can be calculated by multiplying the predicted alpha mattes and foreground images. Experiments on synthetic and real datasets show that the proposed method has promising performance.
Reducing Spreading Processes on Networks to Markov Population Models
Venue: arXiv cs.SI 2019
Year: 2019

Stochastic processes on complex networks, where each node is in one of several compartments, and neighboring nodes interact with each other, can be used to describe a variety of real-world spreading phenomena. However, computational analysis of such processes is hindered by the enormous size of their underlying state space. In this work, we demonstrate that lumping can be used to reduce any epidemic model to a Markov Population Model (MPM). Therefore, we propose a novel lumping scheme based on a partitioning of the nodes. By imposing different types of counting abstractions, we obtain coarse-grained Markov models with a natural MPM representation that approximate the original systems. This makes it possible to transfer the rich pool of approximation techniques developed for MPMs to the computational analysis of complex networks' dynamics. We present numerical examples to investigate the relationship between the accuracy of the MPMs, the size of the lumped state space, and the type of counting abstraction.
Hyp-RL : Hyperparameter Optimization by Reinforcement Learning
Venue: arXiv cs.LG 2019
Year: 2019

Hyperparameter tuning is an omnipresent problem in machine learning as it is an integral aspect of obtaining the state-of-the-art performance for any model. Most often, hyperparameters are optimized just by training a model on a grid of possible hyperparameter values and taking the one that performs best on a validation sample (grid search). More recently, methods have been introduced that build a so-called surrogate model that predicts the validation loss for a specific hyperparameter setting, model and dataset and then sequentially select the next hyperparameter to test, based on a heuristic function of the expected value and the uncertainty of the surrogate model called acquisition function (sequential model-based Bayesian optimization, SMBO). In this paper we model the hyperparameter optimization problem as a sequential decision problem, which hyperparameter to test next, and address it with reinforcement learning. This way our model does not have to rely on a heuristic acquisition function like SMBO, but can learn which hyperparameters to test next based on the subsequent reduction in validation loss they will eventually lead to, either because they yield good models themselves or because they allow the hyperparameter selection policy to build a better surrogate model that is able to choose better hyperparameters later on. Experiments on a large battery of 50 data sets demonstrate that our method outperforms the state-of-the-art approaches for hyperparameter learning.
Multi-Robot Patrolling with Sensing Idleness and Data Delay Objectives
Venue: arXiv cs.RO 2019
Year: 2019

Multi-robot patrolling represents a fundamental problem for many monitoring and surveillance applications and has gained significant interest in recent years. In patrolling, mobile robots repeatedly travel through an environment, capture sensor data at certain sensing locations and deliver this data to the base station in a way that maximizes the changes of detection. Robots move on tours, exchange data when they meet with robots on neighboring tours and so eventually deliver data to the base station. In this paper we jointly consider two important optimization criteria of multi-robot patrolling: (i) idleness, i.e. the time between consecutive visits of sensing locations, and (ii) delay, i.e. the time between capturing data at the sensing location and its arrival at the base station. We systematically investigate the effect of the robots' moving directions along their tours and the selection of meeting points for data exchange. We prove that the problem of determining the movement directions and meeting points such that the data delay is minimized is NP-hard. We propose heuristics and provide a simulation study which shows that the cooperative approach can outperform an uncooperative approach where every robot delivers the captured data individually to the base station.
Flexible SVBRDF Capture with a Multi-Image Deep Network
Venue: arXiv cs.GR 2019
Year: 2019

Empowered by deep learning, recent methods for material capture can estimate a spatially-varying reflectance from a single photograph. Such lightweight capture is in stark contrast with the tens or hundreds of pictures required by traditional optimization-based approaches. However, a single image is often simply not enough to observe the rich appearance of real-world materials. We present a deep-learning method capable of estimating material appearance from a variable number of uncalibrated and unordered pictures captured with a handheld camera and flash. Thanks to an order-independent fusing layer, this architecture extracts the most useful information from each picture, while benefiting from strong priors learned from data. The method can handle both view and light direction variation without calibration. We show how our method improves its prediction with the number of input pictures, and reaches high quality reconstructions with as little as 1 to 10 images -- a sweet spot between existing single-image and complex multi-image approaches.
Approximate Causal Abstraction
Venue: arXiv cs.AI 2019
Year: 2019

Scientific models describe natural phenomena at different levels of abstraction. Abstract descriptions can provide the basis for interventions on the system and explanation of observed phenomena at a level of granularity that is coarser than the most fundamental account of the system. Beckers and Halpern (2019), building on work of Rubenstein et al. (2017), developed an account of abstraction for causal models that is exact. Here we extend this account to the more realistic case where an abstract causal model offers only an approximation of the underlying system. We show how the resulting account handles the discrepancy that can arise between low- and high-level causal models of the same system, and in the process provide an account of how one causal model approximates another, a topic of independent interest. Finally, we extend the account of approximate abstractions to probabilistic causal models, indicating how and where uncertainty can enter into an approximate abstraction.
Dealing with Topological Information within a Fully Convolutional Neural Network
Venue: arXiv cs.CV 2019
Year: 2019

A fully convolutional neural network has a receptive field of limited size and therefore cannot exploit global information, such as topological information. A solution is proposed in this paper to solve this problem, based on pre-processing with a geodesic operator. It is applied to the segmentation of histological images of pigmented reconstructed epidermis acquired via Whole Slide Imaging.
Uncertainty Estimates for Ordinal Embeddings
Venue: arXiv cs.LG 2019
Year: 2019

To investigate objects without a describable notion of distance, one can gather ordinal information by asking triplet comparisons of the form "Is object $x$ closer to $y$ or is $x$ closer to $z$?" In order to learn from such data, the objects are typically embedded in a Euclidean space while satisfying as many triplet comparisons as possible. In this paper, we introduce empirical uncertainty estimates for standard embedding algorithms when few noisy triplets are available, using a bootstrap and a Bayesian approach. In particular, simulations show that these estimates are well calibrated and can serve to select embedding parameters or to quantify uncertainty in scientific applications.
Efficient algorithms for modifying and sampling from a categorical distribution
Venue: arXiv cs.DS 2019
Year: 2019

Probabilistic programming languages and other machine learning applications often require samples to be generated from a categorical distribution where the probability of each one of $n$ categories is specified as a parameter. If the parameters are hyper-parameters then they need to be modified, however, current implementations of categorical distributions take $\mathcal{O}(n)$ time to modify a parameter. If $n$ is large and the parameters are being frequently modified, this can become prohibitive. Here we present the insight that a Huffman tree is an efficient data structure for representing categorical distributions and present algorithms to generate samples as well as add, delete and modify categories in $\mathcal{O}(\log(n))$ time. We demonstrate that the time to sample from the distribution remains, in practice, within a few percent of the theoretical optimal value. The same algorithm may also be useful in the context of adaptive Huffman coding where computational efficiency is important.
Reducing Popularity Bias in Recommendation Over Time
Venue: arXiv cs.IR 2019
Year: 2019

Many recommendation algorithms suffer from popularity bias: a small number of popular items being recommended too frequently, while other items get insufficient exposure. Research in this area so far has concentrated on a one-shot representation of this bias, and on algorithms to improve the diversity of individual recommendation lists. In this work, we take a time-sensitive view of popularity bias, in which the algorithm assesses its long-tail coverage at regular intervals, and compensates in the present moment for omissions in the past. In particular, we present a temporal version of the well-known xQuAD diversification algorithm adapted for long-tail recommendation. Experimental results on two public datasets show that our method is more effective in terms of the long-tail coverage and accuracy tradeoff compared to some other existing approaches.
On Solving Word Equations Using SAT
Venue: arXiv cs.FL 2019
Year: 2019

We present Woorpje, a string solver for bounded word equations (i.e., equations where the length of each variable is upper bounded by a given integer). Our algorithm works by reformulating the satisfiability of bounded word equations as a reachability problem for nondeterministic finite automata, and then carefully encoding this as a propositional satisfiability problem, which we then solve using the well-known Glucose SAT-solver. This approach has the advantage of allowing for the natural inclusion of additional linear length constraints. Our solver obtains reliable and competitive results and, remarkably, discovered several cases where state-of-the-art solvers exhibit a faulty behaviour.
Dynamic Drawing Guidance via Electromagnetic Haptic Feedback
Venue: arXiv cs.HC 2019
Year: 2019

We propose a system to deliver dynamic guidance in drawing, sketching and handwriting tasks via an electromagnet moving underneath a high refresh rate pressure sensitive tablet. The system allows the user to move the pen at their own pace and style and does not take away control. The system continously and iteratively measures the pen motion and adjusts magnet position and power according to the user input in real-time via a receding horizon optimal control formulation. The optimization is based on a novel approximate electromagnet model that is fast enough for use in real-time methods, yet provides very good fit to experimental data. Using a closed-loop time-free approach allows for error-correcting behavior, gently pulling the user back to the desired trajectory rather than pushing or pulling the pen to a continuously advancing setpoint. Our experimental results show that the system can control the pen position with a very low dispersion of 2.8mm (+/-0.8mm). An initial user study indicates that it significantly increases accuracy of users drawing a variety of shapes and that this improvement increases with complexity of the shape.
Singular Value Decomposition and Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Singular Value Decomposition (SVD) constitutes a bridge between the linear algebra concepts and multi-layer neural networks---it is their linear analogy. Besides of this insight, it can be used as a good initial guess for the network parameters, leading to substantially better optimization results.
Mixed-Signal Charge-Domain Acceleration of Deep Neural networks through Interleaved Bit-Partitioned Arithmetic
Venue: arXiv cs.AR 2019
Year: 2019

Low-power potential of mixed-signal design makes it an alluring option to accelerate Deep Neural Networks (DNNs). However, mixed-signal circuitry suffers from limited range for information encoding, susceptibility to noise, and Analog to Digital (A/D) conversion overheads. This paper aims to address these challenges by offering and leveraging the insight that a vector dot-product (the basic operation in DNNs) can be bit-partitioned into groups of spatially parallel low-bitwidth operations, and interleaved across multiple elements of the vectors. As such, the building blocks of our accelerator become a group of wide, yet low-bitwidth multiply-accumulate units that operate in the analog domain and share a single A/D converter. The low-bitwidth operation tackles the encoding range limitation and facilitates noise mitigation. Moreover, we utilize the switched-capacitor design for our bit-level reformulation of DNN operations. The proposed switched-capacitor circuitry performs the group multiplications in the charge domain and accumulates the results of the group in its capacitors over multiple cycles. The capacitive accumulation combined with wide bit-partitioned operations alleviate the need for A/D conversion per operation. With such mathematical reformulation and its switched-capacitor implementation, we define a 3D-stacked microarchitecture, dubbed BIHIWE.
Invariant Detection with Program Verification Tools
Venue: arXiv cs.PL 2019
Year: 2019

Compilers can specialize programs having invariants for performance improvement. Detecting program invariants that span large and complex code, however, is difficult for compilers. Traditional compilers do not perform very expensive analysis and thus only identify limited invariants, which limits the potential of subsequent optimizations. We would like to address the invariant detection problem via more sophisticated analyses using program verification tools. In this paper, we reveal pitfalls of choosing program verification tools for invariant detection, identify challenges of modeling program behavior using one of these tools---CVC4, and propose some ideas about how to address the challenges.
[1,2]-Domination in Generalized Petersen Graphs
Venue: arXiv cs.DM 2019
Year: 2019

A vertex subset $S$ of a graph $G=(V,E)$ is a $[1,2]$-dominating set if each vertex of $V\backslash S$ is adjacent to either one or two vertices in $S$. The minimum cardinality of a $[1,2]$-dominating set of $G$, denoted by $γ_{[1,2]}(G)$, is called the $[1,2]$-domination number of $G$. In this paper the $[1,2]$-domination and the $[1,2]$-total domination numbers of the generalized Petersen graphs $P(n,2)$ are determined.
On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs
Venue: arXiv cs.DM 2019
Year: 2019

A $(0,1)$-matrix has the Consecutive Ones Property (C1P) for the rows if there is a permutation of its columns such that the ones in each row appear consecutively. We say a $(0, 1)$-matrix is nested if it has the consecutive ones property for the rows (C1P) and every two rows are either disjoint or nested. We say a $(0, 1)$-matrix is 2-nested if it has the C1P and admits a partition of its rows into two sets such that the submatrix induced by each of these sets is nested. We say a split graph $G$ with split partition $(K, S)$ is nested (resp.\ 2-nested) if the matrix $A(S, K)$ which indicates the adjacency between vertices in $S$ and $K$ is nested (resp.\ 2-nested). In this work, we characterize nested and 2-nested matrices by minimal forbidden submatrices. This characterization leads to a minimal forbidden induced subgraph characterization for these classes of graphs, which are a superclass of threshold graphs and a subclass of split and circle graphs.
Towards Large-Scale Autonomous Wireless Sensor Networks
Venue: arXiv cs.NI 2019
Year: 2019

Wireless Sensor Networks (WSNs) have the goal of gathering data from the environment. The advent of the Internet of Things (IoT) drastically changed WSN's vision that, as never before, needs to expand and include hundreds or thousands of sensors. But to follow the current IoT trends new techniques need to be implemented since orders of thousands of sensor nodes are not manageable by today's WSNs systems that often rely on manual configuration and hence are not practical. As an example, the replacement of batteries of thousand of nodes could be extremely arduous or even impossible for structural health monitoring of civil infrastructures (i.e. bridges, towers). Hence, the solution to the growing burden of the system manager is automation, allowing the system to check its own status, to re-configure itself and fix the major problems in the network whenever it is possible. In this paper, we present and discuss the main features needed to achieve an autonomous large scale WSN. Furthermore, we compare these features with the state of the art of real-world large scale WSN deployments showing that further solutions are needed to drastically reduce human intervention while guaranteeing the main functionalities of the system.
Supervised Contextual Embeddings for Transfer Learning in Natural Language Processing Tasks
Venue: arXiv cs.CL 2019
Year: 2019

Pre-trained word embeddings are the primary method for transfer learning in several Natural Language Processing (NLP) tasks. Recent works have focused on using unsupervised techniques such as language modeling to obtain these embeddings. In contrast, this work focuses on extracting representations from multiple pre-trained supervised models, which enriches word embeddings with task and domain specific knowledge. Experiments performed in cross-task, cross-domain and cross-lingual settings indicate that such supervised embeddings are helpful, especially in the low-resource setting, but the extent of gains is dependent on the nature of the task and domain. We make our code publicly available.
Pinpointing Performance Inefficiencies in Java
Venue: arXiv cs.PF 2019
Year: 2019

Many performance inefficiencies such as inappropriate choice of algorithms or data structures, developers' inattention to performance, and missed compiler optimizations show up as wasteful memory operations. Wasteful memory operations are those that produce/consume data to/from memory that may have been avoided. We present, JXPerf, a lightweight performance analysis tool for pinpointing wasteful memory operations in Java programs. Traditional byte-code instrumentation for such analysis (1) introduces prohibitive overheads and (2) misses inefficiencies in machine code generation. JXPerf overcomes both of these problems. JXPerf uses hardware performance monitoring units to sample memory locations accessed by a program and uses hardware debug registers to monitor subsequent accesses to the same memory. The result is a lightweight measurement at machine-code level with attribution of inefficiencies to their provenance: machine and source code within full calling contexts. JXPerf introduces only 7% runtime overhead and 7% memory overhead making it useful in production. Guided by JXPerf, we optimize several Java applications by improving code generation and choosing superior data structures and algorithms, which yield significant speedups.