OpenRaiser/Intern-Atlas huggingface dataset:
Ariadne: Analysis for Machine Learning Program
Venue: arXiv cs.PL 2018
Year: 2018

Machine learning has transformed domains like vision and translation, and is now increasingly used in science, where the correctness of such code is vital. Python is popular for machine learning, in part because of its wealth of machine learning libraries, and is felt to make development faster; however, this dynamic language has less support for error detection at code creation time than tools like Eclipse. This is especially problematic for machine learning: given its statistical nature, code with subtle errors may run and produce results that look plausible but are meaningless. This can vitiate scientific results. We report on Ariadne: applying a static framework, WALA, to machine learning code that uses TensorFlow. We have created static analysis for Python, a type system for tracking tensors---Tensorflow's core data structures---and a data flow analysis to track their usage. We report on how it was built and present some early results.
Adding Salt to Pepper: A Structured Security Assessment over a Humanoid Robot
Venue: arXiv cs.CR 2018
Year: 2018

The rise of connectivity, digitalization, robotics, and artificial intelligence (AI) is rapidly changing our society and shaping its future development. During this technological and societal revolution, security has been persistently neglected, yet a hacked robot can act as an insider threat in organizations, industries, public spaces, and private homes. In this paper, we perform a structured security assessment of Pepper, a commercial humanoid robot. Our analysis, composed by an automated and a manual part, points out a relevant number of security flaws that can be used to take over and command the robot. Furthermore, we suggest how these issues could be fixed, thus, avoided in the future. The very final aim of this work is to push the rise of the security level of IoT products before they are sold on the public market.
The Capacity of Private Information Retrieval from Uncoded Storage Constrained Databases
Venue: arXiv cs.IT 2018
Year: 2018

Private information retrieval (PIR) allows a user to retrieve a desired message from a set of databases without revealing the identity of the desired message. The replicated databases scenario was considered by Sun and Jafar, 2016, where $N$ databases can store the same $K$ messages completely. A PIR scheme was developed to achieve the optimal download cost given by $\left(1+ \frac{1}{N}+ \frac{1}{N^{2}}+ \cdots + \frac{1}{N^{K-1}}\right)$. In this work, we consider the problem of PIR from storage constrained databases. Each database has a storage capacity of $μKL$ bits, where $L$ is the size of each message in bits, and $μ\in [1/N, 1]$ is the normalized storage. On one extreme, $μ=1$ is the replicated databases case. On the other hand, when $μ= 1/N$, then in order to retrieve a message privately, the user has to download all the messages from the databases achieving a download cost of $1/K$. We aim to characterize the optimal download cost versus storage trade-off for any storage capacity in the range $μ\in [1/N, 1]$. For any $(N,K)$, we show that the optimal trade-off between storage, $μ$, and the download cost, $D(μ)$, is given by the lower convex hull of the $N$ pairs $\left(μ= \frac{t}{N},D(μ) = \left(1+ \frac{1}{t}+ \frac{1}{t^{2}}+ \cdots + \frac{1}{t^{K-1}}\right)\right)$ for $t=1,2,\ldots, N$. To prove this result, we first present the storage constrained PIR scheme for any $(N,K)$. We next obtain a general lower bound on the download cost for PIR, which is valid for the following storage scenarios: replicated or storage constrained, coded or uncoded, and fixed or optimized. We then specialize this bound using the uncoded storage assumption to obtain lower bounds matching the achievable download cost of the storage constrained PIR scheme for any value of the available storage.
A 1.5-Approximation for Path TSP
Venue: arXiv cs.DM 2018
Year: 2018

We present a $1.5$-approximation for the Metric Path Traveling Salesman Problem (Path TSP). All recent improvements on Path TSP crucially exploit a structural property shown by An, Kleinberg, and Shmoys [Journal of the ACM, 2015], namely that narrow cuts with respect to a Held-Karp solution form a chain. We significantly deviate from these approaches by showing the benefit of dealing with larger $s$-$t$ cuts, even though they are much less structured. More precisely, we show that a variation of the dynamic programming idea recently introduced by Traub and Vygen [SODA, 2018] is versatile enough to deal with larger size cuts, by exploiting a seminal result of Karger on the number of near-minimum cuts. This avoids a recursive application of dynamic programming as used by Traub and Vygen, and leads to a considerably simpler algorithm avoiding an additional error term in the approximation guarantee. We match the still unbeaten $1.5$-approximation guarantee of Christofides' algorithm for TSP. Hence, any further progress on the approximability of Path TSP will also lead to an improvement for TSP.
On the approximation guarantee of obviously strategyproof mechanisms
Venue: arXiv cs.GT 2018
Year: 2018

