OpenRaiser/Intern-Atlas huggingface dataset:
A Unified Iteration Space Transformation Framework for Sparse and Dense Tensor Algebra
Venue: arXiv cs.MS 2019
Year: 2019

We address the problem of optimizing mixed sparse and dense tensor algebra in a compiler. We show that standard loop transformations, such as strip-mining, tiling, collapsing, parallelization and vectorization, can be applied to irregular loops over sparse iteration spaces. We also show how these transformations can be applied to the contiguous value arrays of sparse tensor data structures, which we call their position space, to unlock load-balanced tiling and parallelism. We have prototyped these concepts in the open-source TACO system, where they are exposed as a scheduling API similar to the Halide domain-specific language for dense computations. Using this scheduling API, we show how to optimize mixed sparse/dense tensor algebra expressions, how to generate load-balanced code by scheduling sparse tensor algebra in position space, and how to generate sparse tensor algebra GPU code. Our evaluation shows that our transformations let us generate good code that is competitive with many hand-optimized implementations from the literature.
The Deterministic plus Stochastic Model of the Residual Signal and its Applications
Venue: arXiv cs.SD 2019
Year: 2019

The modeling of speech production often relies on a source-filter approach. Although methods parameterizing the filter have nowadays reached a certain maturity, there is still a lot to be gained for several speech processing applications in finding an appropriate excitation model. This manuscript presents a Deterministic plus Stochastic Model (DSM) of the residual signal. The DSM consists of two contributions acting in two distinct spectral bands delimited by a maximum voiced frequency. Both components are extracted from an analysis performed on a speaker-dependent dataset of pitch-synchronous residual frames. The deterministic part models the low-frequency contents and arises from an orthonormal decomposition of these frames. As for the stochastic component, it is a high-frequency noise modulated both in time and frequency. Some interesting phonetic and computational properties of the DSM are also highlighted. The applicability of the DSM in two fields of speech processing is then studied. First, it is shown that incorporating the DSM vocoder in HMM-based speech synthesis enhances the delivered quality. The proposed approach turns out to significantly outperform the traditional pulse excitation and provides a quality equivalent to STRAIGHT. In a second application, the potential of glottal signatures derived from the proposed DSM is investigated for speaker identification purpose. Interestingly, these signatures are shown to lead to better recognition rates than other glottal-based methods.
Architecting Safe Automated Driving with Legacy Platforms
Venue: arXiv cs.SE 2019
Year: 2019

Modern vehicles have electrical architectures whose complexity grows year after year due to feature growth corresponding to customer expectations. The latest of the expectations, automation of the dynamic driving task however, is poised to bring about some of the largest changes seen so far. In one fell swoop, not only does required functionality for automated driving drastically increase the system complexity, it also removes the fall-back of the human driver who is usually relied upon to handle unanticipated failures after the fact. The need to architect thus requires a greater rigour than ever before, to maintain the level of safety that has been associated with the automotive industry. The work that is part of this thesis has been conducted, in close collaboration with our industrial partner Scania CV AB, within the Vinnova FFI funded project ARCHER. This thesis aims to provide a methodology for architecting during the concept phase of development, using industrial practices and principles including those from safety standards such as ISO 26262. The main contributions of the thesis are in two areas. The first area i.e. Part A contributes, (i) an analysis of the challenges of architecting automated driving, and serves as a motivation for the approach taken in the rest of this thesis, i.e. Part B where the contributions include, (ii) a definition of a viewpoint for functional safety according to the definitions of ISO 42010, (iii) a method to systematically extract information from legacy components and (iv) a process to use legacy information and architect in the presence of uncertainty to provide a work product, the Preliminary Architectural Assumptions (PAA), as required by ISO 26262. The contributions of Part B together comprise a methodology to architect the PAA. <read full abstract in pdf>
Collaborative SLAM based on Wifi Fingerprint Similarity and Motion Information
Venue: arXiv cs.NI 2019
Year: 2019

