OpenRaiser/Intern-Atlas huggingface dataset:
Fair Kernel Regression via Fair Feature Embedding in Kernel Space
Venue: arXiv cs.LG 2019
Year: 2019

In recent years, there have been significant efforts on mitigating unethical demographic biases in machine learning methods. However, very little is done for kernel methods. In this paper, we propose a new fair kernel regression method via fair feature embedding (FKR-F$^2$E) in kernel space. Motivated by prior works on feature selection in kernel space and feature processing for fair machine learning, we propose to learn fair feature embedding functions that minimize demographic discrepancy of feature distributions in kernel space. Compared to the state-of-the-art fair kernel regression method and several baseline methods, we show FKR-F$^2$E achieves significantly lower prediction disparity across three real-world data sets.
FPCNet: Fast Pavement Crack Detection Network Based on Encoder-Decoder Architecture
Venue: arXiv cs.CV 2019
Year: 2019

Timely, accurate and automatic detection of pavement cracks is necessary for making cost-effective decisions concerning road maintenance. Conventional crack detection algorithms focus on the design of single or multiple crack features and classifiers. However, complicated topological structures, varying degrees of damage and oil stains make the design of crack features difficult. In addition, the contextual information around a crack is not investigated extensively in the design process. Accordingly, these design features have limited discriminative adaptability and cannot fuse effectively with the classifiers. To solve these problems, this paper proposes a deep learning network for pavement crack detection. Using the Encoder-Decoder structure, crack characteristics with multiple contexts are automatically learned, and end-to-end crack detection is achieved. Specifically, we first propose the Multi-Dilation (MD) module, which can synthesize the crack features of multiple context sizes via dilated convolution with multiple rates. The crack MD features obtained in this module can describe cracks of different widths and topologies. Next, we propose the SE-Upsampling (SEU) module, which uses the Squeeze-and-Excitation learning operation to optimize the MD features. Finally, the above two modules are integrated to develop the fast crack detection network, namely, FPCNet. This network continuously optimizes the MD features step-by-step to realize fast pixel-level crack detection. Experiments are conducted on challenging public CFD datasets and G45 crack datasets involving various crack types under different shooting conditions. The distinct performance and speed improvements over all the datasets demonstrate that the proposed method outperforms other state-of-the-art crack detection methods.
Hardness of Bichromatic Closest Pair with Jaccard Similarity
Venue: arXiv cs.CC 2019
Year: 2019

