OpenRaiser/Intern-Atlas huggingface dataset:
Biologically inspired alternatives to backpropagation through time for learning in recurrent neural nets
Venue: arXiv cs.NE 2019
Year: 2019

The way how recurrently connected networks of spiking neurons in the brain acquire powerful information processing capabilities through learning has remained a mystery. This lack of understanding is linked to a lack of learning algorithms for recurrent networks of spiking neurons (RSNNs) that are both functionally powerful and can be implemented by known biological mechanisms. Since RSNNs are simultaneously a primary target for implementations of brain-inspired circuits in neuromorphic hardware, this lack of algorithmic insight also hinders technological progress in that area. The gold standard for learning in recurrent neural networks in machine learning is back-propagation through time (BPTT), which implements stochastic gradient descent with regard to a given loss function. But BPTT is unrealistic from a biological perspective, since it requires a transmission of error signals backwards in time and in space, i.e., from post- to presynaptic neurons. We show that an online merging of locally available information during a computation with suitable top-down learning signals in real-time provides highly capable approximations to BPTT. For tasks where information on errors arises only late during a network computation, we enrich locally available information through feedforward eligibility traces of synapses that can easily be computed in an online manner. The resulting new generation of learning algorithms for recurrent neural networks provides a new understanding of network learning in the brain that can be tested experimentally. In addition, these algorithms provide efficient methods for on-chip training of RSNNs in neuromorphic hardware.
A quality model for evaluating and choosing a stream processing framework architecture
Venue: arXiv cs.SE 2019
Year: 2019

Today, we have to deal with many data (Big data) and we need to make decisions by choosing an architectural framework to analyze these data coming from different area. Due to this, it become problematic when we want to process these data, and even more, when it is continuous data. When you want to process some data, you have to first receive it, store it, and then query it. This is what we call Batch Processing. It works well when you process big amount of data, but it finds its limits when you want to get fast (or real-time) processing results, such as financial trades, sensors, user session activity, etc. The solution to this problem is stream processing. Stream processing approach consists of data arriving record by record and rather than storing it, the processing should be done directly. Therefore, direct results are needed with a latency that may vary in real-time. In this paper, we propose an assessment quality model to evaluate and choose stream processing frameworks. We describe briefly different architectural frameworks such as Kafka, Spark Streaming and Flink that address the stream processing. Using our quality model, we present a decision tree to support engineers to choose a framework following the quality aspects. Finally, we evaluate our model doing a case study to Twitter and Netflix streaming.
Visualizing Semantic Structures of Sequential Data by Learning Temporal Dependencies
Venue: arXiv cs.LG 2019
Year: 2019

While conventional methods for sequential learning focus on interaction between consecutive inputs, we suggest a new method which captures composite semantic flows with variable-length dependencies. In addition, the semantic structures within given sequential data can be interpreted by visualizing temporal dependencies learned from the method. The proposed method, called Temporal Dependency Network (TDN), represents a video as a temporal graph whose node represents a frame of the video and whose edge represents the temporal dependency between two frames of a variable distance. The temporal dependency structure of semantic is discovered by learning parameterized kernels of graph convolutional methods. We evaluate the proposed method on the large-scale video dataset, Youtube-8M. By visualizing the temporal dependency structures as experimental results, we show that the suggested method can find the temporal dependency structures of video semantic.
Finding Archetypal Spaces Using Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Archetypal analysis is a data decomposition method that describes each observation in a dataset as a convex combination of "pure types" or archetypes. These archetypes represent extrema of a data space in which there is a trade-off between features, such as in biology where different combinations of traits provide optimal fitness for different environments. Existing methods for archetypal analysis work well when a linear relationship exists between the feature space and the archetypal space. However, such methods are not applicable to systems where the feature space is generated non-linearly from the combination of archetypes, such as in biological systems or image transformations. Here, we propose a reformulation of the problem such that the goal is to learn a non-linear transformation of the data into a latent archetypal space. To solve this problem, we introduce Archetypal Analysis network (AAnet), which is a deep neural network framework for learning and generating from a latent archetypal representation of data. We demonstrate state-of-the-art recovery of ground-truth archetypes in non-linear data domains, show AAnet can generate from data geometry rather than from data density, and use AAnet to identify biologically meaningful archetypes in single-cell gene expression data.
Stopping Active Learning based on Predicted Change of F Measure for Text Classification
Venue: arXiv cs.LG 2019
Year: 2019

