OpenRaiser/Intern-Atlas huggingface dataset:
Degrees of Freedom in Deep Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we explore degrees of freedom in deep sigmoidal neural networks. We show that the degrees of freedom in these models is related to the expected optimism, which is the expected difference between test error and training error. We provide an efficient Monte-Carlo method to estimate the degrees of freedom for multi-class classification methods. We show degrees of freedom are lower than the parameter count in a simple XOR network. We extend these results to neural nets trained on synthetic and real data, and investigate impact of network's architecture and different regularization choices. The degrees of freedom in deep networks are dramatically smaller than the number of parameters, in some real datasets several orders of magnitude. Further, we observe that for fixed number of parameters, deeper networks have less degrees of freedom exhibiting a regularization-by-depth.
Confidence driven TGV fusion
Venue: arXiv cs.CV 2016
Year: 2016

We introduce a novel model for spatially varying variational data fusion, driven by point-wise confidence values. The proposed model allows for the joint estimation of the data and the confidence values based on the spatial coherence of the data. We discuss the main properties of the introduced model as well as suitable algorithms for estimating the solution of the corresponding biconvex minimization problem and their convergence. The performance of the proposed model is evaluated considering the problem of depth image fusion by using both synthetic and real data from publicly available datasets.
Robust Uncalibrated Stereo Rectification with Constrained Geometric Distortions (USR-CGD)
Venue: arXiv cs.CV 2016
Year: 2016

A novel algorithm for uncalibrated stereo image-pair rectification under the constraint of geometric distortion, called USR-CGD, is presented in this work. Although it is straightforward to define a rectifying transformation (or homography) given the epipolar geometry, many existing algorithms have unwanted geometric distortions as a side effect. To obtain rectified images with reduced geometric distortions while maintaining a small rectification error, we parameterize the homography by considering the influence of various kinds of geometric distortions. Next, we define several geometric measures and incorporate them into a new cost function for parameter optimization. Finally, we propose a constrained adaptive optimization scheme to allow a balanced performance between the rectification error and the geometric error. Extensive experimental results are provided to demonstrate the superb performance of the proposed USR-CGD method, which outperforms existing algorithms by a significant margin.
Blind Friendly Maps: Tactile Maps for the Blind as a Part of the Public Map Portal (Mapy.cz)
Venue: arXiv cs.HC 2016
Year: 2016

Blind people can now use maps located at Mapy.cz, thanks to the long-standing joint efforts of the ELSA Center at the Czech Technical University in Prague, the Teiresias Center at Masaryk University, and the company Seznam.cz. Conventional map underlays are automatically adjusted so that they could be read through touch after being printed on microcapsule paper, which opens a whole new perspective in the use of tactile maps. Users may select an area of their choice in the Czech Republic (only within its boundaries, for the time being) and also the production of tactile maps, including the preparation of the map underlays, takes no more than several minutes.
Image Retrieval with a Bayesian Model of Relevance Feedback
Venue: arXiv cs.IR 2016
Year: 2016

A content-based image retrieval system based on multinomial relevance feedback is proposed. The system relies on an interactive search paradigm where at each round a user is presented with k images and selects the one closest to their ideal target. Two approaches, one based on the Dirichlet distribution and one based the Beta distribution, are used to model the problem motivating an algorithm that trades exploration and exploitation in presenting the images in each round. Experimental results show that the new approach compares favourably with previous work.
INDIGO-Datacloud: foundations and architectural description of a Platform as a Service oriented to scientific computing
Venue: arXiv cs.SE 2016
Year: 2016

In this paper we describe the architecture of a Platform as a Service (PaaS) oriented to computing and data analysis. In order to clarify the choices we made, we explain the features using practical examples, applied to several known usage patterns in the area of HEP computing. The proposed architecture is devised to provide researchers with a unified view of distributed computing infrastructures, focusing in facilitating seamless access. In this respect the Platform is able to profit from the most recent developments for computing and processing large amounts of data, and to exploit current storage and preservation technologies, with the appropriate mechanisms to ensure security and privacy.
Characterizing Realizability in Abstract Argumentation
Venue: arXiv cs.AI 2016
Year: 2016

Realizability for knowledge representation formalisms studies the following question: given a semantics and a set of interpretations, is there a knowledge base whose semantics coincides exactly with the given interpretation set? We introduce a general framework for analyzing realizability in abstract dialectical frameworks (ADFs) and various of its subclasses. In particular, the framework applies to Dung argumentation frameworks, SETAFs by Nielsen and Parsons, and bipolar ADFs. We present a uniform characterization method for the admissible, complete, preferred and model/stable semantics. We employ this method to devise an algorithm that decides realizability for the mentioned formalisms and semantics; moreover the algorithm allows for constructing a desired knowledge base whenever one exists. The algorithm is built in a modular way and thus easily extensible to new formalisms and semantics. We have also implemented our approach in answer set programming, and used the implementation to obtain several novel results on the relative expressiveness of the abovementioned formalisms.
Greedy Strategies and Larger Islands of Tractability for Conjunctive Queries and Constraint Satisfaction Problems
Venue: arXiv cs.DB 2016
Year: 2016

