OpenRaiser/Intern-Atlas huggingface dataset:
Entombed: An archaeological examination of an Atari 2600 game
Venue: arXiv cs.SE 2018
Year: 2018

The act and experience of programming is, at its heart, a fundamentally human activity that results in the production of artifacts. When considering programming, therefore, it would be a glaring omission to not involve people who specialize in studying artifacts and the human activity that yields them: archaeologists. Here we consider this with respect to computer games, the focus of archaeology's nascent subarea of archaeogaming. One type of archaeogaming research is digital excavation, a technical examination of the code and techniques used in old games' implementation. We apply that in a case study of Entombed, an Atari 2600 game released in 1982 by US Games. The player in this game is, appropriately, an archaeologist who must make their way through a zombie-infested maze. Maze generation is a fruitful area for comparative retrogame archaeology, because a number of early games on different platforms featured mazes, and their variety of approaches can be compared. The maze in Entombed is particularly interesting: it is shaped in part by the extensive real-time constraints of the Atari 2600 platform, and also had to be generated efficiently and use next to no memory. We reverse engineered key areas of the game's code to uncover its unusual maze-generation algorithm, which we have also built a reconstruction of, and analyzed the mysterious table that drives it. In addition, we discovered what appears to be a 35-year-old bug in the code, as well as direct evidence of code-reuse practices amongst game developers. What further makes this game's development interesting is that, in an era where video games were typically solo projects, a total of five people were involved in various ways with Entombed. We piece together some of the backstory of the game's development and intoxicant-fueled design using interviews to complement our technical work. Finally, we contextualize this example in archaeology and lay the groundwork for a broader interdisciplinary discussion about programming, one that includes both computer scientists and archaeologists.
Conceptua: Institutions in a Topos
Venue: arXiv cs.LO 2018
Year: 2018

Tarski's semantic definition of truth is the composition of its extensional and intensional aspects. Abstract satisfaction, the core of the semantic definition of truth, is the basis for the theory of institutions (Goguen and Burstall). The satisfaction relation for first order languages (the truth classification), and the preservation of truth by first order interpretations (the truth infomorphism), form a key motivating example in the theory of Information Flow (IF) (Barwise and Seligman). The concept lattice notion, which is the central structure studied by the theory of Formal Concept Analysis (FCA) (Ganter and Wille), is constructed by the polar factorization of derivation. The study of classification structures (IF) and the study of conceptual structures (FCA) provide a principled foundation for the logical theory of knowledge representation and organization. In an effort to unify these two areas, the paper "Distributed Conceptual Structures" (Kent arXiv:1810.04774) abstracted the basic theorem of FCA in order to established three levels of categorical equivalence between classification structures and conceptual structures. In this paper, we refine this approach by resolving the equivalence as the category-theoretic factorization of the Galois connection of derivation. The equivalence between classification and conceptual structures is mediated by the opposite motions of factorization and composition. Abstract truth factors through the concept lattice of theories in terms of its extensional and intensional aspects.
QUOTA: The Quantile Option Architecture for Reinforcement Learning
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we propose the Quantile Option Architecture (QUOTA) for exploration based on recent advances in distributional reinforcement learning (RL). In QUOTA, decision making is based on quantiles of a value distribution, not only the mean. QUOTA provides a new dimension for exploration via making use of both optimism and pessimism of a value distribution. We demonstrate the performance advantage of QUOTA in both challenging video games and physical robot simulators.
Unpaired Speech Enhancement by Acoustic and Adversarial Supervision for Speech Recognition
Venue: arXiv cs.CL 2018
Year: 2018

Many speech enhancement methods try to learn the relationship between noisy and clean speech, obtained using an acoustic room simulator. We point out several limitations of enhancement methods relying on clean speech targets; the goal of this work is proposing an alternative learning algorithm, called acoustic and adversarial supervision (AAS). AAS makes the enhanced output both maximizing the likelihood of transcription on the pre-trained acoustic model and having general characteristics of clean speech, which improve generalization on unseen noisy speeches. We employ the connectionist temporal classification and the unpaired conditional boundary equilibrium generative adversarial network as the loss function of AAS. AAS is tested on two datasets including additive noise without and with reverberation, Librispeech + DEMAND and CHiME-4. By visualizing the enhanced speech with different loss combinations, we demonstrate the role of each supervision. AAS achieves a lower word error rate than other state-of-the-art methods using the clean speech target in both datasets.
A Scalable Algorithm for Privacy-Preserving Item-based Top-N Recommendation
Venue: arXiv cs.CR 2018
Year: 2018

