OpenRaiser/Intern-Atlas huggingface dataset:
Optimizing Matrices For Compressed Sensing Using Existing Goodness Measures: Negative Results, And An Alternative
Venue: arXiv cs.IT 2017
Year: 2017

The bound that arises out of sparse recovery analysis in compressed sensing involves input signal sparsity and some property of the sensing matrix. An effort has therefore been made in the literature to optimize sensing matrices for optimal recovery using this property. We discover, in the specific case of optimizing codes for the CACTI camera, that the popular method of mutual coherence minimization does not produce optimal results: codes designed to optimize effective dictionary coherence often perform worse than random codes in terms of mean squared reconstruction error. This surprising phenomenon leads us to investigate the reliability of the coherence bound for matrix optimization, in terms of its looseness. We examine, on simulated data, the looseness of the bound as it propagates across various steps of the inequalities in a derivation leading to the final bound. We then similarly examine an alternate bound derived by Tang, G. et al, based on the $\ell_1/\ell_{\infty}$ notion of sparsity, which is a compromise between coherence and the restricted isometry constant (RIC). Moreover, we also perform a bound looseness analysis for the RIC as derived by Cai, T. et al. The conclusion of these efforts is that coherence optimization is problematic not only because of the coherence bound on the RIC, but also the RIC bound itself. These negative results imply that despite the success of previous work in designing sensing matrices based on optimization of a matrix quality factor, one needs to exercise caution in using them for practical sensing matrix design. We then introduce a paradigm for optimizing sensing matrices that overcomes the looseness of compressed sensing upper bounds using an average case error approach. We show a proof-of-concept design using this paradigm that performs convincingly better than coherence-based design in the CACTI case, and no worse for general matrices.
Wextractor: Follow-up of the evolution of prices in web pages
Venue: arXiv cs.IR 2017
Year: 2017

In the e-commerce world, the follow-up of prices in detail web pages is of great interest for things like buying a product when it falls below some threshold. For doing this task, instead of bookmarking the pages and revisiting them, in this paper we propose a novel web data extraction system, called Wextractor. It consists of an extraction method and a web app for listing the retrieved prices. As for the final user, the main feature of Wextractor is usability because (s)he only has to signal the pages of interest and our system automatically extracts the price from the page.
NO Need to Worry about Adversarial Examples in Object Detection in Autonomous Vehicles
Venue: arXiv cs.CV 2017
Year: 2017

It has been shown that most machine learning algorithms are susceptible to adversarial perturbations. Slightly perturbing an image in a carefully chosen direction in the image space may cause a trained neural network model to misclassify it. Recently, it was shown that physical adversarial examples exist: printing perturbed images then taking pictures of them would still result in misclassification. This raises security and safety concerns. However, these experiments ignore a crucial property of physical objects: the camera can view objects from different distances and at different angles. In this paper, we show experiments that suggest that current constructions of physical adversarial examples do not disrupt object detection from a moving platform. Instead, a trained neural network classifies most of the pictures taken from different distances and angles of a perturbed image correctly. We believe this is because the adversarial property of the perturbation is sensitive to the scale at which the perturbed picture is viewed, so (for example) an autonomous car will misclassify a stop sign only from a small range of distances. Our work raises an important question: can one construct examples that are adversarial for many or most viewing conditions? If so, the construction should offer very significant insights into the internal representation of patterns by deep networks. If not, there is a good prospect that adversarial examples can be reduced to a curiosity with little practical impact.
Aerial Vehicle Tracking by Adaptive Fusion of Hyperspectral Likelihood Maps
Venue: arXiv cs.CV 2017
Year: 2017

