OpenRaiser/Intern-Atlas huggingface dataset:
Unsupervised temporal context learning using convolutional neural networks for laparoscopic workflow analysis
Venue: arXiv cs.CV 2017
Year: 2017

Computer-assisted surgery (CAS) aims to provide the surgeon with the right type of assistance at the right moment. Such assistance systems are especially relevant in laparoscopic surgery, where CAS can alleviate some of the drawbacks that surgeons incur. For many assistance functions, e.g. displaying the location of a tumor at the appropriate time or suggesting what instruments to prepare next, analyzing the surgical workflow is a prerequisite. Since laparoscopic interventions are performed via endoscope, the video signal is an obvious sensor modality to rely on for workflow analysis. Image-based workflow analysis tasks in laparoscopy, such as phase recognition, skill assessment, video indexing or automatic annotation, require a temporal distinction between video frames. Generally computer vision based methods that generalize from previously seen data are used. For training such methods, large amounts of annotated data are necessary. Annotating surgical data requires expert knowledge, therefore collecting a sufficient amount of data is difficult, time-consuming and not always feasible. In this paper, we address this problem by presenting an unsupervised method for training a convolutional neural network (CNN) to differentiate between laparoscopic video frames on a temporal basis. We extract video frames at regular intervals from 324 unlabeled laparoscopic interventions, resulting in a dataset of approximately 2.2 million images. From this dataset, we extract image pairs from the same video and train a CNN to determine their temporal order. To solve this problem, the CNN has to extract features that are relevant for comprehending laparoscopic workflow. Furthermore, we demonstrate that such a CNN can be adapted for surgical workflow segmentation. We performed image-based workflow segmentation on a publicly available dataset of 7 cholecystectomies and 9 colorectal interventions.
An Efficient Decomposition Framework for Discriminative Segmentation with Supermodular Losses
Venue: arXiv cs.CV 2017
Year: 2017

Several supermodular losses have been shown to improve the perceptual quality of image segmentation in a discriminative framework such as a structured output support vector machine (SVM). These loss functions do not necessarily have the same structure as the one used by the segmentation inference algorithm, and in general, we may have to resort to generic submodular minimization algorithms for loss augmented inference. Although these come with polynomial time guarantees, they are not practical to apply to image scale data. Many supermodular losses come with strong optimization guarantees, but are not readily incorporated in a loss augmented graph cuts procedure. This motivates our strategy of employing the alternating direction method of multipliers (ADMM) decomposition for loss augmented inference. In doing so, we create a new API for the structured SVM that separates the maximum a posteriori (MAP) inference of the model from the loss augmentation during training. In this way, we gain computational efficiency, making new choices of loss functions practical for the first time, while simultaneously making the inference algorithm employed during training closer to the test time procedure. We show improvement both in accuracy and computational performance on the Microsoft Research Grabcut database and a brain structure segmentation task, empirically validating the use of several supermodular loss functions during training, and the improved computational properties of the proposed ADMM approach over the Fujishige-Wolfe minimum norm point algorithm.
An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention
Venue: arXiv cs.FL 2017
Year: 2017

Given an integer base $b>1$, a set of integers is represented in base $b$ by a language over $\{0,1,...,b-1\}$. The set is said to be $b$-recognisable if its representation is a regular language. It is known that eventually periodic sets are $b$-recognisable in every base $b$, and Cobham's theorem implies the converse: no other set is $b$-recognisable in every base $b$. We are interested in deciding whether a $b$-recognisable set of integers (given as a finite automaton) is eventually periodic. Honkala showed that this problem decidable in 1986 and recent developments give efficient decision algorithms. However, they only work when the integers are written with the least significant digit first. In this work, we consider the natural order of digits (Most Significant Digit First) and give a quasi-linear algorithm to solve the problem in this case.
Traditional PageRank versus Network Capacity Bound
Venue: arXiv cs.SI 2017
Year: 2017

