OpenRaiser/Intern-Atlas huggingface dataset:
Successive Wyner-Ziv Coding for the Binary CEO Problem under Logarithmic Loss
Venue: arXiv cs.IT 2019
Year: 2019

The $L$-link binary Chief Executive Officer (CEO) problem under logarithmic loss is investigated in this paper. A quantization splitting technique is applied to convert the problem under consideration to a $(2L-1)$-step successive Wyner-Ziv (WZ) problem, for which a practical coding scheme is proposed. In the proposed scheme, low-density generator-matrix (LDGM) codes are used for binary quantization while low-density parity-check (LDPC) codes are used for syndrome generation; the decoder performs successive decoding based on the received syndromes and produces a soft reconstruction of the remote source. The simulation results indicate that the rate-distortion performance of the proposed scheme can approach the theoretical inner bound based on binary-symmetric test-channel models.
Formalization and Correctness of Predictive Shift-Reduce Parsers for Graph Grammars based on Hyperedge Replacement
Venue: arXiv cs.FL 2019
Year: 2019

Hyperedge replacement (HR) grammars can generate NP-complete graph languages, which makes parsing hard even for fixed HR languages. Therefore, we study predictive shift-reduce (PSR) parsing that yields efficient parsers for a subclass of HR grammars, by generalizing the concepts of SLR(1) string parsing to graphs. We formalize the construction of PSR parsers and show that it is correct. PSR parsers run in linear space and time, and are more efficient than the predictive top-down (PTD) parsers recently developed by the authors.
A Noise-Sensitivity-Analysis-Based Test Prioritization Technique for Deep Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

Deep neural networks (DNNs) have been widely used in the fields such as natural language processing, computer vision and image recognition. But several studies have been shown that deep neural networks can be easily fooled by artificial examples with some perturbations, which are widely known as adversarial examples. Adversarial examples can be used to attack deep neural networks or to improve the robustness of deep neural networks. A common way of generating adversarial examples is to first generate some noises and then add them into original examples. In practice, different examples have different noise-sensitive. To generate an effective adversarial example, it may be necessary to add a lot of noise to low noise-sensitive example, which may make the adversarial example meaningless. In this paper, we propose a noise-sensitivity-analysis-based test prioritization technique to pick out examples by their noise sensitivity. We construct an experiment to validate our approach on four image sets and two DNN models, which shows that examples are sensitive to noise and our method can effectively pick out examples by their noise sensitivity.
Determining Principal Component Cardinality through the Principle of Minimum Description Length
Venue: arXiv cs.LG 2019
Year: 2019

PCA (Principal Component Analysis) and its variants areubiquitous techniques for matrix dimension reduction and reduced-dimensionlatent-factor extraction. One significant challenge in using PCA, is thechoice of the number of principal components. The information-theoreticMDL (Minimum Description Length) principle gives objective compression-based criteria for model selection, but it is difficult to analytically applyits modern definition - NML (Normalized Maximum Likelihood) - to theproblem of PCA. This work shows a general reduction of NML prob-lems to lower-dimension problems. Applying this reduction, it boundsthe NML of PCA, by terms of the NML of linear regression, which areknown.
Improving Tree-LSTM with Tree Attention
Venue: arXiv cs.CL 2019
Year: 2019

In Natural Language Processing (NLP), we often need to extract information from tree topology. Sentence structure can be represented via a dependency tree or a constituency tree structure. For this reason, a variant of LSTMs, named Tree-LSTM, was proposed to work on tree topology. In this paper, we design a generalized attention framework for both dependency and constituency trees by encoding variants of decomposable attention inside a Tree-LSTM cell. We evaluated our models on a semantic relatedness task and achieved notable results compared to Tree-LSTM based methods with no attention as well as other neural and non-neural methods and good results compared to Tree-LSTM based methods with attention.
Probery: A Probability-based Incomplete Query Optimization for Big Data
Venue: arXiv cs.DB 2019
Year: 2019

Nowadays, query optimization has been highly concerned in big data management, especially in NoSQL databases. Approximate queries boost query performance by loss of accuracy, for example, sampling approaches trade off query completeness for efficiency. Different from them, we propose an uncertainty of query completeness, called Probability of query Completeness (PC for short). PC refers to the possibility that query results contain all satisfied records. For example PC=0.95, it guarantees that there are no more than 5 incomplete queries among 100 ones, but not guarantees how incomplete they are. We trade off PC for query performance, and experiments show that a small loss of PC doubles query performance. The proposed Probery (PROBability-based data quERY) adopts the uncertainty of query completeness to accelerate OLTP queries. This paper illustrates the data and probability models, the probability based data placement and query processing, and the Apache Drill-based implementation of Probery. In experiments, we first prove that the percentage of complete queries is larger than the given PC confidence for various cases, namely that the PC guarantee is validate. Then Probery is compared with Drill, Impala and Hive in terms of query performance. The results indicate that Drill-based Probery performs as fast as Drill with complete query, while averagely 1.8x, 1.3x and 1.6x faster than Drill, Impala and Hive with possible complete query, respectively.
Parallel Algorithm for Time Series Discords Discovery on the Intel Xeon Phi Knights Landing Many-core Processor
Venue: arXiv cs.DC 2019
Year: 2019