Recommender systems have become an indispensable component in online services during recent years. Effective recommendation is essential for improving the services of various online business applications. However, serious privacy concerns have been raised on recommender systems requiring the collection of users' private information for recommendation. At the same time, the success of e-commerce has generated massive amounts of information, making scalability a key challenge in the design of recommender systems. As such, it is desirable for recommender systems to protect users' privacy while achieving high-quality recommendations with low-complexity computations. This paper proposes a scalable privacy-preserving item-based top-N recommendation solution, which can achieve high-quality recommendations with reduced computation complexity while ensuring that users' private information is protected. Furthermore, the computation complexity of the proposed method increases slowly as the number of users increases, thus providing high scalability for privacy-preserving recommender systems. More specifically, the proposed approach consists of two key components: (1) MinHash-based similarity estimation and (2) client-side privacy-preserving prediction generation. Our theoretical and experimental analysis using real-world data demonstrates the efficiency and effectiveness of the proposed approach.
On the Resource Consumption of M2M Random Access: Efficiency and Pareto Optimality
Venue: arXiv cs.IT 2018
Year: 2018

The advent of Machine-to-Machine communication has sparked a new wave of interest to random access protocols, especially in application to LTE Random Access (RA). By analogy with classical slotted ALOHA, state-of-the-art models LTE RA as a multi-channel slotted ALOHA. In this letter, we direct the attention to the resource consumption of RA. We show that the consumption is a random variable dependent on the contention parameters. We consider two approaches to include the consumption into RA optimization: by defining resource efficiency and by the means of a bi-objective optimization, where resource consumption and throughput are the competing objectives. We then develop the algorithm to obtain Pareto-optimal RA configuration under resource constraint. We show that the algorithm achieves lower burst resolution delay and higher throughput than the state-of-the-art.
Recurrent Skipping Networks for Entity Alignment
Venue: arXiv cs.CL 2018
Year: 2018

We consider the problem of learning knowledge graph (KG) embeddings for entity alignment (EA). Current methods use the embedding models mainly focusing on triple-level learning, which lacks the ability of capturing long-term dependencies existing in KGs. Consequently, the embedding-based EA methods heavily rely on the amount of prior (known) alignment, due to the identity information in the prior alignment cannot be efficiently propagated from one KG to another. In this paper, we propose RSN4EA (recurrent skipping networks for EA), which leverages biased random walk sampling for generating long paths across KGs and models the paths with a novel recurrent skipping network (RSN). RSN integrates the conventional recurrent neural network (RNN) with residual learning and can largely improve the convergence speed and performance with only a few more parameters. We evaluated RSN4EA on a series of datasets constructed from real-world KGs. Our experimental results showed that it outperformed a number of state-of-the-art embedding-based EA methods and also achieved comparable performance for KG completion.
Risk-Sensitive Reinforcement Learning for URLLC Traffic in Wireless Networks
Venue: arXiv cs.NI 2018
Year: 2018

In this paper, we study the problem of dynamic channel allocation for URLLC traffic in a multi-user multi-channel wireless network where urgent packets have to be successfully transmitted in a timely manner. We formulate the problem as a finite-horizon Markov Decision Process with a stochastic constraint related to the QoS requirement, defined as the packet loss rate for each user. We propose a novel weighted formulation that takes into account both the total expected reward (number of successfully transmitted packets) and the risk which we define as the QoS requirement violation. First, we use the value iteration algorithm to find the optimal policy, which assumes a perfect knowledge of the controller of all the parameters, namely the channel statistics. We then propose a Q-learning algorithm where the controller learns the optimal policy without having knowledge of neither the CSI nor the channel statistics. We illustrate the performance of our algorithms with numerical studies.
Fast High-Dimensional Bilateral and Nonlocal Means Filtering
Venue: arXiv cs.CV 2018
Year: 2018

Existing fast algorithms for bilateral and nonlocal means filtering mostly work with grayscale images. They cannot easily be extended to high-dimensional data such as color and hyperspectral images, patch-based data, flow-fields, etc. In this paper, we propose a fast algorithm for high-dimensional bilateral and nonlocal means filtering. Unlike existing approaches, where the focus is on approximating the data (using quantization) or the filter kernel (via analytic expansions), we locally approximate the kernel using weighted and shifted copies of a Gaussian, where the weights and shifts are inferred from the data. The algorithm emerging from the proposed approximation essentially involves clustering and fast convolutions, and is easy to implement. Moreover, a variant of our algorithm comes with a guarantee (bound) on the approximation error, which is not enjoyed by existing algorithms. We present some results for high-dimensional bilateral and nonlocal means filtering to demonstrate the speed and accuracy of our proposal. Moreover, we also show that our algorithm can outperform state-of-the-art fast approximations in terms of accuracy and timing.
Sets of autoencoders with shared latent spaces
Venue: arXiv cs.CV 2018
Year: 2018

