OpenRaiser/Intern-Atlas huggingface dataset:
Connected Vertex Cover for $(sP_1+P_5)$-Free Graphs
Venue: arXiv cs.DS 2018
Year: 2018

The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most $k$ that induces a connected subgraph of $G$. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for $H$-free graphs if $H$ is not a linear forest (a graph is $H$-free if it does not contain $H$ as an induced subgraph). It is easy to see that Connected Vertex Cover is polynomial-time solvable for $P_4$-free graphs. We continue the search for tractable graph classes: we prove that it is also polynomial-time solvable for $(sP_1+P_5)$-free graphs for every integer $s\geq 0$.
An Incremental Self-Organizing Architecture for Sensorimotor Learning and Prediction
Venue: arXiv cs.CV 2018
Year: 2018

During visuomotor tasks, robots must compensate for temporal delays inherent in their sensorimotor processing systems. Delay compensation becomes crucial in a dynamic environment where the visual input is constantly changing, e.g., during the interacting with a human demonstrator. For this purpose, the robot must be equipped with a prediction mechanism for using the acquired perceptual experience to estimate possible future motor commands. In this paper, we present a novel neural network architecture that learns prototypical visuomotor representations and provides reliable predictions on the basis of the visual input. These predictions are used to compensate for the delayed motor behavior in an online manner. We investigate the performance of our method with a set of experiments comprising a humanoid robot that has to learn and generate visually perceived arm motion trajectories. We evaluate the accuracy in terms of mean prediction error and analyze the response of the network to novel movement demonstrations. Additionally, we report experiments with incomplete data sequences, showing the robustness of the proposed architecture in the case of a noisy and faulty visual sensor.
Protecting real-time GPU kernels on integrated CPU-GPU SoC platforms
Venue: arXiv cs.PF 2018
Year: 2018

Integrated CPU-GPU architecture provides excellent acceleration capabilities for data parallel applications on embedded platforms while meeting the size, weight and power (SWaP) requirements. However, sharing of main memory between CPU applications and GPU kernels can severely affect the execution of GPU kernels and diminish the performance gain provided by GPU. For example, in the NVIDIA Tegra K1 platform which has the integrated CPU-GPU architecture, we noticed that in the worst case scenario, the GPU kernels can suffer as much as 4X slowdown in the presence of co-running memory intensive CPU applications compared to their solo execution. In this paper, we propose a software mechanism, which we call BWLOCK++, to protect the performance of GPU kernels from co-scheduled memory intensive CPU applications.
Dual Long Short-Term Memory Networks for Sub-Character Representation Learning
Venue: arXiv cs.CL 2018
Year: 2018

Characters have commonly been regarded as the minimal processing unit in Natural Language Processing (NLP). But many non-latin languages have hieroglyphic writing systems, involving a big alphabet with thousands or millions of characters. Each character is composed of even smaller parts, which are often ignored by the previous work. In this paper, we propose a novel architecture employing two stacked Long Short-Term Memory Networks (LSTMs) to learn sub-character level representation and capture deeper level of semantic meanings. To build a concrete study and substantiate the efficiency of our neural architecture, we take Chinese Word Segmentation as a research case example. Among those languages, Chinese is a typical case, for which every character contains several components called radicals. Our networks employ a shared radical level embedding to solve both Simplified and Traditional Chinese Word Segmentation, without extra Traditional to Simplified Chinese conversion, in such a highly end-to-end way the word segmentation can be significantly simplified compared to the previous work. Radical level embeddings can also capture deeper semantic meaning below character level and improve the system performance of learning. By tying radical and character embeddings together, the parameter count is reduced whereas semantic knowledge is shared and transferred between two levels, boosting the performance largely. On 3 out of 4 Bakeoff 2005 datasets, our method surpassed state-of-the-art results by up to 0.4%. Our results are reproducible, source codes and corpora are available on GitHub.
Deep Learning for Massive MIMO CSI Feedback
Venue: arXiv cs.IT 2018
Year: 2018

In frequency division duplex mode, the downlink channel state information (CSI) should be sent to the base station through feedback links so that the potential gains of a massive multiple-input multiple-output can be exhibited. However, such a transmission is hindered by excessive feedback overhead. In this letter, we use deep learning technology to develop CsiNet, a novel CSI sensing and recovery {mechanism} that learns to effectively use channel structure from training samples. CsiNet learns a transformation from CSI to a near-optimal number of representations (or codewords) and an inverse transformation from codewords to CSI. We perform experiments to demonstrate that CsiNet can recover CSI with significantly improved reconstruction quality compared with existing compressive sensing (CS)-based methods. Even at excessively low compression regions where CS-based methods cannot work, CsiNet retains effective beamforming gain.
Stochastic Multi-armed Bandits in Constant Space
Venue: arXiv cs.DS 2018
Year: 2018

