OpenRaiser/Intern-Atlas huggingface dataset:
Cooperative Games with Bounded Dependency Degree
Venue: arXiv cs.GT 2017
Year: 2017

Cooperative games provide a framework to study cooperation among self-interested agents. They offer a number of solution concepts describing how the outcome of the cooperation should be shared among the players. Unfortunately, computational problems associated with many of these solution concepts tend to be intractable---NP-hard or worse. In this paper, we incorporate complexity measures recently proposed by Feige and Izsak (2013), called dependency degree and supermodular degree, into the complexity analysis of cooperative games. We show that many computational problems for cooperative games become tractable for games whose dependency degree or supermodular degree are bounded. In particular, we prove that simple games admit efficient algorithms for various solution concepts when the supermodular degree is small; further, we show that computing the Shapley value is always in FPT with respect to the dependency degree. Finally, we note that, while determining the dependency among players is computationally hard, there are efficient algorithms for special classes of games.
Detection of Tooth caries in Bitewing Radiographs using Deep Learning
Venue: arXiv cs.CV 2017
Year: 2017

We develop a Computer Aided Diagnosis (CAD) system, which enhances the performance of dentists in detecting wide range of dental caries. The CAD System achieves this by acting as a second opinion for the dentists with way higher sensitivity on the task of detecting cavities than the dentists themselves. We develop annotated dataset of more than 3000 bitewing radiographs and utilize it for developing a system for automated diagnosis of dental caries. Our system consists of a deep fully convolutional neural network (FCNN) consisting 100+ layers, which is trained to mark caries on bitewing radiographs. We have compared the performance of our proposed system with three certified dentists for marking dental caries. We exceed the average performance of the dentists in both recall (sensitivity) and F1-Score (agreement with truth) by a very large margin. Working example of our system is shown in Figure 1.
Performance Evaluation of SDN-Controlled Green Mobile Fronthaul Using a Federation of Experimental Network
Venue: arXiv cs.NI 2017
Year: 2017

When evolved NodeB (eNB) flexible functional split is implemented in Virtualized Radio Access Network (V-RAN) 5G systems, fronthaul connectivity between the virtualized network functions (VNFs) must be seamlessly guaranteed. This study proposes the utilization of Software Defined Networking (SDN) to control the mobile fronthaul. In particular, this study investigates the ability of the SDN-based control of reconfiguring the fronthaul to maintain VNF connectivity when cell and optical access turn into sleep mode (off mode) for energy efficiency purposes. The evaluation of the proposed scheme is performed by federating two remote experimental testbeds. Results show that, upon cell and optical access turning on and off, the fronthaul reconfiguration time is limited to few tens of milliseconds.
Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps
Venue: arXiv cs.RO 2017
Year: 2017

This paper studies the underlying combinatorial structure of a class of object rearrangement problems, which appear frequently in applications. The problems involve multiple, similar-geometry objects placed on a flat, horizontal surface, where a robot can approach them from above and perform pick-and-place operations to rearrange them. The paper considers both the case where the start and goal object poses overlap, and where they do not. For overlapping poses, the primary objective is to minimize the number of pick-and-place actions and then to minimize the distance traveled by the end-effector. For the non-overlapping case, the objective is solely to minimize the travel distance of the end-effector. While such problems do not involve all the complexities of general rearrangement, they remain computationally hard in both cases. This is shown through reductions from well-understood, hard combinatorial challenges to these rearrangement problems. The reductions are also shown to hold in the reverse direction, which enables the convenient application on rearrangement of well studied algorithms. These algorithms can be very efficient in practice despite the hardness results. The paper builds on these reduction results to propose an algorithmic pipeline for dealing with the rearrangement problems. Experimental evaluation, including hardware-based trials, shows that the proposed pipeline computes high-quality paths with regards to the optimization objectives. Furthermore, it exhibits highly desirable scalability as the number of objects increases in both the overlapping and non-overlapping setup.
Distributed Rumor Blocking with Multiple Positive Cascades
Venue: arXiv cs.SI 2017
Year: 2017

Misinformation and rumor can spread rapidly and widely through online social networks and therefore rumor controlling has become a critical issue. It is often assumed that there is a single authority whose goal is to minimize the spread of rumor by generating a positive cascade. In this paper, we study a more realistic scenario when there are multiple positive cascades generated by different agents. For the multiple-cascade diffusion, we propose the P2P independent cascade (PIC) model for private social communications. The main part of this paper is an analysis of the rumor blocking effect (i.e. the number of the users activated by rumor) when the agents non-cooperatively generate the positive cascades. We show that the rumor blocking effect provided by the Nash equilibrium will not be arbitrarily worse even if the positive cascades are generated non-cooperatively. In addition, we give a discussion on how the cascade priority and activation order affect the rumor blocking problem. We experimentally examine the Nash equilibrium of the proposed games by simulations done on real social network structures.
A local graph rewiring algorithm for sampling spanning trees
Venue: arXiv cs.DM 2017
Year: 2017