Hyperspectral cameras can provide unique spectral signatures for consistently distinguishing materials that can be used to solve surveillance tasks. In this paper, we propose a novel real-time hyperspectral likelihood maps-aided tracking method (HLT) inspired by an adaptive hyperspectral sensor. A moving object tracking system generally consists of registration, object detection, and tracking modules. We focus on the target detection part and remove the necessity to build any offline classifiers and tune a large amount of hyperparameters, instead learning a generative target model in an online manner for hyperspectral channels ranging from visible to infrared wavelengths. The key idea is that, our adaptive fusion method can combine likelihood maps from multiple bands of hyperspectral imagery into one single more distinctive representation increasing the margin between mean value of foreground and background pixels in the fused map. Experimental results show that the HLT not only outperforms all established fusion methods but is on par with the current state-of-the-art hyperspectral target tracking frameworks.
Toward transient finite element simulation of thermal deformation of machine tools in real-time
Venue: arXiv cs.CE 2017
Year: 2017

Finite element models without simplifying assumptions can accurately describe the spatial and temporal distribution of heat in machine tools as well as the resulting deformation. In principle, this allows to correct for displacements of the Tool Centre Point and enables high precision manufacturing. However, the computational cost of FEM models and restriction to generic algorithms in commercial tools like ANSYS prevents their operational use since simulations have to run faster than real-time. For the case where heat diffusion is slow compared to machine movement, we introduce a tailored implicit-explicit multi-rate time stepping method of higher order based on spectral deferred corrections. Using the open-source FEM library DUNE, we show that fully coupled simulations of the temperature field are possible in real-time for a machine consisting of a stock sliding up and down on rails attached to a stand.
Cast-as-Intended Mechanism with Return Codes Based on PETs
Venue: arXiv cs.CR 2017
Year: 2017

We propose a method providing cast-as-intended verifiability for remote electronic voting. The method is based on plaintext equivalence tests (PETs), used to match the cast ballots against the pre-generated encrypted code tables. Our solution provides an attractive balance of security and functional properties. It is based on well-known cryptographic building blocks and relies on standard cryptographic assumptions, which allows for relatively simple security analysis. Our scheme is designed with a built-in fine-grained distributed trust mechanism based on threshold decryption. It, finally, imposes only very little additional computational burden on the voting platform, which is especially important when voters use devices of restricted computational power such as mobile phones. At the same time, the computational cost on the server side is very reasonable and scales well with the increasing ballot size.
Two-pixel polarimetric camera by compressive sensing
Venue: arXiv cs.CV 2017
Year: 2017

We propose an original concept of compressive sensing (CS) polarimetric imaging based on a digital micro-mirror (DMD) array and two single-pixel detectors. The polarimetric sensitivity of the proposed setup is due to an experimental imperfection of reflecting mirrors which is exploited here to form an original reconstruction problem, including a CS problem and a source separation task. We show that a two-step approach tackling each problem successively is outperformed by a dedicated combined reconstruction method, which is explicited in this article and preferably implemented through a reweighted FISTA algorithm. The combined reconstruction approach is then further improved by including physical constraints specific to the polarimetric imaging context considered, which are implemented in an original constrained GFB algorithm. Numerical simulations demonstrate the efficiency of the 2-pixel CS polarimetric imaging setup to retrieve polarimetric contrast data with significant compression rate and good reconstruction quality. The influence of experimental imperfections of the DMD are also analyzed through numerical simulations, and 2D polarimetric imaging reconstruction results are finally presented.
DeepProf: Performance Analysis for Deep Learning Applications via Mining GPU Execution Patterns
Venue: arXiv cs.SE 2017
Year: 2017

Deep learning applications are computation-intensive and often employ GPU as the underlying computing devices. Deep learning frameworks provide powerful programming interfaces, but the gap between source codes and practical GPU operations make it difficult to analyze the performance of deep learning applications. In this paper, through examing the features of GPU traces and deep learning applications, we use the suffix tree structure to extract the repeated patten in GPU traces. Performance analysis graphs can be generated from the preprocessed GPU traces. We further present \texttt{DeepProf}, a novel tool to automatically process GPU traces and generate performance analysis reports for deep learning applications. Empirical study verifies the effectiveness of \texttt{DeepProf} in performance analysis and diagnosis. We also find out some interesting properties of Tensorflow, which can be used to guide the deep learning system setup.
Catching Zika Fever: Application of Crowdsourcing and Machine Learning for Tracking Health Misinformation on Twitter
Venue: arXiv cs.SI 2017
Year: 2017

