OpenRaiser/Intern-Atlas huggingface dataset:
Crosscorrelation of Rudin-Shapiro-Like Polynomials
Venue: arXiv cs.IT 2018
Year: 2018

We consider the class of Rudin-Shapiro-like polynomials, whose $L^4$ norms on the complex unit circle were studied by Borwein and Mossinghoff. The polynomial $f(z)=f_0+f_1 z + \cdots + f_d z^d$ is identified with the sequence $(f_0,f_1,\ldots,f_d)$ of its coefficients. From the $L^4$ norm of a polynomial, one can easily calculate the autocorrelation merit factor of its associated sequence, and conversely. In this paper, we study the crosscorrelation properties of pairs of sequences associated to Rudin-Shapiro-like polynomials. We find an explicit formula for the crosscorrelation merit factor. A computer search is then used to find pairs of Rudin-Shapiro-like polynomials whose autocorrelation and crosscorrelation merit factors are simultaneously high. Pursley and Sarwate proved a bound that limits how good this combined autocorrelation and crosscorrelation performance can be. We find infinite families of polynomials whose performance approaches quite close to this fundamental limit.
When Does Diversity of User Preferences Improve Outcomes in Selfish Routing?
Venue: arXiv cs.GT 2018
Year: 2018

We seek to understand when heterogeneity in user preferences yields improved outcomes in terms of overall cost. That this might be hoped for is based on the common belief that diversity is advantageous in many settings. We investigate this in the context of routing. Our main result is a sharp characterization of the network settings in which diversity always helps, versus those in which it is sometimes harmful. Specifically, we consider routing games, where diversity arises in the way that users trade-off two criteria (such as time and money, or, in the case of stochastic delays, expectation and variance of delay). Our main contributions are the following: 1) A participant-oriented measure of cost in the presence of user diversity, together with the identification of the natural benchmark: the same cost measure for an appropriately defined average of the diversity. 2) A full characterization of those network topologies for which diversity always helps, for all latency functions and demands. For single-commodity routings, these are series-parallel graphs, while for multi-commodity routings, they are the newly-defined "block-matching" networks. The latter comprise a suitable interweaving of multiple series-parallel graphs each connecting a distinct source-sink pair. While the result for the single-commodity case may seem intuitive in light of the well-known Braess paradox, the two problems are different: there are instances where diversity helps although the Braess paradox occurs, and vice-versa. But the main technical challenge is to establish the "only if" direction of the result for multi-commodity networks. This follows by constructing an instance where diversity hurts, and showing how to embed it in any network which is not block-matching, by carefully exploiting the way the simple source-sink paths of the commodities intersect in the "non-block-matching" portion of the network.
Supervised Learning of Labeled Pointcloud Differences via Cover-Tree Entropy Reduction
Venue: arXiv cs.LG 2018
Year: 2018

We introduce a new algorithm, called CDER, for supervised machine learning that merges the multi-scale geometric properties of Cover Trees with the information-theoretic properties of entropy. CDER applies to a training set of labeled pointclouds embedded in a common Euclidean space. If typical pointclouds corresponding to distinct labels tend to differ at any scale in any sub-region, CDER can identify these differences in (typically) linear time, creating a set of distributional coordinates which act as a feature extraction mechanism for supervised learning. We describe theoretical properties and implementation details of CDER, and illustrate its benefits on several synthetic examples.
Political Homophily in Independence Movements: Analysing and Classifying Social Media Users by National Identity
Venue: arXiv cs.CL 2018
Year: 2018

Social media and data mining are increasingly being used to analyse political and societal issues. Here we undertake the classification of social media users as supporting or opposing ongoing independence movements in their territories. Independence movements occur in territories whose citizens have conflicting national identities; users with opposing national identities will then support or oppose the sense of being part of an independent nation that differs from the officially recognised country. We describe a methodology that relies on users' self-reported location to build large-scale datasets for three territories -- Catalonia, the Basque Country and Scotland. An analysis of these datasets shows that homophily plays an important role in determining who people connect with, as users predominantly choose to follow and interact with others from the same national identity. We show that a classifier relying on users' follow networks can achieve accurate, language-independent classification performances ranging from 85% to 97% for the three territories.
Privacy-enhancing Aggregation of Internet of Things Data via Sensors Grouping
Venue: arXiv cs.DC 2018
Year: 2018

