OpenRaiser/Intern-Atlas huggingface dataset:
Towards An Angry-Birds-like Game System for Promoting Mental Well-being of Players Using Art-Therapy-embedded PCG
Venue: arXiv cs.HC 2019
Year: 2019

This paper presents an integration of a game system and the art therapy concept for promoting the mental well-being of video game players. In the proposed game system, the player plays an Angry-Birds-like game in which levels in the game are generated based on images they draw. Upon finishing a game level, the player also receives positive feedback (praising words) toward their drawing and the generated level from an Art Therapy AI. The proposed system is composed of three major parts: (1) a drawing recognizer that identifies what object is drawn by the player (Sketcher), (2) a level generator that converts the drawing image into a pixel image, then a set of blocks representing a game level (PCG AI), and (3) the Art Therapy AI that encourages the player and improves their emotion. This paper describes an overview of the system and explains how its major components function.
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
Venue: arXiv cs.GT 2019
Year: 2019

A longstanding open problem in Algorithmic Mechanism Design is to design computationally-efficient truthful mechanisms for (approximately) maximizing welfare in combinatorial auctions with submodular bidders. The first such mechanism was obtained by Dobzinski, Nisan, and Schapira [STOC'06] who gave an $O(\log^2{m})$-approximation where $m$ is the number of items. This problem has been studied extensively since, culminating in an $O(\sqrt{\log{m}})$-approximation mechanism by Dobzinski [STOC'16]. We present a computationally-efficient truthful mechanism with approximation ratio that improves upon the state-of-the-art by an exponential factor. In particular, our mechanism achieves an $O((\log\log{m})^3)$-approximation in expectation, uses only $O(n)$ demand queries, and has universal truthfulness guarantee. This settles an open question of Dobzinski on whether $Θ(\sqrt{\log{m}})$ is the best approximation ratio in this setting in negative.
Trichotomy for the reconfiguration problem of integer linear systems
Venue: arXiv cs.DS 2019
Year: 2019

In this paper, we consider the reconfiguration problem of integer linear systems. In this problem, we are given an integer linear system $I$ and two feasible solutions $\boldsymbol{s}$ and $\boldsymbol{t}$ of $I$, and then asked to transform $\boldsymbol{s}$ to $\boldsymbol{t}$ by changing a value of only one variable at a time, while maintaining a feasible solution of $I$ throughout. $Z(I)$ for $I$ is the complexity index introduced by Kimura and Makino (Discrete Applied Mathematics 200:67--78, 2016), which is defined by the sign pattern of the input matrix. We analyze the complexity of the reconfiguration problem of integer linear systems based on the complexity index $Z(I)$ of given $I$. We then show that the problem is (i) solvable in constant time if $Z(I)$ is less than one, (ii) weakly coNP-complete and pseudo-polynomially solvable if $Z(I)$ is exactly one, and (iii) PSPACE-complete if $Z(I)$ is greater than one. Since the complexity indices of Horn and two-variable-par-inequality integer linear systems are at most one, our results imply that the reconfiguration of these systems are in coNP and pseudo-polynomially solvable. Moreover, this is the first result that reveals coNP-completeness for a reconfiguration problem, to the best of our knowledge.
Active Multi-Label Crowd Consensus
Venue: arXiv cs.LG 2019
Year: 2019

