OpenRaiser/Intern-Atlas huggingface dataset:
Complexity of Reconfiguration Problems for Constraint Satisfaction
Venue: arXiv cs.DS 2018
Year: 2018

Constraint satisfaction problem (CSP) is a well-studied combinatorial search problem, in which we are asked to find an assignment of values to given variables so as to satisfy all of given constraints. We study a reconfiguration variant of CSP, in which we are given an instance of CSP together with its two satisfying assignments, and asked to determine whether one assignment can be transformed into the other by changing a single variable assignment at a time, while always remaining satisfying assignment. This problem generalizes several well-studied reconfiguration problems such as Boolean satisfiability reconfiguration, vertex coloring reconfiguration, homomorphism reconfiguration. In this paper, we study the problem from the viewpoints of polynomial-time solvability and parameterized complexity, and give several interesting boundaries of tractable and intractable cases.
Off-the-grid model based deep learning (O-MODL)
Venue: arXiv cs.LG 2018
Year: 2018

We introduce a model based off-the-grid image reconstruction algorithm using deep learned priors. The main difference of the proposed scheme with current deep learning strategies is the learning of non-linear annihilation relations in Fourier space. We rely on a model based framework, which allows us to use a significantly smaller deep network, compared to direct approaches that also learn how to invert the forward model. Preliminary comparisons against image domain MoDL approach demonstrates the potential of the off-the-grid formulation. The main benefit of the proposed scheme compared to structured low-rank methods is the quite significant reduction in computational complexity.
Towards a Semantic Measure of the Execution Time in Call-by-Value lambda-Calculus (Long Version)
Venue: arXiv cs.LO 2018
Year: 2018

We investigate the possibility of a semantic account of the execution time (i.e. the number of β_v-steps leading to the normal form, if any) for the shuffling calculus, an extension of Plotkin's call-by-value λ-calculus. For this purpose, we use a linear logic based denotational model that can be seen as a non-idempotent intersection type system: relational semantics. Our investigation is inspired by similar ones for linear logic proof-nets and untyped call-by-name λ-calculus. We first prove a qualitative result: a (possibly open) term is normalizable for weak reduction (which does not reduce under abstractions) if and only if its interpretation is not empty. We then show that the size of type derivations can be used to measure the execution time. Finally, we show that, differently from the case of linear logic and call-by-name λ-calculus, the quantitative information enclosed in type derivations does not lift to types (i.e. to the interpretation of terms). To get a truly semantic measure of execution time in a call-by-value setting, we conjecture that a refinement of its syntax and operational semantics is needed.
Identifying Computer-Translated Paragraphs using Coherence Features
Venue: arXiv cs.CL 2018
Year: 2018

We have developed a method for extracting the coherence features from a paragraph by matching similar words in its sentences. We conducted an experiment with a parallel German corpus containing 2000 human-created and 2000 machine-translated paragraphs. The result showed that our method achieved the best performance (accuracy = 72.3%, equal error rate = 29.8%) when it is compared with previous methods on various computer-generated text including translation and paper generation (best accuracy = 67.9%, equal error rate = 32.0%). Experiments on Dutch, another rich resource language, and a low resource one (Japanese) attained similar performances. It demonstrated the efficiency of the coherence features at distinguishing computer-translated from human-created paragraphs on diverse languages.
HUOPM: High Utility Occupancy Pattern Mining
Venue: arXiv cs.DB 2018
Year: 2018