We introduce a Markov Chain Monte Carlo algorithm which samples from the space of spanning trees of complete graphs using local rewiring operations only. The probability distribution of graphs of this kind is shown to depend on the symmetries of these graphs, which are reflected in the equilibrium distribution of the Markov chain. We prove that the algorithm is ergodic and proceed to estimate the probability distribution for small graph ensembles with exactly known probabilities. The autocorrelation time of the graph diameter demonstrates that the algorithm generates independent configurations efficiently as the system size increases. Finally, the mean graph diameter is estimated for spanning trees of sizes ranging over three orders of magnitude. The mean graph diameter results agree with theoretical asymptotic values.
Implementing the Deep Q-Network
Venue: arXiv cs.LG 2017
Year: 2017

The Deep Q-Network proposed by Mnih et al. [2015] has become a benchmark and building point for much deep reinforcement learning research. However, replicating results for complex systems is often challenging since original scientific publications are not always able to describe in detail every important parameter setting and software engineering solution. In this paper, we present results from our work reproducing the results of the DQN paper. We highlight key areas in the implementation that were not covered in great detail in the original paper to make it easier for researchers to replicate these results, including termination conditions and gradient descent algorithms. Finally, we discuss methods for improving the computational performance and provide our own implementation that is designed to work with a range of domains, and not just the original Arcade Learning Environment [Bellemare et al., 2013].
On estimating the alphabet size of a discrete random source
Venue: arXiv cs.DS 2017
Year: 2017

We are concerned with estimating alphabet size $N$ from a stream of symbols taken uniformly at random from that alphabet. We define and analyze a memory-restricted variant of an algorithm that have been earlier proposed for this purpose. The alphabet size $N$ can be estimated in $O(\sqrt{N})$ time and space by the memory-restricted variant of this algorithm.
Neural 3D Mesh Renderer
Venue: arXiv cs.CV 2017
Year: 2017

For modeling the 3D world behind 2D images, which 3D representation is most appropriate? A polygon mesh is a promising candidate for its compactness and geometric properties. However, it is not straightforward to model a polygon mesh from 2D images using neural networks because the conversion from a mesh to an image, or rendering, involves a discrete operation called rasterization, which prevents back-propagation. Therefore, in this work, we propose an approximate gradient for rasterization that enables the integration of rendering into neural networks. Using this renderer, we perform single-image 3D mesh reconstruction with silhouette image supervision and our system outperforms the existing voxel-based approach. Additionally, we perform gradient-based 3D mesh editing operations, such as 2D-to-3D style transfer and 3D DeepDream, with 2D supervision for the first time. These applications demonstrate the potential of the integration of a mesh renderer into neural networks and the effectiveness of our proposed renderer.
On the Distortion of Voting with Multiple Representative Candidates
Venue: arXiv cs.GT 2017
Year: 2017

We study positional voting rules when candidates and voters are embedded in a common metric space, and cardinal preferences are naturally given by distances in the metric space. In a positional voting rule, each candidate receives a score from each ballot based on the ballot's rank order; the candidate with the highest total score wins the election. The cost of a candidate is his sum of distances to all voters, and the distortion of an election is the ratio between the cost of the elected candidate and the cost of the optimum candidate. We consider the case when candidates are representative of the population, in the sense that they are drawn i.i.d. from the population of the voters, and analyze the expected distortion of positional voting rules. Our main result is a clean and tight characterization of positional voting rules that have constant expected distortion (independent of the number of candidates and the metric space). Our characterization result immediately implies constant expected distortion for Borda Count and elections in which each voter approves a constant fraction of all candidates. On the other hand, we obtain super-constant expected distortion for Plurality, Veto, and approving a constant number of candidates. These results contrast with previous results on voting with metric preferences: When the candidates are chosen adversarially, all of the preceding voting rules have distortion linear in the number of candidates or voters. Thus, the model of representative candidates allows us to distinguish voting rules which seem equally bad in the worst case.
Towards a More Reliable Privacy-preserving Recommender System
Venue: arXiv cs.LG 2017
Year: 2017