We consider the stochastic bandit problem in the sublinear space setting, where one cannot record the win-loss record for all $K$ arms. We give an algorithm using $O(1)$ words of space with regret \[ \sum_{i=1}^{K}\frac{1}{Δ_i}\log \frac{Δ_i}Δ\log T \] where $Δ_i$ is the gap between the best arm and arm $i$ and $Δ$ is the gap between the best and the second-best arms. If the rewards are bounded away from $0$ and $1$, this is within an $O(\log 1/Δ)$ factor of the optimum regret possible without space constraints.
Demographics and discussion influence views on algorithmic fairness
Venue: arXiv cs.CY 2018
Year: 2018

The field of algorithmic fairness has highlighted ethical questions which may not have purely technical answers. For example, different algorithmic fairness constraints are often impossible to satisfy simultaneously, and choosing between them requires value judgments about which people may disagree. Achieving consensus on algorithmic fairness will be difficult unless we understand why people disagree in the first place. Here we use a series of surveys to investigate how two factors affect disagreement: demographics and discussion. First, we study whether disagreement on algorithmic fairness questions is caused partially by differences in demographic backgrounds. This is a question of interest because computer science is demographically non-representative. If beliefs about algorithmic fairness correlate with demographics, and algorithm designers are demographically non-representative, decisions made about algorithmic fairness may not reflect the will of the population as a whole. We show, using surveys of three separate populations, that there are gender differences in beliefs about algorithmic fairness. For example, women are less likely to favor including gender as a feature in an algorithm which recommends courses to students if doing so would make female students less likely to be recommended science courses. Second, we investigate whether people's views on algorithmic fairness can be changed by discussion and show, using longitudinal surveys of students in two computer science classes, that they can.
Segmenting Sky Pixels in Images
Venue: arXiv cs.CV 2018
Year: 2018

Outdoor scene parsing models are often trained on ideal datasets and produce quality results. However, this leads to a discrepancy when applied to the real world. The quality of scene parsing, particularly sky classification, decreases in night time images, images involving varying weather conditions, and scene changes due to seasonal weather. This project focuses on approaching these challenges by using a state-of-the-art model in conjunction with a non-ideal dataset: SkyFinder and a subset from SUN database with Sky object. We focus specifically on sky segmentation, the task of determining sky and not-sky pixels, and improving upon an existing state-of-the-art model: RefineNet. As a result of our efforts, we have seen an improvement of 10-15% in the average MCR compared to the prior methods on SkyFinder dataset. We have also improved from an off-the shelf-model in terms of average mIOU by nearly 35%. Further, we analyze our trained models on images w.r.t two aspects: times of day and weather, and find that, in spite of facing same challenges as prior methods, our trained models significantly outperform them.
Fog Computing based SDI Framework for Mineral Resources Information Infrastructure Management in India
Venue: arXiv cs.DC 2018
Year: 2018

Spatial Data Infrastructure (SDI) is an important concept for sharing spatial data across the web. With cumulative techniques with spatial cloud computing and fog computing, SDI has the greater potential and has been emerged as a tool for processing, analysis and transmission of spatial data. The Fog computing is a paradigm where Fog devices help to increase throughput and reduce latency at the edge of the client with respect to cloud computing environment. This paper proposed and developed a fog computing based SDI framework for mining analytics from spatial big data for mineral resources management in India. We built a prototype using Raspberry Pi, an embedded microprocessor. We validated by taking suitable case study of mineral resources management in India by doing preliminary analysis including overlay analysis. Results showed that fog computing hold a great promise for analysis of spatial data. We used open source GIS i.e. QGIS and QIS plugin for reducing the transmission to cloud from the fog node.
Folding Polyominoes into (Poly)Cubes
Venue: arXiv cs.CG 2018
Year: 2018

We study the problem of folding a polyomino $P$ into a polycube $Q$, allowing faces of $Q$ to be covered multiple times. First, we define a variety of folding models according to whether the folds (a) must be along grid lines of $P$ or can divide squares in half (diagonally and/or orthogonally), (b) must be mountain or can be both mountain and valley, (c) can remain flat (forming an angle of $180^\circ$), and (d) must lie on just the polycube surface or can have interior faces as well. Second, we give all the inclusion relations among all models that fold on the grid lines of $P$. Third, we characterize all polyominoes that can fold into a unit cube, in some models. Fourth, we give a linear-time dynamic programming algorithm to fold a tree-shaped polyomino into a constant-size polycube, in some models. Finally, we consider the triangular version of the problem, characterizing which polyiamonds fold into a regular tetrahedron.
Rewriting in Free Hypergraph Categories
Venue: arXiv cs.LO 2018
Year: 2018