Mining useful patterns from varied types of databases is an important research topic, which has many real-life applications. Most studies have considered the frequency as sole interestingness measure for identifying high quality patterns. However, each object is different in nature. The relative importance of objects is not equal, in terms of criteria such as the utility, risk, or interest. Besides, another limitation of frequent patterns is that they generally have a low occupancy, i.e., they often represent small sets of items in transactions containing many items, and thus may not be truly representative of these transactions. To extract high quality patterns in real life applications, this paper extends the occupancy measure to also assess the utility of patterns in transaction databases. We propose an efficient algorithm named High Utility Occupancy Pattern Mining (HUOPM). It considers user preferences in terms of frequency, utility, and occupancy. A novel Frequency-Utility tree (FU-tree) and two compact data structures, called the utility-occupancy list and FU-table, are designed to provide global and partial downward closure properties for pruning the search space. The proposed method can efficiently discover the complete set of high quality patterns without candidate generation. Extensive experiments have been conducted on several datasets to evaluate the effectiveness and efficiency of the proposed algorithm. Results show that the derived patterns are intelligible, reasonable and acceptable, and that HUOPM with its pruning strategies outperforms the state-of-the-art algorithm, in terms of runtime and search space, respectively.
Parallel Algorithm for Frequent Itemset Mining on Intel Many-core Systems
Venue: arXiv cs.DC 2018
Year: 2018

Frequent itemset mining leads to the discovery of associations and correlations among items in large transactional databases. Apriori is a classical frequent itemset mining algorithm, which employs iterative passes over database combining with generation of candidate itemsets based on frequent itemsets found at the previous iteration, and pruning of clearly infrequent itemsets. The Dynamic Itemset Counting (DIC) algorithm is a variation of Apriori, which tries to reduce the number of passes made over a transactional database while keeping the number of itemsets counted in a pass relatively low. In this paper, we address the problem of accelerating DIC on the Intel Xeon Phi many-core system for the case when the transactional database fits in main memory. Intel Xeon Phi provides a large number of small compute cores with vector processing units. The paper presents a parallel implementation of DIC based on OpenMP technology and thread-level parallelism. We exploit the bit-based internal layout for transactions and itemsets. This technique reduces the memory space for storing the transactional database, simplifies the support count via logical bitwise operation, and allows for vectorization of such a step. Experimental evaluation on the platforms of the Intel Xeon CPU and the Intel Xeon Phi coprocessor with large synthetic and real databases showed good performance and scalability of the proposed algorithm.
Deep Ptych: Subsampled Fourier Ptychography using Generative Priors
Venue: arXiv cs.LG 2018
Year: 2018

This paper proposes a novel framework to regularize the highly ill-posed and non-linear Fourier ptychography problem using generative models. We demonstrate experimentally that our proposed algorithm, Deep Ptych, outperforms the existing Fourier ptychography techniques, in terms of quality of reconstruction and robustness against noise, using far fewer samples. We further modify the proposed approach to allow the generative model to explore solutions outside the range, leading to improved performance.
Transition Property For Cube-Free Words
Venue: arXiv cs.FL 2018
Year: 2018

We study cube-free words over arbitrary non-unary finite alphabets and prove the following structural property: for every pair $(u,v)$ of $d$-ary cube-free words, if $u$ can be infinitely extended to the right and $v$ can be infinitely extended to the left respecting the cube-freeness property, then there exists a "transition" word $w$ over the same alphabet such that $uwv$ is cube free. The crucial case is the case of the binary alphabet, analyzed in the central part of the paper. The obtained "transition property", together with the developed technique, allowed us to solve cube-free versions of three old open problems by Restivo and Salemi. Besides, it has some further implications for combinatorics on words; e.g., it implies the existence of infinite cube-free words of very big subword (factor) complexity.
NOMA-based Compressive Random Access using Gaussian Spreading
Venue: arXiv cs.IT 2018
Year: 2018

Compressive random access (CRA) is a random access scheme that has been considered for massive machine-type communication (MTC) with non-orthogonal spreading sequences, where the notion of compressive sensing (CS) is used for low-complexity detectors by exploiting the sparse device activity. In this paper, we study the application of power-domain non-orthogonal multiple access (NOMA) to CRA in order to improve the performance of CRA (or increase the number of devices to be supported). We consider Gaussian spreading sequences and derive design criteria through a large-system analysis to determine the power levels for power-domain NOMA. From simulation results, we can confirm that the number of incorrectly detected device activity can be reduced by applying NOMA to CRA.
QoS-aware Full-duplex Concurrent Scheduling for Millimeter Wave Wireless Backhaul Networks
Venue: arXiv cs.NI 2018
Year: 2018

