OpenRaiser/Intern-Atlas huggingface dataset:
Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs
Venue: arXiv cs.CG 2016
Year: 2016

We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output. We show that every connected PSLG $G=(V,E)$ in general position can be augmented to a 2-connected PSLG $(V,E\cup E^+)$ by adding new edges of total Euclidean length $\|E^+\|\leq 2\|E\|$, and this bound is the best possible. An optimal edge set $E^+$ can be computed in $O(|V|^4)$ time; however the problem becomes NP-hard when $G$ is disconnected. Further, there is a sequence of edge insertions and deletions that transforms a connected PSLG $G=(V,E)$ into a planar straight-line cycle $G'=(V,E')$ such that $\|E'\|\leq 2\|{\rm MST}(V)\|$, and the graph remains connected with edge length below $\|E\|+\|{\rm MST}(V)\|$ at all stages. These bounds are the best possible.
Algorithms for Automatic Ranking of Participants and Tasks in an Anonymized Contest
Venue: arXiv cs.DS 2016
Year: 2016

We introduce a new set of problems based on the Chain Editing problem. In our version of Chain Editing, we are given a set of anonymous participants and a set of undisclosed tasks that every participant attempts. For each participant-task pair, we know whether the participant has succeeded at the task or not. We assume that participants vary in their ability to solve tasks, and that tasks vary in their difficulty to be solved. In an ideal world, stronger participants should succeed at a superset of tasks that weaker participants succeed at. Similarly, easier tasks should be completed successfully by a superset of participants who succeed at harder tasks. In reality, it can happen that a stronger participant fails at a task that a weaker participants succeeds at. Our goal is to find a perfect nesting of the participant-task relations by flipping a minimum number of participant-task relations, implying such a "nearest perfect ordering" to be the one that is closest to the truth of participant strengths and task difficulties. Many variants of the problem are known to be NP-hard. We propose six natural $k$-near versions of the Chain Editing problem and classify their complexity. The input to a $k$-near Chain Editing problem includes an initial ordering of the participants (or tasks) that we are required to respect by moving each participant (or task) at most $k$ positions from the initial ordering. We obtain surprising results on the complexity of the six $k$-near problems: Five of the problems are polynomial-time solvable using dynamic programming, but one of them is NP-hard.
Constraint Selection in Metric Learning
Venue: arXiv cs.LG 2016
Year: 2016

A number of machine learning algorithms are using a metric, or a distance, in order to compare individuals. The Euclidean distance is usually employed, but it may be more efficient to learn a parametric distance such as Mahalanobis metric. Learning such a metric is a hot topic since more than ten years now, and a number of methods have been proposed to efficiently learn it. However, the nature of the problem makes it quite difficult for large scale data, as well as data for which classes overlap. This paper presents a simple way of improving accuracy and scalability of any iterative metric learning algorithm, where constraints are obtained prior to the algorithm. The proposed approach relies on a loss-dependent weighted selection of constraints that are used for learning the metric. Using the corresponding dedicated loss function, the method clearly allows to obtain better results than state-of-the-art methods, both in terms of accuracy and time complexity. Some experimental results on real world, and potentially large, datasets are demonstrating the effectiveness of our proposition.
Some Counterexamples for Compatible Triangulations
Venue: arXiv cs.CG 2016
Year: 2016

We consider the conjecture by Aichholzer, Aurenhammer, Hurtado, and Krasser that any two points sets with the same cardinality and the same size convex hull can be triangulated in the "same" way, more precisely via \emph{compatible triangulations}. We show counterexamples to various strengthened versions of this conjecture.
Learning binary or real-valued time-series via spike-timing dependent plasticity
Venue: arXiv cs.NE 2016
Year: 2016

A dynamic Boltzmann machine (DyBM) has been proposed as a model of a spiking neural network, and its learning rule of maximizing the log-likelihood of given time-series has been shown to exhibit key properties of spike-timing dependent plasticity (STDP), which had been postulated and experimentally confirmed in the field of neuroscience as a learning rule that refines the Hebbian rule. Here, we relax some of the constraints in the DyBM in a way that it becomes more suitable for computation and learning. We show that learning the DyBM can be considered as logistic regression for binary-valued time-series. We also show how the DyBM can learn real-valued data in the form of a Gaussian DyBM and discuss its relation to the vector autoregressive (VAR) model. The Gaussian DyBM extends the VAR by using additional explanatory variables, which correspond to the eligibility traces of the DyBM and capture long term dependency of the time-series. Numerical experiments show that the Gaussian DyBM significantly improves the predictive accuracy over VAR.
Regressing Robust and Discriminative 3D Morphable Models with a very Deep Neural Network
Venue: arXiv cs.CV 2016
Year: 2016