In February 2016, World Health Organization declared the Zika outbreak a Public Health Emergency of International Concern. With developing evidence it can cause birth defects, and the Summer Olympics coming up in the worst affected country, Brazil, the virus caught fire on social media. In this work, use Zika as a case study in building a tool for tracking the misinformation around health concerns on Twitter. We collect more than 13 million tweets -- spanning the initial reports in February 2016 and the Summer Olympics -- regarding the Zika outbreak and track rumors outlined by the World Health Organization and Snopes fact checking website. The tool pipeline, which incorporates health professionals, crowdsourcing, and machine learning, allows us to capture health-related rumors around the world, as well as clarification campaigns by reputable health organizations. In the case of Zika, we discover an extremely bursty behavior of rumor-related topics, and show that, once the questionable topic is detected, it is possible to identify rumor-bearing tweets using automated techniques. Thus, we illustrate insights the proposed tools provide into potentially harmful information on social media, allowing public health researchers and practitioners to respond with a targeted and timely action.
Sampling Random Colorings of Sparse Random Graphs
Venue: arXiv cs.DM 2017
Year: 2017

We study the mixing properties of the single-site Markov chain known as the Glauber dynamics for sampling $k$-colorings of a sparse random graph $G(n,d/n)$ for constant $d$. The best known rapid mixing results for general graphs are in terms of the maximum degree $Δ$ of the input graph $G$ and hold when $k>11Δ/6$ for all $G$. Improved results hold when $k>αΔ$ for graphs with girth $\geq 5$ and $Δ$ sufficiently large where $α\approx 1.7632\ldots$ is the root of $α=\exp(1/α)$; further improvements on the constant $α$ hold with stronger girth and maximum degree assumptions. For sparse random graphs the maximum degree is a function of $n$ and the goal is to obtain results in terms of the expected degree $d$. The following rapid mixing results for $G(n,d/n)$ hold with high probability over the choice of the random graph for sufficiently large constant~$d$. Mossel and Sly (2009) proved rapid mixing for constant $k$, and Efthymiou (2014) improved this to $k$ linear in~$d$. The condition was improved to $k>3d$ by Yin and Zhang (2016) using non-MCMC methods. Here we prove rapid mixing when $k>αd$ where $α\approx 1.7632\ldots$ is the same constant as above. Moreover we obtain $O(n^{3})$ mixing time of the Glauber dynamics, while in previous rapid mixing results the exponent was an increasing function in $d$. As in previous results for random graphs our proof analyzes an appropriately defined block dynamics to "hide" high-degree vertices. One new aspect in our improved approach is utilizing so-called local uniformity properties for the analysis of block dynamics. To analyze the "burn-in" phase we prove a concentration inequality for the number of disagreements propagating in large blocks.
Reduced Electron Exposure for Energy-Dispersive Spectroscopy using Dynamic Sampling
Venue: arXiv cs.LG 2017
Year: 2017

Analytical electron microscopy and spectroscopy of biological specimens, polymers, and other beam sensitive materials has been a challenging area due to irradiation damage. There is a pressing need to develop novel imaging and spectroscopic imaging methods that will minimize such sample damage as well as reduce the data acquisition time. The latter is useful for high-throughput analysis of materials structure and chemistry. In this work, we present a novel machine learning based method for dynamic sparse sampling of EDS data using a scanning electron microscope. Our method, based on the supervised learning approach for dynamic sampling algorithm and neural networks based classification of EDS data, allows a dramatic reduction in the total sampling of up to 90%, while maintaining the fidelity of the reconstructed elemental maps and spectroscopic data. We believe this approach will enable imaging and elemental mapping of materials that would otherwise be inaccessible to these analysis techniques.
Capacity, Fidelity, and Noise Tolerance of Associative Spatial-Temporal Memories Based on Memristive Neuromorphic Network
Venue: arXiv cs.NE 2017
Year: 2017