Simultaneous localization and mapping (SLAM) has been extensively researched in past years particularly with regard to range-based or visual-based sensors. Instead of deploying dedicated devices that use visual features, it is more pragmatic to exploit the radio features to achieve this task, due to their ubiquitous nature and the widespread deployment of Wi-Fi wireless network. This paper presents a novel approach for collaborative simultaneous localization and radio fingerprint mapping (C-SLAM-RF) in large unknown indoor environments. The proposed system uses received signal strengths (RSS) from Wi-Fi access points (AP) in the existing infrastructure and pedestrian dead reckoning (PDR) from a smart phone, without a prior knowledge about map or distribution of AP in the environment. We claim a loop closure based on the similarity of the two radio fingerprints. To further improve the performance, we incorporate the turning motion and assign a small uncertainty value to a loop closure if a matched turning is identified. The experiment was done in an area of 130 meters by 70 meters and the results show that our proposed system is capable of estimating the tracks of four users with an accuracy of 0.6 meters with Tango-based PDR and 4.76 meters with a step counter-based PDR.
CHAMELEON: A Deep Learning Meta-Architecture for News Recommender Systems [Phd. Thesis]
Venue: arXiv cs.IR 2019
Year: 2019

Recommender Systems (RS) have became a popular research topic and, since 2016, Deep Learning methods and techniques have been increasingly explored in this area. News RS are aimed to personalize users experiences and help them discover relevant articles from a large and dynamic search space. The main contribution of this research was named CHAMELEON, a Deep Learning meta-architecture designed to tackle the specific challenges of news recommendation. It consists of a modular reference architecture which can be instantiated using different neural building blocks. As information about users' past interactions is scarce in the news domain, the user context can be leveraged to deal with the user cold-start problem. Articles' content is also important to tackle the item cold-start problem. Additionally, the temporal decay of items (articles) relevance is very accelerated in the news domain. Furthermore, external breaking events may temporally attract global readership attention, a phenomenon generally known as concept drift in machine learning. All those characteristics are explicitly modeled on this research by a contextual hybrid session-based recommendation approach using Recurrent Neural Networks. The task addressed by this research is session-based news recommendation, i.e., next-click prediction using only information available in the current user session. A method is proposed for a realistic temporal offline evaluation of such task, replaying the stream of user clicks and fresh articles being continuously published in a news portal. Experiments performed with two large datasets have shown the effectiveness of the CHAMELEON for news recommendation on many quality factors such as accuracy, item coverage, novelty, and reduced item cold-start problem, when compared to other traditional and state-of-the-art session-based recommendation algorithms.
Medi-Care AI: Predicting Medications From Billing Codes via Robust Recurrent Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we present an effective deep prediction framework based on robust recurrent neural networks (RNNs) to predict the likely therapeutic classes of medications a patient is taking, given a sequence of diagnostic billing codes in their record. Accurately capturing the list of medications currently taken by a given patient is extremely challenging due to undefined errors and omissions. We present a general robust framework that explicitly models the possible contamination through overtime decay mechanism on the input billing codes and noise injection into the recurrent hidden states, respectively. By doing this, billing codes are reformulated into its temporal patterns with decay rates on each medical variable, and the hidden states of RNNs are regularised by random noises which serve as dropout to improved RNNs robustness towards data variability in terms of missing values and multiple errors. The proposed method is extensively evaluated on real health care data to demonstrate its effectiveness in suggesting medication orders from contaminated values.
A Dynamic and Cooperative Tracking System for Crowdfunding
Venue: arXiv cs.SI 2019
Year: 2019

Crowdfunding is an emerging finance platform for creators to fund their efforts by soliciting relatively small contributions from a large number of individuals using the Internet. Due to the unique rules, a campaign succeeds in trading only when it collects adequate funds in a given time. To prevent creators and backers from wasting time and efforts on failing campaigns, dynamically estimating the success probability of a campaign is very important. However, existing crowdfunding systems neither have the mechanism of dynamic predictive tracking, nor provide the real-time campaign status for creators and backers on the platform. To address these issues, we develop a novel system, which contains a dynamic data-driven approach to tracking the success probability and status. We demonstrate the following scenarios using our system. First, users can utilize our system to analyze the emotion of incremental reviews so as to understand backers' perspectives of the campaign in time. Meanwhile, our system visualizes the statistic number of positive and negative reviews. On this basis, our system can dynamically track the success probability of each campaign.
Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms
Venue: arXiv cs.DS 2020
Year: 2020