Big data collection practices using Internet of Things (IoT) pervasive technologies are often privacy-intrusive and result in surveillance, profiling, and discriminatory actions over citizens that in turn undermine the participation of citizens to the development of sustainable smart cities. Nevertheless, real-time data analytics and aggregate information from IoT devices open up tremendous opportunities for managing smart city infrastructures. The privacy-enhancing aggregation of distributed sensor data, such as residential energy consumption or traffic information, is the research focus of this paper. Citizens have the option to choose their privacy level by reducing the quality of the shared data at a cost of a lower accuracy in data analytics services. A baseline scenario is considered in which IoT sensor data are shared directly with an untrustworthy central aggregator. A grouping mechanism is introduced that improves privacy by sharing data aggregated first at a group level compared as opposed to sharing data directly to the central aggregator. Group-level aggregation obfuscates sensor data of individuals, in a similar fashion as differential privacy and homomorphic encryption schemes, thus inference of privacy-sensitive information from single sensors becomes computationally harder compared to the baseline scenario. The proposed system is evaluated using real-world data from two smart city pilot projects. Privacy under grouping increases, while preserving the accuracy of the baseline scenario. Intra-group influences of privacy by one group member on the other ones are measured and fairness on privacy is found to be maximized between group members with similar privacy choices. Several grouping strategies are compared. Grouping by proximity of privacy choices provides the highest privacy gains. The implications of the strategy on the design of incentives mechanisms are discussed.
Binary Search in Graphs Revisited
Venue: arXiv cs.DS 2018
Year: 2018

In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by [Emamjomeh-Zadeh et al., STOC, 2016] to the problem of detecting a target in an arbitrary graph. Similarly to the classical case in the path, the algorithm of Emamjomeh-Zadeh et al. maintains a candidates' set for the target, while each query asks an appropriately chosen vertex-- the "median"--which minimises a potential $Φ$ among the vertices of the candidates' set. In this paper we address three open questions posed by Emamjomeh-Zadeh et al., namely (a) detecting a target when the query response is a direction to an approximately shortest path to the target, (b) detecting a target when querying a vertex that is an approximate median of the current candidates' set (instead of an exact one), and (c) detecting multiple targets, for which to the best of our knowledge no progress has been made so far. We resolve questions (a) and (b) by providing appropriate upper and lower bounds, as well as a new potential $Γ$ that guarantees efficient target detection even by querying an approximate median each time. With respect to (c), we initiate a systematic study for detecting two targets in graphs and we identify sufficient conditions on the queries that allow for strong (linear) lower bounds and strong (polylogarithmic) upper bounds for the number of queries. All of our positive results can be derived using our new potential $Γ$ that allows querying approximate medians.
Algorithms and Bounds for Very Strong Rainbow Coloring
Venue: arXiv cs.DS 2018
Year: 2018

A well-studied coloring problem is to assign colors to the edges of a graph $G$ so that, for every pair of vertices, all edges of at least one shortest path between them receive different colors. The minimum number of colors necessary in such a coloring is the strong rainbow connection number ($\src(G)$) of the graph. When proving upper bounds on $\src(G)$, it is natural to prove that a coloring exists where, for \emph{every} shortest path between every pair of vertices in the graph, all edges of the path receive different colors. Therefore, we introduce and formally define this more restricted edge coloring number, which we call \emph{very strong rainbow connection number} ($\vsrc(G)$). In this paper, we give upper bounds on $\vsrc(G)$ for several graph classes, some of which are tight. These immediately imply new upper bounds on $\src(G)$ for these classes, showing that the study of $\vsrc(G)$ enables meaningful progress on bounding $\src(G)$. Then we study the complexity of the problem to compute $\vsrc(G)$, particularly for graphs of bounded treewidth, and show this is an interesting problem in its own right. We prove that $\vsrc(G)$ can be computed in polynomial time on cactus graphs; in contrast, this question is still open for $\src(G)$. We also observe that deciding whether $\vsrc(G) = k$ is fixed-parameter tractable in $k$ and the treewidth of $G$. Finally, on general graphs, we prove that there is no polynomial-time algorithm to decide whether $\vsrc(G) \leq 3$ nor to approximate $\vsrc(G)$ within a factor $n^{1-\varepsilon}$, unless P$=$NP.
BoxCars: Improving Fine-Grained Recognition of Vehicles using 3-D Bounding Boxes in Traffic Surveillance
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we focus on fine-grained recognition of vehicles mainly in traffic surveillance applications. We propose an approach that is orthogonal to recent advancements in fine-grained recognition (automatic part discovery and bilinear pooling). In addition, in contrast to other methods focused on fine-grained recognition of vehicles, we do not limit ourselves to a frontal/rear viewpoint, but allow the vehicles to be seen from any viewpoint. Our approach is based on 3-D bounding boxes built around the vehicles. The bounding box can be automatically constructed from traffic surveillance data. For scenarios where it is not possible to use precise construction, we propose a method for an estimation of the 3-D bounding box. The 3-D bounding box is used to normalize the image viewpoint by "unpacking" the image into a plane. We also propose to randomly alter the color of the image and add a rectangle with random noise to a random position in the image during the training of convolutional neural networks (CNNs). We have collected a large fine-grained vehicle data set BoxCars116k, with 116k images of vehicles from various viewpoints taken by numerous surveillance cameras. We performed a number of experiments, which show that our proposed method significantly improves CNN classification accuracy (the accuracy is increased by up to 12% points and the error is reduced by up to 50% compared with CNNs without the proposed modifications). We also show that our method outperforms the state-of-the-art methods for fine-grained recognition.
Unsupervised Image-to-Image Translation Networks
Venue: arXiv cs.CV 2018
Year: 2018