The 3D shapes of faces are well known to be discriminative. Yet despite this, they are rarely used for face recognition and always under controlled viewing conditions. We claim that this is a symptom of a serious but often overlooked problem with existing methods for single view 3D face reconstruction: when applied "in the wild", their 3D estimates are either unstable and change for different photos of the same subject or they are over-regularized and generic. In response, we describe a robust method for regressing discriminative 3D morphable face models (3DMM). We use a convolutional neural network (CNN) to regress 3DMM shape and texture parameters directly from an input photo. We overcome the shortage of training data required for this purpose by offering a method for generating huge numbers of labeled examples. The 3D estimates produced by our CNN surpass state of the art accuracy on the MICC data set. Coupled with a 3D-3D face matching pipeline, we show the first competitive face recognition results on the LFW, YTF and IJB-A benchmarks using 3D face shapes as representations, rather than the opaque deep feature vectors used by other modern systems.
Distributed Algorithms for Solving a Class of Convex Feasibility Problems
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, a class of convex feasibility problems (CFPs) are studied for multi-agent systems through local interactions. The objective is to search a feasible solution to the convex inequalities with some set constraints in a distributed manner. The distributed control algorithms, involving subgradient and projection, are proposed for both continuous- and discrete-time systems, respectively. Conditions associated with connectivity of the directed communication graph are given to ensure convergence of the algorithms. It is shown that under mild conditions, the states of all agents reach consensus asymptotically and the consensus state is located in the solution set of the CFP. Simulation examples are presented to demonstrate the effectiveness of the theoretical results.
Collaborative Object Transportation Using MAVs via Passive Force Control
Venue: arXiv cs.RO 2016
Year: 2016

This paper shows a strategy based on passive force control for collaborative object transportation using Micro Aerial Vehicles (MAVs), focusing on the transportation of a bulky object by two hexacopters. The goal is to develop a robust approach which does not rely on: (a) communication links between the MAVs, (b) the knowledge of the payload shape and (c) the position of grasping point. The proposed approach is based on the master-slave paradigm, in which the slave agent guarantees compliance to the external force applied by the master to the payload via an admittance controller. The external force acting on the slave is estimated using a non-linear estimator based on the Unscented Kalman Filter (UKF) from the information provided by a visual inertial navigation system. Experimental results demonstrate the performance of the force estimator and show the collaborative transportation of a 1.2 m long object.
Combination of Linear Prediction and Phase Decomposition for Glottal Source Analysis on Voiced Speech
Venue: arXiv cs.SD 2016
Year: 2016

Some glottal analysis approaches based upon linear prediction or complex cepstrum approaches have been proved to be effective to estimate glottal source from real speech utterances. We propose a new approach employing both an all-pole odd-order linear prediction to provide a coarse estimation and phase decomposition based causality/anti-causality separation to generate further refinements. The obtained measures show that this method improved performance in terms of reducing source-filter separation in estimation of glottal flow pulses (GFP). No glottal model fitting is required by this method, thus it has wide and flexible adaptation to retain fidelity of speakers's vocal features with computationally affordable resource. The method is evaluated on real speech utterances to validate it.
QoS-Based Linear Transceiver Optimization for Full-Duplex Multi-User Communications
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider a multi-user wireless system with one full duplex (FD) base station (BS) serving a set of half duplex (HD) mobile users.To cope with the in-band self-interference (SI) and co-channel interference, we formulate a quality-of-service (QoS) based linear transceiver design problem. The problem jointly optimizes the downlink (DL) and uplink (UL) beamforming vectors of the BS and the transmission powers of UL users so as to provide both the DL and UL users with guaranteed signal-to-interference-plus-noise ratio performance, using a minimum UL and DL transmission sum power.The considered system model not only takes into account noise caused by non-ideal RF circuits, analog/digital SI cancellation but also constrains the maximum signal power at the input of the analog-to-digital converter (ADC) for avoiding signal distortion due to finite ADC precision. The formulated design problem is not convex and challenging to solve in general. We first show that for a special case where the SI channel estimation errors are independent and identically distributed, the QoS-based linear transceiver design problem is globally solvable by a polynomial-time bisection algorithm.For the general case, we propose a suboptimal algorithm based on alternating optimization (AO). The AO algorithm is guaranteed to converge to a Karush-Kuhn-Tucker solution.To reduce the complexity of the AO algorithm, we further develop a fixed-point method by extending the classical uplink-downlink duality in HD systems to the FD system.Simulation results are presented to demonstrate the performance of the proposed algorithms and the comparison with HD systems.
A Compositional Framework for Preference-Aware Agents
Venue: arXiv cs.LO 2016
Year: 2016

