OpenRaiser/Intern-Atlas huggingface dataset:
Comparative evaluation of instrument segmentation and tracking methods in minimally invasive surgery
Venue: arXiv cs.CV 2018
Year: 2018

Intraoperative segmentation and tracking of minimally invasive instruments is a prerequisite for computer- and robotic-assisted surgery. Since additional hardware like tracking systems or the robot encoders are cumbersome and lack accuracy, surgical vision is evolving as promising techniques to segment and track the instruments using only the endoscopic images. However, what is missing so far are common image data sets for consistent evaluation and benchmarking of algorithms against each other. The paper presents a comparative validation study of different vision-based methods for instrument segmentation and tracking in the context of robotic as well as conventional laparoscopic surgery. The contribution of the paper is twofold: we introduce a comprehensive validation data set that was provided to the study participants and present the results of the comparative validation study. Based on the results of the validation study, we arrive at the conclusion that modern deep learning approaches outperform other methods in instrument segmentation tasks, but the results are still not perfect. Furthermore, we show that merging results from different methods actually significantly increases accuracy in comparison to the best stand-alone method. On the other hand, the results of the instrument tracking task show that this is still an open challenge, especially during challenging scenarios in conventional laparoscopic surgery.
Transformer for Emotion Recognition
Venue: arXiv cs.HC 2018
Year: 2018

This paper describes the UMONS solution for the OMG-Emotion Challenge. We explore a context-dependent architecture where the arousal and valence of an utterance are predicted according to its surrounding context (i.e. the preceding and following utterances of the video). We report an improvement when taking into account context for both unimodal and multimodal predictions.
Roundtable Gossip Algorithm: A Novel Sparse Trust Mining Method for Large-scale Recommendation Systems
Venue: arXiv cs.CR 2018
Year: 2018

Cold Start (CS) and sparse evaluation problems dramatically degrade recommendation performance in large-scale recommendation systems such as Taobao and eBay. We name this degradation as the sparse trust problem, which will cause the decrease of the recommendation accuracy rate. To address this problem we propose a novel sparse trust mining method, which is based on the Roundtable Gossip Algorithm (RGA). First, we define the relevant representation of sparse trust, which provides a research idea to solve the problem of sparse evidence in the large-scale recommendation system. Based on which the RGA is proposed for mining latent sparse trust relationships between entities in large-scale recommendation systems. Second, we propose an efficient and simple anti-sparsification method, which overcomes the disadvantages of random trust relationship propagation and Grade Inflation caused by different users have different standard for item rating. Finally, the experimental results show that our method can effectively mine new trust relationships and mitigate the sparse trust problem.
30m resolution Global Annual Burned Area Mapping based on Landsat images and Google Earth Engine
Venue: arXiv cs.CV 2018
Year: 2018

Heretofore, global burned area (BA) products are only available at coarse spatial resolution, since most of the current global BA products are produced with the help of active fire detection or dense time-series change analysis, which requires very high temporal resolution. In this study, however, we focus on automated global burned area mapping approach based on Landsat images. By utilizing the huge catalog of satellite imagery as well as the high-performance computing capacity of Google Earth Engine, we proposed an automated pipeline for generating 30-meter resolution global-scale annual burned area map from time-series of Landsat images, and a novel 30-meter resolution global annual burned area map of 2015 (GABAM 2015) is released. GABAM 2015 consists of spatial extent of fires that occurred during 2015 and not of fires that occurred in previous years. Cross-comparison with recent Fire_cci version 5.0 BA product found a similar spatial distribution and a strong correlation ($R^2=0.74$) between the burned areas from the two products, although differences were found in specific land cover categories (particularly in agriculture land). Preliminary global validation showed the commission and omission error of GABAM 2015 are 13.17% and 30.13%, respectively.
Label Refinery: Improving ImageNet Classification through Label Progression
Venue: arXiv cs.CV 2018
Year: 2018

