OpenRaiser/Intern-Atlas huggingface dataset:
Cross-convolutional-layer Pooling for Image Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Recent studies have shown that a Deep Convolutional Neural Network (DCNN) pretrained on a large image dataset can be used as a universal image descriptor, and that doing so leads to impressive performance for a variety of image classification tasks. Most of these studies adopt activations from a single DCNN layer, usually the fully-connected layer, as the image representation. In this paper, we proposed a novel way to extract image representations from two consecutive convolutional layers: one layer is utilized for local feature extraction and the other serves as guidance to pool the extracted features. By taking different viewpoints of convolutional layers, we further develop two schemes to realize this idea. The first one directly uses convolutional layers from a DCNN. The second one applies the pretrained CNN on densely sampled image regions and treats the fully-connected activations of each image region as convolutional feature activations. We then train another convolutional layer on top of that as the pooling-guidance convolutional layer. By applying our method to three popular visual classification tasks, we find our first scheme tends to perform better on the applications which need strong discrimination on subtle object patterns within small regions while the latter excels in the cases that require discrimination on category-level patterns. Overall, the proposed method achieves superior performance over existing ways of extracting image representations from a DCNN.
Stochastic model for phonemes uncovers an author-dependency of their usage
Venue: arXiv cs.CL 2016
Year: 2016

We study rank-frequency relations for phonemes, the minimal units that still relate to linguistic meaning. We show that these relations can be described by the Dirichlet distribution, a direct analogue of the ideal-gas model in statistical mechanics. This description allows us to demonstrate that the rank-frequency relations for phonemes of a text do depend on its author. The author-dependency effect is not caused by the author's vocabulary (common words used in different texts), and is confirmed by several alternative means. This suggests that it can be directly related to phonemes. These features contrast to rank-frequency relations for words, which are both author and text independent and are governed by the Zipf's law.
Capacity-Achieving Rate-Compatible Polar Codes
Venue: arXiv cs.IT 2016
Year: 2016

We present a method of constructing rate-compatible polar codes that are capacity-achieving with low-complexity sequential decoders. The proposed code construction allows for incremental retransmissions at different rates in order to adapt to channel conditions. The main idea of the construction exploits the common characteristics of polar codes optimized for a sequence of successively degraded channels. The proposed approach allows for an optimized polar code to be used at every transmission thereby achieving capacity.
Synchronization of Pulse-Coupled Oscillators and Clocks under Minimal Connectivity Assumptions
Venue: arXiv cs.SY 2016
Year: 2016

Populations of flashing fireflies, claps of applauding audience, cells of cardiac and circadian pacemakers reach synchrony via event-triggered interactions, referred to as pulse couplings. Synchronization via pulse coupling is widely used in wireless sensor networks, providing clock synchronization with parsimonious packet exchanges. In spite of serious attention paid to networks of pulse coupled oscillators, there is a lack of mathematical results, addressing networks with general communication topologies and general phase-response curves of the oscillators. The most general results of this type (Wang et al., 2012, 2015) establish synchronization of oscillators with a delay-advance phase-response curve over strongly connected networks. In this paper we extend this result by relaxing the connectivity condition to the existence of a root node (or a directed spanning tree) in the graph. This condition is also necessary for synchronization.
FairTest: Discovering Unwarranted Associations in Data-Driven Applications
Venue: arXiv cs.CY 2016
Year: 2016

