OpenRaiser/Intern-Atlas huggingface dataset:
Graph Pattern Matching Preserving Label-Repetition Constraints
Venue: arXiv cs.DB 2018
Year: 2018

Graph pattern matching is a routine process for a wide variety of applications such as social network analysis. It is typically defined in terms of subgraph isomorphism which is NP-Complete. To lower its complexity, many extensions of graph simulation have been proposed which focus on some topological constraints of pattern graphs that can be preserved in polynomial-time over data graphs. We discuss in this paper the satisfaction of a new topological constraint, called Label-Repetition constraint. To the best of our knowledge, existing polynomial approaches fail to preserve this constraint, and moreover, one can adopt only subgraph isomorphism for this end which is cost-prohibitive. We present first a necessary and sufficient condition that a data subgraph must satisfy to preserve the Label-Repetition constraints of the pattern graph. Furthermore, we define matching based on a notion of triple simulation, an extension of graph simulation by considering the new topological constraint. We show that with this extension, graph pattern matching can be performed in polynomial-time, by providing such an algorithm. Our algorithm is sub-quadratic in the size of data graphs only, and quartic in general. We show that our results can be combined with orthogonal approaches for more expressive graph pattern matching.
Nonuniform abstractions, refinement and controller synthesis with novel BDD encodings
Venue: arXiv cs.SY 2018
Year: 2018

This paper presents a control synthesis algorithm for dynamical systems to satisfy specifications given in a fragment of linear temporal logic. It is based on an abstraction-refinement scheme with nonuniform partitions of the state space. A novel encoding of the resulting transition system is proposed that uses binary decision diagrams for efficiency. We discuss several factors affecting scalability and present some benchmark results demonstrating the effectiveness of the new encodings. These ideas are also being implemented on a publicly available prototype tool, ARCS, that we briefly introduce in the paper.
Combating catastrophic forgetting with developmental compression
Venue: arXiv cs.AI 2018
Year: 2018

