OpenRaiser/Intern-Atlas huggingface dataset:
Unsupervised record matching with noisy and incomplete data
Venue: arXiv cs.DB 2018
Year: 2018

We consider the problem of duplicate detection in noisy and incomplete data: given a large data set in which each record has multiple entries (attributes), detect which distinct records refer to the same real world entity. This task is complicated by noise (such as misspellings) and missing data, which can lead to records being different, despite referring to the same entity. Our method consists of three main steps: creating a similarity score between records, grouping records together into "unique entities", and refining the groups. We compare various methods for creating similarity scores between noisy records, considering different combinations of string matching, term frequency-inverse document frequency methods, and n-gram techniques. In particular, we introduce a vectorized soft term frequency-inverse document frequency method, with an optional refinement step. We also discuss two methods to deal with missing data in computing similarity scores. We test our method on the Los Angeles Police Department Field Interview Card data set, the Cora Citation Matching data set, and two sets of restaurant review data. The results show that the methods that use words as the basic units are preferable to those that use 3-grams. Moreover, in some (but certainly not all) parameter ranges soft term frequency-inverse document frequency methods can outperform the standard term frequency-inverse document frequency method. The results also confirm that our method for automatically determining the number of groups typically works well in many cases and allows for accurate results in the absence of a priori knowledge of the number of unique entities in the data set.
Enumeration Complexity of Poor Man's Propositional Dependence Logic
Venue: arXiv cs.LO 2018
Year: 2018

Dependence logics are a modern family of logics of independence and dependence which mimic notions of database theory. In this paper, we aim to initiate the study of enumeration complexity in the field of dependence logics and thereby get a new point of view on enumerating answers of database queries. Consequently, as a first step, we investigate the problem of enumerating all satisfying teams of formulas from a given fragment of propositional dependence logic. We distinguish between restricting the team size by arbitrary functions and the parametrised version where the parameter is the team size. We show that a polynomial delay can be reached for polynomials and otherwise in the parametrised setting we reach FPT delay. However, the constructed enumeration algorithm with polynomial delay requires exponential space. We show that an incremental polynomial delay algorithm exists which uses polynomial space only. Negatively, we show that for the general problem without restricting the team size, an enumeration algorithm running in polynomial space cannot exist.
Efficient Large Scale Clustering based on Data Partitioning
Venue: arXiv cs.DB 2018
Year: 2018

Clustering techniques are very attractive for extracting and identifying patterns in datasets. However, their application to very large spatial datasets presents numerous challenges such as high-dimensionality data, heterogeneity, and high complexity of some algorithms. For instance, some algorithms may have linear complexity but they require the domain knowledge in order to determine their input parameters. Distributed clustering techniques constitute a very good alternative to the big data challenges (e.g.,Volume, Variety, Veracity, and Velocity). Usually these techniques consist of two phases. The first phase generates local models or patterns and the second one tends to aggregate the local results to obtain global models. While the first phase can be executed in parallel on each site and, therefore, efficient, the aggregation phase is complex, time consuming and may produce incorrect and ambiguous global clusters and therefore incorrect models. In this paper we propose a new distributed clustering approach to deal efficiently with both phases, generation of local results and generation of global models by aggregation. For the first phase, our approach is capable of analysing the datasets located in each site using different clustering techniques. The aggregation phase is designed in such a way that the final clusters are compact and accurate while the overall process is efficient in time and memory allocation. For the evaluation, we use two well-known clustering algorithms, K-Means and DBSCAN. One of the key outputs of this distributed clustering technique is that the number of global clusters is dynamic, no need to be fixed in advance. Experimental results show that the approach is scalable and produces high quality results.
Unsupervised Learning of Parsimonious General-Purpose Embeddings for User and Location Modelling
Venue: arXiv cs.IR 2018
Year: 2018

Many social network applications depend on robust representations of spatio-temporal data. In this work, we present an embedding model based on feed-forward neural networks which transforms social media check-ins into dense feature vectors encoding geographic, temporal, and functional aspects for modelling places, neighborhoods, and users. We employ the embedding model in a variety of applications including location recommendation, urban functional zone study, and crime prediction. For location recommendation, we propose a Spatio-Temporal Embedding Similarity algorithm (STES) based on the embedding model. In a range of experiments on real life data collected from Foursquare, we demonstrate our model's effectiveness at characterizing places and people and its applicability in aforementioned problem domains. Finally, we select eight major cities around the globe and verify the robustness and generality of our model by porting pre-trained models from one city to another, thereby alleviating the need for costly local training.
Deep Extreme Multi-label Learning
Venue: arXiv cs.LG 2018
Year: 2018