Catering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms and approximation algorithms. Obviously strategyproof (OSP) mechanisms have recently emerged as the concept of interest to this research agenda. However, the majority of the literature in the area has either highlighted the shortcomings of OSP or focused on the "right" definition rather than on the construction of these mechanisms. We here give the first set of tight results on the approximation guarantee of OSP mechanisms for scheduling related machines and a characterization of optimal OSP mechanisms for set system problems. By extending the well-known cycle monotonicity technique, we are able to concentrate on the algorithmic component of OSP mechanisms and provide some novel paradigms for their design.
Sentiment-driven Community Profiling and Detection on Social Media
Venue: arXiv cs.SI 2018
Year: 2018

Web 2.0 helps to expand the range and depth of conversation on many issues and facilitates the formation of online communities. Online communities draw various individuals together based on their common opinions on a core set of issues. Most existing community detection methods merely focus on discovering communities without providing any insight regarding the collective opinions of community members and the motives behind the formation of communities. Several efforts have been made to tackle this problem by presenting a set of keywords as a community profile. However, they neglect the positions of community members towards keywords, which play an important role for understanding communities in the highly polarized atmosphere of social media. To this end, we present a sentiment-driven community profiling and detection framework which aims to provide community profiles presenting positive and negative collective opinions of community members separately. With this regard, our framework initially extracts key expressions in users' messages as representative of issues and then identifies users' positive/negative attitudes towards these key expressions. Next, it uncovers a low-dimensional latent space in order to cluster users according to their opinions and social interactions (i.e., retweets). We demonstrate the effectiveness of our framework through quantitative and qualitative evaluations.
Graphlets versus node2vec and struc2vec in the task of network alignment
Venue: arXiv cs.SI 2018
Year: 2018

Network embedding aims to represent each node in a network as a low-dimensional feature vector that summarizes the given node's (extended) network neighborhood. The nodes' feature vectors can then be used in various downstream machine learning tasks. Recently, many embedding methods that automatically learn the features of nodes have emerged, such as node2vec and struc2vec, which have been used in tasks such as node classification, link prediction, and node clustering, mainly in the social network domain. There are also other embedding methods that explicitly look at the connections between nodes, i.e., the nodes' network neighborhoods, such as graphlets. Graphlets have been used in many tasks such as network comparison, link prediction, and network clustering, mainly in the computational biology domain. Even though the two types of embedding methods (node2vec/struct2vec versus graphlets) have a similar goal -- to represent nodes as features vectors, no comparisons have been made between them, possibly because they have originated in the different domains. Therefore, in this study, we compare graphlets to node2vec and struc2vec, and we do so in the task of network alignment. In evaluations on synthetic and real-world biological networks, we find that graphlets are both more accurate and faster than node2vec and struc2vec.
Reciprocal Attention Fusion for Visual Question Answering
Venue: arXiv cs.CV 2018
Year: 2018

Existing attention mechanisms either attend to local image grid or object level features for Visual Question Answering (VQA). Motivated by the observation that questions can relate to both object instances and their parts, we propose a novel attention mechanism that jointly considers reciprocal relationships between the two levels of visual details. The bottom-up attention thus generated is further coalesced with the top-down information to only focus on the scene elements that are most relevant to a given question. Our design hierarchically fuses multi-modal information i.e., language, object- and gird-level features, through an efficient tensor decomposition scheme. The proposed model improves the state-of-the-art single model performances from 67.9% to 68.2% on VQAv1 and from 65.7% to 67.4% on VQAv2, demonstrating a significant boost.
A Tube-based Robust MPC for a Fixed-wing UAV: an Application for Precision Farming
Venue: arXiv cs.SY 2018
Year: 2018

The techniques of precision agriculture include the possibility to execute crop monitoring tasks through the application of Unmanned Aerial Vehicles (UAVs). These platforms are flexible, easy to use and low-cost, and they are the best candidates for improving the farm efficiency and productivity. In this research, a guidance algorithm and a robust control system are combined to guarantee the robustness of the system to additive noise (i.e. wind disturbance) and uncertainties (i.e. model parameter variations). A small fixed-wing UAV with an autonomy of about $1$ hour is proposed as case study, to reduce the cost of monitoring and increasing the stability performance of the system. A waypoint-grid on a paddy field is verified by hardware-in-the loop tests. The control scheme provides good results with a low computational effort, guaranteeing the repeatability of the monitoring and reduction of the costs.
Semiotic internationalization and localization of computer programs
Venue: arXiv cs.SE 2018
Year: 2018