Unsupervised image-to-image translation aims at learning a joint distribution of images in different domains by using images from the marginal distributions in individual domains. Since there exists an infinite set of joint distributions that can arrive the given marginal distributions, one could infer nothing about the joint distribution from the marginal distributions without additional assumptions. To address the problem, we make a shared-latent space assumption and propose an unsupervised image-to-image translation framework based on Coupled GANs. We compare the proposed framework with competing approaches and present high quality image translation results on various challenging unsupervised image translation tasks, including street scene image translation, animal image translation, and face image translation. We also apply the proposed framework to domain adaptation and achieve state-of-the-art performance on benchmark datasets. Code and additional results are available in https://github.com/mingyuliutw/unit .
Understanding and Predicting Delay in Reciprocal Relations
Venue: arXiv cs.SI 2018
Year: 2018

Reciprocity in directed networks points to user's willingness to return favors in building mutual interactions. High reciprocity has been widely observed in many directed social media networks such as following relations in Twitter and Tumblr. Therefore, reciprocal relations between users are often regarded as a basic mechanism to create stable social ties and play a crucial role in the formation and evolution of networks. Each reciprocity relation is formed by two parasocial links in a back-and-forth manner with a time delay. Hence, understanding the delay can help us gain better insights into the underlying mechanisms of network dynamics. Meanwhile, the accurate prediction of delay has practical implications in advancing a variety of real-world applications such as friend recommendation and marketing campaign. For example, by knowing when will users follow back, service providers can focus on the users with a potential long reciprocal delay for effective targeted marketing. This paper presents the initial investigation of the time delay in reciprocal relations. Our study is based on a large-scale directed network from Tumblr that consists of 62.8 million users and 3.1 billion user following relations with a timespan of multiple years (from 31 Oct 2007 to 24 Jul 2013). We reveal a number of interesting patterns about the delay that motivate the development of a principled learning model to predict the delay in reciprocal relations. Experimental results on the above mentioned dynamic networks corroborate the effectiveness of the proposed delay prediction model.
Learning Deep Matrix Representations
Venue: arXiv cs.LG 2018
Year: 2018

We present a new distributed representation in deep neural nets wherein the information is represented in native form as a matrix. This differs from current neural architectures that rely on vector representations. We consider matrices as central to the architecture and they compose the input, hidden and output layers. The model representation is more compact and elegant -- the number of parameters grows only with the largest dimension of the incoming layer rather than the number of hidden units. We derive several new deep networks: (i) feed-forward nets that map an input matrix into an output matrix, (ii) recurrent nets which map a sequence of input matrices into a sequence of output matrices. We also reinterpret existing models for (iii) memory-augmented networks and (iv) graphs using matrix notations. For graphs we demonstrate how the new notations lead to simple but effective extensions with multiple attentions. Extensive experiments on handwritten digits recognition, face reconstruction, sequence to sequence learning, EEG classification, and graph-based node classification demonstrate the efficacy and compactness of the matrix architectures.
Controlling for Unobserved Confounds in Classification Using Correlational Constraints
Venue: arXiv cs.AI 2018
Year: 2018

As statistical classifiers become integrated into real-world applications, it is important to consider not only their accuracy but also their robustness to changes in the data distribution. In this paper, we consider the case where there is an unobserved confounding variable $z$ that influences both the features $\mathbf{x}$ and the class variable $y$. When the influence of $z$ changes from training to testing data, we find that the classifier accuracy can degrade rapidly. In our approach, we assume that we can predict the value of $z$ at training time with some error. The prediction for $z$ is then fed to Pearl's back-door adjustment to build our model. Because of the attenuation bias caused by measurement error in $z$, standard approaches to controlling for $z$ are ineffective. In response, we propose a method to properly control for the influence of $z$ by first estimating its relationship with the class variable $y$, then updating predictions for $z$ to match that estimated relationship. By adjusting the influence of $z$, we show that we can build a model that exceeds competing baselines on accuracy as well as on robustness over a range of confounding relationships.
Classification and clustering for observations of event time data using non-homogeneous Poisson process models
Venue: arXiv cs.LG 2018
Year: 2018