The development of self-interference (SI) cancelation technology makes full-duplex (FD) communication possible. Considering the quality of service (QoS) of flows in small cells densely deployed scenario with limited time slot (TS) resources, this paper introduces the FD communication into the concurrent scheduling problem of millimeter-wave (mmWave) wireless backhaul network. We propose a QoS-aware FD concurrent scheduling algorithm to maximize the number of flows with their QoS requirements satisfied. Based on the contention graph, the algorithm makes full use of the FD condition. Both residual self-interference (RSI) and multi-user interference (MUI) are considered. Besides, it also fully considers the QoS requirements of flows and ensures the flows can be transmitted at high rates. Extensive simulations at 60GHz demonstrate that with high SI cancelation level and appropriate contention threshold, the proposed FD algorithm can achieve superior performance in terms of the number of flows with their QoS requirements satisfied and the system throughput compared with other stateof-of-the-art schemes.
SLIM LSTMs
Venue: arXiv cs.NE 2018
Year: 2018

Long Short-Term Memory (LSTM) Recurrent Neural networks (RNNs) rely on gating signals, each driven by a function of a weighted sum of at least 3 components: (i) one of an adaptive weight matrix multiplied by the incoming external input vector sequence, (ii) one adaptive weight matrix multiplied by the previous memory/state vector, and (iii) one adaptive bias vector. In effect, they augment the simple Recurrent Neural Networks (sRNNs) structure with the addition of a "memory cell" and the incorporation of at most 3 gating signals. The standard LSTM structure and components encompass redundancy and overly increased parameterization. In this paper, we systemically introduce variants of the LSTM RNNs, referred to as SLIM LSTMs. These variants express aggressively reduced parameterizations to achieve computational saving and/or speedup in (training) performance---while necessarily retaining (validation accuracy) performance comparable to the standard LSTM RNN.
On Checking Null Rank Conditions of Rational Matrices
Venue: arXiv cs.SY 2018
Year: 2018

In this paper we discuss possible numerical approaches to reliably check the rank condition rank $G(λ) = 0$ for a given rational matrix $G(λ)$ in terms of its descriptor system realization. For test purposes we employ functions available in the Control System Toolbox of MATLAB and the Descriptor System Tools (DSTOOLS) collection.
Modeling, Simulating and Configuring Programmable Wireless Environments for Multi-User Multi-Objective Networking
Venue: arXiv cs.NI 2018
Year: 2018

Programmable wireless environments enable the software-defined propagation of waves within them, yielding exceptional performance potential. Several building-block technologies have been implemented and evaluated at the physical layer. The present work contributes a network-layer scheme to configure such environments for multiple users and objectives, and for any physical-layer technology. Supported objectives include any combination of Quality of Service and power transfer optimization, eavesdropping and Doppler effect mitigation, in multi-cast or uni-cast settings. Additionally, a graph-based model of programmable environments is proposed, which incorporates core physical observations and efficiently separates physical and networking concerns. Evaluation takes place in a specially developed, free simulation tool, and in a variety of environments. Performance gains over regular propagation are highlighted, reaching important insights on the user capacity of programmable environments.
Machine learning in resting-state fMRI analysis
Venue: arXiv cs.LG 2018
Year: 2018

Machine learning techniques have gained prominence for the analysis of resting-state functional Magnetic Resonance Imaging (rs-fMRI) data. Here, we present an overview of various unsupervised and supervised machine learning applications to rs-fMRI. We present a methodical taxonomy of machine learning methods in resting-state fMRI. We identify three major divisions of unsupervised learning methods with regard to their applications to rs-fMRI, based on whether they discover principal modes of variation across space, time or population. Next, we survey the algorithms and rs-fMRI feature representations that have driven the success of supervised subject-level predictions. The goal is to provide a high-level overview of the burgeoning field of rs-fMRI from the perspective of machine learning applications.
Improving forecasting accuracy of time series data using a new ARIMA-ANN hybrid method and empirical mode decomposition
Venue: arXiv cs.LG 2018
Year: 2018

