OpenRaiser/Intern-Atlas huggingface dataset:
Difference Target Propagation
Venue: arXiv cs.LG 2015
Year: 2015

Back-propagation has been the workhorse of recent successes of deep learning but it relies on infinitesimal effects (partial derivatives) in order to perform credit assignment. This could become a serious issue as one considers deeper and more non-linear functions, e.g., consider the extreme case of nonlinearity where the relation between parameters and cost is actually discrete. Inspired by the biological implausibility of back-propagation, a few approaches have been proposed in the past that could play a similar credit assignment role. In this spirit, we explore a novel approach to credit assignment in deep networks that we call target propagation. The main idea is to compute targets rather than gradients, at each layer. Like gradients, they are propagated backwards. In a way that is related but different from previously proposed proxies for back-propagation which rely on a backwards network with symmetric weights, target propagation relies on auto-encoders at each layer. Unlike back-propagation, it can be applied even when units exchange stochastic bits rather than real numbers. We show that a linear correction for the imperfectness of the auto-encoders, called difference target propagation, is very effective to make target propagation actually work, leading to results comparable to back-propagation for deep networks with discrete and continuous units and denoising auto-encoders and achieving state of the art for stochastic networks.
On the complexity of computing Gröbner bases for weighted homogeneous systems
Venue: arXiv cs.SC 2015
Year: 2015

Solving polynomial systems arising from applications is frequently made easier by the structure of the systems. Weighted homogeneity (or quasi-homogeneity) is one example of such a structure: given a system of weights $W=(w\_{1},\dots,w\_{n})$, $W$-homogeneous polynomials are polynomials which are homogeneous w.r.t the weighted degree $°\_{W}(X\_{1}^{α\_{1}},\dots,X\_{n}^{α\_{n}}) = \sum w\_{i}α\_{i}$. Gröbner bases for weighted homogeneous systems can be computed by adapting existing algorithms for homogeneous systems to the weighted homogeneous case. We show that in this case, the complexity estimate for Algorithm~\F5 $\left(\binom{n+\dmax-1}{\dmax}^ω\right)$ can be divided by a factor $\left(\prod w\_{i} \right)^ω$. For zero-dimensional systems, the complexity of Algorithm~\FGLM $nD^ω$ (where $D$ is the number of solutions of the system) can be divided by the same factor $\left(\prod w\_{i} \right)^ω$. Under genericity assumptions, for zero-dimensional weighted homogeneous systems of $W$-degree $(d\_{1},\dots,d\_{n})$, these complexity estimates are polynomial in the weighted Bézout bound $\prod\_{i=1}^{n}d\_{i} / \prod\_{i=1}^{n}w\_{i}$. Furthermore, the maximum degree reached in a run of Algorithm \F5 is bounded by the weighted Macaulay bound $\sum (d\_{i}-w\_{i}) + w\_{n}$, and this bound is sharp if we can order the weights so that $w\_{n}=1$. For overdetermined semi-regular systems, estimates from the homogeneous case can be adapted to the weighted case. We provide some experimental results based on systems arising from a cryptography problem and from polynomial inversion problems. They show that taking advantage of the weighted homogeneous structure yields substantial speed-ups, and allows us to solve systems which were otherwise out of reach.
Analysis of Joint Transmit-Receive Diversity in Downlink MIMO Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

We study multiple-input multiple-output (MIMO) based downlink heterogeneous cellular network (HetNets) with joint transmit-receive diversity using orthogonal space-time block codes at the base stations (BSs) and maximal-ratio combining (MRC) at the users. MIMO diversity with MRC is especially appealing in cellular networks due to the relatively low hardware complexity at both the BS and user device. Using stochastic geometry, we develop a tractable stochastic model for analyzing such HetNets taking into account the irregular and multi-tier BS deployment. We derive the coverage probability for both interference-blind (IB) and interference-aware (IA) MRC as a function of the relevant tier-specific system parameters such as BS density and power, path loss law, and number of transmit (Tx) antennas. Important insights arising from our analysis for typical HetNets are for instance: (i) IA-MRC becomes less favorable than IB-MRC with Tx diversity due to the smaller interference variance and increased interference correlation across Rx antennas; (ii) ignoring spatial interference correlation significantly overestimates the performance of IA-MRC; (iii) for small number of Rx antennas, selection combining may offer a better complexity-performance trade-off than MRC.
Converting Instance Checking to Subsumption: A Rethink for Object Queries over Practical Ontologies
Venue: arXiv cs.AI 2015
Year: 2015

