OpenRaiser/Intern-Atlas huggingface dataset:
Maximal Repetition and Zero Entropy Rate
Venue: arXiv cs.IT 2017
Year: 2017

Maximal repetition of a string is the maximal length of a repeated substring. This paper investigates maximal repetition of strings drawn from stochastic processes. Strengthening previous results, two new bounds for the almost sure growth rate of maximal repetition are identified: an upper bound in terms of conditional Rényi entropy of order $γ>1$ given a sufficiently long past and a lower bound in terms of unconditional Shannon entropy ($γ=1$). Both the upper and the lower bound can be proved using an inequality for the distribution of recurrence time. We also supply an alternative proof of the lower bound which makes use of an inequality for the expectation of subword complexity. In particular, it is shown that a power-law logarithmic growth of maximal repetition with respect to the string length, recently observed for texts in natural language, may hold only if the conditional Rényi entropy rate given a sufficiently long past equals zero. According to this observation, natural language cannot be faithfully modeled by a typical hidden Markov process, which is a class of basic language models used in computational linguistics.
Explaining the emergence of echo chambers on social media: the role of ideology and extremism
Venue: arXiv cs.SI 2017
Year: 2017

The emergence of politically driven divisions in online discussion networks has attracted a wealth of literature, but also one which has thus far been largely limited to single country studies. Hence whilst there is good evidence that these networks do divide and fragment into what are often described as "echo chambers", we know little about the factors which might explain this division or make networks more or less fragmented, as studies have been limited to a small number of political groupings with limited possibilities for systematic comparison. This paper seeks to remedy this deficit, by providing a systematic large scale study of fragmentation on Twitter which considers discussion networks surrounding 90 different political parties in 23 different countries. It shows that political party groupings which are further apart in ideological terms interact less, and that individuals and parties which sit at the extreme ends of the ideological scale are particularly likely to form echo chambers. Indeed, exchanges between centrist parties who sit on different sides of the left-right divide are more likely than communication between centrist and extremist parties who are, notionally, from the same ideological wing. In light of the results, theory about exposure to different ideological viewpoints online is discussed and enhanced.
Design and Analysis of Initial Access in Millimeter Wave Cellular Networks
Venue: arXiv cs.IT 2017
Year: 2017

Initial access is the process which allows a mobile user to first connect to a cellular network. It consists of two main steps: cell search (CS) on the downlink and random access (RA) on the uplink. Millimeter wave (mmWave) cellular systems typically must rely on directional beamforming (BF) in order to create a viable connection. The beamforming direction must therefore be learned-as well as used-in the initial access process for mmWave cellular networks. This paper considers four simple but representative initial access protocols that use various combinations of directional beamforming and omnidirectional transmission and reception at the mobile and the BS, during the CS and RA phases. We provide a system-level analysis of the success probability for CS and RA for each one, as well as of the initial access delay and user-perceived downlink throughput (UPT). For a baseline exhaustive search protocol, we find the optimal BS beamwidth and observe that in terms of initial access delay it is decreasing as blockage becomes more severe, but is relatively constant (about $π/12$) for UPT. Of the considered protocols, the best trade-off between initial access delay and UPT is achieved under a fast cell search protocol.
Multi-Residual Networks: Improving the Speed and Accuracy of Residual Networks
Venue: arXiv cs.CV 2017
Year: 2017

In this article, we take one step toward understanding the learning behavior of deep residual networks, and supporting the observation that deep residual networks behave like ensembles. We propose a new convolutional neural network architecture which builds upon the success of residual networks by explicitly exploiting the interpretation of very deep networks as an ensemble. The proposed multi-residual network increases the number of residual functions in the residual blocks. Our architecture generates models that are wider, rather than deeper, which significantly improves accuracy. We show that our model achieves an error rate of 3.73% and 19.45% on CIFAR-10 and CIFAR-100 respectively, that outperforms almost all of the existing models. We also demonstrate that our model outperforms very deep residual networks by 0.22% (top-1 error) on the full ImageNet 2012 classification dataset. Additionally, inspired by the parallel structure of multi-residual networks, a model parallelism technique has been investigated. The model parallelism method distributes the computation of residual blocks among the processors, yielding up to 15% computational complexity improvement.
Italy goes to Stanford: a collection of CoreNLP modules for Italian
Venue: arXiv cs.CL 2017
Year: 2017