Let F be a finite set of graphs. In the F-Deletion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k vertices can be deleted from G such that the resulting graph does not contain a graph from F as a minor. F-Deletion is a generic problem and by selecting different sets of forbidden minors F, one can obtain various fundamental problems such as Vertex Cover, Feedback Vertex Set or Treewidth t-Deletion. In this paper we obtain a number of generic algorithmic results about Planar F-Deletion, when F contains at least one planar graph. The highlights of our work are - A constant factor approximation algorithm for the optimization version of Planar F-Deletion. - A randomized linear time and single exponential parameterized algorithm, that is, an algorithm running in time O(2^{O(k)} n), for the parameterized version of Planar F-deletion where all graphs in F are connected. The algorithm can be made deterministic at the cost of making the polynomial factor in the running time n*log^2 n rather than linear. - A polynomial kernel for parameterized Planar F-deletion These algorithms unify, generalize, and improve a multitude of results in the literature. Our main results have several direct applications, but also the methods we develop on the way have applicability beyond the scope of this paper. Our results -- constant factor approximation, polynomial kernelization and FPT algorithms -- are stringed together by a common theme of polynomial time preprocessing.
Elaborating Intersection and Union Types
Venue: arXiv cs.PL 2020
Year: 2020

Designing and implementing typed programming languages is hard. Every new type system feature requires extending the metatheory and implementation, which are often complicated and fragile. To ease this process, we would like to provide general mechanisms that subsume many different features. In modern type systems, parametric polymorphism is fundamental, but intersection polymorphism has gained little traction in programming languages. Most practical intersection type systems have supported only refinement intersections, which increase the expressiveness of types (more precise properties can be checked) without altering the expressiveness of terms; refinement intersections can simply be erased during compilation. In contrast, unrestricted intersections increase the expressiveness of terms, and can be used to encode diverse language features, promising an economy of both theory and implementation. We describe a foundation for compiling unrestricted intersection and union types: an elaboration type system that generates ordinary lambda-calculus terms. The key feature is a Forsythe-like merge construct. With this construct, not all reductions of the source program preserve types; however, we prove that ordinary call-by-value evaluation of the elaborated program corresponds to a type-preserving evaluation of the source program. We also describe a prototype implementation and applications of unrestricted intersections and unions: records, operator overloading, and simulating dynamic typing.
The two-dimensional Gabor function adapted to natural image statistics: A model of simple-cell receptive fields and sparse structure in images
Venue: arXiv cs.CV 2020
Year: 2020

The two-dimensional Gabor function is adapted to natural image statistics, leading to a tractable probabilistic generative model that can be used to model simple-cell receptive-field profiles, or generate basis functions for sparse coding applications. Learning is found to be most pronounced in three Gabor-function parameters representing the size and spatial frequency of the two-dimensional Gabor function, and characterized by a non-uniform probability distribution with heavy tails. All three parameters are found to be strongly correlated: resulting in a basis of multiscale Gabor functions with similar aspect ratios, and size-dependent spatial frequencies. A key finding is that the distribution of receptive-field sizes is scale-invariant over a wide range of values, so there is no characteristic receptive-field size selected by natural image statistics. The Gabor-function aspect ratio is found to be approximately conserved by the learning rules and is therefore not well-determined by natural image statistics. This allows for three distinct solutions: a basis of Gabor functions with sharp orientation resolution at the expense of spatial-frequency resolution; a basis of Gabor functions with sharp spatial-frequency resolution at the expense of orientation resolution; or a basis with unit aspect ratio. Arbitrary mixtures of all three cases are also possible. Two parameters controlling the shape of the marginal distributions in a probabilistic generative model fully account for all three solutions. The best-performing probabilistic generative model for sparse coding applications is found to be a Gaussian copula with Pareto marginal probability density functions.
The Compressed Annotation Matrix: an Efficient Data Structure for Computing Persistent Cohomology
Venue: arXiv cs.CG 2020
Year: 2020

The persistent homology with coefficients in a field F coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substancially the amount of matrix operations. In addition, we propose heuristics to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology.
Distributed k-Means and k-Median Clustering on General Topologies
Venue: arXiv cs.LG 2020
Year: 2020

This paper provides new algorithms for distributed clustering for two popular center-based objectives, k-median and k-means. These algorithms have provable guarantees and improve communication complexity over existing approaches. Following a classic approach in clustering by \cite{har2004coresets}, we reduce the problem of finding a clustering with low cost to the problem of finding a coreset of small size. We provide a distributed method for constructing a global coreset which improves over the previous methods by reducing the communication complexity, and which works over general communication topologies. Experimental results on large scale data sets show that this approach outperforms other coreset-based distributed clustering algorithms.
Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements
Venue: arXiv cs.IT 2020
Year: 2020