Extreme multi-label learning (XML) or classification has been a practical and important problem since the boom of big data. The main challenge lies in the exponential label space which involves $2^L$ possible label sets especially when the label dimension $L$ is huge, e.g., in millions for Wikipedia labels. This paper is motivated to better explore the label space by originally establishing an explicit label graph. In the meanwhile, deep learning has been widely studied and used in various classification problems including multi-label classification, however it has not been properly introduced to XML, where the label space can be as large as in millions. In this paper, we propose a practical deep embedding method for extreme multi-label classification, which harvests the ideas of non-linear embedding and graph priors-based label space modeling simultaneously. Extensive experiments on public datasets for XML show that our method performs competitive against state-of-the-art result.
Deep Learning for Photoacoustic Tomography from Sparse Data
Venue: arXiv cs.CV 2018
Year: 2018

The development of fast and accurate image reconstruction algorithms is a central aspect of computed tomography. In this paper, we investigate this issue for the sparse data problem in photoacoustic tomography (PAT). We develop a direct and highly efficient reconstruction algorithm based on deep learning. In our approach image reconstruction is performed with a deep convolutional neural network (CNN), whose weights are adjusted prior to the actual image reconstruction based on a set of training data. The proposed reconstruction approach can be interpreted as a network that uses the PAT filtered backprojection algorithm for the first layer, followed by the U-net architecture for the remaining layers. Actual image reconstruction with deep learning consists in one evaluation of the trained CNN, which does not require time consuming solution of the forward and adjoint problems. At the same time, our numerical results demonstrate that the proposed deep learning approach reconstructs images with a quality comparable to state of the art iterative approaches for PAT from sparse data.
Capacity of the Gaussian Two-Pair Two-Way Relay Channel to Within 1/2 Bit
Venue: arXiv cs.IT 2018
Year: 2018

This paper studies the transceiver design of the Gaussian two-pair two-way relay channel (TWRC), where two pairs of users exchange information through a common relay in a pairwise manner. Our main contribution is to show that the capacity of the Gaussian two-pair TWRC is achievable to within 1/2 bit for arbitrary channel conditions. In the proof, we develop a hybrid coding scheme involving Gaussian random coding, nested lattice coding, superposition coding, and network-coded decoding. Further, we present a message-reassembling strategy to decouple the coding design for the user-to-relay and relay-to-user links, so as to provide flexibility to fully exploit the channel randomness. Finally, judicious power allocation at the relay is necessary to approach the channel capacity under various channel conditions.
Multi-View Image Generation from a Single-View
Venue: arXiv cs.CV 2018
Year: 2018

This paper addresses a challenging problem -- how to generate multi-view cloth images from only a single view input. To generate realistic-looking images with different views from the input, we propose a new image generation model termed VariGANs that combines the strengths of the variational inference and the Generative Adversarial Networks (GANs). Our proposed VariGANs model generates the target image in a coarse-to-fine manner instead of a single pass which suffers from severe artifacts. It first performs variational inference to model global appearance of the object (e.g., shape and color) and produce a coarse image with a different view. Conditioned on the generated low resolution images, it then proceeds to perform adversarial learning to fill details and generate images of consistent details with the input. Extensive experiments conducted on two clothing datasets, MVC and DeepFashion, have demonstrated that images of a novel view generated by our model are more plausible than those generated by existing approaches, in terms of more consistent global appearance as well as richer and sharper details.
Capacity-Achieving Input Distribution in Per-Sample Zero-Dispersion Model of Optical Fiber
Venue: arXiv cs.IT 2018
Year: 2018

The per-sample zero-dispersion channel model of the optical fiber is considered. It is shown that capacity is uniquely achieved by an input probability distribution that has continuous uniform phase and discrete amplitude that takes on finitely many values. This result holds when the channel is subject to general input cost constraints, that include a peak amplitude constraint and a joint average and peak amplitude constraint.
Maximum Likelihood Detection for Cooperative Molecular Communication
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, symbol-by-symbol maximum likelihood (ML) detection is proposed for a cooperative diffusion-based molecular communication (MC) system. In this system, a fusion center (FC) chooses the transmitter's symbol that is more likely, given the likelihood of the observations from multiple receivers (RXs). We propose three different ML detection variants according to different constraints on the information available to the FC, which enables us to demonstrate trade-offs in their performance versus the information available. The system error probability for one variant is derived in closed form. Numerical and simulation results show that the ML detection variants provide lower bounds on the error performance of the simpler cooperative variants and demonstrate that majority rule detection has performance comparable to ML detection when the reporting is noisy.
Stability and Fluctuations in a Simple Model of Phonetic Category Change
Venue: arXiv cs.CL 2018
Year: 2018