Structural decomposition methods have been developed for identifying tractable classes of instances of fundamental problems in databases, such as conjunctive queries and query containment, of the constraint satisfaction problem in artificial intelligence, or more generally of the homomorphism problem over relational structures. Most structural decomposition methods can be characterized through hypergraph games that are variations of the Robber and Cops graph game that characterizes the notion of treewidth. In particular, decomposition trees somehow correspond to monotone winning strategies, where the escape space of the robber on the hypergraph is shrunk monotonically by the cops. In fact, unlike the treewidth case, there are hypergraphs where monotonic strategies do not exist, while the robber can be captured by means of more complex non-monotonic strategies. However, these powerful strategies do not correspond in general to valid decompositions. The paper provides a general way to exploit the power of non-monotonic strategies, by allowing a "disciplined" form of non-monotonicity, characteristic of cops playing in a greedy way. It is shown that deciding the existence of a (non-monotone) greedy winning strategy (and compute one, if any) is tractable. Moreover, despite their non-monotonicity, such strategies always induce valid decomposition trees, which can be computed efficiently based on them. As a consequence, greedy strategies allow us to define new islands of tractability for the considered problems properly including all previously known classes of tractable instances.
Lyapunov stability of a rigid body with two frictional contacts
Venue: arXiv cs.SY 2016
Year: 2016

Lyapunov stability of a mechanical system means that the dynamic response stays bounded in an arbitrarily small neighborhood of a static equilibrium configuration under small perturbations in positions and velocities. This type of stability is highly desired in robotic applications that involve multiple unilateral contacts. Nevertheless, Lyapunov stability analysis of such systems is extremely difficult, because even small perturbations may result in hybrid dynamics where the solution involves many nonsmooth transitions between different contact states. This paper concerns with Lyapunov stability analysis of a planar rigid body with two frictional unilateral contacts under inelastic impacts, for a general class of equilibrium configurations under a constant external load. The hybrid dynamics of the system under contact transitions and impacts is formulated, and a \Poincare map at two-contact states is introduced. Using invariance relations, this \Poincare map is reduced into two semi-analytic scalar functions that entirely encode the dynamic behavior of solutions under any small initial perturbation. These two functions enable determination of Lyapunov stability or instability for almost any equilibrium state. The results are demonstrated via simulation examples and by plotting stability and instability regions in two-dimensional parameter spaces that describe the contact geometry and external load.
Object Boundary Guided Semantic Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Semantic segmentation is critical to image content understanding and object localization. Recent development in fully-convolutional neural network (FCN) has enabled accurate pixel-level labeling. One issue in previous works is that the FCN based method does not exploit the object boundary information to delineate segmentation details since the object boundary label is ignored in the network training. To tackle this problem, we introduce a double branch fully convolutional neural network, which separates the learning of the desirable semantic class labeling with mask-level object proposals guided by relabeled boundaries. This network, called object boundary guided FCN (OBG-FCN), is able to integrate the distinct properties of object shape and class features elegantly in a fully convolutional way with a designed masking architecture. We conduct experiments on the PASCAL VOC segmentation benchmark, and show that the end-to-end trainable OBG-FCN system offers great improvement in optimizing the target semantic segmentation quality.
On the Performance of RF-FSO Links with and without Hybrid ARQ
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies the performance of hybrid radio-frequency (RF) and free-space optical (FSO) links assuming perfect channel state information (CSI) at the receiver. Considering the cases with and without hybrid automatic repeat request (HARQ), we derive closed-form expressions for the message decoding probabilities as well as the throughput and the outage probability of the RF-FSO setups. We also evaluate the effect of adaptive power allocation and different channel conditions on the throughput and the outage probability. The results show the efficiency of the RF-FSO links in different conditions.
It's Moving! A Probabilistic Model for Causal Motion Segmentation in Moving Camera Videos
Venue: arXiv cs.CV 2016
Year: 2016

The human ability to detect and segment moving objects works in the presence of multiple objects, complex background geometry, motion of the observer, and even camouflage. In addition to all of this, the ability to detect motion is nearly instantaneous. While there has been much recent progress in motion segmentation, it still appears we are far from human capabilities. In this work, we derive from first principles a new likelihood function for assessing the probability of an optical flow vector given the 3D motion direction of an object. This likelihood uses a novel combination of the angle and magnitude of the optical flow to maximize the information about the true motions of objects. Using this new likelihood and several innovations in initialization, we develop a motion segmentation algorithm that beats current state-of-the-art methods by a large margin. We compare to five state-of-the-art methods on two established benchmarks, and a third new data set of camouflaged animals, which we introduce to push motion segmentation to the next level.
Approaching Optimal Centralized Scheduling with CSMA-based Random Access over Fading Channels
Venue: arXiv cs.NI 2016
Year: 2016