During active learning, an effective stopping method allows users to limit the number of annotations, which is cost effective. In this paper, a new stopping method called Predicted Change of F Measure will be introduced that attempts to provide the users an estimate of how much performance of the model is changing at each iteration. This stopping method can be applied with any base learner. This method is useful for reducing the data annotation bottleneck encountered when building text classification systems.
The informal semantics of Answer Set Programming: A Tarskian perspective
Venue: arXiv cs.AI 2019
Year: 2019

In Knowledge Representation, it is crucial that knowledge engineers have a good understanding of the formal expressions that they write. What formal expressions state intuitively about the domain of discourse is studied in the theory of the informal semantics of a logic. In this paper we study the informal semantics of Answer Set Programming. The roots of answer set programming lie in the language of Extended Logic Programming, which was introduced initially as an epistemic logic for default and autoepistemic reasoning. In 1999, the seminal papers on answer set programming proposed to use this logic for a different purpose, namely, to model and solve search problems. Currently, the language is used primarily in this new role. However, the original epistemic intuitions lose their explanatory relevance in this new context. How answer set programs are connected to the specifications of problems they model is more easily explained in a classical Tarskian semantics, in which models correspond to possible worlds, rather than to belief states of an epistemic agent. In this paper, we develop a new theory of the informal semantics of answer set programming, which is formulated in the Tarskian setting and based on Frege's compositionality principle. It differs substantially from the earlier epistemic theory of informal semantics, providing a different view on the meaning of the connectives in answer set programming and on its relation to other logics, in particular classical logic.
Kernel-Guided Training of Implicit Generative Models with Stability Guarantees
Venue: arXiv cs.LG 2019
Year: 2019

Modern implicit generative models such as generative adversarial networks (GANs) are generally known to suffer from issues such as instability, uninterpretability, and difficulty in assessing their performance. If we see these implicit models as dynamical systems, some of these issues are caused by being unable to control their behavior in a meaningful way during the course of training. In this work, we propose a theoretically grounded method to guide the training trajectories of GANs by augmenting the GAN loss function with a kernel-based regularization term that controls local and global discrepancies between the model and true distributions. This control signal allows us to inject prior knowledge into the model. We provide theoretical guarantees on the stability of the resulting dynamical system and demonstrate different aspects of it via a wide range of experiments.
Implicit Dimension Identification in User-Generated Text with LSTM Networks
Venue: arXiv cs.CL 2019
Year: 2019

In the process of online storytelling, individual users create and consume highly diverse content that contains a great deal of implicit beliefs and not plainly expressed narrative. It is hard to manually detect these implicit beliefs, intentions and moral foundations of the writers. We study and investigate two different tasks, each of which reflect the difficulty of detecting an implicit user's knowledge, intent or belief that may be based on writer's moral foundation: 1) political perspective detection in news articles 2) identification of informational vs. conversational questions in community question answering (CQA) archives and. In both tasks we first describe new interesting annotated datasets and make the datasets publicly available. Second, we compare various classification algorithms, and show the differences in their performance on both tasks. Third, in political perspective detection task we utilize a narrative representation language of local press to identify perspective differences between presumably neutral American and British press.
Plantinga-Vegter algorithm takes average polynomial time
Venue: arXiv cs.CG 2019
Year: 2019