Crowdsourcing is an economic and efficient strategy aimed at collecting annotations of data through an online platform. Crowd workers with different expertise are paid for their service, and the task requester usually has a limited budget. How to collect reliable annotations for multi-label data and how to compute the consensus within budget is an interesting and challenging, but rarely studied, problem. In this paper, we propose a novel approach to accomplish Active Multi-label Crowd Consensus (AMCC). AMCC accounts for the commonality and individuality of workers, and assumes that workers can be organized into different groups. Each group includes a set of workers who share a similar annotation behavior and label correlations. To achieve an effective multi-label consensus, AMCC models workers' annotations via a linear combination of commonality and individuality, and reduces the impact of unreliable workers by assigning smaller weights to the group. To collect reliable annotations with reduced cost, AMCC introduces an active crowdsourcing learning strategy that selects sample-label-worker triplets. In a triplet, the selected sample and label are the most informative for the consensus model, and the selected worker can reliably annotate the sample with low cost. Our experimental results on multi-label datasets demonstrate the advantages of AMCC over state-of-the-art solutions on computing crowd consensus and on reducing the budget by choosing cost-effective triplets.
Improving Human Annotation in Single Object Tracking
Venue: arXiv cs.CV 2019
Year: 2019

Human annotation is always considered as ground truth in video object tracking tasks. It is used in both training and evaluation purposes. Thus, ensuring its high quality is an important task for the success of trackers and evaluations between them. In this paper, we give a qualitative and quantitative analysis of the existing human annotations. We show that human annotation tends to be non-smooth and is prone to partial visibility and deformation. We propose a smoothing trajectory strategy with the ability to handle moving scenes. We use a two-step adaptive image alignment algorithm to find the canonical view of the video sequence. We then use different techniques to smooth the trajectories at certain degree. Once we convert back to the original image coordination, we can compare with the human annotation. With the experimental results, we can get more consistent trajectories. At a certain degree, it can also slightly improve the trained model. If go beyond a certain threshold, the smoothing error will start eating up the benefit. Overall, our method could help extrapolate the missing annotation frames or identify and correct human annotation outliers as well as help improve the training data quality.
Transition-Based Deep Input Linearization
Venue: arXiv cs.CL 2019
Year: 2019

Traditional methods for deep NLG adopt pipeline approaches comprising stages such as constructing syntactic input, predicting function words, linearizing the syntactic input and generating the surface forms. Though easier to visualize, pipeline approaches suffer from error propagation. In addition, information available across modules cannot be leveraged by all modules. We construct a transition-based model to jointly perform linearization, function word prediction and morphological generation, which considerably improves upon the accuracy compared to a pipelined baseline system. On a standard deep input linearization shared task, our system achieves the best results reported so far.
Explicit Pairwise Word Interaction Modeling Improves Pretrained Transformers for English Semantic Similarity Tasks
Venue: arXiv cs.CL 2019
Year: 2019

In English semantic similarity tasks, classic word embedding-based approaches explicitly model pairwise "interactions" between the word representations of a sentence pair. Transformer-based pretrained language models disregard this notion, instead modeling pairwise word interactions globally and implicitly through their self-attention mechanism. In this paper, we hypothesize that introducing an explicit, constrained pairwise word interaction mechanism to pretrained language models improves their effectiveness on semantic similarity tasks. We validate our hypothesis using BERT on four tasks in semantic textual similarity and answer sentence selection. We demonstrate consistent improvements in quality by adding an explicit pairwise word interaction module to BERT.
Efficacy of Pixel-Level OOD Detection for Semantic Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

The detection of out of distribution samples for image classification has been widely researched. Safety critical applications, such as autonomous driving, would benefit from the ability to localise the unusual objects causing the image to be out of distribution. This paper adapts state-of-the-art methods for detecting out of distribution images for image classification to the new task of detecting out of distribution pixels, which can localise the unusual objects. It further experimentally compares the adapted methods on two new datasets derived from existing semantic segmentation datasets using PSPNet and DeeplabV3+ architectures, as well as proposing a new metric for the task. The evaluation shows that the performance ranking of the compared methods does not transfer to the new task and every method performs significantly worse than their image-level counterparts.
Error Correction for Partially Stuck Memory Cells
Venue: arXiv cs.IT 2019
Year: 2019

