OpenRaiser/Intern-Atlas huggingface dataset:
Graph Classification via Deep Learning with Virtual Nodes
Venue: arXiv cs.LG 2017
Year: 2017

Learning representation for graph classification turns a variable-size graph into a fixed-size vector (or matrix). Such a representation works nicely with algebraic manipulations. Here we introduce a simple method to augment an attributed graph with a virtual node that is bidirectionally connected to all existing nodes. The virtual node represents the latent aspects of the graph, which are not immediately available from the attributes and local connectivity structures. The expanded graph is then put through any node representation method. The representation of the virtual node is then the representation of the entire graph. In this paper, we use the recently introduced Column Network for the expanded graph, resulting in a new end-to-end graph classification model dubbed Virtual Column Network (VCN). The model is validated on two tasks: (i) predicting bio-activity of chemical compounds, and (ii) finding software vulnerability from source code. Results demonstrate that VCN is competitive against well-established rivals.
Quasi-PTAS for Scheduling with Precedences using LP Hierarchies
Venue: arXiv cs.DS 2017
Year: 2017

A central problem in scheduling is to schedule $n$ unit size jobs with precedence constraints on $m$ identical machines so as to minimize the makespan. For $m=3$, it is not even known if the problem is NP-hard and this is one of the last open problems from the book of Garey and Johnson. We show that for fixed $m$ and $ε$, $(\log n)^{O(1)}$ rounds of Sherali-Adams hierarchy applied to a natural LP of the problem provides a $(1+ε)$-approximation algorithm running in quasi-polynomial time. This improves over the recent result of Levey and Rothvoss, who used $r=(\log n)^{O(\log \log n)}$ rounds of Sherali-Adams in order to get a $(1+ε)$-approximation algorithm with a running time of $n^{O(r)}$.
Coexistence of Systems with Different Multicarrier Waveforms in LSA Communications
Venue: arXiv cs.IT 2017
Year: 2017

We study the coexistence of different multicarrier waveforms such as orthogonal frequency division multiplexing (OFDM), filter-bank multicarrier (FBMC) and universal-filtered multicarrier (UFMC) waveforms in licensed shared access (LSA) for next-generation communication systems. The fundamental changes required in the existing physical layer using OFDM towards a hybrid physical layer (either OFDM-FBMC or OFDM- UFMC) ensuring backward compatibility are discussed. We also perform mutual interference analysis for the coexisting asynchronous systems sharing the LSA frequency band. Be- cause of the non-orthogonality between their respective transmit signals, power is spilled from a system to the other causing interference. In consideration of analyzing this interaction, power spectral densities of the multicarrier waveforms are exploited. We quantify the amount of percentage power-loss experienced by the interfering systems for not fully exploiting their available power budgets. The simulation results reveal that the interfering system with FBMC suffers the least percentage power-power loss due to its very low side-lobes while conventional OFDM-based system suffers the most. The UFMC-based system exhibits intermediary performance with respect to achieved throughput and power-loss when compared with OFDM and FBMC-based systems.
Knock-Knock: Acoustic Object Recognition by using Stacked Denoising Autoencoders
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents a successful application of deep learning for object recognition based on acoustic data. The shortcomings of previously employed approaches where handcrafted features describing the acoustic data are being used, include limiting the capability of the found representation to be widely applicable and facing the risk of capturing only insignificant characteristics for a task. In contrast, there is no need to define the feature representation format when using multilayer/deep learning architecture methods: features can be learned from raw sensor data without defining discriminative characteristics a-priori. In this paper, stacked denoising autoencoders are applied to train a deep learning model. Knocking each object in our test set 120 times with a marker pen to obtain the auditory data, thirty different objects were successfully classified in our experiment and each object was knocked 120 times by a marker pen to obtain the auditory data. By employing the proposed deep learning framework, a high accuracy of 91.50% was achieved. A traditional method using handcrafted features with a shallow classifier was taken as a benchmark and the attained recognition rate was only 58.22%. Interestingly, a recognition rate of 82.00% was achieved when using a shallow classifier with raw acoustic data as input. In addition, we could show that the time taken to classify one object using deep learning was far less (by a factor of more than 6) than utilizing the traditional method. It was also explored how different model parameters in our deep architecture affect the recognition performance.
Reference Publication Year Spectroscopy (RPYS) of Eugene Garfield's publications
Venue: arXiv cs.DL 2017
Year: 2017