Many applications in different domains produce large amount of time series data. Making accurate forecasting is critical for many decision makers. Various time series forecasting methods exist which use linear and nonlinear models separately or combination of both. Studies show that combining of linear and nonlinear models can be effective to improve forecasting performance. However, some assumptions that those existing methods make, might restrict their performance in certain situations. We provide a new Autoregressive Integrated Moving Average (ARIMA)-Artificial Neural Network(ANN) hybrid method that work in a more general framework. Experimental results show that strategies for decomposing the original data and for combining linear and nonlinear models throughout the hybridization process are key factors in the forecasting performance of the methods. By using appropriate strategies, our hybrid method can be an effective way to improve forecasting accuracy obtained by traditional hybrid methods and also either of the individual methods used separately.
Monte-Carlo Sampling applied to Multiple Instance Learning for Histological Image Classification
Venue: arXiv cs.CV 2018
Year: 2018

We propose a patch sampling strategy based on a sequential Monte-Carlo method for high resolution image classification in the context of Multiple Instance Learning. When compared with grid sampling and uniform sampling techniques, it achieves higher generalization performance. We validate the strategy on two artificial datasets and two histological datasets for breast cancer and sun exposure classification.
Sentiment Classification of Customer Reviews about Automobiles in Roman Urdu
Venue: arXiv cs.CL 2018
Year: 2018

Text mining is a broad field having sentiment mining as its important constituent in which we try to deduce the behavior of people towards a specific item, merchandise, politics, sports, social media comments, review sites etc. Out of many issues in sentiment mining, analysis and classification, one major issue is that the reviews and comments can be in different languages like English, Arabic, Urdu etc. Handling each language according to its rules is a difficult task. A lot of research work has been done in English Language for sentiment analysis and classification but limited sentiment analysis work is being carried out on other regional languages like Arabic, Urdu and Hindi. In this paper, Waikato Environment for Knowledge Analysis (WEKA) is used as a platform to execute different classification models for text classification of Roman Urdu text. Reviews dataset has been scrapped from different automobiles sites. These extracted Roman Urdu reviews, containing 1000 positive and 1000 negative reviews, are then saved in WEKA attribute-relation file format (arff) as labeled examples. Training is done on 80% of this data and rest of it is used for testing purpose which is done using different models and results are analyzed in each case. The results show that Multinomial Naive Bayes outperformed Bagging, Deep Neural Network, Decision Tree, Random Forest, AdaBoost, k-NN and SVM Classifiers in terms of more accuracy, precision, recall and F-measure.
Cascaded V-Net using ROI masks for brain tumor segmentation
Venue: arXiv cs.CV 2018
Year: 2018

In this work we approach the brain tumor segmentation problem with a cascade of two CNNs inspired in the V-Net architecture \cite{VNet}, reformulating residual connections and making use of ROI masks to constrain the networks to train only on relevant voxels. This architecture allows dense training on problems with highly skewed class distributions, such as brain tumor segmentation, by focusing training only on the vecinity of the tumor area. We report results on BraTS2017 Training and Validation sets.
Joint Overlap Analysis of Multiple Genomic Interval Sets
Venue: arXiv cs.DS 2018
Year: 2018