We present code constructions for masking $u$ partially stuck memory cells with $q$ levels and correcting additional random errors. The results are achieved by combining the methods for masking and error correction for stuck cells in [1] with the masking-only results for partially stuck cells in [2]. We present two constructions for masking $u<q$ cells and error correction: one is general and based on a generator matrix of a specific form. The second construction uses cyclic codes and allows to efficiently bound the error-correction capability using the BCH bound. Furthermore, we extend the results to masking $u\geq q$ cells. For $u>1$ and $q>2$, all new constructions require less redundancy for masking partially stuck cells than previous work on stuck cells, which in turn can result in higher code rates at the same masking and error correction capability.
Priority Quality Attributes for Engineering AI-enabled Systems
Venue: arXiv cs.OH 2019
Year: 2019

Deploying successful software-reliant systems that address their mission goals and user needs within cost, resource, and expected quality constraints require design trade-offs. These trade-offs dictate how systems are structured and how they behave and consequently can effectively be evolved and sustained. Software engineering practices address this challenge by centering system design and evolution around delivering key quality attributes, such as security, privacy, data centricity, sustainability, and explainability. These concerns are more urgent requirements for software-reliant systems that also include AI components due to the uncertainty introduced by data elements. Moreover, systems employed by the public sector exhibit unique design time and runtime challenges due to the regulatory nature of the domains. We assert that the quality attributes of security, privacy, data centricity, sustainability, and explainability pose new challenges to AI engineering and will drive the success of AI-enabled systems in the public sector. In this position paper, we enumerate with examples from healthcare domain concerns related to these requirements to mitigate barriers to architecting and fielding AI-enabled systems in the public sector.
The TechQA Dataset
Venue: arXiv cs.CL 2019
Year: 2019

We introduce TechQA, a domain-adaptation question answering dataset for the technical support domain. The TechQA corpus highlights two real-world issues from the automated customer support domain. First, it contains actual questions posed by users on a technical forum, rather than questions generated specifically for a competition or a task. Second, it has a real-world size -- 600 training, 310 dev, and 490 evaluation question/answer pairs -- thus reflecting the cost of creating large labeled datasets with actual data. Consequently, TechQA is meant to stimulate research in domain adaptation rather than being a resource to build QA systems from scratch. The dataset was obtained by crawling the IBM Developer and IBM DeveloperWorks forums for questions with accepted answers that appear in a published IBM Technote---a technical document that addresses a specific technical issue. We also release a collection of the 801,998 publicly available Technotes as of April 4, 2019 as a companion resource that might be used for pretraining, to learn representations of the IT domain language.
The Pitfall of Evaluating Performance on Emerging AI Accelerators
Venue: arXiv cs.PF 2019
Year: 2019

In recent years, domain-specific hardware has brought significant performance improvements in deep learning (DL). Both industry and academia only focus on throughput when evaluating these AI accelerators, which usually are custom ASICs deployed in datacenter to speed up the inference phase of DL workloads. Pursuing higher hardware throughput such as OPS (Operation Per Second) using various optimizations seems to be their main design target. However, they ignore the importance of accuracy in the DL nature. Motivated by this, this paper argue that a single throughput metric can not comprehensively reflect the real-world performance of AI accelerators. To reveal this pitfall, we evaluates several frequently-used optimizations on a typical AI accelerator and quantifies their impact on accuracy and throughout under representative DL inference workloads. Based on our experimental results, we find that some optimizations cause significant loss on accuracy in some workloads, although it can improves the throughout. Furthermore, our results show the importance of end-to-end evaluation in DL.
Cross-Lingual Relevance Transfer for Document Retrieval
Venue: arXiv cs.IR 2019
Year: 2019

Recent work has shown the surprising ability of multi-lingual BERT to serve as a zero-shot cross-lingual transfer model for a number of language processing tasks. We combine this finding with a similarly-recently proposal on sentence-level relevance modeling for document retrieval to demonstrate the ability of multi-lingual BERT to transfer models of relevance across languages. Experiments on test collections in five different languages from diverse language families (Chinese, Arabic, French, Hindi, and Bengali) show that models trained with English data improve ranking quality, without any special processing, both for (non-English) mono-lingual retrieval as well as cross-lingual retrieval.
Dynamic Influence on Replicator Evolution for the Propagation of Competing Technologies
Venue: arXiv cs.GT 2019
Year: 2019