This paper proposes a privacy-preserving distributed recommendation framework, Secure Distributed Collaborative Filtering (SDCF), to preserve the privacy of value, model and existence altogether. That says, not only the ratings from the users to the items, but also the existence of the ratings as well as the learned recommendation model are kept private in our framework. Our solution relies on a distributed client-server architecture and a two-stage Randomized Response algorithm, along with an implementation on the popular recommendation model, Matrix Factorization (MF). We further prove SDCF to meet the guarantee of Differential Privacy so that clients are allowed to specify arbitrary privacy levels. Experiments conducted on numerical rating prediction and one-class rating action prediction exhibit that SDCF does not sacrifice too much accuracy for privacy.
HybridTune: Spatio-temporal Data and Model Driven Performance Diagnosis for Big Data Systems
Venue: arXiv cs.DC 2017
Year: 2017

With tremendous growing interests in Big Data systems, analyzing and facilitating their performance improvement become increasingly important. Although there have much research efforts for improving Big Data systems performance, efficiently analysing and diagnosing performance bottlenecks over these massively distributed systems remain a major challenge. In this paper, we propose a spatio-temporal correlation analysis approach based on stage characteristic and distribution characteristic of Big Data applications, which can associate the multi-level performance data fine-grained. On the basis of correlation data, we define some priori rules, select features and vectorize the corresponding datasets for different performance bottlenecks, such as, workload imbalance, data skew, abnormal node and outlier metrics. And then, we utilize the data and model driven algorithms for bottlenecks detection and diagnosis. In addition, we design and develop a lightweight, extensible tool HybridTune, and validate the diagnosis effectiveness of our tool with BigDataBench on several benchmark experiments in which the outperform state-of-the-art methods. Our experiments show that the accuracy of abnormal/outlier detection we obtained reaches about 80%. At last, we report several Spark and Hadoop use cases, which are demonstrated how HybridTune supports users to carry out the performance analysis and diagnosis efficiently on the Spark and Hadoop applications, and our experiences demonstrate HybridTune can help users find the performance bottlenecks and provide optimization recommendations.
Using stochastic computation graphs formalism for optimization of sequence-to-sequence model
Venue: arXiv cs.LG 2017
Year: 2017

Variety of machine learning problems can be formulated as an optimization task for some (surrogate) loss function. Calculation of loss function can be viewed in terms of stochastic computation graphs (SCG). We use this formalism to analyze a problem of optimization of famous sequence-to-sequence model with attention and propose reformulation of the task. Examples are given for machine translation (MT). Our work provides a unified view on different optimization approaches for sequence-to-sequence models and could help researchers in developing new network architectures with embedded stochastic nodes.
Towards a Magnetically Actuated Laser Scanner for Endoscopic Microsurgeries
Venue: arXiv cs.RO 2017
Year: 2017

This article presents the design and assembly of a novel magnetically actuated endoscopic laser scanner device. The device is designed to perform 2D position control and high speed scanning of a fiber-based laser for operation in narrow workspaces. The device includes laser focusing optics to allow non-contact incisions and tablet-based control interface for intuitive teleoperation. The performance of the proof-of-concept device is analysed through controllability and the usability studies. The computer-controlled high-speed scanning demonstrates repeatable results with 21 um precision and a stable response up to 48 Hz. Teleoperation user trials, were performed for trajectory-following tasks with 12 subjects, show an accuracy of 39 um. The innovative design of the device can be applied to both surgical and diagnostic (imaging) applications in endoscopic systems.
Solving Poisson's Equation on the Microsoft HoloLens
Venue: arXiv cs.GR 2017
Year: 2017

We present a mixed reality application (HoloFEM) for the Microsoft HoloLens. The application lets a user define and solve a physical problem governed by Poisson's equation with the surrounding real world geometry as input data. Holograms are used to visualise both the problem and the solution. The finite element method is used to solve Poisson's equation. Solving and visualising partial differential equations in mixed reality could have potential usage in areas such as building planning and safety engineering.
Evaluation of bioinspired algorithms for the solution of the job scheduling problem
Venue: arXiv cs.NE 2017
Year: 2017

In this research we used bio-inspired metaheuristics, as artificial immune systems and ant colony algorithms that are based on a number of characteristics and behaviors of living things that are interesting in the computer science area. This paper presents an evaluation of bio-inspired solutions to combinatorial optimization problem, called the Job Shop Scheduling or planning work, in a simple way the objective is to find a configuration or job stream that has the least amount of time to be executed in machine settings. The performance of the algorithms was characterized and evaluated for reference instances of the job shop scheduling problem, comparing the quality of the solutions obtained with respect to the best known solution of the most effective methods. The solutions were evaluated in two aspects, first in relation of quality of solutions, taking as reference the makespan and secondly in relation of performance, taking the number evaluations performed by the algorithm to obtain the best solution.
Situationally Aware Options
Venue: arXiv cs.AI 2017
Year: 2017

