OpenRaiser/Intern-Atlas huggingface dataset:
Deterministic Distributed Dominating Set Approximation in the CONGEST Model
Venue: arXiv cs.DS 2019
Year: 2019

We develop deterministic approximation algorithms for the minimum dominating set problem in the CONGEST model with an almost optimal approximation guarantee. For $ε>1/{\text{poly}}\log Δ$ we obtain two algorithms with approximation factor $(1+ε)(1+\ln (Δ+1))$ and with runtimes $2^{O(\sqrt{\log n \log\log n})}$ and $O(Δ\cdot\text{poly}\log Δ+\text{poly}\log Δ\log^{*} n)$, respectively. Further we show how dominating set approximations can be deterministically transformed into a connected dominating set in the \CONGEST model while only increasing the approximation guarantee by a constant factor. This results in a deterministic $O(\log Δ)$-approximation algorithm for the minimum connected dominating set with time complexity $2^{O(\sqrt{\log n \log\log n})}$.
Cross-Resolution Face Recognition via Prior-Aided Face Hallucination and Residual Knowledge Distillation
Venue: arXiv cs.CV 2019
Year: 2019

Recent deep learning based face recognition methods have achieved great performance, but it still remains challenging to recognize very low-resolution query face like 28x28 pixels when CCTV camera is far from the captured subject. Such face with very low-resolution is totally out of detail information of the face identity compared to normal resolution in a gallery and hard to find corresponding faces therein. To this end, we propose a Resolution Invariant Model (RIM) for addressing such cross-resolution face recognition problems, with three distinct novelties. First, RIM is a novel and unified deep architecture, containing a Face Hallucination sub-Net (FHN) and a Heterogeneous Recognition sub-Net (HRN), which are jointly learned end to end. Second, FHN is a well-designed tri-path Generative Adversarial Network (GAN) which simultaneously perceives facial structure and geometry prior information, i.e. landmark heatmaps and parsing maps, incorporated with an unsupervised cross-domain adversarial training strategy to super-resolve very low-resolution query image to its 8x larger ones without requiring them to be well aligned. Third, HRN is a generic Convolutional Neural Network (CNN) for heterogeneous face recognition with our proposed residual knowledge distillation strategy for learning discriminative yet generalized feature representation. Quantitative and qualitative experiments on several benchmarks demonstrate the superiority of the proposed model over the state-of-the-arts. Codes and models will be released upon acceptance.
Path Ranking with Attention to Type Hierarchies
Venue: arXiv cs.AI 2019
Year: 2019

The objective of the knowledge base completion problem is to infer missing information from existing facts in a knowledge base. Prior work has demonstrated the effectiveness of path-ranking based methods, which solve the problem by discovering observable patterns in knowledge graphs, consisting of nodes representing entities and edges representing relations. However, these patterns either lack accuracy because they rely solely on relations or cannot easily generalize due to the direct use of specific entity information. We introduce Attentive Path Ranking, a novel path pattern representation that leverages type hierarchies of entities to both avoid ambiguity and maintain generalization. Then, we present an end-to-end trained attention-based RNN model to discover the new path patterns from data. Experiments conducted on benchmark knowledge base completion datasets WN18RR and FB15k-237 demonstrate that the proposed model outperforms existing methods on the fact prediction task by statistically significant margins of 26% and 10%, respectively. Furthermore, quantitative and qualitative analyses show that the path patterns balance between generalization and discrimination.
Operation and Imitation under Safety-Aware Shared Control
Venue: arXiv cs.RO 2019
Year: 2019

We describe a shared control methodology that can, without knowledge of the task, be used to improve a human's control of a dynamic system, be used as a training mechanism, and be used in conjunction with Imitation Learning to generate autonomous policies that recreate novel behaviors. Our algorithm introduces autonomy that assists the human partner by enforcing safety and stability constraints. The autonomous agent has no a priori knowledge of the desired task and therefore only adds control information when there is concern for the safety of the system. We evaluate the efficacy of our approach with a human subjects study consisting of 20 participants. We find that our shared control algorithm significantly improves the rate at which users are able to successfully execute novel behaviors. Experimental results suggest that the benefits of our safety-aware shared control algorithm also extend to the human partner's understanding of the system and their control skill. Finally, we demonstrate how a combination of our safety-aware shared control algorithm and Imitation Learning can be used to autonomously recreate the demonstrated behaviors.
Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
Venue: arXiv cs.DS 2019
Year: 2019

