OpenRaiser/Intern-Atlas huggingface dataset:
Random Forests versus Neural Networks - What's Best for Camera Localization?
Venue: arXiv cs.CV 2017
Year: 2017

This work addresses the task of camera localization in a known 3D scene given a single input RGB image. State-of-the-art approaches accomplish this in two steps: firstly, regressing for every pixel in the image its 3D scene coordinate and subsequently, using these coordinates to estimate the final 6D camera pose via RANSAC. To solve the first step, Random Forests (RFs) are typically used. On the other hand, Neural Networks (NNs) reign in many dense regression tasks, but are not test-time efficient. We ask the question: which of the two is best for camera localization? To address this, we make two method contributions: (1) a test-time efficient NN architecture which we term a ForestNet that is derived and initialized from a RF, and (2) a new fully-differentiable robust averaging technique for regression ensembles which can be trained end-to-end with a NN. Our experimental findings show that for scene coordinate regression, traditional NN architectures are superior to test-time efficient RFs and ForestNets, however, this does not translate to final 6D camera pose accuracy where RFs and ForestNets perform slightly better. To summarize, our best method, a ForestNet with a robust average, which has an equivalent fast and lightweight RF, improves over the state-of-the-art for camera localization on the 7-Scenes dataset. While this work focuses on scene coordinate regression for camera localization, our innovations may also be applied to other continuous regression tasks.
Stability Analysis of Wholesale Electricity Markets under Dynamic Consumption Models and Real-Time Pricing
Venue: arXiv cs.SY 2017
Year: 2017

This paper analyzes stability conditions for wholesale electricity markets under real-time retail pricing and realistic consumption models with memory, which explicitly take into account previous electricity prices and consumption levels. By passing on the current retail price of electricity from supplier to consumer and feeding the observed consumption back to the supplier, a closed-loop dynamical system for electricity prices and consumption arises whose stability is to be investigated. Under mild assumptions on the generation cost of electricity and consumers' backlog disutility functions, we show that, for consumer models with price memory only, market stability is achieved if the ratio between the consumers' marginal backlog disutility and the suppliers' marginal cost of supply remains below a fixed threshold. Further, consumer models with price and consumption memory can result in greater stability regions and faster convergence to the equilibrium compared to models with price memory alone, if consumption deviations from nominal demand are adequately penalized.
Outlaw distributions and locally decodable codes
Venue: arXiv cs.CC 2017
Year: 2017

Locally decodable codes (LDCs) are error correcting codes that allow for decoding of a single message bit using a small number of queries to a corrupted encoding. Despite decades of study, the optimal trade-off between query complexity and codeword length is far from understood. In this work, we give a new characterization of LDCs using distributions over Boolean functions whose expectation is hard to approximate (in~$L_\infty$~norm) with a small number of samples. We coin the term `outlaw distributions' for such distributions since they `defy' the Law of Large Numbers. We show that the existence of outlaw distributions over sufficiently `smooth' functions implies the existence of constant query LDCs and vice versa. We give several candidates for outlaw distributions over smooth functions coming from finite field incidence geometry, additive combinatorics and from hypergraph (non)expanders. We also prove a useful lemma showing that (smooth) LDCs which are only required to work on average over a random message and a random message index can be turned into true LDCs at the cost of only constant factors in the parameters.
Production-Level Facial Performance Capture Using Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

We present a real-time deep learning framework for video-based facial performance capture -- the dense 3D tracking of an actor's face given a monocular video. Our pipeline begins with accurately capturing a subject using a high-end production facial capture pipeline based on multi-view stereo tracking and artist-enhanced animations. With 5-10 minutes of captured footage, we train a convolutional neural network to produce high-quality output, including self-occluded regions, from a monocular video sequence of that subject. Since this 3D facial performance capture is fully automated, our system can drastically reduce the amount of labor involved in the development of modern narrative-driven video games or films involving realistic digital doubles of actors and potentially hours of animated dialogue per character. We compare our results with several state-of-the-art monocular real-time facial capture techniques and demonstrate compelling animation inference in challenging areas such as eyes and lips.
Max-Min Multi-Cell Aware Precoding and Power Allocation for Downlink Massive MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

We propose a max-min multi-cell aware regularized zero-forcing (Max-Min MCA-RZF) precoding and power allocation scheme for downlink multi-cell massive multiple-input multiple-output (MIMO) systems. A general correlated channel model is considered, and the adopted channel state information (CSI) acquisition model includes the effects of estimation errors and pilot contamination. We use results from random matrix theory to derive deterministic equivalents for the proposed Max-Min power allocation in the large system limit which solely depend on statistical CSI, but not on individual channel realizations. Our numerical results show that the proposed Max-Min MCA-RZF precoder achieves a substantially higher network-wide minimum rate than the MCA-RZF and the conventional RZF precoders with uniform power allocation, respectively, as well as the conventional RZF precoder with Max-Min power allocation.
Particle-Filter-Enabled Real-Time Sensor Fault Detection Without a Model of Faults
Venue: arXiv cs.SY 2017
Year: 2017