In a former paper we simplified the proof of a theorem on personalized random walk that is fundamental to graph nodes clustering and generalized it to bipartite graphs for a specific case where the proobability of random jump was proprtional to the number of links of "personally prefereed" nodes. In this paper we turn to the more complex issue of graphs in which the random jump follows uniform distribution.
Overlapping Community Detection by Local Decentralised Vertex-centred Process
Venue: arXiv cs.SI 2017
Year: 2017

This paper focuses on the identification of overlapping communities, allowing nodes to simultaneously belong to several communities, in a decentralised way. To that aim it proposes LOCNeSs, an algorithm specially designed to run in a decentralised environment and to limit propagation, two essential characteristics to be applied in mobile networks. It is based on the exploitation of the preferential attachment mechanism in networks. Experimental results show that LOCNeSs is stable and achieves good overlapping vertex identification.
Stealthy Secret Key Generation
Venue: arXiv cs.IT 2017
Year: 2017

In this work, we consider a complete covert communication system, which includes the source-model of a stealthy secret key generation (SSKG) as the first phase. The generated key will be used for the covert communication in the second phase of the current round and also in the first phase of the next round. We investigate the stealthy SK rate performance of the first phase. The derived results show that the SK capacity lower and upper bounds of the source-model SKG are not affected by the additional stealth constraint. This result implies that we can attain the SSKG capacity for free when the sequences observed by the three terminals Alice ($X^n$), Bob ($Y^n$) and Willie ($Z^n$) follow a Markov chain relationship, i.e., $X^n-Y^n-Z^n$. We then prove that the sufficient condition to attain both, the SK capacity as well as the SSK capacity, can be relaxed from physical to stochastic degradedness. In order to underline the practical relevance, we also derive a sufficient condition to attain the degradedness by the usual stochastic order for Maurer's fast fading Gaussian (satellite) model for the source of common randomness.
Reservoir Computing Using Non-Uniform Binary Cellular Automata
Venue: arXiv cs.ET 2017
Year: 2017

The Reservoir Computing (RC) paradigm utilizes a dynamical system, i.e., a reservoir, and a linear classifier, i.e., a read-out layer, to process data from sequential classification tasks. In this paper the usage of Cellular Automata (CA) as a reservoir is investigated. The use of CA in RC has been showing promising results. In this paper, selected state-of-the-art experiments are reproduced. It is shown that some CA-rules perform better than others, and the reservoir performance is improved by increasing the size of the CA reservoir itself. In addition, the usage of parallel loosely coupled CA-reservoirs, where each reservoir has a different CA-rule, is investigated. The experiments performed on quasi-uniform CA reservoir provide valuable insights in CA reservoir design. The results herein show that some rules do not work well together, while other combinations work remarkably well. This suggests that non-uniform CA could represent a powerful tool for novel CA reservoir implementations.
Unit Commitment on the Cloud
Venue: arXiv cs.DC 2017
Year: 2017

The advent of High Performance Computing (HPC) has provided the computational capacity required for power system operators (SO) to obtain solutions in the least time to highly-complex applications, i.e., Unit Commitment (UC). The UC problem, which attempts to schedule the least-cost combination of generating units to meet the load, is increasing in complexity and problem size due to deployments of renewable resources and smart grid technologies. The current approach to solving the UC problem consists of in-house HPC infrastructures, which experience issues at scale, and demands high maintenance and capital expenditures. On the other hand, cloud computing is an ideal substitute due to its powerful computational capacity, rapid scalability, and high cost-effectiveness. In this work, the benefits and challenges of outsourcing the UC application to the cloud are explored. A quantitative analysis of the computational performance gain is explored for a large-scale UC problem solved on the cloud and compared to traditional in-house HPC infrastructure. The results show substantial reduction in solve time when outsourced to the cloud.
The Parallel Meaning Bank: Towards a Multilingual Corpus of Translations Annotated with Compositional Meaning Representations
Venue: arXiv cs.CL 2017
Year: 2017