Autoencoders receive latent models of input data. It was shown in recent works that they also estimate probability density functions of the input. This fact makes using the Bayesian decision theory possible. If we obtain latent models of input data for each class or for some points in the space of parameters in a parameter estimation task, we are able to estimate likelihood functions for those classes or points in parameter space. We show how the set of autoencoders solves the recognition problem. Each autoencoder describes its own model or context, a latent vector that presents input data in the latent space may be called treatment in its context. Sharing latent spaces of autoencoders gives a very important property that is the ability to separate treatment and context where the input information is treated through the set of autoencoders. There are two remarkable and most valuable results of this work: a mechanism that shows a possible way of forming abstract concepts and a way of reducing dataset's size during training. These results are confirmed by tests presented in the article.
Local-Encoding-Preserving Secure Network Coding---Part II: Flexible Rate and Security Level
Venue: arXiv cs.IT 2018
Year: 2018

In the two-part paper, we consider the problem of secure network coding when the information rate and the security level can change over time. To efficiently solve this problem, we put forward local-encoding-preserving secure network coding, where a family of secure linear network codes (SLNCs) is called local-encoding-preserving (LEP) if all the SLNCs in this family share a common local encoding kernel at each intermediate node in the network. In this paper (Part II), we first consider the design of a family of LEP SLNCs for a fixed rate and a flexible security level. We present a novel and efficient approach for constructing upon an SLNC that exists an LEP SLNC with the same rate and the security level increased by one. Next, we consider the design of a family of LEP SLNCs for a fixed dimension (equal to the sum of rate and security level) and a flexible pair of rate and security level. We propose another novel approach for designing an SLNC such that the same SLNC can be applied for all the rate and security-level pairs with the fixed dimension. Also, two polynomial-time algorithms are developed for efficient implementations of our two approaches, respectively. Furthermore, we prove that both approaches do not incur any penalty on the required field size for the existence of SLNCs in terms of the best known lower bound by Guang and Yeung. Finally, we consider the ultimate problem of designing a family of LEP SLNCs that can be applied to all possible pairs of rate and security level. By combining the construction of a family of LEP SLNCs for a fixed security level and a flexible rate (obtained in Part I) with the constructions of the two families of LEP SLNCs in the current paper in suitable ways, we can obtain a family of LEP SLNCs that can be applied for all possible pairs of rate and security level. Three possible such constructions are presented.
Towards digitalisation of summative and formative assessments in academic teaching of statistics
Venue: arXiv cs.HC 2018
Year: 2018

Web-based systems for assessment or homework are commonly used in many different domains. Several studies show that these systems can have positive effects on learning outcomes. Many research efforts also have made these systems quite flexible with respect to different item formats and exercise styles. However, there is still a lack of support for complex exercises in several domains at university level. Although there are systems that allow for quite sophisticated operations for generating exercise contents, there is less support for using similar operations for evaluating students' input and for feedback generation. This paper elaborates on filling this gap in the specific case of statistics. We present both the conceptional requirements for this specific domain as well as a fully implemented solution. Furthermore, we report on using this solution for formative and summative assessments in lectures with large numbers of participants at a big university.
Deep feature transfer between localization and segmentation tasks
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we propose a new pre-training scheme for U-net based image segmentation. We first train the encoding arm as a localization network to predict the center of the target, before extending it into a U-net architecture for segmentation. We apply our proposed method to the problem of segmenting the optic disc from fundus photographs. Our work shows that the features learned by encoding arm can be transferred to the segmentation network to reduce the annotation burden. We propose that an approach could have broad utility for medical image segmentation, and alleviate the burden of delineating complex structures by pre-training on annotations that are much easier to acquire.
Hide-and-Seek: A Data Augmentation Technique for Weakly-Supervised Localization and Beyond
Venue: arXiv cs.CV 2018
Year: 2018

We propose 'Hide-and-Seek' a general purpose data augmentation technique, which is complementary to existing data augmentation techniques and is beneficial for various visual recognition tasks. The key idea is to hide patches in a training image randomly, in order to force the network to seek other relevant content when the most discriminative content is hidden. Our approach only needs to modify the input image and can work with any network to improve its performance. During testing, it does not need to hide any patches. The main advantage of Hide-and-Seek over existing data augmentation techniques is its ability to improve object localization accuracy in the weakly-supervised setting, and we therefore use this task to motivate the approach. However, Hide-and-Seek is not tied only to the image localization task, and can generalize to other forms of visual input like videos, as well as other recognition tasks like image classification, temporal action localization, semantic segmentation, emotion recognition, age/gender estimation, and person re-identification. We perform extensive experiments to showcase the advantage of Hide-and-Seek on these various visual recognition problems.
A Model for General Intelligence
Venue: arXiv cs.AI 2018
Year: 2018