Recall the classical hypothesis testing setting with two convex sets of probability distributions P and Q. One receives either n i.i.d. samples from a distribution p in P or from a distribution q in Q and wants to decide from which set the points were sampled. It is known that the optimal exponential rate at which errors decrease can be achieved by a simple maximum-likelihood ratio test which does not depend on p or q, but only on the sets P and Q. We consider an adaptive generalization of this model where the choice of p in P and q in Q can change in each sample in some way that depends arbitrarily on the previous samples. In other words, in the k'th round, an adversary, having observed all the previous samples in rounds 1,...,k-1, chooses p_k in P and q_k in Q, with the goal of confusing the hypothesis test. We prove that even in this case, the optimal exponential error rate can be achieved by a simple maximum-likelihood test that depends only on P and Q. We then show that the adversarial model has applications in hypothesis testing for quantum states using restricted measurements. For example, it can be used to study the problem of distinguishing entangled states from the set of all separable states using only measurements that can be implemented with local operations and classical communication (LOCC). The basic idea is that in our setup, the deleterious effects of entanglement can be simulated by an adaptive classical adversary. We prove a quantum Stein's Lemma in this setting: In many circumstances, the optimal hypothesis testing rate is equal to an appropriate notion of quantum relative entropy between two states. In particular, our arguments yield an alternate proof of Li and Winter's recent strengthening of strong subadditivity for quantum relative entropy.
KaHIP v3.00 -- Karlsruhe High Quality Partitioning -- User Guide
Venue: arXiv cs.DC 2020
Year: 2020

This paper severs as a user guide to the graph partitioning framework KaHIP (Karlsruhe High Quality Partitioning). We give a rough overview of the techniques used within the framework and describe the user interface as well as the file formats used. Moreover, we provide a short description of the current library functions provided within the framework. Since version 3.00 we support multilevel partitioning, memetic algorithms, distributed and shared-memory parallel algorithms, node separator and ordering algorithms, edge partitioning algorithms as well as ILP solvers.
On the Tractability of Un/Satisfiability
Venue: arXiv cs.CC 2020
Year: 2020

This paper shows effectiveness of X3SAT in proving P = NP. This is due to the fact that it is easy to check unsatisfiability of a particular truth assignment. A truth assignment leads to some reductions of clauses by means of "exactly-1 disjunction". The reductions result in a conjunction of literals, called the scope of the assignment. It is proved that this particular truth assignment makes the formula unsatisfiable iff the scope_s is unsatisfiable for some s, which is trivial to check. Then, each literal such that its scope is unsatisfiable is removed from the formula. Therefore, the formula is satisfiable iff the scope of every literal is satisfied.
Modelling serendipity in a computational context
Venue: arXiv cs.AI 2020
Year: 2020

The term serendipity describes a creative process that develops, in context, with the active participation of a creative agent, but not entirely within that agent's control. While a system cannot be made to perform serendipitously on demand, we argue that its $\mathit{serendipity\ potential}$ can be increased by means of a suitable system architecture and other design choices. We distil a unified description of serendipitous occurrences from historical theorisations of serendipity and creativity. This takes the form of a framework with six phases: $\mathit{perception}$, $\mathit{attention}$, $\mathit{interest}$, $\mathit{explanation}$, $\mathit{bridge}$, and $\mathit{valuation}$. We then use this framework to organise a survey of literature in cognitive science, philosophy, and computing, which yields practical definitions of the six phases, along with heuristics for implementation. We use the resulting model to evaluate the serendipity potential of four existing systems developed by others, and two systems previously developed by two of the authors. Most existing research that considers serendipity in a computing context deals with serendipity as a service; here we relate theories of serendipity to the development of autonomous systems and computational creativity practice. We argue that serendipity is not teleologically blind, and outline representative directions for future applications of our model. We conclude that it is feasible to equip computational systems with the potential for serendipity, and that this could be beneficial in varied computational creativity/AI applications, particularly those designed to operate responsively in real-world contexts.
Rational Groupthink
Venue: arXiv cs.GT 2020
Year: 2020

We study how long-lived rational agents learn from repeatedly observing a private signal and each others' actions. With normal signals, a group of any size learns more slowly than just four agents who directly observe each others' private signals in each period. Similar results apply to general signal structures. We identify rational groupthink---in which agents ignore their private signals and choose the same action for long periods of time---as the cause of this failure of information aggregation.
MATLAB based language for generating randomized multiple choice questions
Venue: arXiv cs.CY 2020
Year: 2020

In this work we describe a simple MATLAB based language which allows to create randomized multiple choice questions with minimal effort. This language has been successfully tested at Flinders University by the author in a number of mathematics topics including Numerical Analysis, Abstract Algebra and Partial Differential Equations. The open source code of Spike is available at: https://github.com/NurullaAzamov/Spike. Enquiries about Spike should be sent to azamovnurulla@gmail.com