This work introduces a novel modified Replicator Dynamics model, which includes external influences on the population. This framework models a realistic market into which companies, the external dynamic influences, invest resources in order to bolster their product's standing and increase their market share. The dynamic influences change in each time step of the game, and directly modify the payoff matrix of the population's interactions. The model can learn from real data how each influence affects the market, and can be used to simulate and predict the outcome of a real system. We specifically analyze how a new technology can compete and attempt to unseat an entrenched technology as the market leader. We establish a relationship between the external influences and the population payoff matrix and show how the system can be implemented to predict outcomes in a real market by simulating the rise of the Android mobile operating system over its primary competition, the iPhone, from 2009 to 2017.
Lock-Free Hopscotch Hashing
Venue: arXiv cs.DC 2019
Year: 2019

In this paper we present a lock-free version of Hopscotch Hashing. Hopscotch Hashing is an open addressing algorithm originally proposed by Herlihy, Shavit, and Tzafrir, which is known for fast performance and excellent cache locality. The algorithm allows users of the table to skip or jump over irrelevant entries, allowing quick search, insertion, and removal of entries. Unlike traditional linear probing, Hopscotch Hashing is capable of operating under a high load factor, as probe counts remain small. Our lock-free version improves on both speed, cache locality, and progress guarantees of the original, being a chimera of two concurrent hash tables. We compare our data structure to various other lock-free and blocking hashing algorithms and show that its performance is in many cases superior to existing strategies. The proposed lock-free version overcomes some of the drawbacks associated with the original blocking version, leading to a substantial boost in scalability while maintaining attractive features like physical deletion or probe-chain compression.
Extracting temporal features into a spatial domain using autoencoders for sperm video analysis
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we present a two-step deep learning method that is used to predict sperm motility and morphology-based on video recordings of human spermatozoa. First, we use an autoencoder to extract temporal features from a given semen video and plot these into image-space, which we call feature-images. Second, these feature-images are used to perform transfer learning to predict the motility and morphology values of human sperm. The presented method shows it's capability to extract temporal information into spatial domain feature-images which can be used with traditional convolutional neural networks. Furthermore, the accuracy of the predicted motility of a given semen sample shows that a deep learning-based model can capture the temporal information of microscopic recordings of human semen.
Statistical Ineffective Fault Analysis of GIMLI
Venue: arXiv cs.CR 2019
Year: 2019

Ineffective Fault Analysis (SIFA) was introduced as a new approach to attack block ciphers at CHES 2018. Since then, they have been proven to be a powerful class of attacks, with an easy to achieve fault model. One of the main benefits of SIFA is to overcome detection-based and infection-based countermeasures. In this paper we explain how the principles of SIFA can be applied to GIMLI, an authenticated encryption cipher participating the NIST-LWC competition. We identified two possible rounds during the intialization phase of GIMLI to mount our attack. If we attack the first location we are able to recover 3 bits of the key uniquely and the parity of 8 key-bits organized in 3 sums using 180 ineffective faults per biased single intermediate bit. If we attack the second location we are able to recover 15 bits of the key uniquely and the parity of 22 key-bits organized in 7 sums using 340 ineffective faults per biased intermediate bit. Furthermore, we investigated the influence of the fault model on the rate of ineffective faults in GIMLI. Finally, we verify the efficiency of our attacks by means of simulation.
Accessible tables in digital documents
Venue: arXiv cs.HC 2019
Year: 2019

