OpenRaiser/Intern-Atlas huggingface dataset:
A Generalized Expression for the Gradient of Mutual Information with the Application in Multiple Access Channels
Venue: arXiv cs.IT 2019
Year: 2019

Taking a functional approach, we derive a general expression for the gradient of the Mutual Information (MI) with respect to the system parameters in the stochastic systems. This expression covers the cases in which the system input depends on the system parameters. As an application, we consider the K-user Multiple Access Channels (MAC) with feedback and utilize the obtained results to explore the behavior of these systems in terms of the MI. Specializing the results to the additive Gaussian noise MAC, we extend the MI and Minimum Mean Square Error (MMSE) relationship, i.e., I-MMSE to the K-user Gaussian MAC with feedback. In this derivation, we show that the gradient of MI can be decomposed into three distinct parts, where the first part is the MMSE term originated from noise, and the second and third parts reflect the effects of the interference and feedback, respectively. Then, considering the capacity achieving Fourier-Modulated Estimate Correction (F-MEC) strategy of Kramer, we show how feedback compensates the destructive effects of the users' interference in the K-user symmetric Gaussian MAC.
Mammalian Value Systems
Venue: arXiv cs.AI 2019
Year: 2019

Characterizing human values is a topic deeply interwoven with the sciences, humanities, art, and many other human endeavors. In recent years, a number of thinkers have argued that accelerating trends in computer science, cognitive science, and related disciplines foreshadow the creation of intelligent machines which meet and ultimately surpass the cognitive abilities of human beings, thereby entangling an understanding of human values with future technological development. Contemporary research accomplishments suggest sophisticated AI systems becoming widespread and responsible for managing many aspects of the modern world, from preemptively planning users' travel schedules and logistics, to fully autonomous vehicles, to domestic robots assisting in daily living. The extrapolation of these trends has been most forcefully described in the context of a hypothetical "intelligence explosion," in which the capabilities of an intelligent software agent would rapidly increase due to the presence of feedback loops unavailable to biological organisms. The possibility of superintelligent agents, or simply the widespread deployment of sophisticated, autonomous AI systems, highlights an important theoretical problem: the need to separate the cognitive and rational capacities of an agent from the fundamental goal structure, or value system, which constrains and guides the agent's actions. The "value alignment problem" is to specify a goal structure for autonomous agents compatible with human values. In this brief article, we suggest that recent ideas from affective neuroscience and related disciplines aimed at characterizing neurological and behavioral universals in the mammalian class provide important conceptual foundations relevant to describing human values. We argue that the notion of "mammalian value systems" points to a potential avenue for fundamental research in AI safety and AI ethics.
Sample Complexity for Non-Truthful Mechanisms
Venue: arXiv cs.GT 2019
Year: 2019

This paper considers the design of non-truthful mechanisms from samples. We identify a parameterized family of mechanisms with strategically simple winner-pays-bid, all-pay, and truthful payment formats. In general (not necessarily downward-closed) single-parameter feasibility environments we prove that the family has low representation and generalization error. Specifically, polynomially many bid samples suffice to identify and run a mechanism that is $ε$-close in Bayes-Nash equilibrium revenue or welfare to that of the optimal truthful mechanism with high probability.
Scalable $M$-Channel Critically Sampled Filter Banks for Graph Signals
Venue: arXiv cs.IT 2019
Year: 2019