We exhibit a condition-based analysis of the adaptive subdivision algorithm due to Plantinga and Vegter. The first complexity analysis of the PV Algorithm is due to Burr, Gao and Tsigaridas who proved a $O\big(2^{τd^{4}\log d}\big)$ worst-case cost bound for degree $d$ plane curves with maximum coefficient bit-size $τ$. This exponential bound, it was observed, is in stark contrast with the good performance of the algorithm in practice. More in line with this performance, we show that, with respect to a broad family of measures, the expected time complexity of the PV Algorithm is bounded by $O(d^7)$ for real, degree $d$, plane curves. We also exhibit a smoothed analysis of the PV Algorithm that yields similar complexity estimates. To obtain these results we combine robust probabilistic techniques coming from geometric functional analysis with condition numbers and the continuous amortization paradigm introduced by Burr, Krahmer and Yap. We hope this will motivate a fruitful exchange of ideas between the different approaches to numerical computation.
Distributed Convolutional Dictionary Learning (DiCoDiLe): Pattern Discovery in Large Images and Signals
Venue: arXiv cs.LG 2019
Year: 2019

Convolutional dictionary learning (CDL) estimates shift invariant basis adapted to multidimensional data. CDL has proven useful for image denoising or inpainting, as well as for pattern discovery on multivariate signals. As estimated patterns can be positioned anywhere in signals or images, optimization techniques face the difficulty of working in extremely high dimensions with millions of pixels or time samples, contrarily to standard patch-based dictionary learning. To address this optimization problem, this work proposes a distributed and asynchronous algorithm, employing locally greedy coordinate descent and an asynchronous locking mechanism that does not require a central server. This algorithm can be used to distribute the computation on a number of workers which scales linearly with the encoded signal's size. Experiments confirm the scaling properties which allows us to learn patterns on large scales images from the Hubble Space Telescope.
Real-time Video Summarization on Commodity Hardware
Venue: arXiv cs.CV 2019
Year: 2019

We present a method for creating video summaries in real-time on commodity hardware. Real-time here refers to the fact that the time required for video summarization is less than the duration of the input video. First, low-level features are use to discard undesirable frames. Next, video is divided into segments, and segment-level features are extracted for each segment. Tree-based models trained on widely available video summarization and computational aesthetics datasets are then used to rank individual segments, and top-ranked segments are selected to generate the final video summary. We evaluate the proposed method on SUMME dataset and show that our method is able to achieve summarization accuracy that is comparable to that of a current state-of-the-art deep learning method, while posting significantly faster run-times. Our method on average is able to generate a video summary in time that is shorter than the duration of the video.
Multi Objective Particle Swarm Optimization based Cooperative Agents with Automated Negotiation
Venue: arXiv cs.NE 2019
Year: 2019

This paper investigates a new hybridization of multi-objective particle swarm optimization (MOPSO) and cooperative agents (MOPSO-CA) to handle the problem of stagnation encounters in MOPSO, which leads solutions to trap in local optima. The proposed approach involves a new distribution strategy based on the idea of having a set of a sub-population, each of which is processed by one agent. The number of the sub-population and agents are adjusted dynamically through the Pareto ranking. This method allocates a dynamic number of sub-population as required to improve diversity in the search space. Additionally, agents are used for better management for the exploitation within a sub-population, and for exploration among sub-populations. Furthermore, we investigate the automated negotiation within agents in order to share the best knowledge. To validate our approach, several benchmarks are performed. The results show that the introduced variant ensures the trade-off between the exploitation and exploration with respect to the comparative algorithms
Energy-Efficient Resource Allocation for Secure UAV Communication Systems
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we study the resource allocation and trajectory design for energy-efficient secure unmanned aerial vehicle (UAV) communication systems where a UAV base station serves multiple legitimate ground users in the existence of a potential eavesdropper. We aim to maximize the energy efficiency of the UAV by jointly optimizing its transmit power, user scheduling, trajectory, and velocity. The design is formulated as a non-convex optimization problem taking into account the maximum tolerable signal-to-noise ratio (SNR) leakage, the minimum data rate requirement of each user, and the location uncertainty of the eavesdropper. An iterative algorithm is proposed to obtain an efficient suboptimal solution. Simulation results demonstrate that the proposed algorithm can achieve a significant improvement of the system energy efficiency while satisfying communication security constraint, compared to some simple scheme adopting straight flight trajectory with a constant speed.
Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
Venue: arXiv cs.LG 2019
Year: 2019