Generally intelligent agents exhibit successful behavior across problems in several settings. Endemic in approaches to realize such intelligence in machines is catastrophic forgetting: sequential learning corrupts knowledge obtained earlier in the sequence, or tasks antagonistically compete for system resources. Methods for obviating catastrophic forgetting have sought to identify and preserve features of the system necessary to solve one problem when learning to solve another, or to enforce modularity such that minimally overlapping sub-functions contain task specific knowledge. While successful, both approaches scale poorly because they require larger architectures as the number of training instances grows, causing different parts of the system to specialize for separate subsets of the data. Here we present a method for addressing catastrophic forgetting called developmental compression. It exploits the mild impacts of developmental mutations to lessen adverse changes to previously-evolved capabilities and `compresses' specialized neural networks into a generalized one. In the absence of domain knowledge, developmental compression produces systems that avoid overt specialization, alleviating the need to engineer a bespoke system for every task permutation and suggesting better scalability than existing approaches. We validate this method on a robot control problem and hope to extend this approach to other machine learning domains in the future.
Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion
Venue: arXiv cs.IT 2018
Year: 2018

The Euclidean distance geometry problem arises in a wide variety of applications, from determining molecular conformations in computational chemistry to localization in sensor networks. When the distance information is incomplete, the problem can be formulated as a nuclear norm minimization problem. In this paper, this minimization program is recast as a matrix completion problem of a low-rank $r$ Gram matrix with respect to a suitable basis. The well known restricted isometry property can not be satisfied in this scenario. Instead, a dual basis approach is introduced to theoretically analyze the reconstruction problem. If the Gram matrix satisfies certain coherence conditions with parameter $ν$, the main result shows that the underlying configuration of $n$ points can be recovered with very high probability from $O(nrν\log^{2}(n))$ uniformly random samples. Computationally, simple and fast algorithms are designed to solve the Euclidean distance geometry problem. Numerical tests on different three dimensional data and protein molecules validate effectiveness and efficiency of the proposed algorithms.
Cross-Modal Retrieval with Implicit Concept Association
Venue: arXiv cs.CV 2018
Year: 2018

Traditional cross-modal retrieval assumes explicit association of concepts across modalities, where there is no ambiguity in how the concepts are linked to each other, e.g., when we do the image search with a query "dogs", we expect to see dog images. In this paper, we consider a different setting for cross-modal retrieval where data from different modalities are implicitly linked via concepts that must be inferred by high-level reasoning; we call this setting implicit concept association. To foster future research in this setting, we present a new dataset containing 47K pairs of animated GIFs and sentences crawled from the web, in which the GIFs depict physical or emotional reactions to the scenarios described in the text (called "reaction GIFs"). We report on a user study showing that, despite the presence of implicit concept association, humans are able to identify video-sentence pairs with matching concepts, suggesting the feasibility of our task. Furthermore, we propose a novel visual-semantic embedding network based on multiple instance learning. Unlike traditional approaches, we compute multiple embeddings from each modality, each representing different concepts, and measure their similarity by considering all possible combinations of visual-semantic embeddings in the framework of multiple instance learning. We evaluate our approach on two video-sentence datasets with explicit and implicit concept association and report competitive results compared to existing approaches on cross-modal retrieval.
Benchmark data and method for real-time people counting in cluttered scenes using depth sensors
Venue: arXiv cs.CV 2018
Year: 2018

Vision-based automatic counting of people has widespread applications in intelligent transportation systems, security, and logistics. However, there is currently no large-scale public dataset for benchmarking approaches on this problem. This work fills this gap by introducing the first real-world RGB-D People Counting DataSet (PCDS) containing over 4,500 videos recorded at the entrance doors of buses in normal and cluttered conditions. It also proposes an efficient method for counting people in real-world cluttered scenes related to public transportations using depth videos. The proposed method computes a point cloud from the depth video frame and re-projects it onto the ground plane to normalize the depth information. The resulting depth image is analyzed for identifying potential human heads. The human head proposals are meticulously refined using a 3D human model. The proposals in each frame of the continuous video stream are tracked to trace their trajectories. The trajectories are again refined to ascertain reliable counting. People are eventually counted by accumulating the head trajectories leaving the scene. To enable effective head and trajectory identification, we also propose two different compound features. A thorough evaluation on PCDS demonstrates that our technique is able to count people in cluttered scenes with high accuracy at 45 fps on a 1.7 GHz processor, and hence it can be deployed for effective real-time people counting for intelligent transportation systems.
Social Anchor-Unit Graph Regularized Tensor Completion for Large-Scale Image Retagging
Venue: arXiv cs.CV 2018
Year: 2018

Image retagging aims to improve tag quality of social images by refining their original tags or assigning new high-quality tags. Recent approaches simultaneously explore visual, user and tag information to improve the performance of image retagging by constructing and exploring an image-tag-user graph. However, such methods will become computationally infeasible with the rapidly increasing number of images, tags and users. It has been proven that Anchor Graph Regularization (AGR) can significantly accelerate large-scale graph learning model by exploring only a small number of anchor points. Inspired by this, we propose a novel Social anchor-Unit GrAph Regularized Tensor Completion (SUGAR-TC) method to effectively refine the tags of social images, which is insensitive to the scale of the applied data. First, we construct an anchor-unit graph across multiple domains (e.g., image and user domains) rather than traditional anchor graph in a single domain. Second, a tensor completion based on SUGAR is implemented on the original image-tag-user tensor to refine the tags of the anchor images. Third, we efficiently assign tags to non-anchor images by leveraging the relationship between the non-anchor images and the anchor units. Experimental results on a real-world social image database well demonstrate the effectiveness of SUGAR-TC, outperforming several related methods.
Regularized Greedy Column Subset Selection
Venue: arXiv cs.LG 2018
Year: 2018

The Column Subset Selection Problem provides a natural framework for unsupervised feature selection. Despite being a hard combinatorial optimization problem, there exist efficient algorithms that provide good approximations. The drawback of the problem formulation is that it incorporates no form of regularization, and is therefore very sensitive to noise when presented with scarce data. In this paper we propose a regularized formulation of this problem, and derive a correct greedy algorithm that is similar in efficiency to existing greedy methods for the unregularized problem. We study its adequacy for feature selection and propose suitable formulations. Additionally, we derive a lower bound for the error of the proposed problems. Through various numerical experiments on real and synthetic data, we demonstrate the significantly increased robustness and stability of our method, as well as the improved conditioning of its output, all while remaining efficient for practical use.
Extraction of Airways using Graph Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

We present extraction of tree structures, such as airways, from image data as a graph refinement task. To this end, we propose a graph auto-encoder model that uses an encoder based on graph neural networks (GNNs) to learn embeddings from input node features and a decoder to predict connections between nodes. Performance of the GNN model is compared with mean-field networks in their ability to extract airways from 3D chest CT scans.
Learning Multilingual Embeddings for Cross-Lingual Information Retrieval in the Presence of Topically Aligned Corpora
Venue: arXiv cs.IR 2018
Year: 2018

Cross-lingual information retrieval is a challenging task in the absence of aligned parallel corpora. In this paper, we address this problem by considering topically aligned corpora designed for evaluating an IR setup. To emphasize, we neither use any sentence-aligned corpora or document-aligned corpora, nor do we use any language specific resources such as dictionary, thesaurus, or grammar rules. Instead, we use an embedding into a common space and learn word correspondences directly from there. We test our proposed approach for bilingual IR on standard FIRE datasets for Bangla, Hindi and English. The proposed method is superior to the state-of-the-art method not only for IR evaluation measures but also in terms of time requirements. We extend our method successfully to the trilingual setting.
Unleashing Linear Optimizers for Group-Fair Learning and Optimization
Venue: arXiv cs.LG 2018
Year: 2018

Most systems and learning algorithms optimize average performance or average loss -- one reason being computational complexity. However, many objectives of practical interest are more complex than simply average loss. This arises, for example, when balancing performance or loss with fairness across people. We prove that, from a computational perspective, optimizing arbitrary objectives that take into account performance over a small number of groups is not significantly harder to optimize than average performance. Our main result is a polynomial-time reduction that uses a linear optimizer to optimize an arbitrary (Lipschitz continuous) function of performance over a (constant) number of possibly-overlapping groups. This includes fairness objectives over small numbers of groups, and we further point out that other existing notions of fairness such as individual fairness can be cast as convex optimization and hence more standard convex techniques can be used. Beyond learning, our approach applies to multi-objective optimization, more generally.
Forecasting Future Humphrey Visual Fields Using Deep Learning
Venue: arXiv cs.CV 2018
Year: 2018

Purpose: To determine if deep learning networks could be trained to forecast a future 24-2 Humphrey Visual Field (HVF). Participants: All patients who obtained a HVF 24-2 at the University of Washington. Methods: All datapoints from consecutive 24-2 HVFs from 1998 to 2018 were extracted from a University of Washington database. Ten-fold cross validation with a held out test set was used to develop the three main phases of model development: model architecture selection, dataset combination selection, and time-interval model training with transfer learning, to train a deep learning artificial neural network capable of generating a point-wise visual field prediction. Results: More than 1.7 million perimetry points were extracted to the hundredth decibel from 32,443 24-2 HVFs. The best performing model with 20 million trainable parameters, CascadeNet-5, was selected. The overall MAE for the test set was 2.47 dB (95% CI: 2.45 dB to 2.48 dB). The 100 fully trained models were able to successfully predict progressive field loss in glaucomatous eyes up to 5.5 years in the future with a correlation of 0.92 between the MD of predicted and actual future HVF (p < 2.2 x 10 -16 ) and an average difference of 0.41 dB. Conclusions: Using unfiltered real-world datasets, deep learning networks show an impressive ability to not only learn spatio-temporal HVF changes but also to generate predictions for future HVFs up to 5.5 years, given only a single HVF.
Locational Marginal Price Variability at Distribution Level: A Regional Study
Venue: arXiv cs.CE 2018
Year: 2018

As distribution systems move towards being more actively managed there is increased potential for regional markets and the application of locational marginal prices (LMPs) to capture spatial variation in the marginal cost of electricity at distribution level. However, with this increased network visibility can come increased price volatility and uncertainty to investors. This paper studies the variation in LMPs in a section of the south west of England distribution network for current and future installed capacity of distributed generation. It has been shown that in an unconstrained network, spatial LMP variation (due to losses) is minimal compared to the temporal variation. In a constrained network, a significant increase in LMP volatility was observed, both spatially and temporally. This could bring risk for generators particularly if they become stranded in low price areas, or flexible demands facing a drop-off in return when constraints are removed.
Unsupervised robotic sorting: Towards autonomous decision making robots
Venue: arXiv cs.RO 2018
Year: 2018

Autonomous sorting is a crucial task in industrial robotics which can be very challenging depending on the expected amount of automation. Usually, to decide where to sort an object, the system needs to solve either an instance retrieval (known object) or a supervised classification (predefined set of classes) problem. In this paper, we introduce a new decision making module, where the robotic system chooses how to sort the objects in an unsupervised way. We call this problem Unsupervised Robotic Sorting (URS) and propose an implementation on an industrial robotic system, using deep CNN feature extraction and standard clustering algorithms. We carry out extensive experiments on various standard datasets to demonstrate the efficiency of the proposed image clustering pipeline. To evaluate the robustness of our URS implementation, we also introduce a complex real world dataset containing images of objects under various background and lighting conditions. This dataset is used to fine tune the design choices (CNN and clustering algorithm) for URS. Finally, we propose a method combining our pipeline with ensemble clustering to use multiple images of each object. This redundancy of information about the objects is shown to increase the clustering results.
A Survey on Neural Network-Based Summarization Methods
Venue: arXiv cs.CL 2018
Year: 2018

Automatic text summarization, the automated process of shortening a text while reserving the main ideas of the document(s), is a critical research area in natural language processing. The aim of this literature review is to survey the recent work on neural-based models in automatic text summarization. We examine in detail ten state-of-the-art neural-based summarizers: five abstractive models and five extractive models. In addition, we discuss the related techniques that can be applied to the summarization tasks and present promising paths for future research in neural-based summarization.
Pilot Comparative Study of Different Deep Features for Palmprint Identification in Low-Quality Images
Venue: arXiv cs.CV 2018
Year: 2018

Deep Convolutional Neural Networks (CNNs) are widespread, efficient tools of visual recognition. In this paper, we present a comparative study of three popular pre-trained CNN models: AlexNet, VGG-16 and VGG-19. We address the problem of palmprint identification in low-quality imagery and apply Support Vector Machines (SVMs) with all of the compared models. For the comparison, we use the MOHI palmprint image database whose images are characterized by low contrast, shadows, and varying illumination, scale, translation and rotation. Another, high-quality database called COEP is also considered to study the recognition gap between high-quality and low-quality imagery. Our experiments show that the deeper pre-trained CNN models, e.g., VGG-16 and VGG-19, tend to extract highly distinguishable features that recognize low-quality palmprints more efficiently than the less deep networks such as AlexNet. Furthermore, our experiments on the two databases using various models demonstrate that the features extracted from lower-level fully connected layers provide higher recognition rates than higher-layer features. Our results indicate that different pre-trained models can be efficiently used in touchless identification systems with low-quality palmprint images.
Loss Rank Mining: A General Hard Example Mining Method for Real-time Detectors
Venue: arXiv cs.CV 2018
Year: 2018

Modern object detectors usually suffer from low accuracy issues, as foregrounds always drown in tons of backgrounds and become hard examples during training. Compared with those proposal-based ones, real-time detectors are in far more serious trouble since they renounce the use of region-proposing stage which is used to filter a majority of backgrounds for achieving real-time rates. Though foregrounds as hard examples are in urgent need of being mined from tons of backgrounds, a considerable number of state-of-the-art real-time detectors, like YOLO series, have yet to profit from existing hard example mining methods, as using these methods need detectors fit series of prerequisites. In this paper, we propose a general hard example mining method named Loss Rank Mining (LRM) to fill the gap. LRM is a general method for real-time detectors, as it utilizes the final feature map which exists in all real-time detectors to mine hard examples. By using LRM, some elements representing easy examples in final feature map are filtered and detectors are forced to concentrate on hard examples during training. Extensive experiments validate the effectiveness of our method. With our method, the improvements of YOLOv2 detector on auto-driving related dataset KITTI and more general dataset PASCAL VOC are over 5% and 2% mAP, respectively. In addition, LRM is the first hard example mining strategy which could fit YOLOv2 perfectly and make it better applied in series of real scenarios where both real-time rates and accurate detection are strongly demanded.
Reputation in M2M Economy
Venue: arXiv cs.CY 2018
Year: 2018

Triggered by modern technologies, our possibilities may now expand beyond the unthinkable. Cars externally may look similar to decades ago, but a dramatic revolution happened inside the cabin as a result of their computation, communications, and storage capabilities. With the advent of Electric Autonomous Vehicles (EAVs), Artificial Intelligence and ecological technologies found the best synergy. Several transportation problems may be solved (accidents, emissions, and congestion among others), and the foundation of Machine-to-Machine (M2M) economy could be established, in addition to value-added services such as infotainment (information and entertainment). In the world where intelligent technologies are pervading everyday life, software and algorithms play a major role. Software has been lately introduced in virtually every technological product available on the market, from phones to television sets to cars and even housing. Artificial Intelligence is one of the consequences of this pervasive presence of algorithms. The role of software is becoming dominant and technology is, at times pervasive, of our existence. Concerns, such as privacy and security, demand high attention and have been already explored to some level of detail. However, intelligent agents and actors are often considered as perfect entities that will overcome human error-prone nature. This may not always be the case and we advocate that the notion of reputation is also applicable to intelligent artificial agents, in particular to EAVs.
Successful Nash Equilibrium Agent for a 3-Player Imperfect-Information Game
Venue: arXiv cs.GT 2018
Year: 2018

Creating strong agents for games with more than two players is a major open problem in AI. Common approaches are based on approximating game-theoretic solution concepts such as Nash equilibrium, which have strong theoretical guarantees in two-player zero-sum games, but no guarantees in non-zero-sum games or in games with more than two players. We describe an agent that is able to defeat a variety of realistic opponents using an exact Nash equilibrium strategy in a 3-player imperfect-information game. This shows that, despite a lack of theoretical guarantees, agents based on Nash equilibrium strategies can be successful in multiplayer games after all.