The Parallel Meaning Bank is a corpus of translations annotated with shared, formal meaning representations comprising over 11 million words divided over four languages (English, German, Italian, and Dutch). Our approach is based on cross-lingual projection: automatically produced (and manually corrected) semantic annotations for English sentences are mapped onto their word-aligned translations, assuming that the translations are meaning-preserving. The semantic annotation consists of five main steps: (i) segmentation of the text in sentences and lexical items; (ii) syntactic parsing with Combinatory Categorial Grammar; (iii) universal semantic tagging; (iv) symbolization; and (v) compositional semantic analysis based on Discourse Representation Theory. These steps are performed using statistical models trained in a semi-supervised manner. The employed annotation models are all language-neutral. Our first results are promising.
Connecting the Dots: Privacy Leakage via Write-Access Patterns to the Main Memory
Venue: arXiv cs.CR 2017
Year: 2017

Data-dependent access patterns of an application to an untrusted storage system are notorious for leaking sensitive information about the user's data. Previous research has shown how an adversary capable of monitoring both read and write requests issued to the memory can correlate them with the application to learn its sensitive data. However, information leakage through only the write access patterns is less obvious and not well studied in the current literature. In this work, we demonstrate an actual attack on power-side-channel resistant Montgomery's ladder based modular exponentiation algorithm commonly used in public key cryptography. We infer the complete 512-bit secret exponent in $\sim3.5$ minutes by virtue of just the write access patterns of the algorithm to the main memory. In order to learn the victim algorithm's write access patterns under realistic settings, we exploit a compromised DMA device to take frequent snapshots of the application's address space, and then run a simple differential analysis on these snapshots to find the write access sequence. The attack has been shown on an Intel Core(TM) i7-4790 3.60GHz processor based system. We further discuss a possible attack on McEliece public-key cryptosystem that also exploits the write-access patterns to learn the secret key.
End-to-End Interpretation of the French Street Name Signs Dataset
Venue: arXiv cs.CV 2017
Year: 2017

We introduce the French Street Name Signs (FSNS) Dataset consisting of more than a million images of street name signs cropped from Google Street View images of France. Each image contains several views of the same street name sign. Every image has normalized, title case folded ground-truth text as it would appear on a map. We believe that the FSNS dataset is large and complex enough to train a deep network of significant complexity to solve the street name extraction problem "end-to-end" or to explore the design trade-offs between a single complex engineered network and multiple sub-networks designed and trained to solve sub-problems. We present such an "end-to-end" network/graph for Tensor Flow and its results on the FSNS dataset.
Size Relationships in Abstract Cyclic Entailment Systems
Venue: arXiv cs.LO 2017
Year: 2017

A cyclic proof system generalises the standard notion of a proof as a finite tree of locally sound inferences by allowing proof objects to be potentially infinite. Regular infinite proofs can be finitely represented as graphs. To preclude spurious cyclic reasoning, cyclic proof systems come equipped with a well-founded notion of 'size' for the models that interpret their logical statements. A global soundness condition on proof objects, stated in terms of this notion of size, ensures that any non-well-founded paths in the proof object can be disregarded. We give an abstract definition of a subclass of such cyclic proof systems: cyclic entailment systems. In this setting, we consider the problem of comparing the size of a model when interpreted in relation to the antecedent of an entailment, with that when interpreted in relation to the consequent. Specifically, we give a further condition on proof objects which ensures that models of a given entailment are always 'smaller' when interpreted with respect to the consequent than when interpreted with respect to the antecedent. Knowledge of such relationships is useful in a program verification setting.
Is a Data-Driven Approach still Better than Random Choice with Naive Bayes classifiers?
Venue: arXiv cs.LG 2017
Year: 2017