In spoken languages, speakers divide up the space of phonetic possibilities into different regions, corresponding to different phonemes. We consider a simple exemplar model of how this division of phonetic space varies over time among a population of language users. In the particular model we consider, we show that, once the system is initialized with a given set of phonemes, that phonemes do not become extinct: all phonemes will be maintained in the system for all time. This is in contrast to what is observed in more complex models. Furthermore, we show that the boundaries between phonemes fluctuate and we quantitatively study the fluctuations in a simple instance of our model. These results prepare the ground for more sophisticated models in which some phonemes go extinct or new phonemes emerge through other processes.
Extreme-Scale Block-Structured Adaptive Mesh Refinement
Venue: arXiv cs.DC 2018
Year: 2018

In this article, we present a novel approach for block-structured adaptive mesh refinement (AMR) that is suitable for extreme-scale parallelism. All data structures are designed such that the size of the meta data in each distributed processor memory remains bounded independent of the processor number. In all stages of the AMR process, we use only distributed algorithms. No central resources such as a master process or replicated data are employed, so that an unlimited scalability can be achieved. For the dynamic load balancing in particular, we propose to exploit the hierarchical nature of the block-structured domain partitioning by creating a lightweight, temporary copy of the core data structure. This copy acts as a local and fully distributed proxy data structure. It does not contain simulation data, but only provides topological information about the domain partitioning into blocks. Ultimately, this approach enables an inexpensive, local, diffusion-based dynamic load balancing scheme. We demonstrate the excellent performance and the full scalability of our new AMR implementation for two architecturally different petascale supercomputers. Benchmarks on an IBM Blue Gene/Q system with a mesh containing 3.7 trillion unknowns distributed to 458,752 processes confirm the applicability for future extreme-scale parallel machines. The algorithms proposed in this article operate on blocks that result from the domain partitioning. This concept and its realization support the storage of arbitrary data. In consequence, the software framework can be used for different simulation methods, including mesh based and meshless methods. In this article, we demonstrate fluid simulations based on the lattice Boltzmann method.
Unsupervised Clustering and Active Learning of Hyperspectral Images with Nonlinear Diffusion
Venue: arXiv cs.CV 2018
Year: 2018

The problem of unsupervised learning and segmentation of hyperspectral images is a significant challenge in remote sensing. The high dimensionality of hyperspectral data, presence of substantial noise, and overlap of classes all contribute to the difficulty of automatically clustering and segmenting hyperspectral images. We propose an unsupervised learning technique called spectral-spatial diffusion learning (DLSS) that combines a geometric estimation of class modes with a diffusion-inspired labeling that incorporates both spectral and spatial information. The mode estimation incorporates the geometry of the hyperspectral data by using diffusion distance to promote learning a unique mode from each class. These class modes are then used to label all points by a joint spectral-spatial nonlinear diffusion process. A related variation of DLSS is also discussed, which enables active learning by requesting labels for a very small number of well-chosen pixels, dramatically boosting overall clustering results. Extensive experimental analysis demonstrates the efficacy of the proposed methods against benchmark and state-of-the-art hyperspectral analysis techniques on a variety of real datasets, their robustness to choices of parameters, and their low computational complexity.
On Improving Deep Reinforcement Learning for POMDPs
Venue: arXiv cs.LG 2018
Year: 2018

Deep Reinforcement Learning (RL) recently emerged as one of the most competitive approaches for learning in sequential decision making problems with fully observable environments, e.g., computer Go. However, very little work has been done in deep RL to handle partially observable environments. We propose a new architecture called Action-specific Deep Recurrent Q-Network (ADRQN) to enhance learning performance in partially observable domains. Actions are encoded by a fully connected layer and coupled with a convolutional observation to form an action-observation pair. The time series of action-observation pairs are then integrated by an LSTM layer that learns latent states based on which a fully connected layer computes Q-values as in conventional Deep Q-Networks (DQNs). We demonstrate the effectiveness of our new architecture in several partially observable domains, including flickering Atari games.
Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms
Venue: arXiv cs.LG 2018
Year: 2018

The $L_1$-regularized models are widely used for sparse regression or classification tasks. In this paper, we propose the orthant-wise passive descent algorithm (OPDA) for optimizing $L_1$-regularized models, as an improved substitute of proximal algorithms, which are the standard tools for optimizing the models nowadays. OPDA uses a stochastic variance-reduced gradient (SVRG) to initialize the descent direction, then apply a novel alignment operator to encourage each element keeping the same sign after one iteration of update, so the parameter remains in the same orthant as before. It also explicitly suppresses the magnitude of each element to impose sparsity. The quasi-Newton update can be utilized to incorporate curvature information and accelerate the speed. We prove a linear convergence rate for OPDA on general smooth and strongly-convex loss functions. By conducting experiments on $L_1$-regularized logistic regression and convolutional neural networks, we show that OPDA outperforms state-of-the-art stochastic proximal algorithms, implying a wide range of applications in training sparse models.
On Scalable Supervisory Control of Multi-Agent Discrete-Event Systems
Venue: arXiv cs.SY 2018
Year: 2018