Consider collections $\mathcal{A}$ and $\mathcal{B}$ of red and blue sets, respectively. Bichromatic Closest Pair is the problem of finding a pair from $\mathcal{A}\times \mathcal{B}$ that has similarity higher than a given threshold according to some similarity measure. Our focus here is the classic Jaccard similarity $|\textbf{a}\cap \textbf{b}|/|\textbf{a}\cup \textbf{b}|$ for $(\textbf{a},\textbf{b})\in \mathcal{A}\times \mathcal{B}$. We consider the approximate version of the problem where we are given thresholds $j_1>j_2$ and wish to return a pair from $\mathcal{A}\times \mathcal{B}$ that has Jaccard similarity higher than $j_2$ if there exists a pair in $\mathcal{A}\times \mathcal{B}$ with Jaccard similarity at least $j_1$. The classic locality sensitive hashing (LSH) algorithm of Indyk and Motwani (STOC '98), instantiated with the MinHash LSH function of Broder et al., solves this problem in $\tilde O(n^{2-δ})$ time if $j_1\ge j_2^{1-δ}$. In particular, for $δ=Ω(1)$, the approximation ratio $j_1/j_2=1/j_2^δ$ increases polynomially in $1/j_2$. In this paper we give a corresponding hardness result. Assuming the Orthogonal Vectors Conjecture (OVC), we show that there cannot be a general solution that solves the Bichromatic Closest Pair problem in $O(n^{2-Ω(1)})$ time for $j_1/j_2=1/j_2^{o(1)}$. Specifically, assuming OVC, we prove that for any $δ>0$ there exists an $\varepsilon>0$ such that Bichromatic Closest Pair with Jaccard similarity requires time $Ω(n^{2-δ})$ for any choice of thresholds $j_2<j_1<1-δ$, that satisfy $j_1\le j_2^{1-\varepsilon}$.
Learning a Domain-Invariant Embedding for Unsupervised Domain Adaptation Using Class-Conditioned Distribution Alignment
Venue: arXiv cs.LG 2019
Year: 2019

We address the problem of unsupervised domain adaptation (UDA) by learning a cross-domain agnostic embedding space, where the distance between the probability distributions of the two source and target visual domains is minimized. We use the output space of a shared cross-domain deep encoder to model the embedding space anduse the Sliced-Wasserstein Distance (SWD) to measure and minimize the distance between the embedded distributions of two source and target domains to enforce the embedding to be domain-agnostic.Additionally, we use the source domain labeled data to train a deep classifier from the embedding space to the label space to enforce the embedding space to be discriminative.As a result of this training scheme, we provide an effective solution to train the deep classification network on the source domain such that it will generalize well on the target domain, where only unlabeled training data is accessible. To mitigate the challenge of class matching, we also align corresponding classes in the embedding space by using high confidence pseudo-labels for the target domain, i.e. assigning the class for which the source classifier has a high prediction probability. We provide experimental results on UDA benchmark tasks to demonstrate that our method is effective and leads to state-of-the-art performance.
Min-Cost Flow in Unit-Capacity Planar Graphs
Venue: arXiv cs.DS 2019
Year: 2019

In this paper we give an $\widetilde{O}((nm)^{2/3}\log C)$ time algorithm for computing min-cost flow (or min-cost circulation) in unit capacity planar multigraphs where edge costs are integers bounded by $C$. For planar multigraphs, this improves upon the best known algorithms for general graphs: the $\widetilde{O}(m^{10/7}\log C)$ time algorithm of Cohen et al. [SODA 2017], the $O(m^{3/2}\log(nC))$ time algorithm of Gabow and Tarjan [SIAM J. Comput. 1989] and the $\widetilde{O}(\sqrt{n}m \log C)$ time algorithm of Lee and Sidford [FOCS 2014]. In particular, our result constitutes the first known fully combinatorial algorithm that breaks the $\widetilde{O}(m^{3/2})$ time barrier for min-cost flow problem in planar graphs. To obtain our result we first give a very simple successive shortest paths based scaling algorithm for unit-capacity min-cost flow problem that does not explicitly operate on dual variables. This algorithm also runs in $\widetilde{O}(m^{3/2}\log{C})$ time for general graphs, and, to the best of our knowledge, it has not been described before. We subsequently show how to implement this algorithm faster on planar graphs using well-established tools: $r$-divisions and efficient algorithms for computing (shortest) paths in so-called dense distance graphs.
Discovering Communities of Community Discovery
Venue: arXiv cs.SI 2019
Year: 2019

Discovering communities in complex networks means grouping nodes similar to each other, to uncover latent information about them. There are hundreds of different algorithms to solve the community detection task, each with its own understanding and definition of what a "community" is. Dozens of review works attempt to order such a diverse landscape -- classifying community discovery algorithms by the process they employ to detect communities, by their explicitly stated definition of community, or by their performance on a standardized task. In this paper, we classify community discovery algorithms according to a fourth criterion: the similarity of their results. We create an Algorithm Similarity Network (ASN), whose nodes are the community detection approaches, connected if they return similar groupings. We then perform community detection on this network, grouping algorithms that consistently return the same partitions or overlapping coverage over a span of more than one thousand synthetic and real world networks. This paper is an attempt to create a similarity-based classification of community detection algorithms based on empirical data. It improves over the state of the art by comparing more than seventy approaches, discovering that the ASN contains well-separated groups, making it a sensible tool for practitioners, aiding their choice of algorithms fitting their analytic needs.
Revisiting local time semantics for networks of timed automata
Venue: arXiv cs.LO 2019
Year: 2019

We investigate a zone based approach for the reachability problem in timed automata. The challenge is to alleviate the size explosion of the search space when considering networks of timed automata working in parallel. In the timed setting this explosion is particularly visible as even different interleavings of local actions of processes may lead to different zones. Salah et al. in 2006 have shown that the union of all these different zones is also a zone. This observation was used in an algorithm which from time to time detects and aggregates these zones into a single zone. We show that such aggregated zones can be calculated more efficiently using the local time semantics and the related notion of local zones proposed by Bengtsson et al. in 1998. Next, we point out a flaw in the existing method to ensure termination of the local zone graph computation. We fix this with a new algorithm that builds the local zone graph and uses abstraction techniques over (standard) zones for termination. We evaluate our algorithm on standard examples. On various examples, we observe an order of magnitude decrease in the search space. On the other examples, the algorithm performs like the standard zone algorithm.
Experience Management in Multi-player Games
Venue: arXiv cs.HC 2019
Year: 2019

Experience Management studies AI systems that automatically adapt interactive experiences such as games to tailor to specific players and to fulfill design goals. Although it has been explored for several decades, existing work in experience management has mostly focused on single-player experiences. This paper is a first attempt at identifying the main challenges to expand EM to multi-player/multi-user games or experiences. We also make connections to related areas where solutions for similar problems have been proposed (especially group recommender systems) and discusses the potential impact and applications of multi-player EM.
A Probabilistic Approach to Model SIC based RACH mechanism for Massive Machine Type Communications in Cellular Networks
Venue: arXiv cs.NI 2019
Year: 2019

In a cellular Internet of Things, burst transmissions from millions of machine type communications (MTC) devices can result in channel congestion. The main bottleneck in such scenario is inefficient random access channel (RACH) mechanism that is used to attach MTC devices to a base station (BS). To address this issue of congestion in RACH mechanism, 3GPP has proposed an extended access barring (3GPP-EAB) mechanism. However, several works indicate that the performance of the 3GPP-EAB mechanism can be further improved. In this work, a successive interference cancellation (SIC) based RACH mechanism is considered to significantly increase the success rate and reduce congestion. In the proposed mechanism, the devices are allowed to transmit repeatedly for a finite number of times in a given cycle, and thereafter, the success rate is improved by applying back-and-forth SIC at the BS. A novel probabilistic approach of the proposed mechanism is presented with all transition and steady-state probabilities. Further, the probability of SIC for a given slot is derived. Through extensive numerical results, it is shown that the proposed mechanism significantly outperforms the existing ones in terms of the success rate. Moreover, to obtain the maximum success rate, the optimum number of devices to be entered in a cycle is also calculated.
Neuron ranking -- an informed way to condense convolutional neural networks architecture
Venue: arXiv cs.LG 2019
Year: 2019

Convolutional neural networks (CNNs) in recent years have made a dramatic impact in science, technology and industry, yet the theoretical mechanism of CNN architecture design remains surprisingly vague. The CNN neurons, including its distinctive element, convolutional filters, are known to be learnable features, yet their individual role in producing the output is rather unclear. The thesis of this work is that not all neurons are equally important and some of them contain more useful information to perform a given task . Consequently, we quantify the significance of each filter and rank its importance in describing input to produce the desired output. This work presents two different methods: (1) a game theoretical approach based on Shapley value which computes the marginal contribution of each filter; and (2) a probabilistic approach based on what-we-call, the Importance switch using variational inference. Strikingly, these two vastly different methods produce similar experimental results, confirming the general theory that some of the filters are inherently more important that the others. The learned ranks can be readily useable for network compression and interpretability.
Measuring the Data Efficiency of Deep Learning Methods
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we propose a new experimental protocol and use it to benchmark the data efficiency --- performance as a function of training set size --- of two deep learning algorithms, convolutional neural networks (CNNs) and hierarchical information-preserving graph-based slow feature analysis (HiGSFA), for tasks in classification and transfer learning scenarios. The algorithms are trained on different-sized subsets of the MNIST and Omniglot data sets. HiGSFA outperforms standard CNN networks when the models are trained on 50 and 200 samples per class for MNIST classification. In other cases, the CNNs perform better. The results suggest that there are cases where greedy, locally optimal bottom-up learning is equally or more powerful than global gradient-based learning.
Spine-Inspired Continuum Soft Exoskeleton for Stoop Lifting Assistance
Venue: arXiv cs.RO 2019
Year: 2019

Back injuries are the most prevalent work-related musculoskeletal disorders and represent a major cause of disability. Although innovations in wearable robots aim to alleviate this hazard, the majority of existing exoskeletons are obtrusive because the rigid linkage design limits natural movement, thus causing ergonomic risk. Moreover, these existing systems are typically only suitable for one type of movement assistance, not ubiquitous for a wide variety of activities. To fill in this gap, this paper presents a new wearable robot design approach continuum soft exoskeleton. This spine-inspired wearable robot is unobtrusive and assists both squat and stoops while not impeding walking motion. To tackle the challenge of the unique anatomy of spine that is inappropriate to be simplified as a single degree of freedom joint, our robot is conformal to human anatomy and it can reduce multiple types of forces along the human spine such as the spinae muscle force, shear, and compression force of the lumbar vertebrae. We derived kinematics and kinetics models of this mechanism and established an analytical biomechanics model of human-robot interaction. Quantitative analysis of disc compression force, disc shear force and muscle force was performed in simulation. We further developed a virtual impedance control strategy to deliver force control and compensate hysteresis of Bowden cable transmission. The feasibility of the prototype was experimentally tested on three healthy subjects. The root mean square error of force tracking is 6.63 N (3.3 % of the 200N peak force) and it demonstrated that it can actively control the stiffness to the desired value. This continuum soft exoskeleton represents a feasible solution with the potential to reduce back pain for multiple activities and multiple forces along the human spine.
Explaining Predictions from Tree-based Boosting Ensembles
Venue: arXiv cs.LG 2019
Year: 2019

Understanding how "black-box" models arrive at their predictions has sparked significant interest from both within and outside the AI community. Our work focuses on doing this by generating local explanations about individual predictions for tree-based ensembles, specifically Gradient Boosting Decision Trees (GBDTs). Given a correctly predicted instance in the training set, we wish to generate a counterfactual explanation for this instance, that is, the minimal perturbation of this instance such that the prediction flips to the opposite class. Most existing methods for counterfactual explanations are (1) model-agnostic, so they do not take into account the structure of the original model, and/or (2) involve building a surrogate model on top of the original model, which is not guaranteed to represent the original model accurately. There exists a method specifically for random forests; we wish to extend this method for GBDTs. This involves accounting for (1) the sequential dependency between trees and (2) training on the negative gradients instead of the original labels.
MetaAnalysis of Methods for Scaling Blockchain Technology for Automotive Uses
Venue: arXiv cs.CR 2019
Year: 2019

The automotive industry has seen an increased need for connectivity, both as a result of the advent of autonomous driving and the rise of connected cars and truck fleets. This shift has led to issues such as trusted coordination and a wider attack surface have come to light, leading to higher costs and bureaucratic interventions. Due to the increasing adoption of connected vehicles, as well as other connected infrastructure, trustless peer to peer systems including blockchain are being explored as potential solution to this efficiency problem. All the while, scalability is still a significant concern for industry players. Current blockchain based systems have difficulty scaling: Bitcoin can only process seven transactions per second (tx/s) whereas Ethereum's fifteen tx/s is not a major improvement. Combined with the high cost of consensus and low throughput, such platforms are unusable with the mobility sector. This paper will address the latest advances in the field that aim to resolve parts of this problem as well as inform its readers about the scalability technologies that could push blockchain automotive infrastructure into the mainstream. This paper will also introduce the theoretical tools and advancements that, if implemented, could bring the mobility industry closer toward adopting efficient, scalable, and cost effective decentralized solutions.
Primate Face Identification in the Wild
Venue: arXiv cs.CV 2019
Year: 2019

Ecological imbalance owing to rapid urbanization and deforestation has adversely affected the population of several wild animals. This loss of habitat has skewed the population of several non-human primate species like chimpanzees and macaques and has constrained them to co-exist in close proximity of human settlements, often leading to human-wildlife conflicts while competing for resources. For effective wildlife conservation and conflict management, regular monitoring of population and of conflicted regions is necessary. However, existing approaches like field visits for data collection and manual analysis by experts is resource intensive, tedious and time consuming, thus necessitating an automated, non-invasive, more efficient alternative like image based facial recognition. The challenge in individual identification arises due to unrelated factors like pose, lighting variations and occlusions due to the uncontrolled environments, that is further exacerbated by limited training data. Inspired by human perception, we propose to learn representations that are robust to such nuisance factors and capture the notion of similarity over the individual identity sub-manifolds. The proposed approach, Primate Face Identification (PFID), achieves this by training the network to distinguish between positive and negative pairs of images. The PFID loss augments the standard cross entropy loss with a pairwise loss to learn more discriminative and generalizable features, thus making it appropriate for other related identification tasks like open-set, closed set and verification. We report state-of-the-art accuracy on facial recognition of two primate species, rhesus macaques and chimpanzees under the four protocols of classification, verification, closed-set identification and open-set recognition.
What is the Benefit of Code-domain NOMA in Massive MIMO?
Venue: arXiv cs.IT 2019
Year: 2019

In overloaded Massive MIMO systems, wherein the number K of user equipments (UEs) exceeds the number of base station antennas M, it has recently been shown that non-orthogonal multiple access (NOMA) can increase performance. This paper aims at identifying cases of the classical operating regime K < M, where code-domain NOMA can also improve the spectral efficiency of Massive MIMO. Particular attention is given to use cases in which poor favorable propagation conditions are experienced. Numerical results show that Massive MIMO with planar antenna arrays can benefit from NOMA in practical scenarios where the UEs are spatially close to each other.
A Unified Framework of Online Learning Algorithms for Training Recurrent Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

We present a framework for compactly summarizing many recent results in efficient and/or biologically plausible online training of recurrent neural networks (RNN). The framework organizes algorithms according to several criteria: (a) past vs. future facing, (b) tensor structure, (c) stochastic vs. deterministic, and (d) closed form vs. numerical. These axes reveal latent conceptual connections among several recent advances in online learning. Furthermore, we provide novel mathematical intuitions for their degree of success. Testing various algorithms on two synthetic tasks shows that performances cluster according to our criteria. Although a similar clustering is also observed for gradient alignment, alignment with exact methods does not alone explain ultimate performance, especially for stochastic algorithms. This suggests the need for better comparison metrics.