We have calculated the key characteristics of associative (content-addressable) spatial-temporal memories based on neuromorphic networks with restricted connectivity - "CrossNets". Such networks may be naturally implemented in nanoelectronic hardware using hybrid CMOS/memristor circuits, which may feature extremely high energy efficiency, approaching that of biological cortical circuits, at much higher operation speed. Our numerical simulations, in some cases confirmed by analytical calculations, have shown that the characteristics depend substantially on the method of information recording into the memory. Of the four methods we have explored, two look especially promising - one based on the quadratic programming, and the other one being a specific discrete version of the gradient descent. The latter method provides a slightly lower memory capacity (at the same fidelity) then the former one, but it allows local recording, which may be more readily implemented in nanoelectronic hardware. Most importantly, at the synchronous retrieval, both methods provide a capacity higher than that of the well-known Ternary Content-Addressable Memories with the same number of nonvolatile memory cells (e.g., memristors), though the input noise immunity of the CrossNet memories is somewhat lower.
Independence, Conditionality and Structure of Dempster-Shafer Belief Functions
Venue: arXiv cs.AI 2017
Year: 2017

Several approaches of structuring (factorization, decomposition) of Dempster-Shafer joint belief functions from literature are reviewed with special emphasis on their capability to capture independence from the point of view of the claim that belief functions generalize bayes notion of probability. It is demonstrated that Zhu and Lee's {Zhu:93} logical networks and Smets' {Smets:93} directed acyclic graphs are unable to capture statistical dependence/independence of bayesian networks {Pearl:88}. On the other hand, though Shenoy and Shafer's hypergraphs can explicitly represent bayesian network factorization of bayesian belief functions, they disclaim any need for representation of independence of variables in belief functions. Cano et al. {Cano:93} reject the hypergraph representation of Shenoy and Shafer just on grounds of missing representation of variable independence, but in their frameworks some belief functions factorizable in Shenoy/Shafer framework cannot be factored. The approach in {Klopotek:93f} on the other hand combines the merits of both Cano et al. and of Shenoy/Shafer approach in that for Shenoy/Shafer approach no simpler factorization than that in {Klopotek:93f} approach exists and on the other hand all independences among variables captured in Cano et al. framework and many more are captured in {Klopotek:93f} approach.%
Identification and Interpretation of Belief Structure in Dempster-Shafer Theory
Venue: arXiv cs.AI 2017
Year: 2017

Mathematical Theory of Evidence called also Dempster-Shafer Theory (DST) is known as a foundation for reasoning when knowledge is expressed at various levels of detail. Though much research effort has been committed to this theory since its foundation, many questions remain open. One of the most important open questions seems to be the relationship between frequencies and the Mathematical Theory of Evidence. The theory is blamed to leave frequencies outside (or aside of) its framework. The seriousness of this accusation is obvious: (1) no experiment may be run to compare the performance of DST-based models of real world processes against real world data, (2) data may not serve as foundation for construction of an appropriate belief model. In this paper we develop a frequentist interpretation of the DST bringing to fall the above argument against DST. An immediate consequence of it is the possibility to develop algorithms acquiring automatically DST belief models from data. We propose three such algorithms for various classes of belief model structures: for tree structured belief networks, for poly-tree belief networks and for general type belief networks.
A Formal Framework to Characterize Interpretability of Procedures
Venue: arXiv cs.AI 2017
Year: 2017

We provide a novel notion of what it means to be interpretable, looking past the usual association with human understanding. Our key insight is that interpretability is not an absolute concept and so we define it relative to a target model, which may or may not be a human. We define a framework that allows for comparing interpretable procedures by linking it to important practical aspects such as accuracy and robustness. We characterize many of the current state-of-the-art interpretable methods in our framework portraying its general applicability.
Additive non-approximability of chromatic number in proper minor-closed classes
Venue: arXiv cs.DM 2017
Year: 2017