Which studies, theories, and ideas have influenced Eugene Garfield's scientific work? Recently, the method reference publication year spectroscopy (RPYS) has been introduced, which can be used to answer this and related questions. Since then, several studies have been published dealing with the historical roots of research fields and scientists. The program CRExplorer (http://www.crexplorer.net) was specifically developed for RPYS. In this study, we use this program to investigate the historical roots of Eugene Garfield's oeuvre.
Convex Approximated Weighted Sum-Rate Maximization for Multicell Multiuser OFDM
Venue: arXiv cs.IT 2017
Year: 2017

This letter considers the weighted sum-rate maximization (WSRMax) problem in downlink multicell multiuser orthogonal frequency-division multiplexing system. The WSRMax problem under per base station transmit power constraint is known to be NP-hard, and the optimal solution is computationally very expensive. We propose two less-complex suboptimal convex approximated solutions which are based on sequential parametric convex approximation approach. We derive provably faster convergent iterative convex approximation techniques that locally optimize the weighted sum-rate function. Both the iterative solutions are found to converge to the local optimal solution within a few iterations compared to other well-known techniques. The numerical results demonstrate the effectiveness and superiority of the proposed approaches.
SCNN: An Accelerator for Compressed-sparse Convolutional Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

Convolutional Neural Networks (CNNs) have emerged as a fundamental technology for machine learning. High performance and extreme energy efficiency are critical for deployments of CNNs in a wide range of situations, especially mobile platforms such as autonomous vehicles, cameras, and electronic personal assistants. This paper introduces the Sparse CNN (SCNN) accelerator architecture, which improves performance and energy efficiency by exploiting the zero-valued weights that stem from network pruning during training and zero-valued activations that arise from the common ReLU operator applied during inference. Specifically, SCNN employs a novel dataflow that enables maintaining the sparse weights and activations in a compressed encoding, which eliminates unnecessary data transfers and reduces storage requirements. Furthermore, the SCNN dataflow facilitates efficient delivery of those weights and activations to the multiplier array, where they are extensively reused. In addition, the accumulation of multiplication products are performed in a novel accumulator array. Our results show that on contemporary neural networks, SCNN can improve both performance and energy by a factor of 2.7x and 2.3x, respectively, over a comparably provisioned dense CNN accelerator.
Analysing Relations involving small number of Monomials in AES S- Box
Venue: arXiv cs.CR 2017
Year: 2017

In the present day, AES is one the most widely used and most secure Encryption Systems prevailing. So, naturally lots of research work is going on to mount a significant attack on AES. Many different forms of Linear and differential cryptanalysis have been performed on AES. Of late, an active area of research has been Algebraic Cryptanalysis of AES, where although fast progress is being made, there are still numerous scopes for research and improvement. One of the major reasons behind this being that algebraic cryptanalysis mainly depends on I/O relations of the AES S- Box (a major component of the AES). As, already known, that the key recovery algorithm of AES can be broken down as an MQ problem which is itself considered hard. Solving these equations depends on our ability reduce them into linear forms which are easily solvable under our current computational prowess. The lower the degree of these equations, the easier it is for us to linearlize hence the attack complexity reduces. The aim of this paper is to analyze the various relations involving small number of monomials of the AES S- Box and to answer the question whether it is actually possible to have such monomial equations for the S- Box if we restrict the degree of the monomials. In other words this paper aims to study such equations and see if they can be applicable for AES.
Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model
Venue: arXiv cs.DS 2017
Year: 2017

A classical difficult isomorphism testing problem is to test isomorphism of p-groups of class 2 and exponent p in time polynomial in the group order. It is known that this problem can be reduced to solving the alternating matrix space isometry problem over a finite field in time polynomial in the underlying vector space size. We propose a venue of attack for the latter problem by viewing it as a linear algebraic analogue of the graph isomorphism problem. This viewpoint leads us to explore the possibility of transferring techniques for graph isomorphism to this long-believed bottleneck case of group isomorphism. In 1970's, Babai, Erdős, and Selkow presented the first average-case efficient graph isomorphism testing algorithm (SIAM J Computing, 1980). Inspired by that algorithm, we devise an average-case efficient algorithm for the alternating matrix space isometry problem over a key range of parameters, in a random model of alternating matrix spaces in vein of the Erdős-Rényi model of random graphs. For this, we develop a linear algebraic analogue of the classical individualisation technique, a technique belonging to a set of combinatorial techniques that has been critical for the progress on the worst-case time complexity for graph isomorphism, but was missing in the group isomorphism context. As a consequence of the main algorithm, we establish a weaker linear algebraic analogue of Erdős and Rényi's classical result that most graphs have the trivial automorphism group. We finally show that Luks' dynamic programming technique for graph isomorphism (STOC 1999) can be adapted to slightly improve the worst-case time complexity of the alternating matrix space isometry problem in a certain range of parameters.
Pathological Pulmonary Lobe Segmentation from CT Images using Progressive Holistically Nested Neural Networks and Random Walker
Venue: arXiv cs.CV 2017
Year: 2017