In this we paper present Tint, an easy-to-use set of fast, accurate and extendable Natural Language Processing modules for Italian. It is based on Stanford CoreNLP and is freely available as a standalone software or a library that can be integrated in an existing project.
Robust Estimation of Multiple Inlier Structures
Venue: arXiv cs.CV 2017
Year: 2017

The robust estimator presented in this paper processes each structure independently. The scales of the structures are estimated adaptively and no threshold is involved in spite of different objective functions. The user has to specify only the number of elemental subsets for random sampling. After classifying all the input data, the segmented structures are sorted by their strengths and the strongest inlier structures come out at the top. Like any robust estimators, this algorithm also has limitations which are described in detail. Several synthetic and real examples are presented to illustrate every aspect of the algorithm.
From Facial Expression Recognition to Interpersonal Relation Prediction
Venue: arXiv cs.CV 2017
Year: 2017

Interpersonal relation defines the association, e.g., warm, friendliness, and dominance, between two or more people. Motivated by psychological studies, we investigate if such fine-grained and high-level relation traits can be characterized and quantified from face images in the wild. We address this challenging problem by first studying a deep network architecture for robust recognition of facial expressions. Unlike existing models that typically learn from facial expression labels alone, we devise an effective multitask network that is capable of learning from rich auxiliary attributes such as gender, age, and head pose, beyond just facial expression data. While conventional supervised training requires datasets with complete labels (e.g., all samples must be labeled with gender, age, and expression), we show that this requirement can be relaxed via a novel attribute propagation method. The approach further allows us to leverage the inherent correspondences between heterogeneous attribute sources despite the disparate distributions of different datasets. With the network we demonstrate state-of-the-art results on existing facial expression recognition benchmarks. To predict inter-personal relation, we use the expression recognition network as branches for a Siamese model. Extensive experiments show that our model is capable of mining mutual context of faces for accurate fine-grained interpersonal prediction.
The Complexity of the Numerical Semigroup Gap Counting Problem
Venue: arXiv cs.CC 2017
Year: 2017

In this paper, we prove that the numerical-semigroup-gap counting problem is #NP-complete as a main theorem. A numerical semigroup is an additive semigroup over the set of all nonnegative integers. A gap of a numerical semigroup is defined as a positive integer that does not belong to the numerical semigroup. The computation of gaps of numerical semigroups has been actively studied from the 19th century. However, little has been known on the computational complexity. In 2005, Ramirez-Alfonsin proposed a question whether or not the numerical-semigroup-gap counting problem is #P-complete. This work is an answer for his question. For proving the main theorem, we show the #NP-completenesses of other two variants of the numerical-semigroup-gap counting problem.
Using CMA-ES for tuning coupled PID controllers within models of combustion engines
Venue: arXiv cs.SY 2017
Year: 2017