Localization, the process--part of translation studies--of adapting a program to a new linguistic community, is often intended in the relatively narrow sense of translating the messages and labels of the program into the target language. Correspondingly, internationalization, the discipline--which is part of software engineering--of putting in place all the measures that will make localization easier, is also limited in scope. In this paper we analyze the various systems through which a program communicates with a person (icons, buttons, actions, interface layout, etc.) and find that most of them, far from being iconic, are in reality symbolic semiotic systems related to the culture in which or for which the program was developed (typically American programmers of western office workers). Based on these findings, we argue that during the localization process, the translator should have the option to translate them all, that is, to adapt the whole interface and its founding metaphors to the cultural environment in which the program is deployed. This conclusion will result in a greater role for internationalization in the software development process, and we outline a few architectural principles that should be considered when creating a program for a multi-cultural market.
Taking the edge off quantization: projected back projection in dithered compressive sensing
Venue: arXiv cs.IT 2018
Year: 2018

Quantized compressive sensing (QCS) deals with the problem of representing compressive signal measurements with finite precision representation, i.e., a mandatory process in any practical sensor design. To characterize the signal reconstruction quality in this framework, most of the existing theoretical analyses lie heavily on the quantization of sub-Gaussian random projections (e.g., Gaussian or Bernoulli). We show here that a simple uniform scalar quantizer is compatible with a large class of random sensing matrices known to respect, with high probability, the restricted isometry property (RIP). Critically, this compatibility arises from the addition of a uniform random vector, or "dithering", to the linear signal observations before quantization. In this setting, we prove the existence of (at least) one signal reconstruction method, i.e., the projected back projection (PBP), whose reconstruction error decays when the number of quantized measurements increases. This holds with high probability in the estimation of sparse signals and low-rank matrices. We validate numerically the predicted error decay as the number of measurements increases.
Game Design with Pocket Code: Providing a Constructionist Environment for Girls in the School Context
Venue: arXiv cs.CY 2018
Year: 2018

The widespread use of mobile phones is changing how learning takes place in many disciplines and contexts. As a scenario in a constructionist learning environment, students are given powerful tools to create games using their own ideas. In the "No One Left Behind" (NOLB) project we will study through experimental cycles whether the use of mobile game design has an impact on learning, understanding, and retention of knowledge for students at risk of social exclusion. We will use the mobile learning app Pocket Code with partner schools in three countries: Austria, Spain, and the UK. This paper focuses on the Austrian pilot, which is exploring gender inclusion in game creation within an educational environment. We first study differences in game creation between girls and boys. This study that started in September 2015, will help teachers to integrate Pocket Code effectively into their courses. For future studies an enhanced school version of Pocket Code will be designed using the results and insights gathered at schools with pupils and teachers.
Female Teenagers and Coding: Create Gender Sensitive and Creative Learning Environments
Venue: arXiv cs.CY 2018
Year: 2018

The number of women in technical fields is far below the average number of males, especially in developed countries. Gender differences in STEM are already present in secondary schools in students aged between 12 to 15 years. Adolescence is a critical time for identity formation, and self-attributes are a source for internal conflicts, especially for female teenagers. It is during this intermediate female adolescence that girls begin to make critical career choices, which therefore makes this a key age to reinforce them and reduce the gender disparities in ICT. Computational thinking skills are important from a philosophical point of view, since they allow us to understand the foundations of rational thought in a clear, easily understandable, but also inspiring and challenging way. To address the gender bias in schools, one of the goals of the European H2020 project No One Left Behind (NOLB) included integrating Pocket Code, a free open source app developed by the non-profit project Catrobat, into different school lessons. Through game design, Pocket Code allows teenage girls to incorporate diversity and inclusiveness, as well as the ability to reflect their cultural identity, their emotions, their likes, and their ways of interacting and thinking. To evaluate the impact of the use of the app in these courses, we captured the results on engaging girls in design and coding activities. For this paper, the authors present the data of surveys during the second cycle of the project. With a focus on female teenagers, the results allow us to conclude that a suitable classroom setting is significantly more important for them than the coding tool itself.
Bootstrapping Multilingual Intent Models via Machine Translation for Dialog Automation
Venue: arXiv cs.CL 2018
Year: 2018

With the resurgence of chat-based dialog systems in consumer and enterprise applications, there has been much success in developing data-driven and rule-based natural language models to understand human intent. Since these models require large amounts of data and in-domain knowledge, expanding an equivalent service into new markets is disrupted by language barriers that inhibit dialog automation. This paper presents a user study to evaluate the utility of out-of-the-box machine translation technology to (1) rapidly bootstrap multilingual spoken dialog systems and (2) enable existing human analysts to understand foreign language utterances. We additionally evaluate the utility of machine translation in human assisted environments, where a portion of the traffic is processed by analysts. In English->Spanish experiments, we observe a high potential for dialog automation, as well as the potential for human analysts to process foreign language utterances with high accuracy.
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
Venue: arXiv cs.DS 2018
Year: 2018