The overarching problem in artificial intelligence (AI) is that we do not understand the intelligence process well enough to enable the development of adequate computational models. Much work has been done in AI over the years at lower levels, but a big part of what has been missing involves the high level, abstract, general nature of intelligence. We address this gap by developing a model for general intelligence. To accomplish this, we focus on three basic aspects of intelligence. First, we must realize the general order and nature of intelligence at a high level. Second, we must come to know what these realizations mean with respect to the overall intelligence process. Third, we must describe these realizations as clearly as possible. We propose a hierarchical model to help capture and exploit the order within intelligence. The underlying order involves patterns of signals that become organized, stored and activated in space and time. These patterns can be described using a simple, general hierarchy, with physical signals at the lowest level, information in the middle, and abstract signal representations at the top. This high level perspective provides a big picture that literally helps us see the intelligence process, thereby enabling fundamental realizations, a better understanding and clear descriptions of the intelligence process. The resulting model can be used to support all kinds of information processing across multiple levels of abstraction. As computer technology improves, and as cooperation increases between humans and computers, people will become more efficient and more productive in performing their information processing tasks.
Weighted Upper Edge Cover: Complexity and Approximability
Venue: arXiv cs.DS 2018
Year: 2018

Optimization problems consist of either maximizing or minimizing an objective function. Instead of looking for a maximum solution (resp. minimum solution), one can find a minimum maximal solution (resp. maximum minimal solution). Such "flipping" of the objective function was done for many classical optimization problems. For example, Minimum Vertex Cover becomes Maximum Minimal Vertex Cover, Maximum Independent Set becomes Minimum Maximal Independent Set and so on. In this paper, we propose to study the weighted version of Maximum Minimal Edge Cover called Upper Edge Cover, a problem having application in the genomic sequence alignment. It is well-known that Minimum Edge Cover is polynomial-time solvable and the "flipped" version is NP-hard, but constant approximable. We show that the weighted Upper Edge Cover is much more difficult than Upper Edge Cover because it is not $O(\frac{1}{n^{1/2-\varepsilon}})$ approximable, nor $O(\frac{1}{Δ^{1-\varepsilon}})$ in edge-weighted graphs of size $n$ and maximum degree $Δ$ respectively. Indeed, we give some hardness of approximation results for some special restricted graph classes such as bipartite graphs, split graphs and $k$-trees. We counter-balance these negative results by giving some positive approximation results in specific graph classes.
Quaternion Convolutional Neural Networks for Heterogeneous Image Processing
Venue: arXiv cs.CV 2018
Year: 2018

Convolutional neural networks (CNN) have recently achieved state-of-the-art results in various applications. In the case of image recognition, an ideal model has to learn independently of the training data, both local dependencies between the three components (R,G,B) of a pixel, and the global relations describing edges or shapes, making it efficient with small or heterogeneous datasets. Quaternion-valued convolutional neural networks (QCNN) solved this problematic by introducing multidimensional algebra to CNN. This paper proposes to explore the fundamental reason of the success of QCNN over CNN, by investigating the impact of the Hamilton product on a color image reconstruction task performed from a gray-scale only training. By learning independently both internal and external relations and with less parameters than real valued convolutional encoder-decoder (CAE), quaternion convolutional encoder-decoders (QCAE) perfectly reconstructed unseen color images while CAE produced worst and gray-scale versions.
MAMMO: A Deep Learning Solution for Facilitating Radiologist-Machine Collaboration in Breast Cancer Diagnosis
Venue: arXiv cs.CV 2018
Year: 2018

With an aging and growing population, the number of women requiring either screening or symptomatic mammograms is increasing. To reduce the number of mammograms that need to be read by a radiologist while keeping the diagnostic accuracy the same or better than current clinical practice, we develop Man and Machine Mammography Oracle (MAMMO) - a clinical decision support system capable of triaging mammograms into those that can be confidently classified by a machine and those that cannot be, thus requiring the reading of a radiologist. The first component of MAMMO is a novel multi-view convolutional neural network (CNN) with multi-task learning (MTL). MTL enables the CNN to learn the radiological assessments known to be associated with cancer, such as breast density, conspicuity, suspicion, etc., in addition to learning the primary task of cancer diagnosis. We show that MTL has two advantages: 1) learning refined feature representations associated with cancer improves the classification performance of the diagnosis task and 2) issuing radiological assessments provides an additional layer of model interpretability that a radiologist can use to debug and scrutinize the diagnoses provided by the CNN. The second component of MAMMO is a triage network, which takes as input the radiological assessment and diagnostic predictions of the first network's MTL outputs and determines which mammograms can be correctly and confidently diagnosed by the CNN and which mammograms cannot, thus needing to be read by a radiologist. Results obtained on a private dataset of 8,162 patients show that MAMMO reduced the number of radiologist readings by 42.8% while improving the overall diagnostic accuracy in comparison to readings done by radiologists alone. We analyze the triage of patients decided by MAMMO to gain a better understanding of what unique mammogram characteristics require radiologists' expertise.