OpenRaiser/Intern-Atlas huggingface dataset:
Soft Methodology for Cost-and-error Sensitive Classification
Venue: arXiv cs.LG 2017
Year: 2017

Many real-world data mining applications need varying cost for different types of classification errors and thus call for cost-sensitive classification algorithms. Existing algorithms for cost-sensitive classification are successful in terms of minimizing the cost, but can result in a high error rate as the trade-off. The high error rate holds back the practical use of those algorithms. In this paper, we propose a novel cost-sensitive classification methodology that takes both the cost and the error rate into account. The methodology, called soft cost-sensitive classification, is established from a multicriteria optimization problem of the cost and the error rate, and can be viewed as regularizing cost-sensitive classification with the error rate. The simple methodology allows immediate improvements of existing cost-sensitive classification algorithms. Experiments on the benchmark and the real-world data sets show that our proposed methodology indeed achieves lower test error rates and similar (sometimes lower) test costs than existing cost-sensitive classification algorithms. We also demonstrate that the methodology can be extended for considering the weighted error rate instead of the original error rate. This extension is useful for tackling unbalanced classification problems.
Learning Wireless Networks' Topologies Using Asymmetric Granger Causality
Venue: arXiv cs.NI 2017
Year: 2017

Sharing spectrum with a communicating incumbent user (IU) network requires avoiding interference to IU receivers. But since receivers are passive when in the receive mode and cannot be detected, the network topology can be used to predict the potential receivers of a currently active transmitter. For this purpose, this paper proposes a method to detect the directed links between IUs of time multiplexing communication networks from their transmission start and end times. It models the response mechanism of commonly used communication protocols using Granger causality: the probability of an IU starting a transmission after another IU's transmission ends increases if the former is a receiver of the latter. This paper proposes a non-parametric test statistic for detecting such behavior. To help differentiate between a response and the opportunistic access of available spectrum, the same test statistic is used to estimate the response time of each link. The causal structure of the response is studied through a discrete time Markov chain that abstracts the IUs' medium access protocol and focuses on the response time and response probability of 2 IUs. Through NS-3 simulations, it is shown that the proposed algorithm outperforms existing methods in accurately learning the topologies of infrastructure-based networks and that it can infer the directed data flow in ad hoc networks with finer time resolution than an existing method.
High Capacity, Secure (n, n/8) Multi Secret Image Sharing Scheme with Security Key
Venue: arXiv cs.CR 2017
Year: 2017

The rising need of secret image sharing with high security has led to much advancement in lucrative exchange of important images which contain vital and confidential information. Multi secret image sharing system (MSIS) is an efficient and robust method for transmitting one or more secret images securely. In recent research, n secret images are encrypted into n or n+ 1 shared images and stored in different database servers. The decoder has to receive all n or n+1 encrypted images to reproduce the secret image. One can recover partial secret information from n-1 or fewer shared images, which poses risk for the confidential information encrypted. In this proposed paper we developed a novel algorithm to increase the sharing capacity by using (n, n/8) multi-secret sharing scheme with increased security by generating a unique security key. A unrevealed comparison image is used to produce shares which makes the secret image invulnerable to the hackers
Artifact reduction for separable non-local means
Venue: arXiv cs.CV 2017
Year: 2017

It was recently demonstrated [J. Electron. Imaging, 25(2), 2016] that one can perform fast non-local means (NLM) denoising of one-dimensional signals using a method called lifting. The cost of lifting is independent of the patch length, which dramatically reduces the run-time for large patches. Unfortunately, it is difficult to directly extend lifting for non-local means denoising of images. To bypass this, the authors proposed a separable approximation in which the image rows and columns are filtered using lifting. The overall algorithm is significantly faster than NLM, and the results are comparable in terms of PSNR. However, the separable processing often produces vertical and horizontal stripes in the image. This problem was previously addressed by using a bilateral filter-based post-smoothing, which was effective in removing some of the stripes. In this letter, we demonstrate that stripes can be mitigated in the first place simply by involving the neighboring rows (or columns) in the filtering. In other words, we use a two-dimensional search (similar to NLM), while still using one-dimensional patches (as in the previous proposal). The novelty is in the observation that one can use lifting for performing two-dimensional searches. The proposed approach produces artifact-free images, whose quality and PSNR are comparable to NLM, while being significantly faster.
Automated Lemma Synthesis in Symbolic-Heap Separation Logic
Venue: arXiv cs.LO 2017
Year: 2017