We investigate a scalable $M$-channel critically sampled filter bank for graph signals, where each of the $M$ filters is supported on a different subband of the graph Laplacian spectrum. For analysis, the graph signal is filtered on each subband and downsampled on a corresponding set of vertices. However, the classical synthesis filters are replaced with interpolation operators. For small graphs, we use a full eigendecomposition of the graph Laplacian to partition the graph vertices such that the $m^{th}$ set comprises a uniqueness set for signals supported on the $m^{th}$ subband. The resulting transform is critically sampled, the dictionary atoms are orthogonal to those supported on different bands, and graph signals are perfectly reconstructable from their analysis coefficients. We also investigate fast versions of the proposed transform that scale efficiently for large, sparse graphs. Issues that arise in this context include designing the filter bank to be more amenable to polynomial approximation, estimating the number of samples required for each band, performing non-uniform random sampling for the filtered signals on each band, and using efficient reconstruction methods. We empirically explore the joint vertex-frequency localization of the dictionary atoms, the sparsity of the analysis coefficients for different classes of signals, the reconstruction error resulting from the numerical approximations, and the ability of the proposed transform to compress piecewise-smooth graph signals. The proposed filter bank also yields a fast, approximate graph Fourier transform with a coarse resolution in the spectral domain.
Aristotle vs. Ringelmann: On Superlinear Production in Open Source Software
Venue: arXiv cs.SE 2019
Year: 2019