A fundamental question in reinforcement learning is whether model-free algorithms are sample efficient. Recently, Jin et al. \cite{jin2018q} proposed a Q-learning algorithm with UCB exploration policy, and proved it has nearly optimal regret bound for finite-horizon episodic MDP. In this paper, we adapt Q-learning with UCB-exploration bonus to infinite-horizon MDP with discounted rewards \emph{without} accessing a generative model. We show that the \textit{sample complexity of exploration} of our algorithm is bounded by $\tilde{O}({\frac{SA}{ε^2(1-γ)^7}})$. This improves the previously best known result of $\tilde{O}({\frac{SA}{ε^4(1-γ)^8}})$ in this setting achieved by delayed Q-learning \cite{strehl2006pac}, and matches the lower bound in terms of $ε$ as well as $S$ and $A$ except for logarithmic factors.
Robust Dynamic Resource Allocation via Probabilistic Task Pruning in Heterogeneous Computing Systems
Venue: arXiv cs.DC 2019
Year: 2019

In heterogeneous distributed computing (HC) systems, diversity can exist in both computational resources and arriving tasks. In an inconsistently heterogeneous computing system, task types have different execution times on heterogeneous machines. A method is required to map arriving tasks to machines based on machine availability and performance, maximizing the number of tasks meeting deadlines (defined as robustness). For tasks with hard deadlines (eg those in live video streaming), tasks that miss their deadlines are dropped. The problem investigated in this research is maximizing the robustness of an oversubscribed HC system. A way to maximize this robustness is to prune (ie defer or drop) tasks with low probability of meeting their deadlines to increase the probability of other tasks meeting their deadlines. In this paper, we first provide a mathematical model to estimate a task's probability of meeting its deadline in the presence of task dropping. We then investigate methods for engaging probabilistic dropping and we find thresholds for dropping and deferring. Next, we develop a pruning-aware mapping heuristic and extend it to engender fairness across various task types. We show the cost benefit of using probabilistic pruning in an HC system. Simulation results, harnessing a selection of mapping heuristics, show efficacy of the pruning mechanism in improving robustness (on average by 25%) and cost in an oversubscribed HC system by up to 40%.
Asynchronous Early Output Block Carry Lookahead Adder with Improved Quality of Results
Venue: arXiv cs.AR 2019
Year: 2019

A new asynchronous early output block carry lookahead adder (BCLA) incorporating redundant carries is proposed. Compared to the best of existing semi-custom asynchronous carry lookahead adders (CLAs) employing delay-insensitive data encoding and following a 4-phase handshaking, the proposed BCLA with redundant carries achieves 13% reduction in forward latency and 14.8% reduction in cycle time compared to the best of the existing CLAs featuring redundant carries with no area or power penalty. A hybrid variant involving a ripple carry adder (RCA) in the least significant stages i.e. BCLA-RCA is also considered that achieves a further 4% reduction in the forward latency and a 2.4% reduction in the cycle time compared to the proposed BCLA featuring redundant carries without area or power penalties.
Augment your batch: better training with larger batches
Venue: arXiv cs.LG 2019
Year: 2019

Large-batch SGD is important for scaling training of deep neural networks. However, without fine-tuning hyperparameter schedules, the generalization of the model may be hampered. We propose to use batch augmentation: replicating instances of samples within the same batch with different data augmentations. Batch augmentation acts as a regularizer and an accelerator, increasing both generalization and performance scaling. We analyze the effect of batch augmentation on gradient variance and show that it empirically improves convergence for a wide variety of deep neural networks and datasets. Our results show that batch augmentation reduces the number of necessary SGD updates to achieve the same accuracy as the state-of-the-art. Overall, this simple yet effective method enables faster training and better generalization by allowing more computational resources to be used concurrently.
Large Minors in Expanders
Venue: arXiv cs.DS 2019
Year: 2019