The symbolic-heap fragment of separation logic has been actively developed and advocated for verifying the memory-safety property of computer programs. At present, one of its biggest challenges is to effectively prove entailments containing inductive heap predicates. These entailments are usually proof obligations generated when verifying programs that manipulate complex data structures like linked lists, trees, or graphs. To assist in proving such entailments, this paper introduces a lemma synthesis framework, which automatically discovers lemmas to serve as eureka steps in the proofs. Mathematical induction and template-based constraint solving are two pillars of our framework. To derive the supporting lemmas for a given entailment, the framework firstly identifies possible lemma templates from the entailment's heap structure. It then sets up unknown relations among each template's variables and conducts structural induction proof to generate constraints about these relations. Finally, it solves the constraints to find out actual definitions of the unknown relations, thus discovers the lemmas. We have integrated this framework into a prototype prover and have experimented it on various entailment benchmarks. The experimental results show that our lemma-synthesis-assisted prover can prove many entailments that could not be handled by existing techniques. This new proposal opens up more opportunities to automatically reason with complex inductive heap predicates.
Tackling information asymmetry in networks: a new entropy-based ranking index
Venue: arXiv cs.SI 2017
Year: 2017

Information is a valuable asset for agents in socio-economic systems, a significant part of the information being entailed into the very network of connections between agents. The different interlinkages patterns that agents establish may, in fact, lead to asymmetries in the knowledge of the network structure; since this entails a different ability of quantifying relevant systemic properties (e.g. the risk of financial contagion in a network of liabilities), agents capable of providing a better estimate of (otherwise) unaccessible network properties, ultimately have a competitive advantage. In this paper, we address for the first time the issue of quantifying the information asymmetry arising from the network topology. To this aim, we define a novel index - InfoRank - intended to measure the quality of the information possessed by each node, computing the Shannon entropy of the ensemble conditioned on the node-specific information. Further, we test the performance of our novel ranking procedure in terms of the reconstruction accuracy of the (unaccessible) network structure and show that it outperforms other popular centrality measures in identifying the "most informative" nodes. Finally, we discuss the socio-economic implications of network information asymmetry.
Impact of Coreference Resolution on Slot Filling
Venue: arXiv cs.CL 2017
Year: 2017

In this paper, we demonstrate the importance of coreference resolution for natural language processing on the example of the TAC Slot Filling shared task. We illustrate the strengths and weaknesses of automatic coreference resolution systems and provide experimental results to show that they improve performance in the slot filling end-to-end setting. Finally, we publish KBPchains, a resource containing automatically extracted coreference chains from the TAC source corpus in order to support other researchers working on this topic.
Interactions of Computational Complexity Theory and Mathematics
Venue: arXiv cs.CC 2017
Year: 2017