Discord is a refinement of the concept of anomalous subsequence of a time series. The task of discords discovery is applied in a wide range of subject domains related to time series: medicine, economics, climate modeling, etc. In this paper, we propose a novel parallel algorithm for discords discovery for the Intel Xeon Phi Knights Landing (KNL) many-core systems for the case when input data fit in main memory. The algorithm exploits the ability to independently calculate Euclidean distances between the subsequences of the time series. Computations are paralleled through OpenMP technology. The algorithm consists of two stages, namely precomputations and discovery. At the precomputations stage, we construct the auxiliary matrix data structures, which ensure efficient vectorization of computations on Intel Xeon Phi KNL. At the discovery stage, the algorithm finds discord based upon the structures above. Experimental evaluation confirms the high scalability of the developed algorithm.
A Field-Size Independent Code Construction for Groupcast Index Coding Problems
Venue: arXiv cs.IT 2019
Year: 2019

The length of an optimal scalar linear index code of a groupcast index coding problem is equal to the minrank of its side information hypergraph. The side-information hypergraph becomes a side-information graph for a special class of groupcast index coding problems known as unicast index coding problems. The computation of minrank is an NP-hard problem. There exists a low rank matrix completion method and clique cover method to find suboptimal solutions to the index coding problem represented by a side-information graph. However, both the methods are NP-hard. The number of computations required to find the minrank depends on the number of edges present in the side-information graph. In this paper, we define the notion of minrank-critical edges in a side-information graph and derive some properties of minrank, which identifies minrank-non-critical edges. Using these properties we present a method for reduction of the given minrank computation problem into a smaller problem. Also, we give an heuristic algorithm to find a clique cover of the side-information graph by using some binary operations on the adjacency matrix of the side-information graph. We also give a method to convert a groupcast index coding problem into a single unicast index coding problem. Combining all these results, we construct index codes (not necessarily optimal length) for groupcast index coding problems. The construction technique is independent of field size and hence can be used to construct index codes over binary field. In some cases the constructed index codes are better than the best known in the literature both in terms of the length of the code and the minimum field size required.
EdgeConnect: Generative Image Inpainting with Adversarial Edge Learning
Venue: arXiv cs.CV 2019
Year: 2019

Over the last few years, deep learning techniques have yielded significant improvements in image inpainting. However, many of these techniques fail to reconstruct reasonable structures as they are commonly over-smoothed and/or blurry. This paper develops a new approach for image inpainting that does a better job of reproducing filled regions exhibiting fine details. We propose a two-stage adversarial model EdgeConnect that comprises of an edge generator followed by an image completion network. The edge generator hallucinates edges of the missing region (both regular and irregular) of the image, and the image completion network fills in the missing regions using hallucinated edges as a priori. We evaluate our model end-to-end over the publicly available datasets CelebA, Places2, and Paris StreetView, and show that it outperforms current state-of-the-art techniques quantitatively and qualitatively. Code and models available at: https://github.com/knazeri/edge-connect
The Divide-and-Conquer Framework: A Suitable Setting for the DDM of the Future
Venue: arXiv cs.CE 2019
Year: 2019

This paper was prompted by numerical experiments we performed, in which algorithms already available in the literature (DVS-BDDM) yielded accelerations (or speedups) many times larger (more than seventy in some examples already treated, but probably often much larger) than the number of processors used. Based on these outstanding results, here it is shown that believing in the standard ideal speedup, which is taken to be equal to the number of processors, has limited much the performance goal sought by research on domain decomposition methods (DDM) and has hindered much its development, thus far. Hence, an improved theory in which the speedup goal is based on the Divide and Conquer algorithmic paradigm, frequently considered as the leitmotiv of domain decomposition methods, is proposed as a suitable setting for the DDM of the future.
Singularity Structure Simplification of Hexahedral Mesh via Weighted Ranking
Venue: arXiv cs.CG 2019
Year: 2019