Proportional integral derivative (PID) controllers are important and widely used tools in system control. Tuning of the controller gains is a laborious task, especially for complex systems such as combustion engines. To minimize the time of an engineer for tuning of the gains in a simulation software, we propose to formulate a part of the problem as a black-box optimization task. In this paper, we summarize the properties and practical limitations of tuning of the gains in this particular application. We investigate the latest methods of black-box optimization and conclude that the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) with bi-population restart strategy, elitist parent selection and active covariance matrix adaptation is best suited for this task. Details of the algorithm's experiment-based calibration are explained as well as derivation of a suitable objective function. The method's performance is compared with that of PSO and SHADE. Finally, its usability is verified on six models of real engines.
Channel Estimation and Performance Analysis of One-Bit Massive MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers channel estimation and system performance for the uplink of a single-cell massive multiple-input multiple-output (MIMO) system. Each receive antenna of the base station (BS) is assumed to be equipped with a pair of one-bit analog-to-digital converters (ADCs) to quantize the real and imaginary part of the received signal. We first propose an approach for channel estimation that is applicable for both flat and frequency-selective fading, based on the Bussgang decomposition that reformulates the nonlinear quantizer as a linear functionwith identical first- and second-order statistics. The resulting channel estimator outperforms previously proposed approaches across all SNRs. We then derive closed-form expressions for the achievable rate in flat fading channels assuming low SNR and a large number of users for the maximal ratio and zero forcing receivers that takes channel estimation error due to both noise and one-bit quantization into account. The closed-form expressions in turn allow us to obtain insight into important system design issues such as optimal resource allocation, maximal sum spectral efficiency, overall energy efficiency, and number of antennas. Numerical results are presented to verify our analytical results and demonstrate the benefit of optimizing system performance accordingly.
Balancing Speed and Coverage by Sequential Seeding in Complex Networks
Venue: arXiv cs.SI 2017
Year: 2017

Information spreading in complex networks is often modeled as diffusing information with certain probability from nodes that possess it to their neighbors that do not. Information cascades are triggered when the activation of a set of initial nodes (seeds) results in diffusion to large number of nodes. Here, several novel approaches for seed initiation that replace the commonly used activation of all seeds at once with a sequence of initiation stages are introduced. Sequential strategies at later stages avoid seeding highly ranked nodes that are already activated by diffusion active between stages. The gain arises when a saved seed is allocated to a node difficult to reach via diffusion. Sequential seeding and a single stage approach are compared using various seed ranking methods and diffusion parameters on real complex networks. The experimental results indicate that, regardless of the seed ranking method used, sequential seeding strategies deliver better coverage than single stage seeding in about 90% of cases. Longer seeding sequences tend to activate more nodes but they also extend the duration of diffusion. Various variants of sequential seeding resolve the trade-off between the coverage and speed of diffusion differently.
Gone with the Wind: Nonlinear Guidance for Small Fixed-Wing Aircrafts in Arbitrarily Strong Windfields
Venue: arXiv cs.SY 2017
Year: 2017

The recent years have witnessed increased development of small, autonomous fixed-wing Unmanned Aerial Vehicles (UAVs). In order to unlock widespread applicability of these platforms, they need to be capable of operating under a variety of environmental conditions. Due to their small size, low weight, and low speeds, they require the capability of coping with wind speeds that are approaching or even faster than the nominal airspeed. In this paper we present a principled nonlinear guidance strategy, addressing this problem. More broadly, we propose a methodology for the high-level control of non-holonomic unicycle-like vehicles in the presence of strong flowfields (e.g. winds, underwater currents) which may outreach the maximum vehicle speed. The proposed strategy guarantees convergence to a safe and stable vehicle configuration with respect to the flowfield, while preserving some tracking performance with respect to the target path. Evaluations in simulations and a challenging real-world flight experiment in very windy conditions confirm the feasibility of the proposed guidance approach.
Testing Quantum Models of Conjunction Fallacy on the World Wide Web
Venue: arXiv cs.AI 2017
Year: 2017

The 'conjunction fallacy' has been extensively debated by scholars in cognitive science and, in recent times, the discussion has been enriched by the proposal of modeling the fallacy using the quantum formalism. Two major quantum approaches have been put forward: the first assumes that respondents use a two-step sequential reasoning and that the fallacy results from the presence of 'question order effects'; the second assumes that respondents evaluate the cognitive situation as a whole and that the fallacy results from the 'emergence of new meanings', as an 'effect of overextension' in the conceptual conjunction. Thus, the question arises as to determine whether and to what extent conjunction fallacies would result from 'order effects' or, instead, from 'emergence effects'. To help clarify this situation, we propose to use the World Wide Web as an 'information space' that can be interrogated both in a sequential and non-sequential way, to test these two quantum approaches. We find that 'emergence effects', and not 'order effects', should be considered the main cognitive mechanism producing the observed conjunction fallacies.
Visual Fashion-Product Search at SK Planet
Venue: arXiv cs.CV 2017
Year: 2017