In this paper we study expander graphs and their minors. Specifically, we attempt to answer the following question: what is the largest function $f(n,α,d)$, such that every $n$-vertex $α$-expander with maximum vertex degree at most $d$ contains {\bf every} graph $H$ with at most $f(n,α,d)$ edges and vertices as a minor? Our main result is that there is some universal constant $c$, such that $f(n,α,d)\geq \frac{n}{c\log n}\cdot \left(\fracα{d}\right )^c$. This bound achieves a tight dependence on $n$: it is well known that there are bounded-degree $n$-vertex expanders, that do not contain any grid with $Ω(n/\log n)$ vertices and edges as a minor. The best previous result showed that $f(n,α,d) \geq Ω(n/\log^κn)$, where $κ$ depends on both $α$ and $d$. Additionally, we provide a randomized algorithm, that, given an $n$-vertex $α$-expander with maximum vertex degree at most $d$, and another graph $H$ containing at most $\frac{n}{c\log n}\cdot \left(\fracα{d}\right )^c$ vertices and edges, with high probability finds a model of $H$ in $G$, in time poly$(n)\cdot (d/α)^{O\left( \log(d/α) \right)}$. We note that similar but stronger results were independently obtained by Krivelevich and Nenadov: they show that $f(n,α,d)=Ω\left(\frac{nα^2}{d^2\log n} \right)$, and provide an efficient algorithm, that, given an $n$-vertex $α$-expander of maximum vertex degree at most $d$, and a graph $H$ with $O\left( \frac{nα^2}{d^2\log n} \right)$ vertices and edges, finds a model of $H$ in $G$. Finally, we observe that expanders are the `most minor-rich' family of graphs in the following sense: for every $n$-vertex and $m$-edge graph $G$, there exists a graph $H$ with $O \left( \frac{n+m}{\log n} \right)$ vertices and edges, such that $H$ is not a minor of $G$.
An Information-Theoretic Explanation for the Adversarial Fragility of AI Classifiers
Venue: arXiv cs.IT 2019
Year: 2019

We present a simple hypothesis about a compression property of artificial intelligence (AI) classifiers and present theoretical arguments to show that this hypothesis successfully accounts for the observed fragility of AI classifiers to small adversarial perturbations. We also propose a new method for detecting when small input perturbations cause classifier errors, and show theoretical guarantees for the performance of this detection method. We present experimental results with a voice recognition system to demonstrate this method. The ideas in this paper are motivated by a simple analogy between AI classifiers and the standard Shannon model of a communication system.
Subspace arrangements, graph rigidity and derandomization through submodular optimization
Venue: arXiv cs.CC 2019
Year: 2019

This paper presents a deterministic, strongly polynomial time algorithm for computing the matrix rank for a class of symbolic matrices (whose entries are polynomials over a field). This class was introduced, in a different language, by Lovász [Lov] in his study of flats in matroids, and proved a duality theorem putting this problem in $NP \cap coNP$. As such, our result is another demonstration where ``good characterization'' in the sense of Edmonds leads to an efficient algorithm. In a different paper Lovász [Lov79] proved that all such symbolic rank problems have efficient probabilistic algorithms, namely are in $BPP$. As such, our algorithm may be interpreted as a derandomization result, in the long sequence special cases of the PIT (Polynomial Identity Testing) problem. Finally, Lovász and Yemini [LoYe] showed how the same problem generalizes the graph rigidity problem in two dimensions. As such, our algorithm may be seen as a generalization of the well-known deterministic algorithm for the latter problem. There are two somewhat unusual technical features in this paper. The first is the translation of Lovász' flats problem into a symbolic rank one. The second is the use of submodular optimization for derandomization. We hope that the tools developed for both will be useful for related problems, in particular for better understanding of graph rigidity in higher dimensions.