OpenRaiser/Intern-Atlas huggingface dataset:
Limits of End-to-End Learning
Venue: arXiv cs.LG 2017
Year: 2017

End-to-end learning refers to training a possibly complex learning system by applying gradient-based learning to the system as a whole. End-to-end learning system is specifically designed so that all modules are differentiable. In effect, not only a central learning machine, but also all "peripheral" modules like representation learning and memory formation are covered by a holistic learning process. The power of end-to-end learning has been demonstrated on many tasks, like playing a whole array of Atari video games with a single architecture. While pushing for solutions to more challenging tasks, network architectures keep growing more and more complex. In this paper we ask the question whether and to what extent end-to-end learning is a future-proof technique in the sense of scaling to complex and diverse data processing architectures. We point out potential inefficiencies, and we argue in particular that end-to-end learning does not make optimal use of the modular design of present neural networks. Our surprisingly simple experiments demonstrate these inefficiencies, up to the complete breakdown of learning.
A Distributed Shared Memory Model and C++ Templated Meta-Programming Interface for the Epiphany RISC Array Processor
Venue: arXiv cs.DC 2017
Year: 2017

The Adapteva Epiphany many-core architecture comprises a scalable 2D mesh Network-on-Chip (NoC) of low-power RISC cores with minimal uncore functionality. Whereas such a processor offers high computational energy efficiency and parallel scalability, developing effective programming models that address the unique architecture features has presented many challenges. We present here a distributed shared memory (DSM) model supported in software transparently using C++ templated metaprogramming techniques. The approach offers an extremely simple parallel programming model well suited for the architecture. Initial results are presented that demonstrate the approach and provide insight into the efficiency of the programming model and also the ability of the NoC to support a DSM without explicit control over data movement and localization.
Duluth at Semeval-2017 Task 7 : Puns upon a midnight dreary, Lexical Semantics for the weak and weary
Venue: arXiv cs.CL 2017
Year: 2017

This paper describes the Duluth systems that participated in SemEval-2017 Task 7 : Detection and Interpretation of English Puns. The Duluth systems participated in all three subtasks, and relied on methods that included word sense disambiguation and measures of semantic relatedness.
Tweeting AI: Perceptions of AI-Tweeters (AIT) vs Expert AI-Tweeters (EAIT)
Venue: arXiv cs.AI 2017
Year: 2017