We build a large-scale visual search system which finds similar product images given a fashion item. Defining similarity among arbitrary fashion-products is still remains a challenging problem, even there is no exact ground-truth. To resolve this problem, we define more than 90 fashion-related attributes, and combination of these attributes can represent thousands of unique fashion-styles. The fashion-attributes are one of the ingredients to define semantic similarity among fashion-product images. To build our system at scale, these fashion-attributes are again used to build an inverted indexing scheme. In addition to these fashion-attributes for semantic similarity, we extract colour and appearance features in a region-of-interest (ROI) of a fashion item for visual similarity. By sharing our approach, we expect active discussion on that how to apply current computer vision research into the e-commerce industry.
Deep Structured Features for Semantic Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

We propose a highly structured neural network architecture for semantic segmentation with an extremely small model size, suitable for low-power embedded and mobile platforms. Specifically, our architecture combines i) a Haar wavelet-based tree-like convolutional neural network (CNN), ii) a random layer realizing a radial basis function kernel approximation, and iii) a linear classifier. While stages i) and ii) are completely pre-specified, only the linear classifier is learned from data. We apply the proposed architecture to outdoor scene and aerial image semantic segmentation and show that the accuracy of our architecture is competitive with conventional pixel classification CNNs. Furthermore, we demonstrate that the proposed architecture is data efficient in the sense of matching the accuracy of pixel classification CNNs when trained on a much smaller data set.
Metrics Based on Finite Directed Graphs and Coding Invariants
Venue: arXiv cs.IT 2017
Year: 2017

Given a finite directed graph with $n$ vertices, we define a metric $d_G$ on $\mathbb{F}_q^n$, where $\mathbb{F}_q$ is the finite field with $q$ elements. The weight of a word is defined as the number of vertices that can be reached by a directed path starting at the support of the vector. Two canonical forms, which do not affect the metric, are given to each graph. Based on these forms we characterize each such metric. We further use these forms to prove that two graphs with different canonical forms yield different metrics. Efficient algorithms to check if a set of metric weights define a metric based on a graph are given. We provide tight bounds on the number of metric weights required to reconstruct the metric. Furthermore, we give a complete description of the group of linear isometries of the graph metrics and a characterization of the graphs for which every linear code admits a $G$-canonical decomposition. Considering those graphs, we are able to derive an expression of the packing radius of linear codes in such metric spaces. Finally, given a directed graph which determines a hierarchical poset, we present sufficient and necessary conditions to ensure the validity of the MacWilliams Identity and the MacWilliams Extension Property.
An Efficient Method for Robust Projection Matrix Design
Venue: arXiv cs.LG 2017
Year: 2017

Our objective is to efficiently design a robust projection matrix $Φ$ for the Compressive Sensing (CS) systems when applied to the signals that are not exactly sparse. The optimal projection matrix is obtained by mainly minimizing the average coherence of the equivalent dictionary. In order to drop the requirement of the sparse representation error (SRE) for a set of training data as in [15] [16], we introduce a novel penalty function independent of a particular SRE matrix. Without requiring of training data, we can efficiently design the robust projection matrix and apply it for most of CS systems, like a CS system for image processing with a conventional wavelet dictionary in which the SRE matrix is generally not available. Simulation results demonstrate the efficiency and effectiveness of the proposed approach compared with the state-of-the-art methods. In addition, we experimentally demonstrate with natural images that under similar compression rate, a CS system with a learned dictionary in high dimensions outperforms the one in low dimensions in terms of reconstruction accuracy. This together with the fact that our proposed method can efficiently work in high dimension suggests that a CS system can be potentially implemented beyond the small patches in sparsity-based image processing.
Weakly Supervised PLDA Training
Venue: arXiv cs.LG 2017
Year: 2017