Next-generation sequencing (NGS) technologies have produced large volumes of genomic data. One common operation on heterogeneous genomic data is genomic interval intersection. Most of the existing tools impose restrictions such as not allowing nested intervals or requiring intervals to be sorted when finding overlaps in two or more interval sets. We proposed segment tree (ST) and indexed segment tree forest (ISTF) based solutions for intersection of multiple genomic interval sets in parallel. We developed these methods as a tool, Joint Overlap Analysis (JOA), which takes n interval sets and finds overlapping intervals with no constraints on the given intervals. The proposed indexed segment tree forest is a novel composite data structure, which leverages on indexing and natural binning of a segment tree. We also presented construction and search algorithms for this novel data structure. We compared JOA ST and JOA ISTF with each other, and with other interval intersection tools for verification of its correctness and for showing that it attains comparable execution times. We implemented JOA in Java using the fork/join framework which speeds up parallel processing by taking advantage of all available processor cores. We compared JOA ST with JOA ISTF and showed that segment tree and indexed segment tree forest methods are comparable with each other in terms of execution time and memory usage. We also carried out execution time comparison analysis for JOA and other tools and demonstrated that JOA has comparable execution time and is able to further reduce its running time by using more processors per node. JOA can be run using its GUI or as a command line tool. JOA is available with source code at https://github.com/burcakotlu/JOA/. A user manual is provided at https://joa.readthedocs.org
The Device War - The War Between IOT Brands In A Household
Venue: arXiv cs.NI 2018
Year: 2018

Users buy compatible IOT devices from different brands with an expectation that their cooperation is smooth, but while function may superficially look friendly, cohabitation can subversively cause early battery depletion in competitor devices. The Wi-Fi Direct standard was introduced with the intention of simplifying peer-to-peer connections in home applications while helping devices to save power through centralization of effort into a single group owner device negotiated on start-up. Attacks on the group formation stage can be based on manipulating a victim device to frequently end up being assigned the group owner function, thereby depleting its batteries at faster rates than its peer devices. This manipulation is made easy by the group formation mechanism adopted by the standard. We show that group formation procedures could be better secured with features ensuring fairness by relying on commitments and by learning about the behavior observed for peer devices in the past. Simulations are used to quantify the resistance achieved against several attack strategies.
Predicting Aircraft Trajectories: A Deep Generative Convolutional Recurrent Neural Networks Approach
Venue: arXiv cs.LG 2018
Year: 2018

Reliable 4D aircraft trajectory prediction, whether in a real-time setting or for analysis of counterfactuals, is important to the efficiency of the aviation system. Toward this end, we first propose a highly generalizable efficient tree-based matching algorithm to construct image-like feature maps from high-fidelity meteorological datasets - wind, temperature and convective weather. We then model the track points on trajectories as conditional Gaussian mixtures with parameters to be learned from our proposed deep generative model, which is an end-to-end convolutional recurrent neural network that consists of a long short-term memory (LSTM) encoder network and a mixture density LSTM decoder network. The encoder network embeds last-filed flight plan information into fixed-size hidden state variables and feeds the decoder network, which further learns the spatiotemporal correlations from the historical flight tracks and outputs the parameters of Gaussian mixtures. Convolutional layers are integrated into the pipeline to learn representations from the high-dimension weather features. During the inference process, beam search, adaptive Kalman filter, and Rauch-Tung-Striebel smoother algorithms are used to prune the variance of generated trajectories.
On the Complexity of the Inverse Semivalue Problem for Weighted Voting Games
Venue: arXiv cs.GT 2018
Year: 2018

Weighted voting games are a family of cooperative games, typically used to model voting situations where a number of agents (players) vote against or for a proposal. In such games, a proposal is accepted if an appropriately weighted sum of the votes exceeds a prespecified threshold. As the influence of a player over the voting outcome is not in general proportional to her assigned weight, various power indices have been proposed to measure each player's influence. The inverse power index problem is the problem of designing a weighted voting game that achieves a set of target influences according to a predefined power index. In this work, we study the computational complexity of the inverse problem when the power index belongs to the class of semivalues. We prove that the inverse problem is computationally intractable for a broad family of semivalues, including all regular semivalues. As a special case of our general result, we establish computational hardness of the inverse problem for the Banzhaf indices and the Shapley values, arguably the most popular power indices.