Among the three main components (data, labels, and models) of any supervised learning system, data and models have been the main subjects of active research. However, studying labels and their properties has received very little attention. Current principles and paradigms of labeling impose several challenges to machine learning algorithms. Labels are often incomplete, ambiguous, and redundant. In this paper we study the effects of various properties of labels and introduce the Label Refinery: an iterative procedure that updates the ground truth labels after examining the entire dataset. We show significant gain using refined labels across a wide range of models. Using a Label Refinery improves the state-of-the-art top-1 accuracy of (1) AlexNet from 59.3 to 67.2, (2) MobileNet from 70.6 to 73.39, (3) MobileNet-0.25 from 50.6 to 55.59, (4) VGG19 from 72.7 to 75.46, and (5) Darknet19 from 72.9 to 74.47.
Biform Theories: Project Description
Venue: arXiv cs.LO 2018
Year: 2018

A biform theory is a combination of an axiomatic theory and an algorithmic theory that supports the integration of reasoning and computation. These are ideal for specifying and reasoning about algorithms that manipulate mathematical expressions. However, formalizing biform theories is challenging since it requires the means to express statements about the interplay of what these algorithms do and what their actions mean mathematically. This paper describes a project to develop a methodology for expressing, manipulating, managing, and generating mathematical knowledge as a network of biform theories. It is a subproject of MathScheme, a long-term project at McMaster University to produce a framework for integrating formal deduction and symbolic computation.
Security and Privacy Analyses of Internet of Things Children's Toys
Venue: arXiv cs.CR 2018
Year: 2018

This paper investigates the security and privacy of Internet-connected children's smart toys through case studies of three commercially-available products. We conduct network and application vulnerability analyses of each toy using static and dynamic analysis techniques, including application binary decompilation and network monitoring. We discover several publicly undisclosed vulnerabilities that violate the Children's Online Privacy Protection Rule (COPPA) as well as the toys' individual privacy policies. These vulnerabilities, especially security flaws in network communications with first-party servers, are indicative of a disconnect between many IoT toy developers and security and privacy best practices despite increased attention to Internet-connected toy hacking risks.
T-Reqs: Tool Support for Managing Requirements in Large-Scale Agile System Development
Venue: arXiv cs.SE 2018
Year: 2018

T-Reqs is a text-based requirements management solution based on the git version control system. It combines useful conventions, templates and helper scripts with powerful existing solutions from the git ecosystem and provides a working solution to address some known requirements engineering challenges in large-scale agile system development. Specifically, it allows agile cross-functional teams to be aware of requirements at system level and enables them to efficiently propose updates to those requirements. Based on our experience with T-Reqs, we i) relate known requirements challenges of large-scale agile system development to tool support; ii) list key requirements for tooling in such a context; and iii) propose concrete solutions for challenges.
Fast Online Exact Solutions for Deterministic MDPs with Sparse Rewards
Venue: arXiv cs.LG 2018
Year: 2018

Markov Decision Processes (MDPs) are a mathematical framework for modeling sequential decision making under uncertainty. The classical approaches for solving MDPs are well known and have been widely studied, some of which rely on approximation techniques to solve MDPs with large state space and/or action space. However, most of these classical solution approaches and their approximation techniques still take much computation time to converge and usually must be re-computed if the reward function is changed. This paper introduces a novel alternative approach for exactly and efficiently solving deterministic, continuous MDPs with sparse reward sources. When the environment is such that the "distance" between states can be determined in constant time, e.g. grid world, our algorithm offers $O( |R|^2 \times |A|^2 \times |S|)$, where $|R|$ is the number of reward sources, $|A|$ is the number of actions, and $|S|$ is the number of states. Memory complexity for the algorithm is $O( |S| + |R| \times |A|)$. This new approach opens new avenues for boosting computational performance for certain classes of MDPs and is of tremendous value for MDP applications such as robotics and unmanned systems. This paper describes the algorithm and presents numerical experiment results to demonstrate its powerful computational performance. We also provide rigorous mathematical description of the approach.
Live Recovery of Bit Corruptions in Datacenter Storage Systems
Venue: arXiv cs.DC 2018
Year: 2018