Efficiently querying Description Logic (DL) ontologies is becoming a vital task in various data-intensive DL applications. Considered as a basic service for answering object queries over DL ontologies, instance checking can be realized by using the most specific concept (MSC) method, which converts instance checking into subsumption problems. This method, however, loses its simplicity and efficiency when applied to large and complex ontologies, as it tends to generate very large MSC's that could lead to intractable reasoning. In this paper, we propose a revision to this MSC method for DL SHI, allowing it to generate much simpler and smaller concepts that are specific-enough to answer a given query. With independence between computed MSC's, scalability for query answering can also be achieved by distributing and parallelizing the computations. An empirical evaluation shows the efficacy of our revised MSC method and the significant efficiency achieved when using it for answering object queries.
Proceedings Scholar Metrics: H Index of proceedings on Computer Science, Electrical & Electronic Engineering, and Communications according to Google Scholar Metrics (2009-2013)
Venue: arXiv cs.DL 2015
Year: 2015

The objective of this report is to present a list of proceedings (conferences, workshops, symposia, meetings) in the areas of Computer Science, Electrical & Electronic Engineering, and Communications covered by Google Scholar Metrics and ranked according to their h-index. Google Scholar Metrics only displays publications that have published at least 100 papers and have received at least one citation in the last five years (2009-2013). The searches were conducted between the 15th and 22nd of December, 2014. A total of 1208 proceedings have been identified
Compressive Deconvolution in Random Mask Imaging
Venue: arXiv cs.IT 2015
Year: 2015

We investigate the problem of reconstructing signals from a subsampled convolution of their modulated versions and a known filter. The problem is studied as applies to specific imaging systems relying on spatial phase modulation by randomly coded "masks." The diversity induced by the random masks is deemed to improve the conditioning of the deconvolution problem while maintaining sampling efficiency. We analyze a linear model of the system, where the joint effect of the spatial modulation, blurring, and spatial subsampling is represented by a measurement matrix. We provide a bound on the conditioning of this measurement matrix in terms of the number of masks, the dimension of the image, and certain characteristics of the blurring kernel and subsampling operator. The derived bound shows that stable deconvolution is possible with high probability even if the total number of (scalar) measurements is within a logarithmic factor of the image size. Furthermore, beyond a critical number of masks determined by the extent of blurring and subsampling, every additional mask improves the conditioning of the measurement matrix. We also consider a more interesting scenario where the target image is sparse. We show that under mild conditions on the blurring kernel, with high probability the measurement matrix is a restricted isometry when the number of masks is within a logarithmic factor of the sparsity of the image. Therefore, the image can be reconstructed using many sparse recovery algorithms such as the basis pursuit. The bound on the required number of masks is linear in sparsity of the image but it is logarithmic in its dimension. The bound provides a quantitative view of the effect of the blurring and subsampling on the required number of masks, which is critical for designing efficient imaging systems.
Conversion of HOL Light proofs into Metamath
Venue: arXiv cs.LO 2015
Year: 2015

We present an algorithm for converting proofs from the OpenTheory interchange format, which can be translated to and from any of the HOL family of proof languages (HOL4, HOL Light, ProofPower, and Isabelle), into the ZFC-based Metamath language. This task is divided into two steps: the translation of an OpenTheory proof into a Metamath HOL formalization, $\mathtt{\text{hol.mm}}$, followed by the embedding of the HOL formalization into the main ZFC foundations of the main Metamath library, $\mathtt{\text{set.mm}}$. This process provides a means to link the simplicity of the Metamath foundations to the intense automation efforts which have borne fruit in HOL Light, allowing the production of complete Metamath proofs of theorems in HOL Light, while also proving that HOL Light is consistent, relative to Metamath's ZFC axiomatization.
Algebraic synchronization criterion and computing reset words
Venue: arXiv cs.FL 2015
Year: 2015

We refine a uniform algebraic approach for deriving upper bounds on reset thresholds of synchronizing automata. We express the condition that an automaton is synchronizing in terms of linear algebra, and obtain upper bounds for the reset thresholds of automata with a short word of a small rank. The results are applied to make several improvements in the area. We improve the best general upper bound for reset thresholds of finite prefix codes (Huffman codes): we show that an $n$-state synchronizing decoder has a reset word of length at most $O(n \log^3 n)$. In addition to that, we prove that the expected reset threshold of a uniformly random synchronizing binary $n$-state decoder is at most $O(n \log n)$. We also show that for any non-unary alphabet there exist decoders whose reset threshold is in $\varTheta(n)$. We prove the Černý conjecture for $n$-state automata with a letter of rank at most $\sqrt[3]{6n-6}$. In another corollary, based on the recent results of Nicaud, we show that the probability that the Černý conjecture does not hold for a random synchronizing binary automaton is exponentially small in terms of the number of states, and also that the expected value of the reset threshold of an $n$-state random synchronizing binary automaton is at most $n^{3/2+o(1)}$. Moreover, reset words of lengths within all of our bounds are computable in polynomial time. We present suitable algorithms for this task for various classes of automata, such as (quasi-)one-cluster and (quasi-)Eulerian automata, for which our results can be applied.
LIVEIA: A Light-based Immersive Visualization Environment for Imaginative Actualization
Venue: arXiv cs.CY 2015
Year: 2015