Hierarchical abstractions, also known as options -- a type of temporally extended action (Sutton et. al. 1999) that enables a reinforcement learning agent to plan at a higher level, abstracting away from the lower-level details. In this work, we learn reusable options whose parameters can vary, encouraging different behaviors, based on the current situation. In principle, these behaviors can include vigor, defence or even risk-averseness. These are some examples of what we refer to in the broader context as Situational Awareness (SA). We incorporate SA, in the form of vigor, into hierarchical RL by defining and learning situationally aware options in a Probabilistic Goal Semi-Markov Decision Process (PG-SMDP). This is achieved using our Situationally Aware oPtions (SAP) policy gradient algorithm which comes with a theoretical convergence guarantee. We learn reusable options in different scenarios in a RoboCup soccer domain (i.e., winning/losing). These options learn to execute with different levels of vigor resulting in human-like behaviours such as `time-wasting' in the winning scenario. We show the potential of the agent to exit bad local optima using reusable options in RoboCup. Finally, using SAP, the agent mitigates feature-based model misspecification in a Bottomless Pit of Death domain.
Effective Strategies in Zero-Shot Neural Machine Translation
Venue: arXiv cs.CL 2017
Year: 2017

In this paper, we proposed two strategies which can be applied to a multilingual neural machine translation system in order to better tackle zero-shot scenarios despite not having any parallel corpus. The experiments show that they are effective in terms of both performance and computing resources, especially in multilingual translation of unbalanced data in real zero-resourced condition when they alleviate the language bias problem.
Low-Complexity Integer-Forcing Methods for Block Fading MIMO Multiple-Access Channels
Venue: arXiv cs.IT 2017
Year: 2017

Integer forcing is an alternative approach to conventional linear receivers for multiple-antenna systems. In an integer-forcing receiver, integer linear combinations of messages are extracted from the received matrix before each individual message is recovered. Recently, the integer-forcing approach was generalized to a block fading scenario. Among the existing variations of the scheme, the ones with the highest achievable rates have the drawback that no efficient algorithm is known to find the best choice of integer linear combination coefficients. In this paper, we propose several sub-optimal methods to find these coefficients with low complexity, covering both parallel and successive interference cancellation versions of the receiver. Simulation results show that the proposed methods attain a performance close to optimal in terms of achievable rates for a given outage probability. Moreover, a low-complexity implementation using root LDPC codes is developed, showing that the benefits of the proposed methods also carry on to practice.
Relating Input Concepts to Convolutional Neural Network Decisions
Venue: arXiv cs.LG 2017
Year: 2017

Many current methods to interpret convolutional neural networks (CNNs) use visualization techniques and words to highlight concepts of the input seemingly relevant to a CNN's decision. The methods hypothesize that the recognition of these concepts are instrumental in the decision a CNN reaches, but the nature of this relationship has not been well explored. To address this gap, this paper examines the quality of a concept's recognition by a CNN and the degree to which the recognitions are associated with CNN decisions. The study considers a CNN trained for scene recognition over the ADE20k dataset. It uses a novel approach to find and score the strength of minimally distributed representations of input concepts (defined by objects in scene images) across late stage feature maps. Subsequent analysis finds evidence that concept recognition impacts decision making. Strong recognition of concepts frequently-occurring in few scenes are indicative of correct decisions, but recognizing concepts common to many scenes may mislead the network.
Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
Venue: arXiv cs.CC 2017
Year: 2017

Alternating minimization heuristics seek to solve a (difficult) global optimization task through iteratively solving a sequence of (much easier) local optimization tasks on different parts (or blocks) of the input parameters. While popular and widely applicable, very few examples of this heuristic are rigorously shown to converge to optimality, and even fewer to do so efficiently. In this paper we present a general framework which is amenable to rigorous analysis, and expose its applicability. Its main feature is that the local optimization domains are each a group of invertible matrices, together naturally acting on tensors, and the optimization problem is minimizing the norm of an input tensor under this joint action. The solution of this optimization problem captures a basic problem in Invariant Theory, called the null-cone problem. This algebraic framework turns out to encompass natural computational problems in combinatorial optimization, algebra, analysis, quantum information theory, and geometric complexity theory. It includes and extends to high dimensions the recent advances on (2-dimensional) operator scaling. Our main result is a fully polynomial time approximation scheme for this general problem, which may be viewed as a multi-dimensional scaling algorithm. This directly leads to progress on some of the problems in the areas above, and a unified view of others. We explain how faster convergence of an algorithm for the same problem will allow resolving central open problems. Our main techniques come from Invariant Theory, and include its rich non-commutative duality theory, and new bounds on the bitsizes of coefficients of invariant polynomials. They enrich the algorithmic toolbox of this very computational field of mathematics, and are directly related to some challenges in geometric complexity theory (GCT).