We study the performance of data-driven, a priori and random approaches to label space partitioning for multi-label classification with a Gaussian Naive Bayes classifier. Experiments were performed on 12 benchmark data sets and evaluated on 5 established measures of classification quality: micro and macro averaged F1 score, Subset Accuracy and Hamming loss. Data-driven methods are significantly better than an average run of the random baseline. In case of F1 scores and Subset Accuracy - data driven approaches were more likely to perform better than random approaches than otherwise in the worst case. There always exists a method that performs better than a priori methods in the worst case. The advantage of data-driven methods against a priori methods with a weak classifier is lesser than when tree classifiers are used.
Towards LTE-U Interference Detection, Assessment and Mitigation in 802.11 Networks using Commodity Hardware
Venue: arXiv cs.NI 2017
Year: 2017

We propose WiPLUS -- a system that enables WiFi to deal with the stealthy invasion of LTE-U into the frequency bands used by WiFi. Using solely MAC layer information extracted passively, during runtime, out of the hardware registers of the WiFi NIC at the WiFi access point, WiPLUS is able to: i) detect interfering LTE-U signals, ii) compute their duty-cycles, and iii) derive the effective medium airtime available for each WiFi link in a WiFi Basic Service Set (BSS). Moreover WiPLUS provides accurate timing information about the detected LTE-U ON and OFF phases enabling advanced interference mitigation strategies such as interference-aware scheduling of packet transmissions, rate adaptation and adaptive channel bonding. WiPLUS does not require any modifications to the WiFi client stations and works with commodity WiFi APs where it has a simple software installation process. We present the design, the implementation details and the evaluation of the WiPLUS approach. Evaluation results reveal that it is able to accurately estimate the effective available medium airtime for each link in a WiFi BSS under a wide range of LTE-U signal strengths with a root-mean-square error of less than 3% for the downlink and less 10% for the uplink.
Occupy the Cloud: Distributed Computing for the 99%
Venue: arXiv cs.DC 2017
Year: 2017

Distributed computing remains inaccessible to a large number of users, in spite of many open source platforms and extensive commercial offerings. While distributed computation frameworks have moved beyond a simple map-reduce model, many users are still left to struggle with complex cluster management and configuration tools, even for running simple embarrassingly parallel jobs. We argue that stateless functions represent a viable platform for these users, eliminating cluster management overhead, fulfilling the promise of elasticity. Furthermore, using our prototype implementation, PyWren, we show that this model is general enough to implement a number of distributed computing models, such as BSP, efficiently. Extrapolating from recent trends in network bandwidth and the advent of disaggregated storage, we suggest that stateless functions are a natural fit for data processing in future computing environments.
Scheduling Algorithms for Asymmetric Multi-core Processors
Venue: arXiv cs.DC 2017
Year: 2017

Growing power dissipation due to high performance requirement of processor suggests multicore processor technology, which has become the technology for present and next decade. Research advocates asymmetric multi-core processor system for better utilization of chip real state. However, asymmetric multi core architecture poses a new challenge to operating system scheduler, which traditionally assumes homogeneous hardware. So, scheduling threads to core has become a major issue to operating system kernel. In this paper, proposed scheduling algorithms for asymmetric multicore processors have been categorized. This paper explores some representative algorithms of these classes to get an overview of scheduling algorithms for asymmetric multicore system.
Constraint Answer Set Solver EZCSP and Why Integration Schemas Matter
Venue: arXiv cs.AI 2017
Year: 2017