In a world where traditional notions of privacy are increasingly challenged by the myriad companies that collect and analyze our data, it is important that decision-making entities are held accountable for unfair treatments arising from irresponsible data usage. Unfortunately, a lack of appropriate methodologies and tools means that even identifying unfair or discriminatory effects can be a challenge in practice. We introduce the unwarranted associations (UA) framework, a principled methodology for the discovery of unfair, discriminatory, or offensive user treatment in data-driven applications. The UA framework unifies and rationalizes a number of prior attempts at formalizing algorithmic fairness. It uniquely combines multiple investigative primitives and fairness metrics with broad applicability, granular exploration of unfair treatment in user subgroups, and incorporation of natural notions of utility that may account for observed disparities. We instantiate the UA framework in FairTest, the first comprehensive tool that helps developers check data-driven applications for unfair user treatment. It enables scalable and statistically rigorous investigation of associations between application outcomes (such as prices or premiums) and sensitive user attributes (such as race or gender). Furthermore, FairTest provides debugging capabilities that let programmers rule out potential confounders for observed unfair effects. We report on use of FairTest to investigate and in some cases address disparate impact, offensive labeling, and uneven rates of algorithmic error in four data-driven applications. As examples, our results reveal subtle biases against older populations in the distribution of error in a predictive health application and offensive racial labeling in an image tagger.
A Stochastic Beamformed Amplify-and-Forward Scheme in a Multigroup Multicast MIMO Relay Network with Per-Antenna Power Constraints
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider a two-hop one-way relay network for multigroup multicast transmission between long-distance users, in which the relay is equipped with multiple antennas, while the transmitters and receivers are all with a single antenna. Assuming that perfect channel state information is available, we study amplify-and-forward (AF) schemes that aim at optimizing the max-min-fair (MMF) rate. We begin by considering the classic beamformed AF (BF-AF) scheme, whose corresponding MMF design problem can be formulated as a rank-constrained fractional semidefinite program (SDP). We show that the gap between the BF-AF rate and the SDR rate associated with an optimal SDP solution is sensitive to the number of users as well as the number of power constraints in the relay system. This reveals that the BF-AF scheme may not be well suited for large-scale systems. We therefore propose the stochastic beamformed AF (SBF-AF) schemes, which differ from the BF-AF scheme in that time-varying AF weights are used. We prove that the MMF rates of the proposed SBF-AF schemes are at most $0.8317$ bits/s/Hz less than the SDR rate, irrespective of the number of users or power constraints. Thus, SBF-AF can outperform BF-AF especially in large-scale systems. Finally, we present numerical results to demonstrate the viability of our proposed schemes.
Early Inference in Energy-Based Models Approximates Back-Propagation
Venue: arXiv cs.LG 2016
Year: 2016

We show that Langevin MCMC inference in an energy-based model with latent variables has the property that the early steps of inference, starting from a stationary point, correspond to propagating error gradients into internal layers, similarly to back-propagation. The error that is back-propagated is with respect to visible units that have received an outside driving force pushing them away from the stationary point. Back-propagated error gradients correspond to temporal derivatives of the activation of hidden units. This observation could be an element of a theory for explaining how brains perform credit assignment in deep hierarchies as efficiently as back-propagation does. In this theory, the continuous-valued latent variables correspond to averaged voltage potential (across time, spikes, and possibly neurons in the same minicolumn), and neural computation corresponds to approximate inference and error back-propagation at the same time.
Vector Reachability Problem in $\mathrm{SL}(2,\mathbb{Z})$
Venue: arXiv cs.FL 2016
Year: 2016

The decision problems on matrices were intensively studied for many decades as matrix products play an essential role in the representation of various computational processes. However, many computational problems for matrix semigroups are inherently difficult to solve even for problems in low dimensions and most matrix semigroup problems become undecidable in general starting from dimension three or four. This paper solves two open problems about the decidability of the vector reachability problem over a finitely generated semigroup of matrices from $\mathrm{SL}(2,\mathbb{Z})$ and the point to point reachability (over rational numbers) for fractional linear transformations, where associated matrices are from $\mathrm{SL}(2,\mathbb{Z})$. The approach to solving reachability problems is based on the characterization of reachability paths between points which is followed by the translation of numerical problems on matrices into computational and combinatorial problems on words and formal languages. We also give a geometric interpretation of reachability paths and extend the decidability results to matrix products represented by arbitrary labelled directed graphs. Finally, we will use this technique to prove that a special case of the scalar reachability problem is decidable.
Several types of types in programming languages
Venue: arXiv cs.PL 2016
Year: 2016