We give deterministic distributed $(1+ε)$-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in $O(\frac{1}ε \log n)$ rounds, and our independent set algorithm has a runtime of $O(\frac{1}ε\log(\frac{1}ε)\log^* n)$ rounds. For coloring, existing lower bounds imply that the dependencies on $\frac{1}ε$ and $\log n$ are best possible. For independent set, we prove that $O(\frac{1}ε)$ rounds are necessary. Both our algorithms make use of a tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into $O(\log n)$ layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first $O( \log \frac{1}ε)$ layers are required as they already contain a large enough independent set. We develop a $(1+ε)$-approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. This work raises the question as to how useful tree decompositions are for distributed computing.
The Domain Transform Solver
Venue: arXiv cs.CV 2018
Year: 2018

We present a framework for edge-aware optimization that is an order of magnitude faster than the state of the art while having comparable performance. Our key insight is that the optimization can be formulated by leveraging properties of the domain transform, a method for edge-aware filtering that defines a distance-preserving 1D mapping of the input space. This enables our method to improve performance for a variety of problems including stereo, depth super-resolution, and render from defocus, while keeping the computational complexity linear in the number of pixels. Our method is highly parallelizable and adaptable, and it has demonstrable scalability with respect to image resolution.
Joint Flow: Temporal Flow Fields for Multi Person Tracking
Venue: arXiv cs.CV 2018
Year: 2018

In this work we propose an online multi person pose tracking approach which works on two consecutive frames $I_{t-1}$ and $I_t$. The general formulation of our temporal network allows to rely on any multi person pose estimation approach as spatial network. From the spatial network we extract image features and pose features for both frames. These features serve as input for our temporal model that predicts Temporal Flow Fields (TFF). These TFF are vector fields which indicate the direction in which each body joint is going to move from frame $I_{t-1}$ to frame $I_t$. This novel representation allows to formulate a similarity measure of detected joints. These similarities are used as binary potentials in a bipartite graph optimization problem in order to perform tracking of multiple poses. We show that these TFF can be learned by a relative small CNN network whilst achieving state-of-the-art multi person pose tracking results.
Bitcoin With Heterogeneous Block Sizes: A Scaling Proposal
Venue: arXiv cs.CR 2018
Year: 2018

We propose a bitcoin generalization as a solution to the problem of scalability. The block is redefined as a sequence of sub-blocks of increasing sizes that coexist as different levels of compromise between decentralization and transactions throughput. Miners and users can decide individually the sizes they use without affecting others in the network.
I Have Seen Enough: A Teacher Student Network for Video Classification Using Fewer Frames
Venue: arXiv cs.CV 2018
Year: 2018

Over the past few years, various tasks involving videos such as classification, description, summarization and question answering have received a lot of attention. Current models for these tasks compute an encoding of the video by treating it as a sequence of images and going over every image in the sequence. However, for longer videos this is very time consuming. In this paper, we focus on the task of video classification and aim to reduce the computational time by using the idea of distillation. Specifically, we first train a teacher network which looks at all the frames in a video and computes a representation for the video. We then train a student network whose objective is to process only a small fraction of the frames in the video and still produce a representation which is very close to the representation computed by the teacher network. This smaller student network involving fewer computations can then be employed at inference time for video classification. We experiment with the YouTube-8M dataset and show that the proposed student network can reduce the inference time by upto 30% with a very small drop in the performance
An Indexing for Quadratic Residues Modulo $N$ and a Non-uniform Efficient Decoding Algorithm
Venue: arXiv cs.CC 2018
Year: 2018

An \emph{indexing} of a finite set $S$ is a bijection $D : \{1,...,|S|\} \rightarrow S$. We present an indexing for the set of quadratic residues modulo $N$ that is decodable in polynomial time on the size of $N$, given the factorization of $N$. One consequence of this result is a procedure for sampling quadratic residues modulo $N$, when the factorization of $N$ is known, that runs in strict polynomial time and requires the theoretical minimum amount of random bits (i.e., $\log{(ϕ(N)/2^r)}$ bits, where $ϕ(N)$ is Euler's totient function and $r$ is the number of distinct prime factors of $N$). A previously known procedure for this same problem runs in expected (not strict) polynomial time and requires more random bits.