Due to its high performance and decreasing cost per bit, flash is becoming the main storage medium in datacenters for hot data. However, flash endurance is a perpetual problem, and due to technology trends, subsequent generations of flash devices exhibit progressively shorter lifetimes before they experience uncorrectable bit errors. In this paper we propose extending flash lifetime by allowing devices to expose higher bit error rates. To do so, we present DIRECT, a novel set of policies that leverages latent redundancy in distributed storage systems to recover from bit corruption errors with minimal performance and recovery overhead. In doing so, DIRECT can significantly extend the lifetime of flash devices by effectively utilizing these devices even after they begin exposing bit errors. We implemented DIRECT on two real-world storage systems: ZippyDB, a distributed key-value store backed by RocksDB, and HDFS, a distributed file system. When tested on production traces at Facebook, DIRECT reduces application-visible error rates in ZippyDB by more than 10^2 and recovery time by more than 10^4. DIRECT also allows HDFS to tolerate a 10^4--10^5 higher bit error rate without experiencing application-visible errors.
Identification of Hessian matrix in distributed gradient-based multi-agent coordination control systems
Venue: arXiv cs.SY 2018
Year: 2018

Multi-agent coordination control usually involves a potential function that encodes information of a global control task, while the control input for individual agents is often designed by a gradient-based control law. The property of Hessian matrix associated with a potential function plays an important role in the stability analysis of equilibrium points in gradient-based coordination control systems. Therefore, the identification of Hessian matrix in gradient-based multi-agent coordination systems becomes a key step in multi-agent equilibrium analysis. However, very often the identification of Hessian matrix via the entry-wise calculation is a very tedious task and can easily introduce calculation errors. In this paper we present some general and fast approaches for the identification of Hessian matrix based on matrix differentials and calculus rules, which can easily derive a compact form of Hessian matrix for multi-agent coordination systems. We also present several examples on Hessian identification for certain typical potential functions involving edge-tension distance functions and triangular-area functions, and illustrate their applications in the context of distributed coordination and formation control.
Formal Analysis of Robotic Cell Injection Systems using Theorem Proving
Venue: arXiv cs.LO 2018
Year: 2018

Cell injection is an approach used for the delivery of small sample substances into a biological cell and is widely used in drug development, gene injection, intracytoplasmic sperm injection (ICSI) and in-virto fertilization (IVF). Robotic cell injection systems provide the automation of the process as opposed to the manual and semi-automated cell injection systems, which require expert operators and involve time consuming processes and also have lower success rates. The automation of the cell injection process is achieved by controlling the injection force and planning the motion of the injection pipette. Traditionally, these systems are analyzed using paper-and-pencil proof and computer simulation methods. However, the former is human-error prone and the later is based on the numerical algorithms, where the approximation of the mathematical expressions introduces inaccuracies in the analysis. Formal methods can overcome these limitations and thus provide an accurate analysis of the cell injection systems. Model checking, i.e., a state-based formal method, has been recently proposed for the analysis of these systems. However, it involves the discretization of the differential equations that are used for modeling the dynamics of the system and thus compromises on the completeness of the analysis of these safety-critical systems. In this paper, we propose to use higher-order-logic theorem proving, a deductive-reasoning based formal method, for the modeling and analysis of the dynamical behaviour of the robotic cell injection systems. The proposed analysis, based on the HOL Light theorem prover, enabled us to identify some discrepancies in the simulation and model checking based analysis of the same robotic cell injection system.
Online normalizer calculation for softmax
Venue: arXiv cs.PF 2018
Year: 2018