Types are an important part of any modern programming language, but we often forget that the concept of type we understand nowadays is not the same it was perceived in the sixties. Moreover, we conflate the concept of "type" in programming languages with the concept of the same name in mathematical logic, an identification that is only the result of the convergence of two different paths, which started apart with different aims. The paper will present several remarks (some historical, some of more conceptual character) on the subject, as a basis for a further investigation. The thesis we will argue is that there are three different characters at play in programming languages, all of them now called types: the technical concept used in language design to guide implementation; the general abstraction mechanism used as a modelling tool; the classifying tool inherited from mathematical logic. We will suggest three possible dates ad quem for their presence in the programming language literature, suggesting that the emergence of the concept of type in computer science is relatively independent from the logical tradition, until the Curry-Howard isomorphism will make an explicit bridge between them.
Enhanced asymmetrically-clipped optical OFDM
Venue: arXiv cs.IT 2016
Year: 2016

Asymmetrically clipped optical orthogonal frequency-division multiplexing (ACO-OFDM) is a technique that sacrifices spectral efficiency in order to transmit an orthogonally frequency-division multiplexed signal over a unipolar channel, such as a directly modulated direct-detection fiber or free-space channel. Several methods have been proposed to regain this spectral efficiency, including: asymmetrically clipped DC-biased optical OFDM (ADO-OFDM), enhanced U-OFDM (EU-OFDM), and spectral and energy efficient OFDM (SEE-OFDM). This paper presents a new method that offers the highest receiver sensitivity for a given optical power at spectral efficiencies above 3 bit/s/Hz, having a 7-dB sensitivity advantage over DC-biased OFDM for 1024-QAM at 87.5% of its spectral efficiency, at the same bit rate and optical power.
User Attitudes Toward the Inspection of Encrypted Traffic
Venue: arXiv cs.CR 2016
Year: 2016

This paper reports the results of a survey of 1,976 individuals regarding their opinions on TLS inspection, a controversial technique that can be used for both benevolent and malicious purposes. Responses indicate that participants hold nuanced opinions on security and privacy trade-offs, with most recognizing legitimate uses for the practice, but also concerned about threats from hackers or government surveillance. There is strong support for notification and consent when a system is intercepting their encrypted traffic, although this support varies depending on the situation. A significant concern about malicious uses of TLS inspection is identity theft, and many would react negatively and some would change their behavior if they discovered inspection occurring without their knowledge. We also find that there are a small but significant number of participants who are jaded by the current state of affairs and have no expectation of privacy.
A simple agent-based spatial model of the economy: tools for policy
Venue: arXiv cs.MA 2016
Year: 2016

This study simulates the evolution of artificial economies in order to understand the tax relevance of administrative boundaries in the quality of life of its citizens. The modeling involves the construction of a computational algorithm, which includes citizens, bounded into families; firms and governments; all of them interacting in markets for goods, labor and real estate. The real estate market allows families to move to dwellings with higher quality or lower price when the families capitalize property values. The goods market allows consumers to search on a flexible number of firms choosing by price and proximity. The labor market entails a matching process between firms (location) and candidates (qualification). The government may be configured into one, four or seven distinct sub-national governments. The role of government is to collect taxes on the value added of firms in its territory and invest the taxes into higher levels of quality of life for residents. The model does not have a credit market. The results suggest that the configuration of administrative boundaries is relevant to the levels of quality of life arising from the reversal of taxes. The model with seven regions is more dynamic, with higher GDP values, but more unequal and heterogeneous across regions. The simulation with only one region is more homogeneously poor. The study seeks to contribute to a theoretical and methodological framework as well as to describe, operationalize and test computer models of public finance analysis, with explicitly spatial and dynamic emphasis. Several alternatives of expansion of the model for future research are described. Moreover, this study adds to the existing literature in the realm of simple microeconomic computational models, specifying structural relationships between local governments and firms, consumers and dwellings mediated by distance.
Partitioned Sampling of Public Opinions Based on Their Social Dynamics
Venue: arXiv cs.SI 2016
Year: 2016