We study rewriting for equational theories in the context of symmetric monoidal categories where there is a separable Frobenius monoid on each object. These categories, also called hypergraph categories, are increasingly relevant: Frobenius structures recently appeared in cross-disciplinary applications, including the study of quantum processes, dynamical systems and natural language processing. In this work we give a combinatorial characterisation of arrows of a free hypergraph category as cospans of labelled hypergraphs and establish a precise correspondence between rewriting modulo Frobenius structure on the one hand and double-pushout rewriting of hypergraphs on the other. This interpretation allows to use results on hypergraphs to ensure decidability of confluence for rewriting in a free hypergraph category. Our results generalise previous approaches where only categories generated by a single object (props) were considered.
Impact of Spatial Filtering on Distortion from Low-Noise Amplifiers in Massive MIMO Base Stations
Venue: arXiv cs.IT 2018
Year: 2018

In massive MIMO base stations, power consumption and cost of the low-noise amplifiers (LNAs) can be substantial because of the many antennas. We investigate the feasibility of inexpensive, power efficient LNAs, which inherently are less linear. A polynomial model is used to characterize the nonlinear LNAs and to derive the second-order statistics and spatial correlation of the distortion. We show that, with spatial matched filtering (maximum-ratio combining) at the receiver, some distortion terms combine coherently, and that the SINR of the symbol estimates therefore is limited by the linearity of the LNAs. Furthermore, it is studied how the power from a blocker in the adjacent frequency band leaks into the main band and creates distortion. The distortion term that scales cubically with the power received from the blocker has a spatial correlation that can be filtered out by spatial processing and only the coherent term that scales quadratically with the power remains. When the blocker is in free-space line-of-sight and the LNAs are identical, this quadratic term has the same spatial direction as the desired signal, and hence cannot be removed by linear receiver processing.
Adversarial Patch
Venue: arXiv cs.CV 2018
Year: 2018

We present a method to create universal, robust, targeted adversarial image patches in the real world. The patches are universal because they can be used to attack any scene, robust because they work under a wide variety of transformations, and targeted because they can cause a classifier to output any target class. These adversarial patches can be printed, added to any scene, photographed, and presented to image classifiers; even when the patches are small, they cause the classifiers to ignore the other items in the scene and report a chosen target class. To reproduce the results from the paper, our code is available at https://github.com/tensorflow/cleverhans/tree/master/examples/adversarial_patch
Report: Dynamic Eye Movement Matching and Visualization Tool in Neuro Gesture
Venue: arXiv cs.NE 2018
Year: 2018

In the research of the impact of gestures using by a lecturer, one challenging task is to infer the attention of a group of audiences. Two important measurements that can help infer the level of attention are eye movement data and Electroencephalography (EEG) data. Under the fundamental assumption that a group of people would look at the same place if they all pay attention at the same time, we apply a method, "Time Warp Edit Distance", to calculate the similarity of their eye movement trajectories. Moreover, we also cluster eye movement pattern of audiences based on these pair-wised similarity metrics. Besides, since we don't have a direct metric for the "attention" ground truth, a visual assessment would be beneficial to evaluate the gesture-attention relationship. Thus we also implement a visualization tool.
Topological and Algebraic Properties of Chernoff Information between Gaussian Graphs
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we want to find out the determining factors of Chernoff information in distinguishing a set of Gaussian graphs. We find that Chernoff information of two Gaussian graphs can be determined by the generalized eigenvalues of their covariance matrices. We find that the unit generalized eigenvalue doesn't affect Chernoff information and its corresponding dimension doesn't provide information for classification purpose. In addition, we can provide a partial ordering using Chernoff information between a series of Gaussian trees connected by independent grafting operations. With the relationship between generalized eigenvalues and Chernoff information, we can do optimal linear dimension reduction with least loss of information for classification.
Sky detection and log illumination refinement for PDE-based hazy image contrast enhancement
Venue: arXiv cs.CV 2018
Year: 2018

This report presents the results of a sky detection technique used to improve the performance of a previously developed partial differential equation (PDE)-based hazy image enhancement algorithm. Additionally, a proposed alternative method utilizes a function for log illumination refinement to improve de-hazing results while avoiding over-enhancement of sky or homogeneous regions. The algorithms were tested with several benchmark and calibration images and compared with several standard algorithms from the literature. Results indicate that the algorithms yield mostly consistent results and surpasses several of the other algorithms in terms of colour and contrast enhancement in addition to improved edge visibility.
Topic Compositional Neural Language Model
Venue: arXiv cs.LG 2018
Year: 2018