The minimum-weight $2$-edge-connected spanning subgraph (2-ECSS) problem is a natural generalization of the well-studied minimum-weight spanning tree (MST) problem, and it has received considerable attention in the area of network design. The latter problem asks for a minimum-weight subgraph with an edge connectivity of $1$ between each pair of vertices while the former strengthens this edge-connectivity requirement to $2$. Despite this resemblance, the 2-ECSS problem is considerably more complex than MST. While MST admits a linear-time centralized exact algorithm, 2-ECSS is NP-hard and the best known centralized approximation algorithm for it (that runs in polynomial time) gives a $2$-approximation. In this paper, we give a deterministic distributed algorithm with round complexity of $\widetilde{O}(D+\sqrt{n})$ that computes a $(5+ε)$-approximation of 2-ECSS, for any constant $ε>0$. Up to logarithmic factors, this complexity matches the $\widetildeΩ(D+\sqrt{n})$ lower bound that can be derived from Das Sarma et al. [STOC'11], as shown by Censor-Hillel and Dory [OPODIS'17]. Our result is the first distributed constant approximation for 2-ECSS in the nearly optimal time and it improves on a recent randomized algorithm of Dory [PODC'18], which achieved an $O(\log n)$-approximation in $\widetilde{O}(D+\sqrt{n})$ rounds. We also present an alternative algorithm for $O(\log n)$-approximation, whose round complexity is linear in the low-congestion shortcut parameter of the network, following a framework introduced by Ghaffari and Haeupler [SODA'16]. This algorithm has round complexity $\widetilde{O}(D+\sqrt{n})$ in worst-case networks but it provably runs much faster in many well-behaved graph families of interest. For instance, it runs in $\widetilde{O}(D)$ time in planar networks and those with bounded genus, bounded path-width or bounded tree-width.
Taxonomization of Combinatorial Optimization Problems in Fourier Space
Venue: arXiv cs.DM 2019
Year: 2019

We propose and develop a novel framework for analyzing permutation-based combinatorial optimization problems, which could eventually be extended to other types of problems. Our approach is based on the decomposition of the objective functions via the generalized Fourier transform. We characterize the Fourier coefficients of three different problems: the Traveling Salesman Problem, the Linear Ordering Problem and the Quadratic Assignment Problem. This implies that these three problems can be viewed in a homogeneous space, such as the Fourier domain. Our final target would be to create a taxonomy of problem instances, so that functions which are treated similarly under the same search algorithms are grouped together. For this purpose, we simplify the representations of the objective functions by considering them as permutations of the elements of the search space, and study the permutations that are associated with different problems.
Integration of Text-maps in Convolutional Neural Networks for Region Detection among Different Textual Categories
Venue: arXiv cs.CV 2019
Year: 2019

In this work, we propose a new technique that combines appearance and text in a Convolutional Neural Network (CNN), with the aim of detecting regions of different textual categories. We define a novel visual representation of the semantic meaning of text that allows a seamless integration in a standard CNN architecture. This representation, referred to as text-map, is integrated with the actual image to provide a much richer input to the network. Text-maps are colored with different intensities depending on the relevance of the words recognized over the image. Concretely, these words are previously extracted using Optical Character Recognition (OCR) and they are colored according to the probability of belonging to a textual category of interest. In this sense, this solution is especially relevant in the context of item coding for supermarket products, where different types of textual categories must be identified, such as ingredients or nutritional facts. We evaluated our solution in the proprietary item coding dataset of Nielsen Brandbank, which contains more than 10,000 images for train and 2,000 images for test. The reported results demonstrate that our approach focused on visual and textual data outperforms state-of-the-art algorithms only based on appearance, such as standard Faster R-CNN. These enhancements are reflected in precision and recall, which are improved in 42 and 33 points respectively.
Risk Analysis Study of Fully Autonomous Vehicle
Venue: arXiv cs.CR 2019
Year: 2019

Fully autonomous vehicles are emerging vehicular technologies that have gained significant attention in todays research endeavours. Even though it promises to optimize road safety, the proliferation of wireless and sensor technologies makes it susceptible to cyber threats thus dawdling its adoption. The identification of threats and design of apposite security solutions is therefore pertinent to expedite its adoption. In this paper, we analyse the security risks of the communication infrastructure for the fully autonomous vehicle using a subset of the TVRA methodology by ETSI. We described the model of communication infrastructure. This model clarifies the potential communication possibilities of the vehicle. Then we defined the security objectives and identified threats. Furthermore, we classified risks and propose countermeasures to facilitate the design of security solutions. We find that all identified high impact threats emanates from a particular source and required encryption mechanisms as countermeasures. Finally, we discovered that all threats due to an interaction with humans are of serious consequences.
Policy Based Inference in Trick-Taking Card Games
Venue: arXiv cs.AI 2019
Year: 2019