We are experiencing an explosion in the amount of sensors measuring our activities and the world around us. These sensors are spread throughout the built environment and can help us perform state estimation and control of related systems, but they are often built and/or maintained by third parties or system users. As a result, by outsourcing system measurement to third parties, the controller must accept their measurements without being able to directly verify the sensors' correct operation. Instead, detection and rejection of measurements from faulty sensors must be done with the raw data only. Towards this goal, we present a method of detecting possibly faulty behavior of sensors. The method does not require that the control designer have any model of faulty sensor behavior. As we discuss, it turns out that the widely-used particle filter state estimation algorithm provides the ingredients necessary for a hypothesis test against all ranges of correct operating behavior, obviating the need for a fault model to compare measurements. We demonstrate the applicability of our method by demonstrating its ability to reject faulty measurements and improve state estimation accuracy in a nonlinear vehicle traffic model without information of generated faulty measurements' characteristics. In our test, we correctly identify nearly 90% of measurements as faulty or non-faulty without having any fault model. This leads to only a 3% increase in state estimation error over a theoretical 100%-accurate fault detector.
Slowly synchronizing automata with fixed alphabet size
Venue: arXiv cs.FL 2017
Year: 2017

It was conjectured by Černý in 1964 that a synchronizing DFA on $n$ states always has a shortest synchronizing word of length at most $(n-1)^2$, and he gave a sequence of DFAs for which this bound is reached. In this paper, we investigate the role of the alphabet size. For each possible alphabet size, we count DFAs on $n \le 6$ states which synchronize in $(n-1)^2 - e$ steps, for all $e < 2\lceil n/2 \rceil$. Furthermore, we give constructions of automata with any number of states, and $3$, $4$, or $5$ symbols, which synchronize slowly, namely in $n^2 - 3n + O(1)$ steps. In addition, our results prove Černý's conjecture for $n \le 6$. Our computation has led to $27$ DFAs on $3$, $4$, $5$ or $6$ states, which synchronize in $(n-1)^2$ steps, but do not belong to Černý's sequence. Of these $27$ DFA's, $19$ are new, and the remaining $8$ which were already known are exactly the \emph{minimal} ones: they will not synchronize any more after removing a symbol. So the $19$ new DFAs are extensions of automata which were already known, including the Černý automaton on $3$ states. But for $n > 3$, we prove that the Černý automaton on $n$ states does not admit non-trivial extensions with the same smallest synchronizing word length $(n-1)^2$.
Scaling betweenness centrality using communication-efficient sparse matrix multiplication
Venue: arXiv cs.DC 2017
Year: 2017

Betweenness centrality (BC) is a crucial graph problem that measures the significance of a vertex by the number of shortest paths leading through it. We propose Maximal Frontier Betweenness Centrality (MFBC): a succinct BC algorithm based on novel sparse matrix multiplication routines that performs a factor of $p^{1/3}$ less communication on $p$ processors than the best known alternatives, for graphs with $n$ vertices and average degree $k=n/p^{2/3}$. We formulate, implement, and prove the correctness of MFBC for weighted graphs by leveraging monoids instead of semirings, which enables a surprisingly succinct formulation. MFBC scales well for both extremely sparse and relatively dense graphs. It automatically searches a space of distributed data decompositions and sparse matrix multiplication algorithms for the most advantageous configuration. The MFBC implementation outperforms the well-known CombBLAS library by up to 8x and shows more robust performance. Our design methodology is readily extensible to other graph problems.
Annotating Derivations: A New Evaluation Strategy and Dataset for Algebra Word Problems
Venue: arXiv cs.CL 2017
Year: 2017

We propose a new evaluation for automatic solvers for algebra word problems, which can identify mistakes that existing evaluations overlook. Our proposal is to evaluate such solvers using derivations, which reflect how an equation system was constructed from the word problem. To accomplish this, we develop an algorithm for checking the equivalence between two derivations, and show how derivation an- notations can be semi-automatically added to existing datasets. To make our experiments more comprehensive, we include the derivation annotation for DRAW-1K, a new dataset containing 1000 general algebra word problems. In our experiments, we found that the annotated derivations enable a more accurate evaluation of automatic solvers than previously used metrics. We release derivation annotations for over 2300 algebra word problems for future evaluations.
Tight bounds on the maximum number of shortest unique substrings
Venue: arXiv cs.DM 2017
Year: 2017