PLDA is a popular normalization approach for the i-vector model, and it has delivered state-of-the-art performance in speaker verification. However, PLDA training requires a large amount of labelled development data, which is highly expensive in most cases. We present a cheap PLDA training approach, which assumes that speakers in the same session can be easily separated, and speakers in different sessions are simply different. This results in `weak labels' which are not fully accurate but cheap, leading to a weak PLDA training. Our experimental results on real-life large-scale telephony customer service achieves demonstrated that the weak training can offer good performance when human-labelled data are limited. More interestingly, the weak training can be employed as a discriminative adaptation approach, which is more efficient than the prevailing unsupervised method when human-labelled data are insufficient.
Blind Facial Image Quality Enhancement using Non-Rigid Semantic Patches
Venue: arXiv cs.CV 2017
Year: 2017

We propose to combine semantic data and registration algorithms to solve various image processing problems such as denoising, super-resolution and color-correction. It is shown how such new techniques can achieve significant quality enhancement, both visually and quantitatively, in the case of facial image enhancement. Our model assumes prior high quality data of the person to be processed, but no knowledge of the degradation model. We try to overcome the classical processing limits by using semantically-aware patches, with adaptive size and location regions of coherent structure and context, as building blocks. The method is demonstrated on the problem of cellular photography enhancement of dark facial images for different identities, expressions and poses.
UbuntuWorld 1.0 LTS - A Platform for Automated Problem Solving & Troubleshooting in the Ubuntu OS
Venue: arXiv cs.AI 2017
Year: 2017

In this paper, we present UbuntuWorld 1.0 LTS - a platform for developing automated technical support agents in the Ubuntu operating system. Specifically, we propose to use the Bash terminal as a simulator of the Ubuntu environment for a learning-based agent and demonstrate the usefulness of adopting reinforcement learning (RL) techniques for basic problem solving and troubleshooting in this environment. We provide a plug-and-play interface to the simulator as a python package where different types of agents can be plugged in and evaluated, and provide pathways for integrating data from online support forums like AskUbuntu into an automated agent's learning process. Finally, we show that the use of this data significantly improves the agent's learning efficiency. We believe that this platform can be adopted as a real-world test bed for research on automated technical support.
Adaptive 360 VR Video Streaming: Divide and Conquer!
Venue: arXiv cs.MM 2017
Year: 2017

While traditional multimedia applications such as games and videos are still popular, there has been a significant interest in the recent years towards new 3D media such as 3D immersion and Virtual Reality (VR) applications, especially 360 VR videos. 360 VR video is an immersive spherical video where the user can look around during playback. Unfortunately, 360 VR videos are extremely bandwidth intensive, and therefore are difficult to stream at acceptable quality levels. In this paper, we propose an adaptive bandwidth-efficient 360 VR video streaming system using a divide and conquer approach. In our approach, we propose a dynamic view-aware adaptation technique to tackle the huge streaming bandwidth demands of 360 VR videos. We spatially divide the videos into multiple tiles while encoding and packaging, use MPEG-DASH SRD to describe the spatial relationship of tiles in the 360-degree space, and prioritize the tiles in the Field of View (FoV). In order to describe such tiled representations, we extend MPEG-DASH SRD to the 3D space of 360 VR videos. We spatially partition the underlying 3D mesh, and construct an efficient 3D geometry mesh called hexaface sphere to optimally represent a tiled 360 VR video in the 3D space. Our initial evaluation results report up to 72% bandwidth savings on 360 VR video streaming with minor negative quality impacts compared to the baseline scenario when no adaptations is applied.