Carrier Sense Multiple Access (CSMA) based distributed algorithms can attain the largest capacity region as the centralized Max-Weight policy does. Despite their capability of achieving throughput-optimality, these algorithms can either incur large delay and have large complexity or only operate over non-fading channels. In this letter, by assuming arbitrary back-off time we first propose a fully distributed randomized algorithm whose performance can be pushed to the performance of the centralized Max-Weight policy not only in terms of throughput but also in terms of delay for completely-connected interference networks with fading channels. Then, inspired by the proposed algorithm we introduce an implementable distributed algorithm for practical networks with a reservation scheme. We show that the proposed practical algorithm can still achieve the performance of the centralized Max-Weight policy.
Singing Voice Separation and Vocal F0 Estimation based on Mutual Combination of Robust Principal Component Analysis and Subharmonic Summation
Venue: arXiv cs.SD 2016
Year: 2016

This paper presents a new method of singing voice analysis that performs mutually-dependent singing voice separation and vocal fundamental frequency (F0) estimation. Vocal F0 estimation is considered to become easier if singing voices can be separated from a music audio signal, and vocal F0 contours are useful for singing voice separation. This calls for an approach that improves the performance of each of these tasks by using the results of the other. The proposed method first performs robust principal component analysis (RPCA) for roughly extracting singing voices from a target music audio signal. The F0 contour of the main melody is then estimated from the separated singing voices by finding the optimal temporal path over an F0 saliency spectrogram. Finally, the singing voices are separated again more accurately by combining a conventional time-frequency mask given by RPCA with another mask that passes only the harmonic structures of the estimated F0s. Experimental results showed that the proposed method significantly improved the performances of both singing voice separation and vocal F0 estimation. The proposed method also outperformed all the other methods of singing voice separation submitted to an international music analysis competition called MIREX 2014.
Iterative Packing for Demand and Hypergraph Matching
Venue: arXiv cs.DS 2016
Year: 2016

Iterative rounding has enjoyed tremendous success in elegantly resolving open questions regarding the approximability of problems dominated by covering constraints. Although iterative rounding methods have been applied to packing problems, no single method has emerged that matches the effectiveness and simplicity afforded by the covering case. We offer a simple iterative packing technique that retains features of Jain's seminal approach, including the property that the magnitude of the fractional value of the element rounded during each iteration has a direct impact on the approximation guarantee. We apply iterative packing to generalized matching problems including demand matching and $k$-column-sparse column-restricted packing ($k$-CS-PIP) and obtain approximation algorithms that essentially settle the integrality gap for these problems. We present a simple deterministic $2k$-approximation for $k$-CS-PIP, where an $8k$-approximation was the best deterministic algorithm previously known. The integrality gap in this case is at least $2(k-1+1/k)$. We also give a deterministic $3$-approximation for a generalization of demand matching, settling its natural integrality gap.
AuDroid: Preventing Attacks on Audio Channels in Mobile Devices
Venue: arXiv cs.CR 2016
Year: 2016

Voice control is a popular way to operate mobile devices, enabling users to communicate requests to their devices. However, adversaries can leverage voice control to trick mobile devices into executing commands to leak secrets or to modify critical information. Contemporary mobile operating systems fail to prevent such attacks because they do not control access to the speaker at all and fail to control when untrusted apps may use the microphone, enabling authorized apps to create exploitable communication channels. In this paper, we propose a security mechanism that tracks the creation of audio communication channels explicitly and controls the information flows over these channels to prevent several types of attacks.We design and implement AuDroid, an extension to the SELinux reference monitor integrated into the Android operating system for enforcing lattice security policies over the dynamically changing use of system audio resources. To enhance flexibility, when information flow errors are detected, the device owner, system apps and services are given the opportunity to resolve information flow errors using known methods, enabling AuDroid to run many configurations safely. We evaluate our approach on 17 widely-used apps that make extensive use of the microphone and speaker, finding that AuDroid prevents six types of attack scenarios on audio channels while permitting all 17 apps to run effectively. AuDroid shows that it is possible to prevent attacks using audio channels without compromising functionality or introducing significant performance overhead.
Refactoring Delta-Oriented Product Lines to achieve Monotonicity
Venue: arXiv cs.SE 2016
Year: 2016