The Softmax function is ubiquitous in machine learning, multiple previous works suggested faster alternatives for it. In this paper we propose a way to compute classical Softmax with fewer memory accesses and hypothesize that this reduction in memory accesses should improve Softmax performance on actual hardware. The benchmarks confirm this hypothesis: Softmax accelerates by up to 1.3x and Softmax+TopK combined and fused by up to 5x.
A Characterization of Completely Reachable Automata
Venue: arXiv cs.FL 2018
Year: 2018

A complete deterministic finite automaton in which every non-empty subset of the state set occurs as the image of the whole state set under the action of a suitable input word is called completely reachable. We characterize completely reachable automata in terms of certain directed graphs.
Do Smarter People Have Better Passwords?
Venue: arXiv cs.CR 2018
Year: 2018

The National Institute of Standards and Technology (NIST) released new guidelines in June of 2017 that recommended new standards for managing and accepting user passwords. Among the new guidelines is a requirement that verifiers should check if a user's supplied password is compromised - that is, already listed in previous breach corpuses. Using a corpus of 320M breached passwords, the researcher collected information regarding Asia Pacific College students using breached passwords. Correlating these with academic performance data from each student's grade history, the researcher found that the students in the highest GPA tier had the lowest % of terrible passwords. The difference is not that large, however, which suggests that weak passwords aren't mainly because of any level of intelligence, nor should it be assumed that highly-intelligent users will have good passwords.
Exploring Mechanically Self-Reconfiguring Robots for Autonomous Design
Venue: arXiv cs.RO 2018
Year: 2018

Evolutionary robotics has aimed to optimize robot control and morphology to produce better and more robust robots. Most previous research only addresses optimization of control, and does this only in simulation. We have developed a four-legged mammal-inspired robot that features a self-reconfiguring morphology. In this paper, we discuss the possibilities opened up by being able to efficiently do experiments on a changing morphology in the real world. We discuss present challenges for such a platform and potential experimental designs that could unlock new discoveries. Finally, we place our robot in its context within general developments in the field of evolutionary robotics, and consider what advances the future might hold.
A Spiking Neural Dynamical Drift-Diffusion Model on Collective Decision Making with Self-Organized Criticality
Venue: arXiv cs.SY 2018
Year: 2018

This article proposes a novel collective decision making scheme to solve the multi-agent drift-diffusion-model problem with the help of spiking neural networks. The exponential integrate-and-fire model is used here to capture the individual dynamics of each agent in the system, and we name this new model as Exponential Decision Making (EDM) model. We demonstrate analytically and experimentally that the gating variable for instantaneous activation follows Boltzmann probability distribution, and the collective system reaches meta-stable critical states under the Markov chain premises. With mean field analysis, we derive the global criticality from local dynamics and achieve a power law distribution. Critical behavior of EDM exhibits the convergence dynamics of Boltzmann distribution, and we conclude that the EDM model inherits the property of self-organized criticality, that the system will eventually evolve toward criticality.
Parallel Graph Connectivity in Log Diameter Rounds
Venue: arXiv cs.DS 2018
Year: 2018

We study graph connectivity problem in MPC model. On an undirected graph with $n$ nodes and $m$ edges, $O(\log n)$ round connectivity algorithms have been known for over 35 years. However, no algorithms with better complexity bounds were known. In this work, we give fully scalable, faster algorithms for the connectivity problem, by parameterizing the time complexity as a function of the diameter of the graph. Our main result is a $O(\log D \log\log_{m/n} n)$ time connectivity algorithm for diameter-$D$ graphs, using $Θ(m)$ total memory. If our algorithm can use more memory, it can terminate in fewer rounds, and there is no lower bound on the memory per processor. We extend our results to related graph problems such as spanning forest, finding a DFS sequence, exact/approximate minimum spanning forest, and bottleneck spanning forest. We also show that achieving similar bounds for reachability in directed graphs would imply faster boolean matrix multiplication algorithms. We introduce several new algorithmic ideas. We describe a general technique called double exponential speed problem size reduction which roughly means that if we can use total memory $N$ to reduce a problem from size $n$ to $n/k$, for $k=(N/n)^{Θ(1)}$ in one phase, then we can solve the problem in $O(\log\log_{N/n} n)$ phases. In order to achieve this fast reduction for graph connectivity, we use a multistep algorithm. One key step is a carefully constructed truncated broadcasting scheme where each node broadcasts neighbor sets to its neighbors in a way that limits the size of the resulting neighbor sets. Another key step is random leader contraction, where we choose a smaller set of leaders than many previous works do.
CloudAR: A Cloud-based Framework for Mobile Augmented Reality
Venue: arXiv cs.MM 2018
Year: 2018