Automatic pathological pulmonary lobe segmentation(PPLS) enables regional analyses of lung disease, a clinically important capability. Due to often incomplete lobe boundaries, PPLS is difficult even for experts, and most prior art requires inference from contextual information. To address this, we propose a novel PPLS method that couples deep learning with the random walker (RW) algorithm. We first employ the recent progressive holistically-nested network (P-HNN) model to identify potential lobar boundaries, then generate final segmentations using a RW that is seeded and weighted by the P-HNN output. We are the first to apply deep learning to PPLS. The advantages are independence from prior airway/vessel segmentations, increased robustness in diseased lungs, and methodological simplicity that does not sacrifice accuracy. Our method posts a high mean Jaccard score of 0.888$\pm$0.164 on a held-out set of 154 CT scans from lung-disease patients, while also significantly (p < 0.001) outperforming a state-of-the-art method.
A Framework for Android Based Shopping Mall Applications
Venue: arXiv cs.HC 2017
Year: 2017

Android is Google's latest open source software platform for mobile devices which has already attained enormous popularity. The purpose of this paper is to describe the development of mobile application for shopping mall using Android platform. A prototype was developed for the shoppers of Bashundhara Shopping Mall of Bangladesh. This prototype will serve as a framework for any such applications (apps). The paper presents a practical demonstration of how to integrate shops' information, such as names, categories, locations, descriptions, floor layout and so forth, with map module via an android application. A summary of survey results of the related literature and projects have also been included. Critical Evaluation of the prototype along with future research and development plan has been revealed. The paper will serve as a guideline for the researchers and developers to introduce and develop similar apps.
Beating the Multiplicative Weights Update Algorithm
Venue: arXiv cs.DC 2017
Year: 2017

Multiplicative weights update algorithms have been used extensively in designing iterative algorithms for many computational tasks. The core idea is to maintain a distribution over a set of experts and update this distribution in an online fashion based on the parameters of the underlying optimization problem. In this report, we study the behavior of a special MWU algorithm used for generating a global coin flip in the presence of an adversary that tampers the experts' advice. Specifically, we focus our attention on two adversarial strategies: (1) non-adaptive, in which the adversary chooses a fixed set of experts a priori and corrupts their advice in each round; and (2) adaptive, in which this set is chosen as the rounds of the algorithm progress. We formulate these adversarial strategies as being greedy in terms of trying to maximize the share of the corrupted experts in the final weighted advice the MWU computes and provide the underlying optimization problem that needs to be solved to achieve this goal. We provide empirical results to show that in the presence of either of the above adversaries, the MWU algorithm takes $\mathcal{O}(n)$ rounds in expectation to produce the desired output. This result compares well with the current state of the art of $\mathcal{O}(n^3)$ for the general Byzantine consensus problem. Finally, we briefly discuss the extension of these adversarial strategies for a general MWU algorithm and provide an outline for the framework in that setting.
DeepFaceLIFT: Interpretable Personalized Models for Automatic Estimation of Self-Reported Pain
Venue: arXiv cs.CV 2017
Year: 2017

Previous research on automatic pain estimation from facial expressions has focused primarily on "one-size-fits-all" metrics (such as PSPI). In this work, we focus on directly estimating each individual's self-reported visual-analog scale (VAS) pain metric, as this is considered the gold standard for pain measurement. The VAS pain score is highly subjective and context-dependent, and its range can vary significantly among different persons. To tackle these issues, we propose a novel two-stage personalized model, named DeepFaceLIFT, for automatic estimation of VAS. This model is based on (1) Neural Network and (2) Gaussian process regression models, and is used to personalize the estimation of self-reported pain via a set of hand-crafted personal features and multi-task learning. We show on the benchmark dataset for pain analysis (The UNBC-McMaster Shoulder Pain Expression Archive) that the proposed personalized model largely outperforms the traditional, unpersonalized models: the intra-class correlation improves from a baseline performance of 19\% to a personalized performance of 35\% while also providing confidence in the model\textquotesingle s estimates -- in contrast to existing models for the target task. Additionally, DeepFaceLIFT automatically discovers the pain-relevant facial regions for each person, allowing for an easy interpretation of the pain-related facial cues.
Identifying Harm Events in Clinical Care through Medical Narratives
Venue: arXiv cs.CL 2017
Year: 2017