Public opinion polling is usually done by random sampling from the entire population, treating individual opinions as independent. In the real world, individuals' opinions are often correlated, e.g., among friends in a social network. In this paper, we explore the idea of partitioned sampling, which partitions individuals with high opinion similarities into groups and then samples every group separately to obtain an accurate estimate of the population opinion. We rigorously formulate the above idea as an optimization problem. We then show that the simple partitions which contain only one sample in each group are always better, and reduce finding the optimal simple partition to a well-studied Min-r-Partition problem. We adapt an approximation algorithm and a heuristic algorithm to solve the optimization problem. Moreover, to obtain opinion similarity efficiently, we adapt a well-known opinion evolution model to characterize social interactions, and provide an exact computation of opinion similarities based on the model. We use both synthetic and real-world datasets to demonstrate that the partitioned sampling method results in significant improvement in sampling quality and it is robust when some opinion similarities are inaccurate or even missing.
Exploring the Space of Adversarial Images
Venue: arXiv cs.NE 2016
Year: 2016

Adversarial examples have raised questions regarding the robustness and security of deep neural networks. In this work we formalize the problem of adversarial images given a pretrained classifier, showing that even in the linear case the resulting optimization problem is nonconvex. We generate adversarial images using shallow and deep classifiers on the MNIST and ImageNet datasets. We probe the pixel space of adversarial images using noise of varying intensity and distribution. We bring novel visualizations that showcase the phenomenon and its high variability. We show that adversarial images appear in large regions in the pixel space, but that, for the same task, a shallow classifier seems more robust to adversarial images than a deep convolutional network.
Semi-Implicit Time Integration of Atmospheric Flows with Characteristic-Based Flux Partitioning
Venue: arXiv cs.CE 2016
Year: 2016

This paper presents a characteristic-based flux partitioning for the semi-implicit time integration of atmospheric flows. Nonhydrostatic models require the solution of the compressible Euler equations. The acoustic time-scale is significantly faster than the advective scale, yet it is typically not relevant to atmospheric and weather phenomena. The acoustic and advective components of the hyperbolic flux are separated in the characteristic space. High-order, conservative additive Runge-Kutta methods are applied to the partitioned equations so that the acoustic component is integrated in time implicitly with an unconditionally stable method, while the advective component is integrated explicitly. The time step of the overall algorithm is thus determined by the advective scale. Benchmark flow problems are used to demonstrate the accuracy, stability, and convergence of the proposed algorithm. The computational cost of the partitioned semi-implicit approach is compared with that of explicit time integration.
Learning-based Compressive Subsampling
Venue: arXiv cs.IT 2016
Year: 2016

The problem of recovering a structured signal $\mathbf{x} \in \mathbb{C}^p$ from a set of dimensionality-reduced linear measurements $\mathbf{b} = \mathbf {A}\mathbf {x}$ arises in a variety of applications, such as medical imaging, spectroscopy, Fourier optics, and computerized tomography. Due to computational and storage complexity or physical constraints imposed by the problem, the measurement matrix $\mathbf{A} \in \mathbb{C}^{n \times p}$ is often of the form $\mathbf{A} = \mathbf{P}_Ω\boldsymbolΨ$ for some orthonormal basis matrix $\boldsymbolΨ\in \mathbb{C}^{p \times p}$ and subsampling operator $\mathbf{P}_Ω: \mathbb{C}^{p} \rightarrow \mathbb{C}^{n}$ that selects the rows indexed by $Ω$. This raises the fundamental question of how best to choose the index set $Ω$ in order to optimize the recovery performance. Previous approaches to addressing this question rely on non-uniform \emph{random} subsampling using application-specific knowledge of the structure of $\mathbf{x}$. In this paper, we instead take a principled learning-based approach in which a \emph{fixed} index set is chosen based on a set of training signals $\mathbf{x}_1,\dotsc,\mathbf{x}_m$. We formulate combinatorial optimization problems seeking to maximize the energy captured in these signals in an average-case or worst-case sense, and we show that these can be efficiently solved either exactly or approximately via the identification of modularity and submodularity structures. We provide both deterministic and statistical theoretical guarantees showing how the resulting measurement matrices perform on signals differing from the training signals, and we provide numerical examples showing our approach to be effective on a variety of data sets.
An EKF-SLAM algorithm with consistency properties
Venue: arXiv cs.RO 2016
Year: 2016

