OpenRaiser/Intern-Atlas huggingface dataset:
Peacock: Probe-Based Scheduling of Jobs by Rotating Between Elastic Queues
Venue: arXiv cs.DC 2018
Year: 2018

In this paper, we propose Peacock, a new distributed probe-based scheduler which handles heterogeneous workloads in data analytics frameworks with low latency. Peacock mitigates the \emph{Head-of-Line blocking} problem, i.e., shorter tasks are enqueued behind the longer tasks, better than the state-of-the-art. To this end, we introduce a novel probe rotation technique. Workers form a ring overlay network and rotate probes using elastic queues. It is augmented by a novel probe reordering algorithm executed in workers. We evaluate the performance of Peacock against two state-of-the-art probe-based solutions through both trace-driven simulation and distributed experiment in Spark under various loads and cluster sizes. Our large-scale performance results indicate that Peacock outperforms the state-of-the-art in all cluster sizes and loads. Our distributed experiments confirm our simulation results.
The role of game jams in developing informal learning of computational thinking: a cross-european case study
Venue: arXiv cs.CY 2018
Year: 2018

This paper will present a cross-European experience of game jams as part of a Horizon 2020 funded project: No-one Left Behind (NOLB). The NOLB project was created to unlock inclusive gaming creation and experiences in formal learning situations from primary to secondary level, particularly for children at risk of social exclusion. The project has engendered the concept of game jams, events organised with the aim of designing and creating small games in a short time-frame around a central theme. Game jams can support engagement with informal learning beyond schools across a range of disciplines, resulting in an exciting experience associated with strong, positive emotions which can significantly support learning goals. This paper will disseminate experience of two cross-European game jams; the first a pilot and the second having over 95 submissions from countries across Europe, America, Canada, Egypt, the Philippians and India. Data collected through these games jams supports that coding, designing, reflection, analysing, creating, debugging, persevering and application, as well as developing computational thinking concepts such as decomposition, using patterns, abstraction and evaluation. The notion of game jams provides a paradigm for creating both formal and informal learning experiences such as directed learning experience, problem-solving, hands-on projects, working collaboratively, and creative invention, within a learner-centred learning environment where children are creators of their own knowledge and learning material.
Laconic Deep Learning Computing
Venue: arXiv cs.NE 2018
Year: 2018

We motivate a method for transparently identifying ineffectual computations in unmodified Deep Learning models and without affecting accuracy. Specifically, we show that if we decompose multiplications down to the bit level the amount of work performed during inference for image classification models can be consistently reduced by two orders of magnitude. In the best case studied of a sparse variant of AlexNet, this approach can ideally reduce computation work by more than 500x. We present Laconic a hardware accelerator that implements this approach to improve execution time, and energy efficiency for inference with Deep Learning Networks. Laconic judiciously gives up some of the work reduction potential to yield a low-cost, simple, and energy efficient design that outperforms other state-of-the-art accelerators. For example, a Laconic configuration that uses a weight memory interface with just 128 wires outperforms a conventional accelerator with a 2K-wire weight memory interface by 2.3x on average while being 2.13x more energy efficient on average. A Laconic configuration that uses a 1K-wire weight memory interface, outperforms the 2K-wire conventional accelerator by 15.4x and is 1.95x more energy efficient. Laconic does not require but rewards advances in model design such as a reduction in precision, the use of alternate numeric representations that reduce the number of bits that are "1", or an increase in weight or activation sparsity.
NRC-Canada at SMM4H Shared Task: Classifying Tweets Mentioning Adverse Drug Reactions and Medication Intake
Venue: arXiv cs.CL 2018
Year: 2018