Preventable medical errors are estimated to be among the leading causes of injury and death in the United States. To prevent such errors, healthcare systems have implemented patient safety and incident reporting systems. These systems enable clinicians to report unsafe conditions and cases where patients have been harmed due to errors in medical care. These reports are narratives in natural language and while they provide detailed information about the situation, it is non-trivial to perform large scale analysis for identifying common causes of errors and harm to the patients. In this work, we present a method based on attentive convolutional and recurrent networks for identifying harm events in patient care and categorize the harm based on its severity level. We demonstrate that our methods can significantly improve the performance over existing methods in identifying harm in clinical care.
Generalized Uniformity Testing
Venue: arXiv cs.DS 2017
Year: 2017

In this work, we revisit the problem of uniformity testing of discrete probability distributions. A fundamental problem in distribution testing, testing uniformity over a known domain has been addressed over a significant line of works, and is by now fully understood. The complexity of deciding whether an unknown distribution is uniform over its unknown (and arbitrary) support, however, is much less clear. Yet, this task arises as soon as no prior knowledge on the domain is available, or whenever the samples originate from an unknown and unstructured universe. In this work, we introduce and study this generalized uniformity testing question, and establish nearly tight upper and lower bound showing that -- quite surprisingly -- its sample complexity significantly differs from the known-domain case. Moreover, our algorithm is intrinsically adaptive, in contrast to the overwhelming majority of known distribution testing algorithms.
On Error-Correction Performance and Implementation of Polar Code List Decoders for 5G
Venue: arXiv cs.IT 2017
Year: 2017

Polar codes are a class of capacity achieving error correcting codes that has been recently selected for the next generation of wireless communication standards (5G). Polar code decoding algorithms have evolved in various directions, striking different balances between error-correction performance, speed and complexity. Successive-cancellation list (SCL) and its incarnations constitute a powerful, well-studied set of algorithms, in constant improvement. At the same time, different implementation approaches provide a wide range of area occupations and latency results. 5G puts a focus on improved error-correction performance, high throughput and low power consumption: a comprehensive study considering all these metrics is currently lacking in literature. In this work, we evaluate SCL-based decoding algorithms in terms of error-correction performance and compare them to low-density parity-check (LDPC) codes. Moreover, we consider various decoder implementations, for both polar and LDPC codes, and compare their area occupation and power and energy consumption when targeting short code lengths and rates. Our work shows that among SCL-based decoders, the partitioned SCL (PSCL) provides the lowest area occupation and power consumption, whereas fast simplified SCL (Fast-SSCL) yields the lowest energy consumption. Compared to LDPC decoder architectures, different SCL implementations occupy up to 17.1x less area, dissipate up to 7.35x less power, and up to 26x less energy.
Active Orthogonal Matching Pursuit for Sparse Subspace Clustering
Venue: arXiv cs.LG 2017
Year: 2017

Sparse Subspace Clustering (SSC) is a state-of-the-art method for clustering high-dimensional data points lying in a union of low-dimensional subspaces. However, while $\ell_1$ optimization-based SSC algorithms suffer from high computational complexity, other variants of SSC, such as Orthogonal Matching Pursuit-based SSC (OMP-SSC), lose clustering accuracy in pursuit of improving time efficiency. In this letter, we propose a novel Active OMP-SSC, which improves clustering accuracy of OMP-SSC by adaptively updating data points and randomly dropping data points in the OMP process, while still enjoying the low computational complexity of greedy pursuit algorithms. We provide heuristic analysis of our approach, and explain how these two active steps achieve a better tradeoff between connectivity and separation. Numerical results on both synthetic data and real-world data validate our analyses and show the advantages of the proposed active algorithm.
Dialogue Act Segmentation for Vietnamese Human-Human Conversational Texts
Venue: arXiv cs.CL 2017
Year: 2017

Dialog act identification plays an important role in understanding conversations. It has been widely applied in many fields such as dialogue systems, automatic machine translation, automatic speech recognition, and especially useful in systems with human-computer natural language dialogue interfaces such as virtual assistants and chatbots. The first step of identifying dialog act is identifying the boundary of the dialog act in utterances. In this paper, we focus on segmenting the utterance according to the dialog act boundaries, i.e. functional segments identification, for Vietnamese utterances. We investigate carefully functional segment identification in two approaches: (1) machine learning approach using maximum entropy (ME) and conditional random fields (CRFs); (2) deep learning approach using bidirectional Long Short-Term Memory (LSTM) with a CRF layer (Bi-LSTM-CRF) on two different conversational datasets: (1) Facebook messages (Message data); (2) transcription from phone conversations (Phone data). To the best of our knowledge, this is the first work that applies deep learning based approach to dialog act segmentation. As the results show, deep learning approach performs appreciably better as to compare with traditional machine learning approaches. Moreover, it is also the first study that tackles dialog act and functional segment identification for Vietnamese.