Data of the form of event times arise in various applications. A simple model for such data is a non-homogeneous Poisson process (NHPP) which is specified by a rate function that depends on time. We consider the problem of having access to multiple independent observations of event time data, observed on a common interval, from which we wish to classify or cluster the observations according to their rate functions. Each rate function is unknown but assumed to belong to a finite number of rate functions each defining a distinct class. We model the rate functions using a spline basis expansion, the coefficients of which need to be estimated from data. The classification approach consists of using training data for which the class membership is known, to calculate maximum likelihood estimates of the coefficients for each group, then assigning test observations to a group by a maximum likelihood criterion. For clustering, by analogy to the Gaussian mixture model approach for Euclidean data, we consider mixtures of NHPP and use the expectation-maximisation algorithm to estimate the coefficients of the rate functions for the component models and group membership probabilities for each observation. The classification and clustering approaches perform well on both synthetic and real-world data sets. Code associated with this paper is available at https://github.com/duncan-barrack/NHPP .
Relay-Pair Selection in Buffer-Aided Successive Opportunistic Relaying using a Multi-Antenna Source
Venue: arXiv cs.IT 2018
Year: 2018

We study a cooperative network with a buffer-aided multi-antenna source, multiple half-duplex (HD) buffer-aided relays and a single destination. Such a setup could represent a cellular downlink scenario, in which the source can be a more powerful wireless device with a buffer and multiple antennas, while a set of intermediate less powerful devices are used as relays to reach the destination. The main target is to recover the multiplexing loss of the network by having the source and a relay to simultaneously transmit their information to another relay and the destination, respectively. Successive transmissions in such a cooperative network, however, cause inter-relay interference (IRI). First, by assuming global channel state information (CSI), we show that the detrimental effect of IRI can be alleviated by precoding at the source, mitigating or even fully cancelling the interference. A cooperative relaying policy is proposed that employs a joint precoding design and relay-pair selection. Note that both fixed rate and adaptive rate transmissions can be considered. For the case when channel state information is only available at the receiver side (CSIR), we propose a relay selection policy that employs a phase alignment technique to reduce the IRI. The performance of the two proposed relay pair selection policies are evaluated and compared with other state-of-the-art relaying schemes in terms of outage and throughput. The results show that the use of a powerful source can provide considerable performance improvements.
Integer Factorization with a Neuromorphic Sieve
Venue: arXiv cs.NE 2018
Year: 2018

The bound to factor large integers is dominated by the computational effort to discover numbers that are smooth, typically performed by sieving a polynomial sequence. On a von Neumann architecture, sieving has log-log amortized time complexity to check each value for smoothness. This work presents a neuromorphic sieve that achieves a constant time check for smoothness by exploiting two characteristic properties of neuromorphic architectures: constant time synaptic integration and massively parallel computation. The approach is validated by modifying msieve, one of the fastest publicly available integer factorization implementations, to use the IBM Neurosynaptic System (NS1e) as a coprocessor for the sieving stage.
Depth from Monocular Images using a Semi-Parallel Deep Neural Network (SPDNN) Hybrid Architecture
Venue: arXiv cs.CV 2018
Year: 2018

Deep neural networks are applied to a wide range of problems in recent years. In this work, Convolutional Neural Network (CNN) is applied to the problem of determining the depth from a single camera image (monocular depth). Eight different networks are designed to perform depth estimation, each of them suitable for a feature level. Networks with different pooling sizes determine different feature levels. After designing a set of networks, these models may be combined into a single network topology using graph optimization techniques. This "Semi Parallel Deep Neural Network (SPDNN)" eliminates duplicated common network layers, and can be further optimized by retraining to achieve an improved model compared to the individual topologies. In this study, four SPDNN models are trained and have been evaluated at 2 stages on the KITTI dataset. The ground truth images in the first part of the experiment are provided by the benchmark, and for the second part, the ground truth images are the depth map results from applying a state-of-the-art stereo matching method. The results of this evaluation demonstrate that using post-processing techniques to refine the target of the network increases the accuracy of depth estimation on individual mono images. The second evaluation shows that using segmentation data alongside the original data as the input can improve the depth estimation results to a point where performance is comparable with stereo depth estimation. The computational time is also discussed in this study.
Poisson multi-Bernoulli mixture filter: direct derivation and implementation
Venue: arXiv cs.CV 2018
Year: 2018

We provide a derivation of the Poisson multi-Bernoulli mixture (PMBM) filter for multi-target tracking with the standard point target measurements without using probability generating functionals or functional derivatives. We also establish the connection with the δ-generalised labelled multi-Bernoulli (δ-GLMB) filter, showing that a δ-GLMB density represents a multi-Bernoulli mixture with labelled targets so it can be seen as a special case of PMBM. In addition, we propose an implementation for linear/Gaussian dynamic and measurement models and how to efficiently obtain typical estimators in the literature from the PMBM. The PMBM filter is shown to outperform other filters in the literature in a challenging scenario.