In this paper, we propose an improved singularity structure simplification method for hexahedral (hex) meshes using a weighted ranking approach. In previous work, the selection of to-be-collapsed base complex sheets/chords is only based on their thickness, which will introduce a few closed-loops and cause an early termination of simplification and a slow convergence rate. In this paper, a new weighted ranking function is proposed by combining the valence prediction function of local singularity structure, shape quality metric of elements and the width of base complex sheets/chords together. Adaptive refinement and local optimization are also introduced to improve the uniformity and aspect ratio of mesh elements. Compared to thickness ranking methods, our weighted ranking approach can yield a simpler singularity structure with fewer base-complex components, while achieving comparable Hausdorff distance ratio and better mesh quality. Comparisons on a hex-mesh dataset are performed to demonstrate the effectiveness of the proposed method.
General Subpopulation Framework and Taming the Conflict Inside Populations
Venue: arXiv cs.NE 2019
Year: 2019

Structured evolutionary algorithms have been investigated for some time. However, they have been under-explored specially in the field of multi-objective optimization. Despite their good results, the use of complex dynamics and structures make their understanding and adoption rate low. Here, we propose the general subpopulation framework that has the capability of integrating optimization algorithms without restrictions as well as aid the design of structured algorithms. The proposed framework is capable of generalizing most of the structured evolutionary algorithms, such as cellular algorithms, island models, spatial predator-prey and restricted mating based algorithms under its formalization. Moreover, we propose two algorithms based on the general subpopulation framework, demonstrating that with the simple addition of a number of single-objective differential evolution algorithms for each objective the results improve greatly, even when the combined algorithms behave poorly when evaluated alone at the tests. Most importantly, the comparison between the subpopulation algorithms and their related panmictic algorithms suggests that the competition between different strategies inside one population can have deleterious consequences for an algorithm and reveal a strong benefit of using the subpopulation framework. The code for SAN, the proposed multi-objective algorithm which has the current best results in the hardest benchmark, is available at the following https://github.com/zweifel/zweifel
Multi-level CNN for lung nodule classification with Gaussian Process assisted hyperparameter optimization
Venue: arXiv cs.LG 2019
Year: 2019

This paper investigates lung nodule classification by using deep neural networks (DNNs). Hyperparameter optimization in DNNs is a computationally expensive problem, where evaluating a hyperparameter configuration may take several hours or even days. Bayesian optimization has been recently introduced for the automatically searching of optimal hyperparameter configurations of DNNs. It applies probabilistic surrogate models to approximate the validation error function of hyperparameter configurations, such as Gaussian processes, and reduce the computational complexity to a large extent. However, most existing surrogate models adopt stationary covariance functions to measure the difference between hyperparameter points based on spatial distance without considering its spatial locations. This distance-based assumption together with the condition of constant smoothness throughout the whole hyperparameter search space clearly violates the property that the points far away from optimal points usually get similarly poor performance even though each two of them have huge spatial distance between them. In this paper, a non-stationary kernel is proposed which allows the surrogate model to adapt to functions whose smoothness varies with the spatial location of inputs, and a multi-level convolutional neural network (ML-CNN) is built for lung nodule classification whose hyperparameter configuration is optimized by using the proposed non-stationary kernel based Gaussian surrogate model. Our algorithm searches the surrogate for optimal setting via hyperparameter importance based evolutionary strategy, and the experiments demonstrate our algorithm outperforms manual tuning and well-established hyperparameter optimization methods such as Random search, Gaussian processes with stationary kernels, and recently proposed Hyperparameter Optimization via RBF and Dynamic coordinate search.
A Deep Learning Approach for Similar Languages, Varieties and Dialects
Venue: arXiv cs.CL 2019
Year: 2019

Deep learning mechanisms are prevailing approaches in recent days for the various tasks in natural language processing, speech recognition, image processing and many others. To leverage this we use deep learning based mechanism specifically Bidirectional- Long Short-Term Memory (B-LSTM) for the task of dialectic identification in Arabic and German broadcast speech and Long Short-Term Memory (LSTM) for discriminating between similar Languages. Two unique B-LSTM models are created using the Large-vocabulary Continuous Speech Recognition (LVCSR) based lexical features and a fixed length of 400 per utterance bottleneck features generated by i-vector framework. These models were evaluated on the VarDial 2017 datasets for the tasks Arabic, German dialect identification with dialects of Egyptian, Gulf, Levantine, North African, and MSA for Arabic and Basel, Bern, Lucerne, and Zurich for German. Also for the task of Discriminating between Similar Languages like Bosnian, Croatian and Serbian. The B-LSTM model showed accuracy of 0.246 on lexical features and accuracy of 0.577 bottleneck features of i-Vector framework.
A Full Probabilistic Model for Yes/No Type Crowdsourcing in Multi-Class Classification
Venue: arXiv cs.LG 2019
Year: 2019