Trick-taking card games feature a large amount of private information that slowly gets revealed through a long sequence of actions. This makes the number of histories exponentially large in the action sequence length, as well as creating extremely large information sets. As a result, these games become too large to solve. To deal with these issues many algorithms employ inference, the estimation of the probability of states within an information set. In this paper, we demonstrate a Policy Based Inference (PI) algorithm that uses player modelling to infer the probability we are in a given state. We perform experiments in the German trick-taking card game Skat, in which we show that this method vastly improves the inference as compared to previous work, and increases the performance of the state-of-the-art Skat AI system Kermit when it is employed into its determinized search algorithm.
An Empirical Study on Post-processing Methods for Word Embeddings
Venue: arXiv cs.LG 2019
Year: 2019

Word embeddings learnt from large corpora have been adopted in various applications in natural language processing and served as the general input representations to learning systems. Recently, a series of post-processing methods have been proposed to boost the performance of word embeddings on similarity comparison and analogy retrieval tasks, and some have been adapted to compose sentence representations. The general hypothesis behind these methods is that by enforcing the embedding space to be more isotropic, the similarity between words can be better expressed. We view these methods as an approach to shrink the covariance/gram matrix, which is estimated by learning word vectors, towards a scaled identity matrix. By optimising an objective in the semi-Riemannian manifold with Centralised Kernel Alignment (CKA), we are able to search for the optimal shrinkage parameter, and provide a post-processing method to smooth the spectrum of learnt word vectors which yields improved performance on downstream tasks.
Deep Multi-Index Hashing for Person Re-Identification
Venue: arXiv cs.CV 2019
Year: 2019

Traditional person re-identification (ReID) methods typically represent person images as real-valued features, which makes ReID inefficient when the gallery set is extremely large. Recently, some hashing methods have been proposed to make ReID more efficient. However, these hashing methods will deteriorate the accuracy in general, and the efficiency of them is still not high enough. In this paper, we propose a novel hashing method, called deep multi-index hashing (DMIH), to improve both efficiency and accuracy for ReID. DMIH seamlessly integrates multi-index hashing and multi-branch based networks into the same framework. Furthermore, a novel block-wise multi-index hashing table construction approach and a search-aware multi-index (SAMI) loss are proposed in DMIH to improve the search efficiency. Experiments on three widely used datasets show that DMIH can outperform other state-of-the-art baselines, including both hashing methods and real-valued methods, in terms of both efficiency and accuracy.
An Intelligent Monitoring System of Vehicles on Highway Traffic
Venue: arXiv cs.CV 2019
Year: 2019

Vehicle speed monitoring and management of highways is the critical problem of the road in this modern age of growing technology and population. A poor management results in frequent traffic jam, traffic rules violation and fatal road accidents. Using traditional techniques of RADAR, LIDAR and LASAR to address this problem is time-consuming, expensive and tedious. This paper presents an efficient framework to produce a simple, cost efficient and intelligent system for vehicle speed monitoring. The proposed method uses an HD (High Definition) camera mounted on the road side either on a pole or on a traffic signal for recording video frames. On the basis of these frames, a vehicle can be tracked by using radius growing method, and its speed can be calculated by calculating vehicle mask and its displacement in consecutive frames. The method uses pattern recognition, digital image processing and mathematical techniques for vehicle detection, tracking and speed calculation. The validity of the proposed model is proved by testing it on different highways.
Attention-based Supply-Demand Prediction for Autonomous Vehicles
Venue: arXiv cs.LG 2019
Year: 2019

As one of the important functions of the intelligent transportation system (ITS), supply-demand prediction for autonomous vehicles provides a decision basis for its control. In this paper, we present two prediction models (i.e. ARLP model and Advanced ARLP model) based on two system environments that only the current day's historical data is available or several days' historical data are available. These two models jointly consider the spatial, temporal, and semantic relations. Spatial dependency is captured with residual network and dimension reduction. Short term temporal dependency is captured with LSTM. Long term temporal dependency and temporal shifting are captured with LSTM and attention mechanism. Semantic dependency is captured with multi-attention mechanism and autocorrelation coefficient method. Extensive experiments show that our frameworks provide more accurate and stable prediction results than the existing methods.
Using Social Choice Theory to Finalize Architectural Decisions
Venue: arXiv cs.SE 2019
Year: 2019

Unbiased and objective architectural design decisions are crucial for the success of a software development project. Stakeholder inputs play an important role in arriving at such design decisions. However, the stakeholders may act in a biased manner in order to ensure that their requirements and concerns are addressed in a specific way in the software. Most of the existing methods of architectural decision-making do not adequately account for such biased behaviour of stakeholders. We view the software architecture design as a collective decision making (CDM) problem in social choice theory, and introduce the central ideas of mechanism design to our field. Our contributions are twofold: i) Using the impossibility results from social choice theory, we show that a rational stakeholder can game, to her advantage, almost every known method of software architecture decision making. ii) We also show that if the architect is willing to bear the extra cost of giving suitable incentives to stakeholders, then architectural decision making can be protected from strategic (biased) manipulations. For achieving this objective, we introduce the Vickrey-Clarke-Groves (VCG) mechanism from social choice theory to the software architecture domain. We illustrate our contributions by comparing and using the examples drawn from the well-known CBAM method of architectural decision making.
The Impact of GPU DVFS on the Energy and Performance of Deep Learning: an Empirical Study
Venue: arXiv cs.PF 2019
Year: 2019