Our team, NRC-Canada, participated in two shared tasks at the AMIA-2017 Workshop on Social Media Mining for Health Applications (SMM4H): Task 1 - classification of tweets mentioning adverse drug reactions, and Task 2 - classification of tweets describing personal medication intake. For both tasks, we trained Support Vector Machine classifiers using a variety of surface-form, sentiment, and domain-specific features. With nine teams participating in each task, our submissions ranked first on Task 1 and third on Task 2. Handling considerable class imbalance proved crucial for Task 1. We applied an under-sampling technique to reduce class imbalance (from about 1:10 to 1:2). Standard n-gram features, n-grams generalized over domain terms, as well as general-domain and domain-specific word embeddings had a substantial impact on the overall performance in both tasks. On the other hand, including sentiment lexicon features did not result in any improvement.
Quantifying Users' Beliefs about Software Updates
Venue: arXiv cs.CR 2018
Year: 2018

Software updates are critical to the performance, compatibility, and security of software systems. However, users do not always install updates, leaving their machines vulnerable to attackers' exploits. While recent studies have highlighted numerous reasons why users ignore updates, little is known about how prevalent each of these beliefs is. Gaining a better understanding of the prevalence of each belief may help software designers better target their efforts in understanding what specific user concerns to address when developing and deploying software updates. In our study, we performed a survey to quantify the prevalence of users' reasons for not updating uncovered by previous studies. We used this data to derive three factors underlying these beliefs: update costs, update necessity, and update risks. Based on our results, we provide recommendations for how software developers can better improve users' software updating experiences, thereby increasing compliance and, with it, security.
π: Towards a Simple Formal Semantic Framework for Compiler Construction
Venue: arXiv cs.PL 2018
Year: 2018

This paper proposes π, a formal semantic framework for compiler construction together with program validation. π is comprised by π Lib, a set of programming languages constructs inspired by Peter Mosses' Component-Based Semantics and π Automata, an automata-based formalism to describe the operational semantics of programming languages, that generalizes Gordon Plotkin's Interpreting Automata.
Exploring object-centric and scene-centric CNN features and their complementarity for human rights violations recognition in images
Venue: arXiv cs.CV 2018
Year: 2018