With the recent advancements in Artificial Intelligence (AI), various organizations and individuals started debating about the progress of AI as a blessing or a curse for the future of the society. This paper conducts an investigation on how the public perceives the progress of AI by utilizing the data shared on Twitter. Specifically, this paper performs a comparative analysis on the understanding of users from two categories -- general AI-Tweeters (AIT) and the expert AI-Tweeters (EAIT) who share posts about AI on Twitter. Our analysis revealed that users from both the categories express distinct emotions and interests towards AI. Users from both the categories regard AI as positive and are optimistic about the progress of AI but the experts are more negative than the general AI-Tweeters. Characterization of users manifested that `London' is the popular location of users from where they tweet about AI. Tweets posted by AIT are highly retweeted than posts made by EAIT that reveals greater diffusion of information from AIT.
Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory
Venue: arXiv cs.DS 2017
Year: 2017

For a positive parameter $β$, the $β$-bounded distance between a pair of vertices $u,v$ in a weighted undirected graph $G = (V,E,ω)$ is the length of the shortest $u-v$ path in $G$ with at most $β$ edges, aka {\em hops}. For $β$ as above and $ε>0$, a {\em $(β,ε)$-hopset} of $G = (V,E,ω)$ is a graph $G' =(V,H,ω_H)$ on the same vertex set, such that all distances in $G$ are $(1+ε)$-approximated by $β$-bounded distances in $G\cup G'$. Hopsets are a fundamental graph-theoretic and graph-algorithmic construct, and they are widely used for distance-related problems in a variety of computational settings. Currently existing constructions of hopsets produce hopsets either with $Ω(n \log n)$ edges, or with a hopbound $n^{Ω(1)}$. In this paper we devise a construction of {\em linear-size} hopsets with hopbound $(\log n)^{\log^{(3)}n+O(1)}$. This improves the previous bound almost exponentially. We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm \cite{EN16} for computing hopsets with a constant (i.e., independent of $n$) hopbound requires $n^{Ω(1)}$ time. We devise a PRAM algorithm with polylogarithmic running time for computing hopsets with a constant hopbound, i.e., our running time is exponentially better than the previous one. Moreover, these hopsets are also significantly sparser than their counterparts from \cite{EN16}. We use our hopsets to devise a distributed routing scheme that exhibits near-optimal tradeoff between individual memory requirement $\tilde{O}(n^{1/k})$ of vertices throughout preprocessing and routing phases of the algorithm, and stretch $O(k)$, along with a near-optimal construction time $\approx D + n^{1/2 + 1/k}$, where $D$ is the hop-diameter of the input graph.
An Efficient Reconfigurable FIR Digital Filter Using Modified Distribute Arithmetic Technique
Venue: arXiv cs.AR 2017
Year: 2017

This paper provides modified Distributed Arithmetic based technique to compute sum of products saving appreciable number of Multiply And accumulation blocks and this consecutively reduces circuit size. In this technique multiplexer based structure is used to reuse the blocks so as to reduce the required memory locations. In this technique a Carry Look Ahead based adder tree is used to have better area-delay product. Designing of FIR filter is done using VHDL and synthesized using Xilinx 12.2 synthesis tool and ISIM simulator. The power analysis is done using Xilinx Xpower analyzer. The proposed structure requires nearly 42% less cells, 40% less LUT flip-flop pairs used, and also 2% less power compared with existing structure.
TFDASH: A Fairness, Stability, and Efficiency Aware Rate Control Approach for Multiple Clients over DASH
Venue: arXiv cs.MM 2017
Year: 2017

Dynamic adaptive streaming over HTTP (DASH) has recently been widely deployed in the Internet and adopted in the industry. It, however, does not impose any adaptation logic for selecting the quality of video fragments requested by clients and suffers from lackluster performance with respect to a number of desirable properties: efficiency, stability, and fairness when multiple players compete for a bottleneck link. In this paper, we propose a throughput-friendly DASH (TFDASH) rate control scheme for video streaming with multiple clients over DASH to well balance the trade-offs among efficiency, stability, and fairness. The core idea behind guaranteeing fairness and high efficiency (bandwidth utilization) is to avoid OFF periods during the downloading process for all clients, i.e., the bandwidth is in perfect-subscription or over-subscription with bandwidth utilization approach to 100\%. We also propose a dual-threshold buffer model to solve the instability problem caused by the above idea. As a result, by integrating these novel components, we also propose a probability-driven rate adaption logic taking into account several key factors that most influence visual quality, including buffer occupancy, video playback quality, video bit-rate switching frequency and amplitude, to guarantee high-quality video streaming. Our experiments evidently demonstrate the superior performance of the proposed method.
A Reduced Semantics for Deciding Trace Equivalence
Venue: arXiv cs.LO 2017
Year: 2017

Many privacy-type properties of security protocols can be modelled using trace equivalence properties in suitable process algebras. It has been shown that such properties can be decided for interesting classes of finite processes (i.e., without replication) by means of symbolic execution and constraint solving. However, this does not suffice to obtain practical tools. Current prototypes suffer from a classical combinatorial explosion problem caused by the exploration of many interleavings in the behaviour of processes. Mödersheim et al. have tackled this problem for reachability properties using partial order reduction techniques. We revisit their work, generalize it and adapt it for equivalence checking. We obtain an optimisation in the form of a reduced symbolic semantics that eliminates redundant interleavings on the fly. The obtained partial order reduction technique has been integrated in a tool called APTE. We conducted complete benchmarks showing dramatic improvements.
Privacy Assessment of De-identified Opal Data: A report for Transport for NSW
Venue: arXiv cs.CR 2017
Year: 2017

We consider the privacy implications of public release of a de-identified dataset of Opal card transactions. The data was recently published at https://opendata.transport.nsw.gov.au/dataset/opal-tap-on-and-tap-off. It consists of tap-on and tap-off counts for NSW's four modes of public transport, collected over two separate week-long periods. The data has been further treated to improve privacy by removing small counts, aggregating some stops and routes, and perturbing the counts. This is a summary of our findings.
Practical and Effective Re-Pair Compression
Venue: arXiv cs.DS 2017
Year: 2017

Re-Pair is an efficient grammar compressor that operates by recursively replacing high-frequency character pairs with new grammar symbols. The most space-efficient linear-time algorithm computing Re-Pair uses $(1+ε)n+\sqrt n$ words on top of the re-writable text (of length $n$ and stored in $n$ words), for any constant $ε>0$; in practice however, this solution uses complex sub-procedures preventing it from being practical. In this paper, we present an implementation of the above-mentioned result making use of more practical solutions; our tool further improves the working space to $(1.5+ε)n$ words (text included), for some small constant $ε$. As a second contribution, we focus on compact representations of the output grammar. The lower bound for storing a grammar with $d$ rules is $\log(d!)+2d\approx d\log d+0.557 d$ bits, and the most efficient encoding algorithm in the literature uses at most $d\log d + 2d$ bits and runs in $\mathcal O(d^{1.5})$ time. We describe a linear-time heuristic maximizing the compressibility of the output Re-Pair grammar. On real datasets, our grammar encoding uses---on average---only $2.8\%$ more bits than the information-theoretic minimum. In half of the tested cases, our compressor improves the output size of 7-Zip with maximum compression rate turned on.
Frequency-domain Compressive Channel Estimation for Frequency-Selective Hybrid mmWave MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

Channel estimation is useful in millimeter wave (mmWave) MIMO communication systems. Channel state information allows optimized designs of precoders and combiners under different metrics such as mutual information or signal-to-interference-noise (SINR) ratio. At mmWave, MIMO precoders and combiners are usually hybrid, since this architecture provides a means to trade-off power consumption and achievable rate. Channel estimation is challenging when using these architectures, however, since there is no direct access to the outputs of the different antenna elements in the array. The MIMO channel can only be observed through the analog combining network, which acts as a compression stage of the received signal. Most of prior work on channel estimation for hybrid architectures assumes a frequency-flat mmWave channel model. In this paper, we consider a frequency-selective mmWave channel and propose compressed-sensing-based strategies to estimate the channel in the frequency domain. We evaluate different algorithms and compute their complexity to expose trade-offs in complexity-overhead-performance as compared to those of previous approaches.
Faster Betweenness Centrality Updates in Evolving Networks
Venue: arXiv cs.DS 2017
Year: 2017

Finding central nodes is a fundamental problem in network analysis. Betweenness centrality is a well-known measure which quantifies the importance of a node based on the fraction of shortest paths going though it. Due to the dynamic nature of many today's networks, algorithms that quickly update centrality scores have become a necessity. For betweenness, several dynamic algorithms have been proposed over the years, targeting different update types (incremental- and decremental-only, fully-dynamic). In this paper we introduce a new dynamic algorithm for updating betweenness centrality after an edge insertion or an edge weight decrease. Our method is a combination of two independent contributions: a faster algorithm for updating pairwise distances as well as number of shortest paths, and a faster algorithm for updating dependencies. Whereas the worst-case running time of our algorithm is the same as recomputation, our techniques considerably reduce the number of operations performed by existing dynamic betweenness algorithms.
Non-Uniform Attacks Against Pseudoentropy
Venue: arXiv cs.CR 2017
Year: 2017

De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over $n$-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping $n-1$ to $n$ bit strings), can be distinguished from the uniform distribution with advantage $ε$ by a circuit of size $O( 2^nε^2)$. We generalize this result, showing that a distribution which has less than $k$ bits of min-entropy, can be distinguished from any distribution with $k$ bits of $δ$-smooth min-entropy with advantage $ε$ by a circuit of size $O(2^kε^2/δ^2)$. As a special case, this implies that any distribution with support at most $2^k$ (e.g., the output of a pseudoentropy generator mapping $k$ to $n$ bit strings) can be distinguished from any given distribution with min-entropy $k+1$ with advantage $ε$ by a circuit of size $O(2^kε^2)$. Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions.
Bifurcation Mechanism Design -- From Optimal Flat Taxes to Improved Cancer Treatments
Venue: arXiv cs.GT 2017
Year: 2017

Small changes to the parameters of a system can lead to abrupt qualitative changes of its behavior, a phenomenon known as bifurcation. Such instabilities are typically considered problematic, however, we show that their power can be leveraged to design novel types of mechanisms. Hysteresis mechanisms use transient changes of system parameters to induce a permanent improvement to its performance via optimal equilibrium selection. Optimal control mechanisms induce convergence to states whose performance is better than even the best equilibrium. We apply these mechanisms in two different settings that illustrate the versatility of bifurcation mechanism design. In the first one we explore how introducing flat taxation can improve social welfare, despite decreasing agent "rationality", by destabilizing inefficient equilibria. From there we move on to consider a well known game of tumor metabolism and use our approach to derive novel cancer treatment strategies.
Strong Coordination over Noisy Channels: Is Separation Sufficient?
Venue: arXiv cs.IT 2017
Year: 2017

We study the problem of strong coordination of actions of two agents $X$ and $Y$ that communicate over a noisy communication channel such that the actions follow a given joint probability distribution. We propose two novel schemes for this noisy strong coordination problem, and derive inner bounds for the underlying strong coordination capacity region. The first scheme is a joint coordination-channel coding scheme that utilizes the randomness provided by the communication channel to reduce the local randomness required in generating the action sequence at agent $Y$. The second scheme exploits separate coordination and channel coding where local randomness is extracted from the channel after decoding. Finally, we present an example in which the joint scheme is able to outperform the separate scheme in terms of coordination rate.
A new image compression by gradient Haar wavelet
Venue: arXiv cs.CV 2017
Year: 2017

With the development of human communications the usage of Visual Communications has also increased. The advancement of image compression methods is one of the main reasons for the enhancement. This paper first presents main modes of image compression methods such as JPEG and JPEG2000 without mathematical details. Also, the paper describes gradient Haar wavelet transforms in order to construct a preliminary image compression algorithm. Then, a new image compression method is proposed based on the preliminary image compression algorithm that can improve standards of image compression. The new method is compared with original modes of JPEG and JPEG2000 (based on Haar wavelet) by image quality measures such as MAE, PSNAR, and SSIM. The image quality and statistical results confirm that can boost image compression standards. It is suggested that the new method is used in a part or all of an image compression standard.
Outline Colorization through Tandem Adversarial Networks
Venue: arXiv cs.CV 2017
Year: 2017

When creating digital art, coloring and shading are often time consuming tasks that follow the same general patterns. A solution to automatically colorize raw line art would have many practical applications. We propose a setup utilizing two networks in tandem: a color prediction network based only on outlines, and a shading network conditioned on both outlines and a color scheme. We present processing methods to limit information passed in the color scheme, improving generalization. Finally, we demonstrate natural-looking results when colorizing outlines from scratch, as well as from a messy, user-defined color scheme.
Deterministic Gathering with Crash Faults
Venue: arXiv cs.DC 2017
Year: 2017

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node and terminate. This problem is known as {\em gathering}. We study deterministic gathering algorithms under the assumption that agents are subject to {\em crash faults} which can occur at any time. Two fault scenarios are considered. A {\em motion fault} immobilizes the agent at a node or inside an edge but leaves intact its memory at the time when the fault occurred. A more severe {\em total fault} immobilizes the agent as well, but also erases its entire memory. Of course, we cannot require faulty agents to gather. Thus the gathering problem for fault prone agents calls for all fault-free agents to gather at a single node, and terminate. When agents move completely asynchronously, gathering with crash faults of any type is impossible. Hence we consider a restricted version of asynchrony, where each agent is assigned by the adversary a fixed speed, possibly different for each agent. Agents have clocks ticking at the same rate. Each agent can wait for a time of its choice at any node, or decide to traverse an edge but then it moves at constant speed assigned to it. Moreover, agents have different labels. Each agent knows its label and speed but not those of other agents. We construct a gathering algorithm working for any team of at least two agents in the scenario of motion faults, and a gathering algorithm working in the presence of total faults, provided that at least two agents are fault free all the time. If only one agent is fault free, the task of gathering with total faults is sometimes impossible. Both our algorithms work in time polynomial in the size of the graph, in the logarithm of the largest label, in the inverse of the smallest speed, and in the ratio between the largest and the smallest speed.
Improving Small Object Proposals for Company Logo Detection
Venue: arXiv cs.CV 2017
Year: 2017

Many modern approaches for object detection are two-staged pipelines. The first stage identifies regions of interest which are then classified in the second stage. Faster R-CNN is such an approach for object detection which combines both stages into a single pipeline. In this paper we apply Faster R-CNN to the task of company logo detection. Motivated by its weak performance on small object instances, we examine in detail both the proposal and the classification stage with respect to a wide range of object sizes. We investigate the influence of feature map resolution on the performance of those stages. Based on theoretical considerations, we introduce an improved scheme for generating anchor proposals and propose a modification to Faster R-CNN which leverages higher-resolution feature maps for small objects. We evaluate our approach on the FlickrLogos dataset improving the RPN performance from 0.52 to 0.71 (MABO) and the detection performance from 0.52 to 0.67 (mAP).
Traffic Light Control Using Deep Policy-Gradient and Value-Function Based Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

Recent advances in combining deep neural network architectures with reinforcement learning techniques have shown promising potential results in solving complex control problems with high dimensional state and action spaces. Inspired by these successes, in this paper, we build two kinds of reinforcement learning algorithms: deep policy-gradient and value-function based agents which can predict the best possible traffic signal for a traffic intersection. At each time step, these adaptive traffic light control agents receive a snapshot of the current state of a graphical traffic simulator and produce control signals. The policy-gradient based agent maps its observation directly to the control signal, however the value-function based agent first estimates values for all legal control signals. The agent then selects the optimal control action with the highest value. Our methods show promising results in a traffic network simulated in the SUMO traffic simulator, without suffering from instability issues during the training process.
A Framework for Rate Efficient Control of Distributed Discrete Systems
Venue: arXiv cs.IT 2017
Year: 2017

A key issue in the control of distributed discrete systems modeled as Markov decisions processes, is that often the state of the system is not directly observable at any single location in the system. The participants in the control scheme must share information with one another regarding the state of the system in order to collectively make informed control decisions, but this information sharing can be costly. Harnessing recent results from information theory regarding distributed function computation, in this paper we derive, for several information sharing model structures, the minimum amount of control information that must be exchanged to enable local participants to derive the same control decisions as an imaginary omniscient controller having full knowledge of the global state. Incorporating consideration for this amount of information that must be exchanged into the reward enables one to trade the competing objectives of minimizing this control information exchange and maximizing the performance of the controller. An alternating optimization framework is then provided to help find the efficient controllers and messaging schemes. A series of running examples from wireless resource allocation illustrate the ideas and design tradeoffs.