Organizations exist because they provide additional production gains, in comparison to horizontal ways of allocating resources, such as markets, and the open source movement is deemed to be a new kind of peer-production organization somehow in between hierarchically organized firms and markets. However, to strive as a new kind of organization, open source must provide production gains, which in turn should be measurable. The open source movement is particularly interesting to study for this reason. Here, we confront and discuss two contrasting views, which were reported in the literature recently. On the one hand, Sornette et al. uncovered a superlinear production mechanism, which quantifies Aristotle adage: `the whole is more than the sum of its parts'. On the other hand, Scholtes et al. found opposite results, and referred to Maximilien Ringelmann, a French agricultural engineer (1861-1931), who discovered the tendency for individual members of a group to become increasingly less productive as the size of their group increases. Since Ringelmann, the topic of collective intelligence has interested numbers of researchers in social sciences and social psychology, as well as practitioners in management aiming at improving the performance of their team. In most research and practice case studies, the Ringelmann effect has been found to hold, while, in contrast, the superlinear effect found by Sornette et al.is novel and may challenge common wisdom. Here, we compare these two theories, weigh their strengths and weaknesses, and discuss how they have been tested with empirical data. We find that they may not contradict each other as much as was claimed by Scholtes et al.
Causal Inference for Social Discrimination Reasoning
Venue: arXiv cs.CY 2019
Year: 2019

The discovery of discriminatory bias in human or automated decision making is a task of increasing importance and difficulty, exacerbated by the pervasive use of machine learning and data mining. Currently, discrimination discovery largely relies upon correlation analysis of decisions records, disregarding the impact of confounding biases. We present a method for causal discrimination discovery based on propensity score analysis, a statistical tool for filtering out the effect of confounding variables. We introduce causal measures of discrimination which quantify the effect of group membership on the decisions, and highlight causal discrimination/favoritism patterns by learning regression trees over the novel measures. We validate our approach on two real world datasets. Our proposed framework for causal discrimination has the potential to enhance the transparency of machine learning with tools for detecting discriminatory bias both in the training data and in the learning algorithms.
Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm
Venue: arXiv cs.CC 2019
Year: 2019

We introduce a new concept of approximation applicable to decision problems and functions, inspired by Bayesian probability. From the perspective of a Bayesian reasoner with limited computational resources, the answer to a problem that cannot be solved exactly is uncertain and therefore should be described by a random variable. It thus should make sense to talk about the expected value of this random variable, an idea we formalize in the language of average-case complexity theory by introducing the concept of "optimal polynomial-time estimators." We prove some existence theorems and completeness results, and show that optimal polynomial-time estimators exhibit many parallels with "classical" probability theory.
CarbonKit: Designing A Personal Carbon Tracking Platform
Venue: arXiv cs.HC 2019
Year: 2019

Ubiquitous technology platforms have been created to track and improve health and fitness; similar technologies can help individuals monitor and reduce their carbon footprints. This paper proposes CarbonKit, a platform combining technology, markets, and incentives to empower and reward people for reducing their carbon footprint. We argue that a goal-and-reward behavioral feedback loop can be combined with the Big Data available from tracked activities, apps, and social media to make CarbonKit an integral part of individuals daily lives. CarbonKit comprises five modules that link personal carbon tracking, health and fitness, social media, and economic incentives. Protocols for safeguarding security, privacy and individuals control over their own data are essential to the design of the CarbonKit. Initially CarbonKit would operate on a voluntary basis, but such a system can also serve as part of a mandatory region-wide initiative. We use the example of the British Columbia to illustrate the regulatory framework and participating stakeholders that would be required to support the CarbonKit in specific jurisdictions.
MIMO Gaussian Broadcast Channels with Common, Private and Confidential Messages
Venue: arXiv cs.IT 2019
Year: 2019

The two-user multiple-input multiple-output (MIMO) Gaussian broadcast channel (BC) with common, private and confidential messages is considered. The transmitter sends a common message to both users, a confidential message to User 1 and a private (non-confidential) message to User 2. The secrecy-capacity region is characterized by showing that certain inner and outer bounds coincide and that the boundary points are achieved by Gaussian inputs, which enables the development of a tight converse. The proof relies on factorization of upper concave envelopes and a variant of dirty-paper coding (DPC). It is shown that the entire region is exhausted by using DPC to cancel out the signal of the non-confidential message at Receiver 1, thus making DPC against the signal of the confidential message unnecessary. A numerical example illustrates the secrecy-capacity results.
Deep Learning Human Mind for Automated Visual Classification
Venue: arXiv cs.CV 2019
Year: 2019

What if we could effectively read the mind and transfer human visual capabilities to computer vision methods? In this paper, we aim at addressing this question by developing the first visual object classifier driven by human brain signals. In particular, we employ EEG data evoked by visual object stimuli combined with Recurrent Neural Networks (RNN) to learn a discriminative brain activity manifold of visual categories. Afterwards, we train a Convolutional Neural Network (CNN)-based regressor to project images onto the learned manifold, thus effectively allowing machines to employ human brain-based features for automated visual classification. We use a 32-channel EEG to record brain activity of seven subjects while looking at images of 40 ImageNet object classes. The proposed RNN based approach for discriminating object classes using brain signals reaches an average accuracy of about 40%, which outperforms existing methods attempting to learn EEG visual object representations. As for automated object categorization, our human brain-driven approach obtains competitive performance, comparable to those achieved by powerful CNN models, both on ImageNet and CalTech 101, thus demonstrating its classification and generalization capabilities. This gives us a real hope that, indeed, human mind can be read and transferred to machines.
Gradient Descent Learns Linear Dynamical Systems
Venue: arXiv cs.LG 2019
Year: 2019

We prove that stochastic gradient descent efficiently converges to the global optimizer of the maximum likelihood objective of an unknown linear time-invariant dynamical system from a sequence of noisy observations generated by the system. Even though the objective function is non-convex, we provide polynomial running time and sample complexity bounds under strong but natural assumptions. Linear systems identification has been studied for many decades, yet, to the best of our knowledge, these are the first polynomial guarantees for the problem we consider.
The MGB-2 Challenge: Arabic Multi-Dialect Broadcast Media Recognition
Venue: arXiv cs.CL 2019
Year: 2019

This paper describes the Arabic Multi-Genre Broadcast (MGB-2) Challenge for SLT-2016. Unlike last year's English MGB Challenge, which focused on recognition of diverse TV genres, this year, the challenge has an emphasis on handling the diversity in dialect in Arabic speech. Audio data comes from 19 distinct programmes from the Aljazeera Arabic TV channel between March 2005 and December 2015. Programmes are split into three groups: conversations, interviews, and reports. A total of 1,200 hours have been released with lightly supervised transcriptions for the acoustic modelling. For language modelling, we made available over 110M words crawled from Aljazeera Arabic website Aljazeera.net for a 10 year duration 2000-2011. Two lexicons have been provided, one phoneme based and one grapheme based. Finally, two tasks were proposed for this year's challenge: standard speech transcription, and word alignment. This paper describes the task data and evaluation process used in the MGB challenge, and summarises the results obtained.
The Complexity of Flat Freeze LTL
Venue: arXiv cs.FL 2019
Year: 2019

We consider the model-checking problem for freeze LTL on one-counter automata (OCA). Freeze LTL extends LTL with the freeze quantifier, which allows one to store different counter values of a run in registers so that they can be compared with one another. As the model-checking problem is undecidable in general, we focus on the flat fragment of freeze LTL, in which the usage of the freeze quantifier is restricted. In a previous work, Lechner et al. showed that model checking for flat freeze LTL on OCA with binary encoding of counter updates is decidable and in 2NEXPTIME. In this paper, we prove that the problem is, in fact, NEXPTIME-complete no matter whether counter updates are encoded in unary or binary. Like Lechner et al., we rely on a reduction to the reachability problem in OCA with parameterized tests (OCA(P)). The new aspect is that we simulate OCA(P) by alternating two-way automata over words. This implies an exponential upper bound on the parameter values that we exploit towards an NP algorithm for reachability in OCA(P) with unary updates. We obtain our main result as a corollary. As another application, relying on a reduction by Bundala and Ouaknine, one obtains an alternative proof of the known fact that reachability in closed parametric timed automata with one parametric clock is in NEXPTIME.
Random Popular Matchings with Incomplete Preference Lists
Venue: arXiv cs.DM 2019
Year: 2019

Given a set $A$ of $n$ people and a set $B$ of $m \geq n$ items, with each person having a list that ranks his/her preferred items in order of preference, we want to match every person with a unique item. A matching $M$ is called popular if for any other matching $M'$, the number of people who prefer $M$ to $M'$ is not less than the number of those who prefer $M'$ to $M$. For given $n$ and $m$, consider the probability of existence of a popular matching when each person's preference list is independently and uniformly generated at random. Previously, Mahdian showed that when people's preference lists are strict (containing no ties) and complete (containing all items in $B$), if $α= m/n > α_*$, where $α_* \approx 1.42$ is the root of equation $x^2 = e^{1/x}$, then a popular matching exists with probability $1-o(1)$; and if $α< α_*$, then a popular matching exists with probability $o(1)$, i.e. a phase transition occurs at $α_*$. In this paper, we investigate phase transitions in the case that people's preference lists are strict but not complete. We show that in the case where every person has a preference list with length of a constant $k \geq 4$, a similar phase transition occurs at $α_k$, where $α_k \geq 1$ is the root of equation $x e^{-1/2x} = 1-(1-e^{-1/x})^{k-1}$.
Learning by Stimulation Avoidance: A Principle to Control Spiking Neural Networks Dynamics
Venue: arXiv cs.NE 2019
Year: 2019

Learning based on networks of real neurons, and by extension biologically inspired models of neural networks, has yet to find general learning rules leading to widespread applications. In this paper, we argue for the existence of a principle allowing to steer the dynamics of a biologically inspired neural network. Using carefully timed external stimulation, the network can be driven towards a desired dynamical state. We term this principle "Learning by Stimulation Avoidance" (LSA). We demonstrate through simulation that the minimal sufficient conditions leading to LSA in artificial networks are also sufficient to reproduce learning results similar to those obtained in biological neurons by Shahaf and Marom [1]. We examine the mechanism's basic dynamics in a reduced network, and demonstrate how it scales up to a network of 100 neurons. We show that LSA has a higher explanatory power than existing hypotheses about the response of biological neural networks to external simulation, and can be used as a learning rule for an embodied application: learning of wall avoidance by a simulated robot. The surge in popularity of artificial neural networks is mostly directed to disembodied models of neurons with biologically irrelevant dynamics: to the authors' knowledge, this is the first work demonstrating sensory-motor learning with random spiking networks through pure Hebbian learning.
Macroscopic Modeling, Calibration, and Simulation of Managed Lane-Freeway Networks, Part I: Topological and Phenomenological Modeling
Venue: arXiv cs.SY 2019
Year: 2019

To help mitigate road congestion caused by the unrelenting growth of traffic demand, many transit authorities have implemented managed lane policies. Managed lanes typically run parallel to a freeway's standard, general-purpose (GP) lanes, but are restricted to certain types of vehicles. It was originally thought that managed lanes would improve the use of existing infrastructure through incentivization of demand-management behaviors like carpooling, but implementations have often been characterized by unpredicted phenomena that is often to detrimental system performance. This paper presents several macroscopic traffic modeling tools we have used for study of freeways equipped with managed lanes, or "managed lane-freeway networks." The proposed framework is based on the widely-used first-order kinematic wave theory. In this model, the GP and the managed lanes are modeled as parallel links connected by nodes, where certain type of traffic may switch between GP and managed lane links. Two types of managed lane topologies are considered: full-access, where vehicles can switch between the GP and the managed lanes anywhere; and separated, where such switching is allowed only at certain locations called gates. We also describe methods to incorporate in three phenomena into our model that are particular to managed lane-freeway networks. The inertia effect reflects drivers' inclination to stay in their lane as long as possible and switch only if this would obviously improve their travel condition. The friction effect reflects the empirically-observed driver fear of moving fast in a managed lane while traffic in the adjacent GP lanes moves slowly due to congestion. The smoothing effect describes how managed lanes can increase throughput at bottlenecks by reducing lane changes. We present simple models for each of these phenomena that fit within the general macroscopic theory.
Poly-Symmetry in Processor-Sharing Systems
Venue: arXiv cs.PF 2019
Year: 2019

We consider a system of processor-sharing queues with state-dependent service rates. These are allocated according to balanced fairness within a polymatroid capacity set. Balanced fairness is known to be both insensitive and Pareto-efficient in such systems, which ensures that the performance metrics, when computable, will provide robust insights into the real performance of the system considered. We first show that these performance metrics can be evaluated with a complexity that is polynomial in the system size if the system is partitioned into a finite number of parts, so that queues are exchangeable within each part and asymmetric across different parts. This in turn allows us to derive stochastic bounds for a larger class of systems which satisfy less restrictive symmetry assumptions. These results are applied to practical examples of tree data networks, such as backhaul networks of Internet service providers, and computer clusters.
Demand Dispatch with Heterogeneous Intelligent Loads
Venue: arXiv cs.SY 2019
Year: 2019

A distributed control architecture is presented that is intended to make a collection of heterogeneous loads appear to the grid operator as a nearly perfect battery. Local control is based on randomized decision rules advocated in prior research, and extended in this paper to any load with a discrete number of power states. Additional linear filtering at the load ensures that the input-output dynamics of the aggregate has a nearly flat input-output response: the behavior of an ideal, multi-GW battery system.
Stationary time-vertex signal processing
Venue: arXiv cs.LG 2019
Year: 2019

This paper considers regression tasks involving high-dimensional multivariate processes whose structure is dependent on some {known} graph topology. We put forth a new definition of time-vertex wide-sense stationarity, or joint stationarity for short, that goes beyond product graphs. Joint stationarity helps by reducing the estimation variance and recovery complexity. In particular, for any jointly stationary process (a) one reliably learns the covariance structure from as little as a single realization of the process, and (b) solves MMSE recovery problems, such as interpolation and denoising, in computational time nearly linear on the number of edges and timesteps. Experiments with three datasets suggest that joint stationarity can yield accuracy improvements in the recovery of high-dimensional processes evolving over a graph, even when the latter is only approximately known, or the process is not strictly stationary.