$ $[This paper is a (self contained) chapter in a new book, Mathematics and Computation, whose draft is available on my homepage at https://www.math.ias.edu/avi/book ]. We survey some concrete interaction areas between computational complexity theory and different fields of mathematics. We hope to demonstrate here that hardly any area of modern mathematics is untouched by the computational connection (which in some cases is completely natural and in others may seem quite surprising). In my view, the breadth, depth, beauty and novelty of these connections is inspiring, and speaks to a great potential of future interactions (which indeed, are quickly expanding). We aim for variety. We give short, simple descriptions (without proofs or much technical detail) of ideas, motivations, results and connections; this will hopefully entice the reader to dig deeper. Each vignette focuses only on a single topic within a large mathematical filed. We cover the following: $\bullet$ Number Theory: Primality testing $\bullet$ Combinatorial Geometry: Point-line incidences $\bullet$ Operator Theory: The Kadison-Singer problem $\bullet$ Metric Geometry: Distortion of embeddings $\bullet$ Group Theory: Generation and random generation $\bullet$ Statistical Physics: Monte-Carlo Markov chains $\bullet$ Analysis and Probability: Noise stability $\bullet$ Lattice Theory: Short vectors $\bullet$ Invariant Theory: Actions on matrix tuples
On Quantum Stabilizer Codes derived from Local Frobenius Rings
Venue: arXiv cs.IT 2017
Year: 2017

In this paper we consider stabilizer codes over local Frobenius rings. First, we study the relative minimum distances of a stabilizer code and its reduction onto the residue field. We show that for various scenarios, a free stabilizer code over the ring does not underperform the according stabilizer code over the field. This leads us to conjecture that the same is true for all free stabilizer codes. Secondly, we focus on the isometries of stabilizer codes. We present some preliminary results and introduce some interesting open problems.
CANDiS: Coupled & Attention-Driven Neural Distant Supervision
Venue: arXiv cs.CL 2017
Year: 2017

Distant Supervision for Relation Extraction uses heuristically aligned text data with an existing knowledge base as training data. The unsupervised nature of this technique allows it to scale to web-scale relation extraction tasks, at the expense of noise in the training data. Previous work has explored relationships among instances of the same entity-pair to reduce this noise, but relationships among instances across entity-pairs have not been fully exploited. We explore the use of inter-instance couplings based on verb-phrase and entity type similarities. We propose a novel technique, CANDiS, which casts distant supervision using inter-instance coupling into an end-to-end neural network model. CANDiS incorporates an attention module at the instance-level to model the multi-instance nature of this problem. CANDiS outperforms existing state-of-the-art techniques on a standard benchmark dataset.
A Single-Channel Architecture for Algebraic Integer Based 8$\times$8 2-D DCT Computation
Venue: arXiv cs.AR 2017
Year: 2017

An area efficient row-parallel architecture is proposed for the real-time implementation of bivariate algebraic integer (AI) encoded 2-D discrete cosine transform (DCT) for image and video processing. The proposed architecture computes 8$\times$8 2-D DCT transform based on the Arai DCT algorithm. An improved fast algorithm for AI based 1-D DCT computation is proposed along with a single channel 2-D DCT architecture. The design improves on the 4-channel AI DCT architecture that was published recently by reducing the number of integer channels to one and the number of 8-point 1-D DCT cores from 5 down to 2. The architecture offers exact computation of 8$\times$8 blocks of the 2-D DCT coefficients up to the FRS, which converts the coefficients from the AI representation to fixed-point format using the method of expansion factors. Prototype circuits corresponding to FRS blocks based on two expansion factors are realized, tested, and verified on FPGA-chip, using a Xilinx Virtex-6 XC6VLX240T device. Post place-and-route results show a 20% reduction in terms of area compared to the 2-D DCT architecture requiring five 1-D AI cores. The area-time and area-time${}^2$ complexity metrics are also reduced by 23% and 22% respectively for designs with 8-bit input word length. The digital realizations are simulated up to place and route for ASICs using 45 nm CMOS standard cells. The maximum estimated clock rate is 951 MHz for the CMOS realizations indicating 7.608$\cdot$10$^9$ pixels/seconds and a 8$\times$8 block rate of 118.875 MHz.
Flexible Multi-Group Single-Carrier Modulation: Optimal Subcarrier Grouping and Rate Maximization
Venue: arXiv cs.IT 2017
Year: 2017

Orthogonal frequency division multiplexing (OFDM) and single-carrier frequency domain equalization (SC-FDE) are two commonly adopted modulation schemes for frequency-selective channels. Compared to SC-FDE, OFDM generally achieves higher data rate, but at the cost of higher transmit signal peak-to-average power ratio (PAPR) that leads to lower power amplifier efficiency. This paper proposes a new modulation scheme, called flexible multi-group single-carrier (FMG-SC), which encapsulates both OFDM and SC-FDE as special cases, thus achieving more flexible rate-PAPR trade-offs between them. Specifically, a set of frequency subcarriers are flexibly divided into orthogonal groups based on their channel gains, and SC-FDE is applied over each of the groups to send different data streams in parallel. We aim to maximize the achievable sum-rate of all groups by optimizing the subcarrier-group mapping. We propose two low-complexity subcarrier grouping methods and show via simulation that they perform very close to the optimal grouping by exhaustive search. Simulation results also show the effectiveness of the proposed FMG-SC modulation scheme with optimized subcarrier grouping in improving the rate-PAPR trade-off over conventional OFDM and SC-FDE.
Separation of Moving Sound Sources Using Multichannel NMF and Acoustic Tracking
Venue: arXiv cs.SD 2017
Year: 2017

In this paper we propose a method for separation of moving sound sources. The method is based on first tracking the sources and then estimation of source spectrograms using multichannel non-negative matrix factorization (NMF) and extracting the sources from the mixture by single-channel Wiener filtering. We propose a novel multichannel NMF model with time-varying mixing of the sources denoted by spatial covariance matrices (SCM) and provide update equations for optimizing model parameters minimizing squared Frobenius norm. The SCMs of the model are obtained based on estimated directions of arrival of tracked sources at each time frame. The evaluation is based on established objective separation criteria and using real recordings of two and three simultaneous moving sound sources. The compared methods include conventional beamforming and ideal ratio mask separation. The proposed method is shown to exceed the separation quality of other evaluated blind approaches according to all measured quantities. Additionally, we evaluate the method's susceptibility towards tracking errors by comparing the separation quality achieved using annotated ground truth source trajectories.
Deep Learning for Accelerated Ultrasound Imaging
Venue: arXiv cs.CV 2017
Year: 2017

In portable, 3-D, or ultra-fast ultrasound (US) imaging systems, there is an increasing demand to reconstruct high quality images from limited number of data. However, the existing solutions require either hardware changes or computationally expansive algorithms. To overcome these limitations, here we propose a novel deep learning approach that interpolates the missing RF data by utilizing the sparsity of the RF data in the Fourier domain. Extensive experimental results from sub-sampled RF data from a real US system confirmed that the proposed method can effectively reduce the data rate without sacrificing the image quality.
Towards efficient coexistence of IEEE 802.15.4e TSCH and IEEE 802.11
Venue: arXiv cs.NI 2017
Year: 2017

A major challenge in wide deployment of smart wireless devices, using different technologies and sharing the same 2.4 GHz spectrum, is to achieve coexistence across multiple technologies. The IEEE~802.11 (WLAN) and the IEEE 802.15.4e TSCH (WSN) where designed with different goals in mind and both play important roles for respective applications. However, they cause mutual interference and degraded performance while operating in the same space. To improve this situation we propose an approach to enable a cooperative control which type of network is transmitting at given time, frequency and place. We recognize that TSCH based sensor network is expected to occupy only small share of time, and that the nodes are by design tightly synchronized. We develop mechanism enabling over-the-air synchronization of the Wi-Fi network to the TSCH based sensor network. Finally, we show that Wi-Fi network can avoid transmitting in the "collision periods". We provide full design and show prototype implementation based on the Commercial off-the-shelf (COTS) devices. Our solution does not require changes in any of the standards.
Transform-Invariant Non-Parametric Clustering of Covariance Matrices and its Application to Unsupervised Joint Segmentation and Action Discovery
Venue: arXiv cs.LG 2017
Year: 2017

In this work, we tackle the problem of transform-invariant unsupervised learning in the space of Covariance matrices and applications thereof. We begin by introducing the Spectral Polytope Covariance Matrix (SPCM) Similarity function; a similarity function for Covariance matrices, invariant to any type of transformation. We then derive the SPCM-CRP mixture model, a transform-invariant non-parametric clustering approach for Covariance matrices that leverages the proposed similarity function, spectral embedding and the distance-dependent Chinese Restaurant Process (dd-CRP) (Blei and Frazier, 2011). The scalability and applicability of these two contributions is extensively validated on real-world Covariance matrix datasets from diverse research fields. Finally, we couple the SPCM-CRP mixture model with the Bayesian non-parametric Indian Buffet Process (IBP) - Hidden Markov Model (HMM) (Fox et al., 2009), to jointly segment and discover transform-invariant action primitives from complex sequential data. Resulting in a topic-modeling inspired hierarchical model for unsupervised time-series data analysis which we call ICSC-HMM (IBP Coupled SPCM-CRP Hidden Markov Model). The ICSC-HMM is validated on kinesthetic demonstrations of uni-manual and bi-manual cooking tasks; achieving unsupervised human-level decomposition of complex sequential tasks.
Recovery of Structured Signals with Prior Information via Maximizing Correlation
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the problem of recovering a structured signal from a relatively small number of noisy measurements with the aid of a similar signal which is known beforehand. We propose a new approach to integrate prior information into the standard recovery procedure by maximizing the correlation between the prior knowledge and the desired signal. We then establish performance guarantees (in terms of the number of measurements) for the proposed method under sub-Gaussian measurements. Specific structured signals including sparse vectors, block-sparse vectors, and low-rank matrices are also analyzed. Furthermore, we present an interesting geometrical interpretation for the proposed procedure. Our results demonstrate that if prior information is good enough, then the proposed approach can (remarkably) outperform the standard recovery procedure. Simulations are provided to verify our results.
On modeling vagueness and uncertainty in data-to-text systems through fuzzy sets
Venue: arXiv cs.AI 2017
Year: 2017

Vagueness and uncertainty management is counted among one of the challenges that remain unresolved in systems that generate texts from non-linguistic data, known as data-to-text systems. In the last decade, work in fuzzy linguistic summarization and description of data has raised the interest of using fuzzy sets to model and manage the imprecision of human language in data-to-text systems. However, despite some research in this direction, there has not been an actual clear discussion and justification on how fuzzy sets can contribute to data-to-text for modeling vagueness and uncertainty in words and expressions. This paper intends to bridge this gap by answering the following questions: What does vagueness mean in fuzzy sets theory? What does vagueness mean in data-to-text contexts? In what ways can fuzzy sets theory contribute to improve data-to-text systems? What are the challenges that researchers from both disciplines need to address for a successful integration of fuzzy sets into data-to-text systems? In what cases should the use of fuzzy sets be avoided in D2T? For this, we review and discuss the state of the art of vagueness modeling in natural language generation and data-to-text, describe potential and actual usages of fuzzy sets in data-to-text contexts, and provide some additional insights about the engineering of data-to-text systems that make use of fuzzy set-based techniques.
Image matting with normalized weight and semi-supervised learning
Venue: arXiv cs.CV 2017
Year: 2017

Image matting is an important vision problem. The main stream methods for it combine sampling-based methods and propagation-based methods. In this paper, we deal with the combination with a normalized weighting parameter, which could well control the relative relationship between information from sampling and from propagation. A reasonable value range for this parameter is given based on statistics from the standard benchmark dataset. The matting is further improved by introducing semi-supervised learning iterations, which automatically refine the trimap without user's interaction. This is especially beneficial when the trimap is coarse. The experimental results on standard benchmark dataset have shown that both the normalized weighting parameter and the semi-supervised learning iteration could significantly improve the matting performance.