This paper describes an immersive and interactive visualization environment that uses light as a metaphor for psychological phenomena. Creative life force is portrayed as ambient light, and peoples' psyches are represented by spheres that amplify and transform light. Personality characteristics, situations, and relationships are systematically depicted using a systematic visual language based on the properties of light and how it interacts with physical objects. The technology enables users to visualize and creatively experiment with light-based representations of themselves and others, including patterns of interaction and how they have come about, and how they could change and unfold in the future.
Advanced Interference Management Technique: Potentials and Limitations
Venue: arXiv cs.IT 2015
Year: 2015

Interference management has the potential to improve spectrum efficiency in current and next generation wireless systems (e.g. 3GPP LTE and IEEE 802.11). Recently, new paradigms for interference management have emerged to tackle interference in a general class of wireless networks: interference shaping and interference exploitation. Both approaches offer better performance in interference-limited communication regimes than traditionally thought possible. This article provides a high-level overview of several different interference shaping and exploitation techniques for single-hop, multi-hop, and multi-way network architectures. Graphical illustrations that explain the intuition behind each strategy are provided. The article concludes with a discussion of practical challenges associated with adopting sophisticated interference management strategies in the future.
ModDrop: adaptive multi-modal gesture recognition
Venue: arXiv cs.CV 2015
Year: 2015

We present a method for gesture detection and localisation based on multi-scale and multi-modal deep learning. Each visual modality captures spatial information at a particular spatial scale (such as motion of the upper body or a hand), and the whole system operates at three temporal scales. Key to our technique is a training strategy which exploits: i) careful initialization of individual modalities; and ii) gradual fusion involving random dropping of separate channels (dubbed ModDrop) for learning cross-modality correlations while preserving uniqueness of each modality-specific representation. We present experiments on the ChaLearn 2014 Looking at People Challenge gesture recognition track, in which we placed first out of 17 teams. Fusing multiple modalities at several spatial and temporal scales leads to a significant increase in recognition rates, allowing the model to compensate for errors of the individual classifiers as well as noise in the separate channels. Futhermore, the proposed ModDrop training technique ensures robustness of the classifier to missing signals in one or several channels to produce meaningful predictions from any number of available modalities. In addition, we demonstrate the applicability of the proposed fusion scheme to modalities of arbitrary nature by experiments on the same dataset augmented with audio.
Contact Representations of Sparse Planar Graphs
Venue: arXiv cs.CG 2015
Year: 2015

We study representations of graphs by contacts of circular arcs, CCA-representations for short, where the vertices are interior-disjoint circular arcs in the plane and each edge is realized by an endpoint of one arc touching the interior of another. A graph is (2,k)-sparse if every s-vertex subgraph has at most 2s - k edges, and (2, k)-tight if in addition it has exactly 2n - k edges, where n is the number of vertices. Every graph with a CCA- representation is planar and (2, 0)-sparse, and it follows from known results on contacts of line segments that for k >= 3 every (2, k)-sparse graph has a CCA-representation. Hence the question of CCA-representability is open for (2, k)-sparse graphs with 0 <= k <= 2. We partially answer this question by computing CCA-representations for several subclasses of planar (2,0)-sparse graphs. In particular, we show that every plane (2, 2)-sparse graph has a CCA-representation, and that any plane (2, 1)-tight graph or (2, 0)-tight graph dual to a (2, 3)-tight graph or (2, 4)-tight graph has a CCA-representation. Next, we study CCA-representations in which each arc has an empty convex hull. We characterize the plane graphs that have such a representation, based on the existence of a special orientation of the graph edges. Using this characterization, we show that every plane graph of maximum degree 4 has such a representation, but that finding such a representation for a plane (2, 0)-tight graph with maximum degree 5 is an NP-complete problem. Finally, we describe a simple algorithm for representing plane (2, 0)-sparse graphs with wedges, where each vertex is represented with a sequence of two circular arcs (straight-line segments).
Data-Discriminants of Likelihood Equations
Venue: arXiv cs.SC 2015
Year: 2015

Maximum likelihood estimation (MLE) is a fundamental computational problem in statistics. The problem is to maximize the likelihood function with respect to given data on a statistical model. An algebraic approach to this problem is to solve a very structured parameterized polynomial system called likelihood equations. For general choices of data, the number of complex solutions to the likelihood equations is finite and called the ML-degree of the model. The only solutions to the likelihood equations that are statistically meaningful are the real/positive solutions. However, the number of real/positive solutions is not characterized by the ML-degree. We use discriminants to classify data according to the number of real/positive solutions of the likelihood equations. We call these discriminants data-discriminants (DD). We develop a probabilistic algorithm for computing DDs. Experimental results show that, for the benchmarks we have tried, the probabilistic algorithm is more efficient than the standard elimination algorithm. Based on the computational results, we discuss the real root classification problem for the 3 by 3 symmetric matrix~model.
Static Analysis for Biological Systems (BioAmbients)
Venue: arXiv cs.CE 2015
Year: 2015