In this paper we study multi-agent discrete-event systems where the agents can be divided into several groups, and within each group the agents have similar or identical state transition structures. We employ a relabeling map to generate a "template structure" for each group, and synthesize a scalable supervisor whose state size and computational process are independent of the number of agents. This scalability allows the supervisor to remain invariant (no recomputation or reconfiguration needed) if and when there are agents removed due to failure or added for increasing productivity. The constant computational effort for synthesizing the scalable supervisor also makes our method promising for handling large-scale multi-agent systems. Moreover, based on the scalable supervisor we design scalable local controllers, one for each component agent, to establish a purely distributed control architecture. Three examples are provided to illustrate our proposed scalable supervisory synthesis and the resulting scalable supervisors as well as local controllers.
Simultaneous diagonalisation of the covariance and complementary covariance matrices in quaternion widely linear signal processing
Venue: arXiv cs.NA 2018
Year: 2018

Recent developments in quaternion-valued widely linear processing have established that the exploitation of complete second-order statistics requires consideration of both the standard covariance and the three complementary covariance matrices. Although such matrices have a tremendous amount of structure and their decomposition is a powerful tool in a variety of applications, the non-commutative nature of the quaternion product has been prohibitive to the development of quaternion uncorrelating transforms. To this end, we introduce novel techniques for a simultaneous decomposition of the covariance and complementary covariance matrices in the quaternion domain, whereby the quaternion version of the Takagi factorisation is explored to diagonalise symmetric quaternion-valued matrices. This gives new insights into the quaternion uncorrelating transform (QUT) and forms a basis for the proposed quaternion approximate uncorrelating transform (QAUT) which simultaneously diagonalises all four covariance matrices associated with improper quaternion signals. The effectiveness of the proposed uncorrelating transforms is validated by simulations on both synthetic and real-world quaternion-valued signals.
Common greedy wiring and rewiring heuristics do not guarantee maximum assortative graphs of given degree
Venue: arXiv cs.DS 2018
Year: 2018

We examine two greedy heuristics - wiring and rewiring - for constructing maximum assortative graphs over all simple connected graphs with a target degree sequence. Counterexamples show that natural greedy rewiring heuristics do not necessarily return a maximum assortative graph, even though it is known that the meta-graph of all simple connected graphs with given degree is connected under rewiring. Counterexamples show an elegant greedy graph wiring heuristic from the literature may fail to achieve the target degree sequence or may fail to wire a maximally assortative graph.
ΔBreakpad: Diversified Binary Crash Reporting
Venue: arXiv cs.CR 2018
Year: 2018

This paper introduces ΔBreakpad. It extends the Breakpad crash reporting system to handle software diversity effectively and efficiently by replicating and patching the debug information of diversified software versions. Simple adaptations to existing open source compiler tools are presented that on the one hand introduce significant amounts of diversification in the code and stack layout of ARMv7 binaries to mitigate the widespread deployment of code injection and code reuse attacks, while on the other hand still supporting accurate crash reporting. An evaluation on SPEC2006 benchmarks demonstrates that the corresponding computational, storage, and communication overheads are small.
D2D User Selection For Simultaneous Spectrum Sharing And Energy Harvesting
Venue: arXiv cs.IT 2018
Year: 2018

This paper presents a device-to-device (D2D) user selection protocol wherein multiple D2D pairs coexist with a cellular network. In the developed framework, certain D2D users harvest energy and share the spectrum of the cellular users by adopting a hybrid time switching and power splitting protocol. The D2D user which harvests the maximum energy and achieves the desired target rate for the cellular communication is selected to serve as a decode-and-forward (DF) relay for the cellular user. The proposed work analyzes the impact of increase in the number of D2D users on the performance of cellular user as well as derives an upper bound on the time duration of energy harvesting within which best possible rate for cellular user can be obtained. The performance of the proposed protocol has been quantified by obtaining the closed form expressions of outage probability.
MIDA: Multiple Imputation using Denoising Autoencoders
Venue: arXiv cs.LG 2018
Year: 2018

Missing data is a significant problem impacting all domains. State-of-the-art framework for minimizing missing data bias is multiple imputation, for which the choice of an imputation model remains nontrivial. We propose a multiple imputation model based on overcomplete deep denoising autoencoders. Our proposed model is capable of handling different data types, missingness patterns, missingness proportions and distributions. Evaluation on several real life datasets show our proposed model significantly outperforms current state-of-the-art methods under varying conditions while simultaneously improving end of the line analytics.