Accessibility of tables on websites for Visually Impaired Persons (VIP) is not optimal with screen readers which are not always effective for the recovery of visual information (2D). Actual Web/Multimedia technologies are not taking in account the difference of the visual perception with respect to the vocal perception which is linear. This paper analyses the difficulties for accessing to spatial information with the existing recommendations for the conception of accessible (for all) websites. Different solutions to facilitate accessible table creation are presented.
PnyxDB: a Lightweight Leaderless Democratic Byzantine Fault Tolerant Replicated Datastore
Venue: arXiv cs.DB 2019
Year: 2019

Byzantine-Fault-Tolerant (BFT) systems are rapidly emerging as a viable technology for production-grade systems, notably in closed consortia deployments for nancial and supply-chain applications. Unfortunately, most algorithms proposed so far to coordinate these systems suffer from substantial scalability issues, and lack important features to implement Internet-scale governance mechanisms. In this paper, we observe that many application workloads offer little concurrency, and propose PnyxDB, an eventually-consistent Byzantine Fault Tolerant replicated datastore that exhibits both high scalability and low latency. Our approach is based on conditional endorsements, that allow nodes to specify the set of transactions that must not be committed for the endorsement to be valid. In addition to its high scalability, PnyxDB supports application-level voting, i.e. individual nodes are able to endorse or reject a transaction according to application-defined policies without compromising consistency. We provide a comparison against BFTSMaRt and Tendermint, two competitors with different design aims, and show that our implementation speeds up commit latencies by a factor of 11, remaining below 5 seconds in a worldwide geodistributed deployment of 180 nodes.
Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages
Venue: arXiv cs.CL 2019
Year: 2019

We introduce three memory-augmented Recurrent Neural Networks (MARNNs) and explore their capabilities on a series of simple language modeling tasks whose solutions require stack-based mechanisms. We provide the first demonstration of neural networks recognizing the generalized Dyck languages, which express the core of what it means to be a language with hierarchical structure. Our memory-augmented architectures are easy to train in an end-to-end fashion and can learn the Dyck languages over as many as six parenthesis-pairs, in addition to two deterministic palindrome languages and the string-reversal transduction task, by emulating pushdown automata. Our experiments highlight the increased modeling capacity of memory-augmented models over simple RNNs, while inflecting our understanding of the limitations of these models.
Automatic Identification of Traditional Colombian Music Genres based on Audio Content Analysis and Machine Learning Technique
Venue: arXiv cs.CV 2019
Year: 2019

Colombia has a diversity of genres in traditional music, which allows to express the richness of the Colombian culture according to the region. This musical diversity is the result of a mixture of African, native Indigenous, and European influences. Organizing large collections of songs is a time consuming task that requires that a human listens to fragments of audio to identify genre, singer, year, instruments and other relevant characteristics that allow to index the song dataset. This paper presents a method to automatically identify the genre of a Colombian song by means of its audio content. The method extracts audio features that are used to train a machine learning model that learns to classify the genre. The method was evaluated in a dataset of 180 musical pieces belonging to six folkloric Colombian music genres: Bambuco, Carranga, Cumbia, Joropo, Pasillo, and Vallenato. Results show that it is possible to automatically identify the music genre in spite of the complexity of Colombian rhythms reaching an average accuracy of 69\%.
A Good Sample is Hard to Find: Noise Injection Sampling and Self-Training for Neural Language Generation Models
Venue: arXiv cs.CL 2019
Year: 2019

Deep neural networks (DNN) are quickly becoming the de facto standard modeling method for many natural language generation (NLG) tasks. In order for such models to truly be useful, they must be capable of correctly generating utterances for novel meaning representations (MRs) at test time. In practice, even sophisticated DNNs with various forms of semantic control frequently fail to generate utterances faithful to the input MR. In this paper, we propose an architecture agnostic self-training method to sample novel MR/text utterance pairs to augment the original training data. Remarkably, after training on the augmented data, even simple encoder-decoder models with greedy decoding are capable of generating semantically correct utterances that are as good as state-of-the-art outputs in both automatic and human evaluations of quality.