A formal description of a Cyber-Physical system should include a rigorous specification of the computational and physical components involved, as well as their interaction. Such a description, thus, lends itself to a compositional model where every module in the model specifies the behavior of a (computational or physical) component or the interaction between different components. We propose a framework based on Soft Constraint Automata that facilitates the component-wise description of such systems and includes the tools necessary to compose subsystems in a meaningful way, to yield a description of the entire system. Most importantly, Soft Constraint Automata allow the description and composition of components' preferences as well as environmental constraints in a uniform fashion. We illustrate the utility of our framework using a detailed description of a patrolling robot, while highlighting methods of composition as well as possible techniques to employ them.
Output Feedback Controller Design with Symbolic Observers for Cyber-physical Systems
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we design a symbolic output feedback controller of a cyber-physical system (CPS). The physical plant is modeled by an infinite transition system. We consider the situation that a finite abstracted system of the physical plant, called a c-abstracted system, is given. There exists an approximate alternating simulation relation from the c-abstracted system to the physical plant. A desired behavior of the c-abstracted system is also given, and we have a symbolic state feedback controller of the physical plant. We consider the case where some states of the plant are not measured. Then, to estimate the states with abstracted outputs measured by sensors, we introduce a finite abstracted system of the physical plant, called an o-abstracted system, such that there exists an approximate simulation relation. The relation guarantees that an observer designed based on the state of the o-abstracted system estimates the current state of the plant. We construct a symbolic output feedback controller by composing these systems. By a relation-based approach, we proved that the controlled system approximately exhibits the desired behavior.
Characterizing DAG-depth of Directed Graphs
Venue: arXiv cs.DM 2016
Year: 2016

We study DAG-depth, a structural depth measure of directed graphs, which naturally extends the tree-depth of ordinary graphs. We define a DAG-depth decomposition as a strategy for the cop player in the lift-free version of the cops-and-robber game on directed graphs and prove its correctness. The DAG-depth decomposition is related to DAG-depth in a similar way as an elimination tree is related to the tree-depth. We study the size aspect of DAG-depth decomposition and provide a definition of mergeable and optimally mergeable vertices in order to make the decomposition smaller and acceptable for the cop player as a strategy. We also provide a way to find the closure of a DAG-depth decomposition, which is the largest digraph for which the given decomposition represents a winning strategy for the cop player.
Avalanche Effect in Improperly Initialized CAESAR Candidates
Venue: arXiv cs.CR 2016
Year: 2016

Cryptoprimitives rely on thorough theoretical background, but often lack basic usability features making them prone to unintentional misuse by developers. We argue that this is true even for the state-of-the-art designs. Analyzing 52 candidates of the current CAESAR competition has shown none of them have an avalanche effect in authentication tag strong enough to work properly when partially misconfigured. Although not directly decreasing their security profile, this hints at their security usability being less than perfect. Paper details available at crcs.cz/papers/memics2016
HADES: Microprocessor Hazard Analysis via Formal Verification of Parameterized Systems
Venue: arXiv cs.AR 2016
Year: 2016

HADES is a fully automated verification tool for pipeline-based microprocessors that aims at flaws caused by improperly handled data hazards. It focuses on single-pipeline microprocessors designed at the register transfer level (RTL) and deals with read-after-write, write-after-write, and write-after-read hazards. HADES combines several techniques, including data-flow analysis, error pattern matching, SMT solving, and abstract regular model checking. It has been successfully tested on several microprocessors for embedded applications.
Development of a Real-time Colorectal Tumor Classification System for Narrow-band Imaging zoom-videoendoscopy
Venue: arXiv cs.CV 2016
Year: 2016

Colorectal endoscopy is important for the early detection and treatment of colorectal cancer and is used worldwide. A computer-aided diagnosis (CAD) system that provides an objective measure to endoscopists during colorectal endoscopic examinations would be of great value. In this study, we describe a newly developed CAD system that provides real-time objective measures. Our system captures the video stream from an endoscopic system and transfers it to a desktop computer. The captured video stream is then classified by a pretrained classifier and the results are displayed on a monitor. The experimental results show that our developed system works efficiently in actual endoscopic examinations and is medically significant.
Orthogonal Edge Routing for the EditLens
Venue: arXiv cs.GR 2016
Year: 2016

The EditLens is an interactive lens technique that supports the editing of graphs. The user can insert, update, or delete nodes and edges while maintaining an already existing layout of the graph. For the nodes and edges that are affected by an edit operation, the EditLens suggests suitable locations and routes, which the user can accept or adjust. For this purpose, the EditLens requires an efficient routing algorithm that can compute results at interactive framerates. Existing algorithms cannot fully satisfy the needs of the EditLens. This paper describes a novel algorithm that can compute orthogonal edge routes for incremental edit operations of graphs. Tests indicate that, in general, the algorithm is better than alternative solutions.
Towards End-to-End Audio-Sheet-Music Retrieval
Venue: arXiv cs.SD 2016
Year: 2016