In this paper, I present a summary on some works that utilized static analysis techniques for understanding biological systems. Control flow analysis, context dependent analysis, and other techniques were employed to investigate the properties of BioAmbients. In this summary report, I tried to introduce the ideas and explain the techniques used in the subject papers. This summary will highlight the biological concepts of BioAmbients.
A linear-time algorithm for the geodesic center of a simple polygon
Venue: arXiv cs.CG 2015
Year: 2015

Given two points in a simple polygon $P$ of $n$ vertices, its geodesic distance is the length of the shortest path that connects them among all paths that stay within $P$. The geodesic center of $P$ is the unique point in $P$ that minimizes the largest geodesic distance to all other points of $P$. In 1989, Pollack, Sharir and Rote [Disc. \& Comput. Geom. 89] showed an $O(n\log n)$-time algorithm that computes the geodesic center of $P$. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.
Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback
Venue: arXiv cs.DS 2015
Year: 2015

We provide tight upper and lower bounds on the noise resilience of interactive communication over noisy channels with feedback. In this setting, we show that the maximal fraction of noise that any robust protocol can resist is 1/3. Additionally, we provide a simple and efficient robust protocol that succeeds as long as the fraction of noise is at most 1/3 - ε. Surprisingly, both bounds hold regardless of whether the parties send bits or symbols from an arbitrarily large alphabet. We also consider interactive communication over erasure channels. We provide a protocol that matches the optimal tolerable erasure rate of 1/2 - εof previous protocols (Franklin et al., CRYPTO '13) but operates in a much simpler and more efficient way. Our protocol works with an alphabet of size 4, in contrast to prior protocols in which the alphabet size grows as epsilon goes to zero. Building on the above algorithm with a fixed alphabet size, we are able to devise a protocol for binary erasure channels that tolerates erasure rates of up to 1/3 - ε.
"Should I break up with my girlfriend? Will I find another?" Or: An Algorithm for the Forecasting of Romantic Options
Venue: arXiv cs.SI 2015
Year: 2015

The prospect of finding love may be scary but the prospect of committing to a relationship for the rest of your life is almost certainly scary. The secretary problem is a parallel to romantic decision making where an individual decides when to be satisfied with a selection choice in the face of uncertain future options. However, the secretary problem and its variations still do not provide a practical solution in a world where individual preference, goals, and societal context create a highly complex space of values that factor into decision making. In light of these complexities, we offer a general process that can determine the value of romantic options in a highly personal context. This algorithm is currently being developed into a service that will be available in 2015 for the general public.
Unsupervised Feature Learning for Dense Correspondences across Scenes
Venue: arXiv cs.CV 2015
Year: 2015

We propose a fast, accurate matching method for estimating dense pixel correspondences across scenes. It is a challenging problem to estimate dense pixel correspondences between images depicting different scenes or instances of the same object category. While most such matching methods rely on hand-crafted features such as SIFT, we learn features from a large amount of unlabeled image patches using unsupervised learning. Pixel-layer features are obtained by encoding over the dictionary, followed by spatial pooling to obtain patch-layer features. The learned features are then seamlessly embedded into a multi-layer match- ing framework. We experimentally demonstrate that the learned features, together with our matching model, outperforms state-of-the-art methods such as the SIFT flow, coherency sensitive hashing and the recent deformable spatial pyramid matching methods both in terms of accuracy and computation efficiency. Furthermore, we evaluate the performance of a few different dictionary learning and feature encoding methods in the proposed pixel correspondences estimation framework, and analyse the impact of dictionary learning and feature encoding with respect to the final matching performance.
Asynchronous Programming in a Prioritized Form
Venue: arXiv cs.PL 2015
Year: 2015

Asynchronous programming has appeared as a programming style that overcomes undesired properties of concurrent programming. Typically in asynchronous models of programming, methods are posted into a post list for latter execution. The order of method executions is serial, but nondeterministic. This paper presents a new and simple, yet powerful, model for asynchronous programming. The proposed model consists of two components; a context-free grammar and an operational semantics. The model is supported by the ability to express important applications. An advantage of our model over related work is that the model simplifies the way posted methods are assigned priorities. Another advantage is that the operational semantics uses the simple concept of singly linked list to simulate the prioritized process of methods posting and execution. The simplicity and expressiveness make it relatively easy for analysis algorithms to disclose the otherwise un-captured programming bugs in asynchronous programs.