Delta-oriented programming (DOP) is a flexible transformational approach to implement software product lines. In delta-oriented product lines, variants are generated by applying operations contained in delta modules to a (possibly empty) base program. These operations can add, remove or modify named elements in a program (e.g., classes, methods and fields in a Java program). This paper presents algorithms for refactoring a delta-oriented product line into monotonic form, i.e., either to contain add and modify operations only (monotonic increasing) or to contain remove and modify operations only (monotonic decreasing). Because of their simpler structure, monotonic delta-oriented product lines are easier to analyze. The algorithms are formalized by means of a core calculus for DOP of product lines of Java programs and their correctness and complexity are given.
Person Re-identification in Appearance Impaired Scenarios
Venue: arXiv cs.CV 2016
Year: 2016

Person re-identification is critical in surveillance applications. Current approaches rely on appearance based features extracted from a single or multiple shots of the target and candidate matches. These approaches are at a disadvantage when trying to distinguish between candidates dressed in similar colors or when targets change their clothing. In this paper we propose a dynamics-based feature to overcome this limitation. The main idea is to capture soft biometrics from gait and motion patterns by gathering dense short trajectories (tracklets) which are Fisher vector encoded. To illustrate the merits of the proposed features we introduce three new "appearance-impaired" datasets. Our experiments on the original and the appearance impaired datasets demonstrate the benefits of incorporating dynamics-based information with appearance-based information to re-identification algorithms.
Stability of Analytic Neural Networks with Event-triggered Synaptic Feedbacks
Venue: arXiv cs.NE 2016
Year: 2016

In this paper, we investigate stability of a class of analytic neural networks with the synaptic feedback via event-triggered rules. This model is general and include Hopfield neural network as a special case. These event-trigger rules can efficiently reduces loads of computation and information transmission at synapses of the neurons. The synaptic feedback of each neuron keeps a constant value based on the outputs of the other neurons at its latest triggering time but changes at its next triggering time, which is determined by certain criterion. It is proved that every trajectory of the analytic neural network converges to certain equilibrium under this event-triggered rule for all initial values except a set of zero measure. The main technique of the proof is the Lojasiewicz inequality to prove the finiteness of trajectory length. The realization of this event-triggered rule is verified by the exclusion of Zeno behaviors. Numerical examples are provided to illustrate the efficiency of the theoretical results.
Centralized and Decentralized Global Outer-synchronization of Asymmetric Recurrent Time-varying Neural Network by Data-sampling
Venue: arXiv cs.NE 2016
Year: 2016

In this paper, we discuss the outer-synchronization of the asymmetrically connected recurrent time-varying neural networks. By both centralized and decentralized discretization data sampling principles, we derive several sufficient conditions based on diverse vector norms that guarantee that any two trajectories from different initial values of the identical neural network system converge together. The lower bounds of the common time intervals between data samples in centralized and decentralized principles are proved to be positive, which guarantees exclusion of Zeno behavior. A numerical example is provided to illustrate the efficiency of the theoretical results.
Overlay Text Extraction From TV News Broadcast
Venue: arXiv cs.CV 2016
Year: 2016

The text data present in overlaid bands convey brief descriptions of news events in broadcast videos. The process of text extraction becomes challenging as overlay text is presented in widely varying formats and often with animation effects. We note that existing edge density based methods are well suited for our application on account of their simplicity and speed of operation. However, these methods are sensitive to thresholds and have high false positive rates. In this paper, we present a contrast enhancement based preprocessing stage for overlay text detection and a parameter free edge density based scheme for efficient text band detection. The second contribution of this paper is a novel approach for multiple text region tracking with a formal identification of all possible detection failure cases. The tracking stage enables us to establish the temporal presence of text bands and their linking over time. The third contribution is the adoption of Tesseract OCR for the specific task of overlay text recognition using web news articles. The proposed approach is tested and found superior on news videos acquired from three Indian English television news channels along with benchmark datasets.
Elzar: Triple Modular Redundancy using Intel Advanced Vector Extensions (technical report)
Venue: arXiv cs.DC 2016
Year: 2016

Instruction-Level Redundancy (ILR) is a well-known approach to tolerate transient CPU faults. It replicates instructions in a program and inserts periodic checks to detect and correct CPU faults using majority voting, which essentially requires three copies of each instruction and leads to high performance overheads. As SIMD technology can operate simultaneously on several copies of the data, it appears to be a good candidate for decreasing these overheads. To verify this hypothesis, we propose Elzar, a compiler framework that transforms unmodified multithreaded applications to support triple modular redundancy using Intel AVX extensions for vectorization. Our experience with several benchmark suites and real-world case-studies yields mixed results: while SIMD may be beneficial for some workloads, e.g., CPU-intensive ones with many floating-point operations, it exhibits higher overhead than ILR in many applications we tested. We study the sources of overheads and discuss possible improvements to Intel AVX that would lead to better performance.