We propose a Topic Compositional Neural Language Model (TCNLM), a novel method designed to simultaneously capture both the global semantic meaning and the local word ordering structure in a document. The TCNLM learns the global semantic coherence of a document via a neural topic model, and the probability of each learned latent topic is further used to build a Mixture-of-Experts (MoE) language model, where each expert (corresponding to one topic) is a recurrent neural network (RNN) that accounts for learning the local structure of a word sequence. In order to train the MoE model efficiently, a matrix factorization method is applied, by extending each weight matrix of the RNN to be an ensemble of topic-dependent weight matrices. The degree to which each member of the ensemble is used is tied to the document-dependent probability of the corresponding topics. Experimental results on several corpora show that the proposed approach outperforms both a pure RNN-based model and other topic-guided language models. Further, our model yields sensible topics, and also has the capacity to generate meaningful sentences conditioned on given topics.
An Innovative Approach to Achieve Compositionality Efficiently using Multi-Version Object Based Transactional Systems
Venue: arXiv cs.DC 2018
Year: 2018

In the modern era of multicore processors, utilizing cores is a tedious job. Synchronization and communication among processors involve high cost. Software transaction memory systems (STMs) addresses this issues and provide better concurrency in which programmer need not have to worry about consistency issues. Another advantage of STMs is that they facilitate compositionality of concurrent programs with great ease. Different concurrent operations that need to be composed to form a single atomic unit is achieved by encapsulating them in a single transaction. In this paper, we introduce a new STM system as multi-version object based STM (MVOSTM) which is the combination of both of these ideas for harnessing greater concurrency in STMs. As the name suggests MVOSTM, works on a higher level and maintains multiple versions corresponding to each key. We have developed MVOSTM with the unlimited number of versions corresponding to each key. In addition to that, we have developed garbage collection for MVOSTM (MVOSTM-GC) to delete unwanted versions corresponding to the keys to reduce traversal overhead. MVOSTM provides greater concurrency while reducing the number of aborts and it ensures compositionality by making the transactions atomic. Here, we have used MVOSTM for the list and hash-table data structure as list-MVOSTM and HT- MVOSTM. Experimental results of list-MVOSTM outperform almost two to twenty fold speedup than existing state-of-the-art list based STMs (Trans-list, Boosting-list, NOrec-list, list-MVTO, and list-OSTM). HT-MVOSTM shows a significant performance gain of almost two to nineteen times better than existing state-of-the-art hash-table based STMs (ESTM, RWSTMs, HT-MVTO, and HT-OSTM). MVOSTM with list and hash-table shows the least number of aborts among all the existing STM algorithms. MVOSTM satisfies correctness-criteria as opacity.
Game-Theoretic Design of Optimal Two-Sided Rating Protocols for Service Exchange Dilemma in Crowdsourcing
Venue: arXiv cs.GT 2018
Year: 2018

Despite the increasing popularity and successful examples of crowdsourcing, it is stripped of aureole when collective efforts are derailed or severely hindered by elaborate sabotage. A service exchange dilemma arises when non-cooperation among self-interested users, and zero social welfare is obtained at myopic equilibrium. Traditional rating protocols are not effective to overcome the inefficiency of the socially undesirable equilibrium due to specific features of crowdsourcing: a large number of anonymous users having asymmetric service requirements, different service capabilities, and dynamically joining/leaving a crowdsourcing platform with imperfect monitoring. In this paper, we develop the first game-theoretic design of the two-sided rating protocol to stimulate cooperation among self-interested users, which consists of a recommended strategy and a rating update rule. The recommended strategy recommends a desirable behavior from three predefined plans according to intrinsic parameters, while the rating update rule involves the update of ratings of both users, and uses differential punishments that punish users with different ratings differently. By quantifying necessary and sufficient conditions for a sustainable social norm, we formulate the problem of designing an optimal two-sided rating protocol that maximizes the social welfare among all sustainable protocols, provide design guidelines for optimal two-sided rating protocols and a low-complexity algorithm to select optimal design parameters in an alternate manner. Finally, evaluation results show the validity and effectiveness of our protocol designed for service exchange dilemma in crowdsourcing.
Handwritten Bangla Character Recognition Using The State-of-Art Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

In spite of advances in object recognition technology, Handwritten Bangla Character Recognition (HBCR) remains largely unsolved due to the presence of many ambiguous handwritten characters and excessively cursive Bangla handwritings. Even the best existing recognizers do not lead to satisfactory performance for practical applications related to Bangla character recognition and have much lower performance than those developed for English alpha-numeric characters. To improve the performance of HBCR, we herein present the application of the state-of-the-art Deep Convolutional Neural Networks (DCNN) including VGG Network, All Convolution Network (All-Conv Net), Network in Network (NiN), Residual Network, FractalNet, and DenseNet for HBCR. The deep learning approaches have the advantage of extracting and using feature information, improving the recognition of 2D shapes with a high degree of invariance to translation, scaling and other distortions. We systematically evaluated the performance of DCNN models on publicly available Bangla handwritten character dataset called CMATERdb and achieved the superior recognition accuracy when using DCNN models. This improvement would help in building an automatic HBCR system for practical applications.