Robin Thomas asked whether for every proper minor-closed class C, there exists a polynomial-time algorithm approximating the chromatic number of graphs from C up to a constant additive error independent on the class C. We show this is not the case: unless P=NP, for every integer k>=1, there is no polynomial-time algorithm to color a K_{4k+1}-minor-free graph G using at most chi(G)+k-1 colors. More generally, for every k>=1 and 1<=β<=4/3, there is no polynomial-time algorithm to color a K_{4k+1}-minor-free graph G using less than beta.chi(G)+(4-3beta)k colors. As far as we know, this is the first non-trivial non-approximability result regarding the chromatic number in proper minor-closed classes. We also give somewhat weaker non-approximability bound for K_{4k+1}-minor-free graphs with no cliques of size 4. On the positive side, we present additive approximation algorithm whose error depends on the apex number of the forbidden minor, and an algorithm with additive error 6 under the additional assumption that the graph has no 4-cycles.
Quasar: Datasets for Question Answering by Search and Reading
Venue: arXiv cs.CL 2017
Year: 2017

We present two new large-scale datasets aimed at evaluating systems designed to comprehend a natural language query and extract its answer from a large corpus of text. The Quasar-S dataset consists of 37000 cloze-style (fill-in-the-gap) queries constructed from definitions of software entity tags on the popular website Stack Overflow. The posts and comments on the website serve as the background corpus for answering the cloze questions. The Quasar-T dataset consists of 43000 open-domain trivia questions and their answers obtained from various internet sources. ClueWeb09 serves as the background corpus for extracting these answers. We pose these datasets as a challenge for two related subtasks of factoid Question Answering: (1) searching for relevant pieces of text that include the correct answer to a query, and (2) reading the retrieved text to answer the query. We also describe a retrieval system for extracting relevant sentences and documents from the corpus given a query, and include these in the release for researchers wishing to only focus on (2). We evaluate several baselines on both datasets, ranging from simple heuristics to powerful neural models, and show that these lag behind human performance by 16.4% and 32.1% for Quasar-S and -T respectively. The datasets are available at https://github.com/bdhingra/quasar .
Asymptotic Blind-spot Analysis of Localization Networks under Correlated Blocking using a Poisson Line Process
Venue: arXiv cs.NI 2017
Year: 2017

In a localization network, the line-of-sight between anchors (transceivers) and targets may be blocked due to the presence of obstacles in the environment. Due to the non-zero size of the obstacles, the blocking is typically correlated across both anchor and target locations, with the extent of correlation increasing with obstacle size. If a target does not have line-of-sight to a minimum number of anchors, then its position cannot be estimated unambiguously and is, therefore, said to be in a blind-spot. However, the analysis of the blind-spot probability of a given target is challenging due to the inherent randomness in the obstacle locations and sizes. In this letter, we develop a new framework to analyze the worst-case impact of correlated blocking on the blind-spot probability of a typical target; in particular, we model the obstacles by a Poisson line process and the anchor locations by a Poisson point process. For this setup, we define the notion of the asymptotic blind-spot probability of the typical target and derive a closed-form expression for it as a function of the area distribution of a typical Poisson-Voronoi cell. As an upper bound for the more realistic case when obstacles have finite dimensions, the asymptotic blind-spot probability is useful as a design tool to ensure that the blind-spot probability of a typical target does not exceed a desired threshold, $ε$.
Enumerating Vertices of $0/1$-Polyhedra associated with $0/1$-Totally Unimodular Matrices
Venue: arXiv cs.DS 2017
Year: 2017

We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron $\mathcal{P}(A,\mathbf{1})=\{x\in\RR^n \mid Ax\geq \b1,~x\geq \b0\}$, when $A$ is a totally unimodular matrix. Our algorithm is based on decomposing the hypergraph transversal problem for unimodular hypergraphs using Seymour's decomposition of totally unimodular matrices, and may be of independent interest.