Over the past years, great progress has been made in improving the computing power of general-purpose graphics processing units (GPGPUs), which facilitates the prosperity of deep neural networks (DNNs) in multiple fields like computer vision and natural language processing. A typical DNN training process repeatedly updates tens of millions of parameters, which not only requires huge computing resources but also consumes significant energy. In order to train DNNs in a more energy-efficient way, we empirically investigate the impact of GPU Dynamic Voltage and Frequency Scaling (DVFS) on the energy consumption and performance of deep learning. Our experiments cover a wide range of GPU architectures, DVFS settings, and DNN configurations. We observe that, compared to the default core frequency settings of three tested GPUs, the optimal core frequency can help conserve 8.7%$\sim$23.1% energy consumption for different DNN training cases. Regarding the inference, the benefits vary from 19.6%$\sim$26.4%. Our findings suggest that GPU DVFS has great potentials to help develop energy efficient DNN training/inference schemes.
Does the $h_α$ index reinforce the Matthew effect in science? Agent-based simulations using Stata and R
Venue: arXiv cs.DL 2019
Year: 2019

Recently, Hirsch (2019a) proposed a new variant of the h index called the $h_α$ index. He formulated as follows: "we define the $h_α$ index of a scientist as the number of papers in the h-core of the scientist (i.e. the set of papers that contribute to the h-index of the scientist) where this scientist is the $α$-author" (p. 673). The $h_α$ index was criticized by Leydesdorff, Bornmann, and Opthof (2019). One of their most important points is that the index reinforces the Matthew effect in science. We address this point in the current study using a recently developed Stata command (h_index) and R package (hindex), which can be used to simulate h index and $h_α$index applications in research evaluation. The user can investigate under which conditions $h_α$ reinforces the Matthew effect. The results of our study confirm what Leydesdorff et al. (2019) expected: the $h_α$ index reinforces the Matthew effect. This effect can be intensified if strategic behavior of the publishing scientists and cumulative advantage effects are additionally considered in the simulation.
A Rate-Distortion Framework for Explaining Neural Network Decisions
Venue: arXiv cs.LG 2019
Year: 2019

We formalise the widespread idea of interpreting neural network decisions as an explicit optimisation problem in a rate-distortion framework. A set of input features is deemed relevant for a classification decision if the expected classifier score remains nearly constant when randomising the remaining features. We discuss the computational complexity of finding small sets of relevant features and show that the problem is complete for $\mathsf{NP}^\mathsf{PP}$, an important class of computational problems frequently arising in AI tasks. Furthermore, we show that it even remains $\mathsf{NP}$-hard to only approximate the optimal solution to within any non-trivial approximation factor. Finally, we consider a continuous problem relaxation and develop a heuristic solution strategy based on assumed density filtering for deep ReLU neural networks. We present numerical experiments for two image classification data sets where we outperform established methods in particular for sparse explanations of neural network decisions.
Autonomous Interpretation of Demonstrations for Modification of Dynamical Movement Primitives
Venue: arXiv cs.RO 2019
Year: 2019

The concept of dynamical movement primitives (DMPs) has become popular for modeling of motion, commonly applied to robots. This paper presents a framework that allows a robot operator to adjust DMPs in an intuitive way. Given a generated trajectory with a faulty last part, the operator can use lead-through programming to demonstrate a corrective trajectory. A modified DMP is formed, based on the first part of the faulty trajectory and the last part of the corrective one. A real-time application is presented and verified experimentally.
Proving Non-Termination via Loop Acceleration
Venue: arXiv cs.LO 2019
Year: 2019

We present the first approach to prove non-termination of integer programs that is based on loop acceleration. If our technique cannot show non-termination of a loop, it tries to accelerate it instead in order to find paths to other non-terminating loops automatically. The prerequisites for our novel loop acceleration technique generalize a simple yet effective non-termination criterion. Thus, we can use the same program transformations to facilitate both non-termination proving and loop acceleration. In particular, we present a novel invariant inference technique that is tailored to our approach. An extensive evaluation of our fully automated tool LoAT shows that it is competitive with the state of the art.
The Largest Contained Quadrilateral and the Smallest Enclosing Parallelogram of a Convex Polygon
Venue: arXiv cs.CG 2019
Year: 2019

We present a linear-time algorithm for finding the quadrilateral of largest area contained in a convex polygon, and we show that it is closely related to an old algorithm for the smallest enclosing parallelogram of a convex polygon.