Crowdsourcing has become widely used in supervised scenarios where training sets are scarce and difficult to obtain. Most crowdsourcing models in the literature assume labelers can provide answers to full questions. In classification contexts, full questions require a labeler to discern among all possible classes. Unfortunately, discernment is not always easy in realistic scenarios. Labelers may not be experts in differentiating all classes. In this work, we provide a full probabilistic model for a shorter type of queries. Our shorter queries only require "yes" or "no" responses. Our model estimates a joint posterior distribution of matrices related to labelers' confusions and the posterior probability of the class of every object. We developed an approximate inference approach, using Monte Carlo Sampling and Black Box Variational Inference, which provides the derivation of the necessary gradients. We built two realistic crowdsourcing scenarios to test our model. The first scenario queries for irregular astronomical time-series. The second scenario relies on the image classification of animals. We achieved results that are comparable with those of full query crowdsourcing. Furthermore, we show that modeling labelers' failures plays an important role in estimating true classes. Finally, we provide the community with two real datasets obtained from our crowdsourcing experiments. All our code is publicly available.
Coverage Protocols for Wireless Sensor Networks: Review and Future Directions
Venue: arXiv cs.NI 2019
Year: 2019

The coverage problem in wireless sensor networks (WSNs) can be generally defined as a measure of how effectively a network field is monitored by its sensor nodes. This problem has attracted a lot of interest over the years and as a result, many coverage protocols were proposed. In this survey, we first propose a taxonomy for classifying coverage protocols in WSNs. Then, we classify the coverage protocols into three categories (i.e. coverage aware deployment protocols, sleep scheduling protocols for flat networks, and cluster-based sleep scheduling protocols) based on the network stage where the coverage is optimized. For each category, relevant protocols are thoroughly reviewed and classified based on the adopted coverage techniques. Finally, we discuss open issues (and recommend future directions to resolve them) associated with the design of realistic coverage protocols. Issues such as realistic sensing models, realistic energy consumption models, realistic connectivity models and sensor localization are covered.
Real-Time EEG Classification via Coresets for BCI Applications
Venue: arXiv cs.DS 2019
Year: 2019

A brain-computer interface (BCI) based on the motor imagery (MI) paradigm translates one's motor intention into a control signal by classifying the Electroencephalogram (EEG) signal of different tasks. However, most existing systems either (i) use a high-quality algorithm to train the data off-line and run only classification in real-time, since the off-line algorithm is too slow, or (ii) use low-quality heuristics that are sufficiently fast for real-time training but introduces relatively large classification error. In this work, we propose a novel processing pipeline that allows real-time and parallel learning of EEG signals using high-quality but possibly inefficient algorithms. This is done by forging a link between BCI and core-sets, a technique that originated in computational geometry for handling streaming data via data summarization. We suggest an algorithm that maintains the representation such coreset tailored to handle the EEG signal which enables: (i) real time and continuous computation of the Common Spatial Pattern (CSP) feature extraction method on a coreset representation of the signal (instead on the signal itself) , (ii) improvement of the CSP algorithm efficiency with provable guarantees by applying CSP algorithm on the coreset, and (iii) real time addition of the data trials (EEG data windows) to the coreset. For simplicity, we focus on the CSP algorithm, which is a classic algorithm. Nevertheless, we expect that our coreset will be extended to other algorithms in future papers. In the experimental results we show that our system can indeed learn EEG signals in real-time for example a 64 channels setup with hundreds of time samples per second. Full open source is provided to reproduce the experiment and in the hope that it will be used and extended to more coresets and BCI applications in the future.
Performance of Three Slim Variants of The Long Short-Term Memory (LSTM) Layer
Venue: arXiv cs.NE 2019
Year: 2019

The Long Short-Term Memory (LSTM) layer is an important advancement in the field of neural networks and machine learning, allowing for effective training and impressive inference performance. LSTM-based neural networks have been successfully employed in various applications such as speech processing and language translation. The LSTM layer can be simplified by removing certain components, potentially speeding up training and runtime with limited change in performance. In particular, the recently introduced variants, called SLIM LSTMs, have shown success in initial experiments to support this view. Here, we perform computational analysis of the validation accuracy of a convolutional plus recurrent neural network architecture using comparatively the standard LSTM and three SLIM LSTM layers. We have found that some realizations of the SLIM LSTM layers can potentially perform as well as the standard LSTM layer for our considered architecture.