Researchers in answer set programming and constraint programming have spent significant efforts in the development of hybrid languages and solving algorithms combining the strengths of these traditionally separate fields. These efforts resulted in a new research area: constraint answer set programming. Constraint answer set programming languages and systems proved to be successful at providing declarative, yet efficient solutions to problems involving hybrid reasoning tasks. One of the main contributions of this paper is the first comprehensive account of the constraint answer set language and solver EZCSP, a mainstream representative of this research area that has been used in various successful applications. We also develop an extension of the transition systems proposed by Nieuwenhuis et al. in 2006 to capture Boolean satisfiability solvers. We use this extension to describe the EZCSP algorithm and prove formal claims about it. The design and algorithmic details behind EZCSP clearly demonstrate that the development of the hybrid systems of this kind is challenging. Many questions arise when one faces various design choices in an attempt to maximize system's benefits. One of the key decisions that a developer of a hybrid solver makes is settling on a particular integration schema within its implementation. Thus, another important contribution of this paper is a thorough case study based on EZCSP, focused on the various integration schemas that it provides. Under consideration in Theory and Practice of Logic Programming (TPLP).
Mutual Kernel Matrix Completion
Venue: arXiv cs.LG 2017
Year: 2017

With the huge influx of various data nowadays, extracting knowledge from them has become an interesting but tedious task among data scientists, particularly when the data come in heterogeneous form and have missing information. Many data completion techniques had been introduced, especially in the advent of kernel methods. However, among the many data completion techniques available in the literature, studies about mutually completing several incomplete kernel matrices have not been given much attention yet. In this paper, we present a new method, called Mutual Kernel Matrix Completion (MKMC) algorithm, that tackles this problem of mutually inferring the missing entries of multiple kernel matrices by combining the notions of data fusion and kernel matrix completion, applied on biological data sets to be used for classification task. We first introduced an objective function that will be minimized by exploiting the EM algorithm, which in turn results to an estimate of the missing entries of the kernel matrices involved. The completed kernel matrices are then combined to produce a model matrix that can be used to further improve the obtained estimates. An interesting result of our study is that the E-step and the M-step are given in closed form, which makes our algorithm efficient in terms of time and memory. After completion, the (completed) kernel matrices are then used to train an SVM classifier to test how well the relationships among the entries are preserved. Our empirical results show that the proposed algorithm bested the traditional completion techniques in preserving the relationships among the data points, and in accurately recovering the missing kernel matrix entries. By far, MKMC offers a promising solution to the problem of mutual estimation of a number of relevant incomplete kernel matrices.
Maximizing Coverage Centrality via Network Design: Extended Version
Venue: arXiv cs.SI 2017
Year: 2017

Network centrality plays an important role in many applications. Central nodes in social networks can be influential, driving opinions and spreading news or rumors.In hyperlinked environments, such as the Web, where users navigate via clicks, central content receives high traffic, becoming targets for advertising campaigns. While there is an extensive amount of work on centrality measures and their efficient computation, controlling nodes' centrality via network updates is a more recent and challenging problem. Performing minimal modifications to a network to achieve a desired property falls under the umbrella of network design problems. This paper is focused on improving the coverage centrality of a set of nodes, which is the number of pairs of nodes that have a shortest path passing through the set, by adding edges to the network. We prove strong inapproximability results and propose a greedy algorithm for maximizing coverage centrality. To ensure scalability to large networks, we also design an efficient sampling algorithm for the problem. In addition to providing an extensive empirical evaluation of our algorithms, we also show that, under some realistic constraints, the proposed solutions achieve almost-optimal approximation for coverage centrality maximization.
One-Step Time-Dependent Future Video Frame Prediction with a Convolutional Encoder-Decoder Neural Network
Venue: arXiv cs.CV 2017
Year: 2017

There is an inherent need for autonomous cars, drones, and other robots to have a notion of how their environment behaves and to anticipate changes in the near future. In this work, we focus on anticipating future appearance given the current frame of a video. Existing work focuses on either predicting the future appearance as the next frame of a video, or predicting future motion as optical flow or motion trajectories starting from a single video frame. This work stretches the ability of CNNs (Convolutional Neural Networks) to predict an anticipation of appearance at an arbitrarily given future time, not necessarily the next video frame. We condition our predicted future appearance on a continuous time variable that allows us to anticipate future frames at a given temporal distance, directly from the input video frame. We show that CNNs can learn an intrinsic representation of typical appearance changes over time and successfully generate realistic predictions at a deliberate time difference in the near future.