Identifying potential abuses of human rights through imagery is a novel and challenging task in the field of computer vision, that will enable to expose human rights violations over large-scale data that may otherwise be impossible. While standard databases for object and scene categorisation contain hundreds of different classes, the largest available dataset of human rights violations contains only 4 classes. Here, we introduce the `Human Rights Archive Database' (HRA), a verified-by-experts repository of 3050 human rights violations photographs, labelled with human rights semantic categories, comprising a list of the types of human rights abuses encountered at present. With the HRA dataset and a two-phase transfer learning scheme, we fine-tuned the state-of-the-art deep convolutional neural networks (CNNs) to provide human rights violations classification CNNs (HRA-CNNs). We also present extensive experiments refined to evaluate how well object-centric and scene-centric CNN features can be combined for the task of recognising human rights abuses. With this, we show that HRA database poses a challenge at a higher level for the well studied representation learning methods, and provide a benchmark in the task of human rights violations recognition in visual context. We expect this dataset can help to open up new horizons on creating systems able of recognising rich information about human rights violations. Our dataset, codes and trained models are available online at https://github.com/GKalliatakis/Human-Rights-Archive-CNNs.
Offline EEG-Based Driver Drowsiness Estimation Using Enhanced Batch-Mode Active Learning (EBMAL) for Regression
Venue: arXiv cs.LG 2018
Year: 2018

There are many important regression problems in real-world brain-computer interface (BCI) applications, e.g., driver drowsiness estimation from EEG signals. This paper considers offline analysis: given a pool of unlabeled EEG epochs recorded during driving, how do we optimally select a small number of them to label so that an accurate regression model can be built from them to label the rest? Active learning is a promising solution to this problem, but interestingly, to our best knowledge, it has not been used for regression problems in BCI so far. This paper proposes a novel enhanced batch-mode active learning (EBMAL) approach for regression, which improves upon a baseline active learning algorithm by increasing the reliability, representativeness and diversity of the selected samples to achieve better regression performance. We validate its effectiveness using driver drowsiness estimation from EEG signals. However, EBMAL is a general approach that can also be applied to many other offline regression problems beyond BCI.
On the Optimality of Treating Interference as Noise for Interfering Multiple Access Channels
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we look at the problem of treating interference as noise (TIN) in the Gaussian interfering multiple access channel (IMAC). The considered network comprises $K$ mutually interfering multiple access channels (MACs), each consisting of two transmitters communicating independent messages to one receiver. We define the TIN scheme for this channel as one in which each MAC performs a power controlled version of its capacity-achieving strategy while treating interference from all other MACs as noise. We characterize an achievable generalized degrees-of-freedom (GDoF) region under the TIN scheme and identify a regime of parameters (in terms of channel strength levels) where this region is optimal.
Program Generation for Small-Scale Linear Algebra Applications
Venue: arXiv cs.PL 2018
Year: 2018

We present SLinGen, a program generation system for linear algebra. The input to SLinGen is an application expressed mathematically in a linear-algebra-inspired language (LA) that we define. LA provides basic scalar/vector/matrix additions/multiplications and higher level operations including linear systems solvers, Cholesky and LU factorizations. The output of SLinGen is performance-optimized single-source C code, optionally vectorized with intrinsics. The target of SLinGen are small-scale computations on fixed-size operands, for which a straightforward implementation using optimized libraries (e.g., BLAS or LAPACK) is known to yield suboptimal performance (besides increasing code size and introducing dependencies), but which are crucial in control, signal processing, computer vision, and other domains. Internally, SLinGen uses synthesis and DSL-based techniques to optimize at a high level of abstraction. We benchmark our program generator on three prototypical applications: the Kalman filter, Gaussian process regression, and an L1-analysis convex solver, as well as basic routines including Cholesky factorization and solvers for the continuous-time Lyapunov and Sylvester equations. The results show significant speed-ups compared to straightforward C with Intel icc and clang with a polyhedral optimizer, as well as library-based and template-based implementations.
Fair Leader Election for Rational Agents in Asynchronous Rings and Networks
Venue: arXiv cs.DC 2018
Year: 2018

We study a game theoretic model where a coalition of processors might collude to bias the outcome of the protocol, where we assume that the processors always prefer any legitimate outcome over a non-legitimate one. We show that the problems of Fair Leader Election and Fair Coin Toss are equivalent, and focus on Fair Leader Election. Our main focus is on a directed asynchronous ring of $n$ processors, where we investigate the protocol proposed by Abraham et al. \cite{abraham2013distributed} and studied in Afek et al. \cite{afek2014distributed}. We show that in general the protocol is resilient only to sub-linear size coalitions. Specifically, we show that $Ω(\sqrt{n\log n})$ randomly located processors or $Ω(\sqrt[3]{n})$ adversarially located processors can force any outcome. We complement this by showing that the protocol is resilient to any adversarial coalition of size $O(\sqrt[4]{n})$. We propose a modification to the protocol, and show that it is resilient to every coalition of size $Θ(\sqrt{n})$, by exhibiting both an attack and a resilience result. For every $k \geq 1$, we define a family of graphs ${\mathcal{G}}_{k}$ that can be simulated by trees where each node in the tree simulates at most $k$ processors. We show that for every graph in ${\mathcal{G}}_{k}$, there is no fair leader election protocol that is resilient to coalitions of size $k$. Our result generalizes a previous result of Abraham et al. \cite{abraham2013distributed} that states that for every graph, there is no fair leader election protocol which is resilient to coalitions of size $\lceil \frac{n}{2} \rceil$.
Nonlinear Metric Learning through Geodesic Interpolation within Lie Groups
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we propose a nonlinear distance metric learning scheme based on the fusion of component linear metrics. Instead of merging displacements at each data point, our model calculates the velocities induced by the component transformations, via a geodesic interpolation on a Lie transfor- mation group. Such velocities are later summed up to produce a global transformation that is guaranteed to be diffeomorphic. Consequently, pair-wise distances computed this way conform to a smooth and spatially varying metric, which can greatly benefit k-NN classification. Experiments on synthetic and real datasets demonstrate the effectiveness of our model.
Deep Learning in Software Engineering
Venue: arXiv cs.SE 2018
Year: 2018

Recent years, deep learning is increasingly prevalent in the field of Software Engineering (SE). However, many open issues still remain to be investigated. How do researchers integrate deep learning into SE problems? Which SE phases are facilitated by deep learning? Do practitioners benefit from deep learning? The answers help practitioners and researchers develop practical deep learning models for SE tasks. To answer these questions, we conduct a bibliography analysis on 98 research papers in SE that use deep learning techniques. We find that 41 SE tasks in all SE phases have been facilitated by deep learning integrated solutions. In which, 84.7% papers only use standard deep learning models and their variants to solve SE problems. The practicability becomes a concern in utilizing deep learning techniques. How to improve the effectiveness, efficiency, understandability, and testability of deep learning based solutions may attract more SE researchers in the future.
Enhanced Signal Recovery via Sparsity Inducing Image Priors
Venue: arXiv cs.CV 2018
Year: 2018

Parsimony in signal representation is a topic of active research. Sparse signal processing and representation is the outcome of this line of research which has many applications in information processing and has shown significant improvement in real-world applications such as recovery, classification, clustering, super resolution, etc. This vast influence of sparse signal processing in real-world problems raises a significant need in developing novel sparse signal representation algorithms to obtain more robust systems. In such algorithms, a few open challenges remain in (a) efficiently posing sparsity on signals that can capture the structure of underlying signal and (b) the design of tractable algorithms that can recover signals under aforementioned sparse models.
Exact size counting in uniform population protocols in nearly logarithmic time
Venue: arXiv cs.DC 2018
Year: 2018

We study population protocols: networks of anonymous agents that interact under a scheduler that picks pairs of agents uniformly at random. The _size counting problem_ is that of calculating the exact number $n$ of agents in the population, assuming no leader (each agent starts in the same state). We give the first protocol that solves this problem in sublinear time. The protocol converges in $O(\log n \log \log n)$ time and uses $O(n^{60})$ states ($O(1) + 60 \log n$ bits of memory per agent) with probability $1-O(\frac{\log \log n}{n})$. The time complexity is also $O(\log n \log \log n)$ in expectation. The time to converge is also $O(\log n \log \log n)$ in expectation. Crucially, unlike most published protocols with $ω(1)$ states, our protocol is _uniform_: it uses the same transition algorithm for any population size, so does not need an estimate of the population size to be embedded into the algorithm. A sub-protocol is the first uniform sublinear-time leader election population protocol, taking $O(\log n \log \log n)$ time and $O(n^{18})$ states. The state complexity of both the counting and leader election protocols can be reduced to $O(n^{30})$ and $O(n^{9})$ respectively, while increasing the time to $O(\log^2 n)$.
Deterministic Blind Radio Networks
Venue: arXiv cs.DC 2018
Year: 2018

Ad-hoc radio networks and multiple access channels are classical and well-studied models of distributed systems, with a large body of literature on deterministic algorithms for fundamental communications primitives such as broadcasting and wake-up. However, almost all of these algorithms assume knowledge of the number of participating nodes and the range of possible IDs, and often make the further assumption that the latter is linear in the former. These are very strong assumptions for models which were designed to capture networks of weak devices organized in an ad-hoc manner. It was believed that without this knowledge, deterministic algorithms must necessarily be much less efficient. In this paper we address this fundamental question and show that this is not the case. We present \emph{deterministic} algorithms for \emph{blind} networks (in which nodes know only their own IDs), which match or nearly match the running times of the fastest algorithms which assume network knowledge (and even surpass the previous fastest algorithms which assume parameter knowledge but not small labels). Specifically, in multiple access channels with $k$ participating nodes and IDs up to $L$, we give a wake-up algorithm requiring $O(\frac{k\log L \log k }{\log\log k})$ time, improving dramatically over the $O(L^3 \log^3 L)$ time algorithm of De Marco et al. (2007), and a broadcasting algorithm requiring \sloppy{$O(k\log L \log\log k)$ }time, improving over the $O(L)$ time algorithm of Gasieniec et al. (2001) in most circumstances. Furthermore, we show how these same algorithms apply directly to multi-hop radio networks, achieving even larger running time improvements.
Randomized Communication Without Network Knowledge
Venue: arXiv cs.DC 2018
Year: 2018

Radio networks are a long-studied model for distributed system of devices which communicate wirelessly. When these devices are mobile or have limited capabilities, the system is often best modeled by the ad-hoc variant, in which the devices do not know the structure of the network. A large body of work has been devoted to designing algorithms for the ad-hoc model, particularly for fundamental communications tasks such as broadcasting. Most of these algorithms, however, assume that devices have some network knowledge (usually bounds on the number of nodes in the network $n$, and the diameter $D$), which may not always be realistic in systems with weak devices or gradual deployment. Very little is known about what can be done when this information is not available. This is the issue we address in this work, by presenting the first \emph{randomized} broadcasting algorithms for \emph{blind} networks in which nodes have no prior knowledge whatsoever. We demonstrate that lack of parameter knowledge can be overcome at only a small increase in running time. Specifically, we show that in networks without collision detection, broadcast can be achieved in $O(D\log\frac nD\log^2\log\frac nD + \log^2 n)$ time, almost reaching the $Ω(D\log\frac nD + \log^2 n)$ lower bound. We also give an algorithm for directed networks with collision detection, which requires only $O(D\log\frac nD\log\log\log\frac nD + \log^2 n)$ time.
Covariance Pooling For Facial Expression Recognition
Venue: arXiv cs.CV 2018
Year: 2018

Classifying facial expressions into different categories requires capturing regional distortions of facial landmarks. We believe that second-order statistics such as covariance is better able to capture such distortions in regional facial fea- tures. In this work, we explore the benefits of using a man- ifold network structure for covariance pooling to improve facial expression recognition. In particular, we first employ such kind of manifold networks in conjunction with tradi- tional convolutional networks for spatial pooling within in- dividual image feature maps in an end-to-end deep learning manner. By doing so, we are able to achieve a recognition accuracy of 58.14% on the validation set of Static Facial Expressions in the Wild (SFEW 2.0) and 87.0% on the vali- dation set of Real-World Affective Faces (RAF) Database. Both of these results are the best results we are aware of. Besides, we leverage covariance pooling to capture the tem- poral evolution of per-frame features for video-based facial expression recognition. Our reported results demonstrate the advantage of pooling image-set features temporally by stacking the designed manifold network of covariance pool-ing on top of convolutional network layers.
Fast Multidimensional Asymptotic and Approximate Consensus
Venue: arXiv cs.DC 2018
Year: 2018

We study the problems of asymptotic and approximate consensus in which agents have to get their values arbitrarily close to each others' inside the convex hull of initial values, either without or with an explicit decision by the agents. In particular, we are concerned with the case of multidimensional data, i.e., the agents' values are $d$-dimensional vectors. We introduce two new algorithms for dynamic networks, subsuming classical failure models like asynchronous message passing systems with Byzantine agents. The algorithms are the first to have a contraction rate and time complexity independent of the dimension $d$. In particular, we improve the time complexity from the previously fastest approximate consensus algorithm in asynchronous message passing systems with Byzantine faults by Mendes et al. [Distrib. Comput. 28] from $Ω\!\left( d \log\frac{dΔ}{\varepsilon} \right)$ to $O\!\left( \log\fracΔ{\varepsilon} \right)$, where $Δ$ is the initial and $\varepsilon$ is the terminal diameter of the set of vectors of correct agents.