A substring Q of a string S is called a shortest unique substring (SUS) for interval [s,t] in S, if Q occurs exactly once in S, this occurrence of Q contains interval [s,t], and every substring of S which contains interval [s,t] and is shorter than Q occurs at least twice in S. The SUS problem is, given a string S, to preprocess S so that for any subsequent query interval [s,t] all the SUSs for interval [s,t] can be answered quickly. When s = t, we call the SUSs for [s,t] as point SUSs, and when s \leq t, we call the SUSs for [s,t] as interval SUSs. There exist optimal O(n)-time preprocessing scheme which answers queries in optimal O(k) time for both point and interval SUSs, where n is the length of S and k is the number of outputs for a given query. In this paper, we reveal structural, combinatorial properties underlying the SUS problem: Namely, we show that the number of intervals in S that correspond to point SUSs for all query positions in S is less than 1.5n, and show that this is a matching upper and lower bound. Also, we consider the maximum number of intervals in S that correspond to interval SUSs for all query intervals in S.
Using Neural Network Formalism to Solve Multiple-Instance Problems
Venue: arXiv cs.LG 2017
Year: 2017

Many objects in the real world are difficult to describe by a single numerical vector of a fixed length, whereas describing them by a set of vectors is more natural. Therefore, Multiple instance learning (MIL) techniques have been constantly gaining on importance throughout last years. MIL formalism represents each object (sample) by a set (bag) of feature vectors (instances) of fixed length where knowledge about objects (e.g., class label) is available on bag level but not necessarily on instance level. Many standard tools including supervised classifiers have been already adapted to MIL setting since the problem got formalized in late nineties. In this work we propose a neural network (NN) based formalism that intuitively bridges the gap between MIL problem definition and the vast existing knowledge-base of standard models and classifiers. We show that the proposed NN formalism is effectively optimizable by a modified back-propagation algorithm and can reveal unknown patterns inside bags. Comparison to eight types of classifiers from the prior art on a set of 14 publicly available benchmark datasets confirms the advantages and accuracy of the proposed solution.
Pro-aperiodic monoids via saturated models
Venue: arXiv cs.FL 2017
Year: 2017

We apply Stone duality and model theory to study the structure theory of free pro-aperiodic monoids. Stone duality implies that elements of the free pro-aperiodic monoid may be viewed as elementary equivalence classes of pseudofinite words. Model theory provides us with saturated words in each such class, i.e., words in which all possible factorizations are realized. We give several applications of this new approach, including a solution to the word problem for $ω$-terms that avoids using McCammond's normal forms, as well as new proofs and extensions of other structural results concerning free pro-aperiodic monoids.
Software Platforms for Smart Cities: Concepts, Requirements, Challenges, and a Unified Reference Architecture
Venue: arXiv cs.CY 2017
Year: 2017

Making cities smarter help improve city services and increase citizens' quality of life. Information and communication technologies (ICT) are fundamental for progressing towards smarter city environments. Smart City software platforms potentially support the development and integration of Smart City applications. However, the ICT community must overcome current significant technological and scientific challenges before these platforms can be widely used. This paper surveys the state-of-the-art in software platforms for Smart Cities. We analyzed 23 projects with respect to the most used enabling technologies, as well as functional and non-functional requirements, classifying them into four categories: Cyber-Physical Systems, Internet of Things, Big Data, and Cloud Computing. Based on these results, we derived a reference architecture to guide the development of next-generation software platforms for Smart Cities. Finally, we enumerated the most frequently cited open research challenges, and discussed future opportunities. This survey gives important references for helping application developers, city managers, system operators, end-users, and Smart City researchers to make project, investment, and research decisions.
Stream Differential Equations: Specification Formats and Solution Methods
Venue: arXiv cs.LO 2017
Year: 2017

Streams, or infinite sequences, are infinite objects of a very simple type, yet they have a rich theory partly due to their ubiquity in mathematics and computer science. Stream differential equations are a coinductive method for specifying streams and stream operations, and their theory has been developed in many papers over the past two decades. In this paper we present a survey of the many results in this area. Our focus is on the classification of different formats of stream differential equations, their solution methods, and the classes of streams they can define. Moreover, we describe in detail the connection between the so-called syntactic solution method and abstract GSOS.
Enhancing Big Data in the Social Sciences with Crowdsourcing: Data Augmentation Practices, Techniques, and Opportunities
Venue: arXiv cs.CY 2017
Year: 2017