This paper demonstrates the feasibility of learning to retrieve short snippets of sheet music (images) when given a short query excerpt of music (audio) -- and vice versa --, without any symbolic representation of music or scores. This would be highly useful in many content-based musical retrieval scenarios. Our approach is based on Deep Canonical Correlation Analysis (DCCA) and learns correlated latent spaces allowing for cross-modality retrieval in both directions. Initial experiments with relatively simple monophonic music show promising results.
A Novel RTL ATPG Model Based on Gate Inherent Faults (GIF-PO) of Complex Gates
Venue: arXiv cs.AR 2016
Year: 2016

This paper starts with a comprehensive survey on RTL ATPG. It then proposes a novel RTL ATPG model based on "Gate Inherent Faults" (GIF). These GIF are extracted from each complex gate (adder, case-statement, etc.) of the RTL source code individually. They are related to the internal logic paths of a complex gate. They are not related to any net/signal in the RTL design. It is observed, that when all GIF on RTL are covered (100%) and the same stimulus is applied, then all gate level stuck-at faults of the netlist are covered (100%) as well. The proposed RTL ATPG model is therefore synthesis independent. This is shown on ITC'99 testcases. The applied semi-automatic test pattern generation process is based on functional simulation.
Building a robust sentiment lexicon with (almost) no resource
Venue: arXiv cs.CL 2016
Year: 2016

Creating sentiment polarity lexicons is labor intensive. Automatically translating them from resourceful languages requires in-domain machine translation systems, which rely on large quantities of bi-texts. In this paper, we propose to replace machine translation by transferring words from the lexicon through word embeddings aligned across languages with a simple linear transform. The approach leads to no degradation, compared to machine translation, when tested on sentiment polarity classification on tweets from four languages.
Private Learning on Networks
Venue: arXiv cs.DC 2016
Year: 2016

Continual data collection and widespread deployment of machine learning algorithms, particularly the distributed variants, have raised new privacy challenges. In a distributed machine learning scenario, the dataset is stored among several machines and they solve a distributed optimization problem to collectively learn the underlying model. We present a secure multi-party computation inspired privacy preserving distributed algorithm for optimizing a convex function consisting of several possibly non-convex functions. Each individual objective function is privately stored with an agent while the agents communicate model parameters with neighbor machines connected in a network. We show that our algorithm can correctly optimize the overall objective function and learn the underlying model accurately. We further prove that under a vertex connectivity condition on the topology, our algorithm preserves privacy of individual objective functions. We establish limits on the what a coalition of adversaries can learn by observing the messages and states shared over a network.
Compressed Control of Complex Wireless Networks
Venue: arXiv cs.NI 2016
Year: 2016

Future wireless networks are envisioned to integrate multi-hop, multi-operator, multi-technology (m3) components in order to meet the increasing traffic demand at an acceptable price for subscribers. The performance of such a network depends on the multitude of parameters defining traffic statistics, network topology/technology, channel characteristics and business models for multi-operator cooperation. So far, most of these aspects have been addressed separately in the literature. Since the above parameters are mutually dependent, and simultaneously present in a network, for a given channel and traffic statistics, a joint optimization of technology and business model parameters is required. In this paper, we present such joint models of complex wireless networks and introduce optimization with parameter clustering to solve the problem in a tractable way for large number of parameters. By parameter clustering we compress the optimization vector and significantly simplify system implementation, hence the algorithm is referred to as compressed control of wireless networks. Two distinct parameter compression techniques are introduced mainly parameter absorption and parameter aggregation. Numerical results obtained in this way demonstrate clear maximum in the network utility as a function of the network topology parameters. The results, for a specific network with traffic offloading, show that the cooperation decisions between the multiple operators will be significantly influenced by the traffic dynamics. For typical example scenarios, the optimum offloading price varies by factor 3 for different traffic patterns which justifies the use of dynamic strategies in the decision process. Besides, if user availability increases by multi-operator cooperation, network capacity can be increased up to 50% and network throughput up to 30-40%.
Automatic time-series phenotyping using massive feature extraction
Venue: arXiv cs.LG 2016
Year: 2016

Across a far-reaching diversity of scientific and industrial applications, a general key problem involves relating the structure of time-series data to a meaningful outcome, such as detecting anomalous events from sensor recordings, or diagnosing patients from physiological time-series measurements like heart rate or brain activity. Currently, researchers must devote considerable effort manually devising, or searching for, properties of their time series that are suitable for the particular analysis problem at hand. Addressing this non-systematic and time-consuming procedure, here we introduce a new tool, hctsa, that selects interpretable and useful properties of time series automatically, by comparing implementations over 7700 time-series features drawn from diverse scientific literatures. Using two exemplar biological applications, we show how hctsa allows researchers to leverage decades of time-series research to quantify and understand informative structure in their time-series data.