Computation capabilities of recent mobile devices enable natural feature processing for Augmented Reality (AR). However, mobile AR applications are still faced with scalability and performance challenges. In this paper, we propose CloudAR, a mobile AR framework utilizing the advantages of cloud and edge computing through recognition task offloading. We explore the design space of cloud-based AR exhaustively and optimize the offloading pipeline to minimize the time and energy consumption. We design an innovative tracking system for mobile devices which provides lightweight tracking in 6 degree of freedom (6DoF) and hides the offloading latency from users' perception. We also design a multi-object image retrieval pipeline that executes fast and accurate image recognition tasks on servers. In our evaluations, the mobile AR application built with the CloudAR framework runs at 30 frames per second (FPS) on average with precise tracking of only 1~2 pixel errors and image recognition of at least 97% accuracy. Our results also show that CloudAR outperforms one of the leading commercial AR framework in several performance metrics.
Ordinal Approximation for Social Choice, Matching, and Facility Location Problems given Candidate Positions
Venue: arXiv cs.MA 2018
Year: 2018

In this work we consider general facility location and social choice problems, in which sets of agents $\mathcal{A}$ and facilities $\mathcal{F}$ are located in a metric space, and our goal is to assign agents to facilities (as well as choose which facilities to open) in order to optimize the social cost. We form new algorithms to do this in the presence of only {\em ordinal information}, i.e., when the true costs or distances from the agents to the facilities are {\em unknown}, and only the ordinal preferences of the agents for the facilities are available. The main difference between our work and previous work in this area is that while we assume that only ordinal information about agent preferences in known, we know the exact locations of the possible facilities $\mathcal{F}$. Due to this extra information about the facilities, we are able to form powerful algorithms which have small {\em distortion}, i.e., perform almost as well as omniscient algorithms but use only ordinal information about agent preferences. For example, we present natural social choice mechanisms for choosing a single facility to open with distortion of at most 3 for minimizing both the total and the median social cost; this factor is provably the best possible. We analyze many general problems including matching, $k$-center, and $k$-median, and present black-box reductions from omniscient approximation algorithms with approximation factor $β$ to ordinal algorithms with approximation factor $1+2β$; doing this gives new ordinal algorithms for many important problems, and establishes a toolkit for analyzing such problems in the future.
Modeling and Analysis of MPTCP Proxy-based LTE-WLAN Path Aggregation
Venue: arXiv cs.NI 2018
Year: 2018

Long Term Evolution (LTE)-Wireless Local Area Network (WLAN) Path Aggregation (LWPA) based on Multi-path Transmission Control Protocol (MPTCP) has been under standardization procedure as a promising and cost-efficient solution to boost Downlink (DL) data rate and handle the rapidly increasing data traffic. This paper aims at providing tractable analysis for the DL performance evaluation of large-scale LWPA networks with the help of tools from stochastic geometry. We consider a simple yet practical model to determine under which conditions a native WLAN Access Point (AP) will work under LWPA mode to help increasing the received data rate. Using stochastic spatial models for the distribution of WLAN APs and LTE Base Stations (BSs), we analyze the density of active LWPA-mode WiFi APs in the considered network model, which further leads to closed-form expressions on the DL data rate and area spectral efficiency (ASE) improvement. Our numerical results illustrate the impact of different network parameters on the performance of LWPA networks, which can be useful for further performance optimization.