In this paper we address the inconsistency of the EKF-based SLAM algorithm that stems from non-observability of the origin and orientation of the global reference frame. We prove on the non-linear two-dimensional problem with point landmarks observed that this type of inconsistency is remedied using the Invariant EKF, a recently introduced variant ot the EKF meant to account for the symmetries of the state space. Extensive Monte-Carlo runs illustrate the theoretical results.
Time-Sensitive Bayesian Information Aggregation for Crowdsourcing Systems
Venue: arXiv cs.AI 2016
Year: 2016

Crowdsourcing systems commonly face the problem of aggregating multiple judgments provided by potentially unreliable workers. In addition, several aspects of the design of efficient crowdsourcing processes, such as defining worker's bonuses, fair prices and time limits of the tasks, involve knowledge of the likely duration of the task at hand. Bringing this together, in this work we introduce a new time--sensitive Bayesian aggregation method that simultaneously estimates a task's duration and obtains reliable aggregations of crowdsourced judgments. Our method, called BCCTime, builds on the key insight that the time taken by a worker to perform a task is an important indicator of the likely quality of the produced judgment. To capture this, BCCTime uses latent variables to represent the uncertainty about the workers' completion time, the tasks' duration and the workers' accuracy. To relate the quality of a judgment to the time a worker spends on a task, our model assumes that each task is completed within a latent time window within which all workers with a propensity to genuinely attempt the labelling task (i.e., no spammers) are expected to submit their judgments. In contrast, workers with a lower propensity to valid labeling, such as spammers, bots or lazy labelers, are assumed to perform tasks considerably faster or slower than the time required by normal workers. Specifically, we use efficient message-passing Bayesian inference to learn approximate posterior probabilities of (i) the confusion matrix of each worker, (ii) the propensity to valid labeling of each worker, (iii) the unbiased duration of each task and (iv) the true label of each task. Using two real-world public datasets for entity linking tasks, we show that BCCTime produces up to 11% more accurate classifications and up to 100% more informative estimates of a task's duration compared to state-of-the-art methods.
Evolutionary Trends of Developer Coordination: A Network Approach
Venue: arXiv cs.SE 2016
Year: 2016

Software evolution is a fundamental process that transcends the realm of technical artifacts and permeates the entire organizational structure of a software project. By means of a longitudinal empirical study of 18 large open-source projects, we examine and discuss the evolutionary principles that govern the coordination of developers. By applying a network-analytic approach, we found that the implicit and self-organizing structure of developer coordination is ubiquitously described by non-random organizational principles that defy conventional software-engineering wisdom. In particular, we found that: (a) developers form scale-free networks, in which the majority of coordination requirements arise among an extremely small number of developers, (b) developers tend to accumulate coordination requirements with more and more developers over time, presumably limited by an upper bound, and (c) initially developers are hierarchically arranged, but over time, form a hybrid structure, in which core developers are hierarchically arranged and peripheral developers are not. Our results suggest that the organizational structure of large projects is constrained to evolve towards a state that balances the costs and benefits of developer coordination, and the mechanisms used to achieve this state depend on the project's scale.