The importance of big data is a contested topic among social scientists. Proponents claim it will fuel a research revolution, but skeptics challenge it as unreliably measured and decontextualized, with limited utility for accurately answering social science research questions. We argue that social scientists need effective tools to quantify big data's measurement error and expand the contextual information associated with it. Standard research efforts in many fields already pursue these goals through data augmentation, the systematic assessment of measurement against known quantities and expansion of extant data by adding new information. Traditionally, these tasks are accomplished using trained research assistants or specialized algorithms. However, such approaches may not be scalable to big data or appease its skeptics. We consider a third alternative that may increase the validity and value of big data: data augmentation with online crowdsourcing. We present three empirical cases to illustrate the strengths and limits of crowdsourcing for academic research, with a particular eye to how they can be applied to data augmentation tasks that will accelerate acceptance of big data among social scientists. The cases use Amazon Mechanical Turk to 1. verify automated coding of the academic discipline of dissertation committee members, 2. link online product pages to a book database, and 3. gather data on mental health resources at colleges. In light of these cases, we consider the costs and benefits of augmenting big data with crowdsourcing marketplaces and provide guidelines on best practices. We also offer a standardized reporting template that will enhance reproducibility.
Cognitive Random Access for Internet-of-Things Networks
Venue: arXiv cs.NI 2017
Year: 2017

This paper focuses on cognitive radio (CR) internet- of-things (IoT) networks where spectrum sensors are deployed for IoT CR devices, which do not have enough hardware capability to identify an unoccupied spectrum by themselves. In this sensor- enabled IoT CR network, the CR devices and the sensors are separated. It induces that spectrum occupancies at locations of CR devices and sensors could be different. To handle this difference, we investigate a conditional interference distribution (CID) at the CR device for a given measured interference at the sensor. We can observe a spatial correlation of the aggregate interference distribution through the CID. Reflecting the CID, we devise a cognitive random access scheme which adaptively adjusts transmission probability with respect to the interference measurement of the sensor. Our scheme improves area spectral efficiency (ASE) compared to a conventional ALOHA and an adaptive transmission scheme which attempts to send data when the sensor measurement is lower than an interference threshold.
Latent fingerprint minutia extraction using fully convolutional network
Venue: arXiv cs.CV 2017
Year: 2017

Minutiae play a major role in fingerprint identification. Extracting reliable minutiae is difficult for latent fingerprints which are usually of poor quality. As the limitation of traditional handcrafted features, a fully convolutional network (FCN) is utilized to learn features directly from data to overcome complex background noises. Raw fingerprints are mapped to a correspondingly-sized minutia-score map with a fixed stride. And thus a large number of minutiae will be extracted through a given threshold. Then small regions centering at these minutia points are entered into a convolutional neural network (CNN) to reclassify these minutiae and calculate their orientations. The CNN shares convolutional layers with the fully convolutional network to speed up. 0.45 second is used on average to detect one fingerprint on a GPU. On the NIST SD27 database, we achieve 53\% recall rate and 53\% precise rate that outperform many other algorithms. Our trained model is also visualized to show that we have successfully extracted features preserving ridge information of a latent fingerprint.
Minimal Inputs/Outputs for a Networked System
Venue: arXiv cs.SY 2017
Year: 2017

This paper investigates the minimal number of inputs/outputs required to guarantees the controllability/observability of a system, under the condition that its state transition matrix (STM) is prescribed. It has been proved that this minimal number is equal to the maximum geometric multiplicity of the system STM. The obtained conclusions are in sharp contrast to those established for the problems of finding the sparest input/output matrix under the restriction of system controllability/observabilty, which have been proved to be NP-hard, and even impossible to be approximated within a multiplicative factor. Moreover, a complete parametrization is also provided for the input/output matrix of a system with this minimal input/output number.
Sentence Segmentation in Narrative Transcripts from Neuropsychological Tests using Recurrent Convolutional Neural Networks
Venue: arXiv cs.CL 2017
Year: 2017

Automated discourse analysis tools based on Natural Language Processing (NLP) aiming at the diagnosis of language-impairing dementias generally extract several textual metrics of narrative transcripts. However, the absence of sentence boundary segmentation in the transcripts prevents the direct application of NLP methods which rely on these marks to function properly, such as taggers and parsers. We present the first steps taken towards automatic neuropsychological evaluation based on narrative discourse analysis, presenting a new automatic sentence segmentation method for impaired speech. Our model uses recurrent convolutional neural networks with prosodic, Part of Speech (PoS) features, and word embeddings. It was evaluated intrinsically on impaired, spontaneous speech, as well as, normal, prepared speech, and presents better results for healthy elderly (CTL) (F1 = 0.74) and Mild Cognitive Impairment (MCI) patients (F1 = 0.70) than the Conditional Random Fields method (F1 = 0.55 and 0.53, respectively) used in the same context of our study. The results suggest that our model is robust for impaired speech and can be used in automated discourse analysis tools to differentiate narratives produced by MCI and CTL.
Nonsymbolic Text Representation
Venue: arXiv cs.CL 2017
Year: 2017

We introduce the first generic text representation model that is completely nonsymbolic, i.e., it does not require the availability of a segmentation or tokenization method that attempts to identify words or other symbolic units in text. This applies to training the parameters of the model on a training corpus as well as to applying it when computing the representation of a new text. We show that our model performs better than prior work on an information extraction and a text denoising task.