A Chain-Detection Algorithm for Two-Dimensional Grids

We describe a general method of detecting valid chains or links of pieces on a two-dimensional grid. Specifically, using the example of the chess variant known as Switch-Side Chain-Chess (SSCC). Presently, no foolproof method of detecting such chains in any given chess position is known and existing graph theory, to our knowledge, is unable to fully address this problem either. We therefore propose a solution implemented and tested using the C++ programming language. We have been unable to find an incorrect result and therefore offer it as the most viable solution thus far to the chain-detection problem in this chess variant. The algorithm is also scalable, in principle, to areas beyond two-dimensional grids such as 3D analysis and molecular chemistry.

A Paradigm for Situated and Goal-Driven Language Learning

A distinguishing property of human intelligence is the ability to flexibly use language in order to communicate complex ideas with other humans in a variety of contexts. Research in natural language dialogue should focus on designing communicative agents which can integrate themselves into these contexts and productively collaborate with humans. In this abstract, we propose a general situated language learning paradigm which is designed to bring about robust language agents able to cooperate productively with humans.

How Many Components should be Retained from a Multivariate Time Series PCA?

We report on the results of two new approaches to considering how many principal components to retain from an analysis of a multivariate time series. The first is by using a ‘heat map’ based approach. A heat map in this context refers to a series of principal component coefficients created by applying a sliding window to a multivariate time series. Furthermore the heat maps can provide detailed insights into the evolution of the structure of each principal component over time. The second is by examining the change of the angle of the principal component over time within the high-dimensional data space. We provide evidence that both are useful in studying structure and evolution of a multivariate time series.

On statistical learning via the lens of compression

This work continues the study of the relationship between sample compression schemes and statistical learning, which has been mostly investigated within the framework of binary classification. The central theme of this work is establishing equivalences between learnability and compressibility, and utilizing these equivalences in the study of statistical learning theory. We begin with the setting of multiclass categorization (zero/one loss). We prove that in this case learnability is equivalent to compression of logarithmic sample size, and that uniform convergence implies compression of constant size. We then consider Vapnik’s general learning setting: we show that in order to extend the compressibility-learnability equivalence to this case, it is necessary to consider an approximate variant of compression. Finally, we provide some applications of the compressibility-learnability equivalences: (i) Agnostic-case learnability and realizable-case learnability are equivalent in multiclass categorization problems (in terms of sample complexity). (ii) This equivalence between agnostic-case learnability and realizable-case learnability does not hold for general learning problems: There exists a learning problem whose loss function takes just three values, under which agnostic-case and realizable-case learnability are not equivalent. (iii) Uniform convergence implies compression of constant size in multiclass categorization problems. Part of the argument includes an analysis of the uniform convergence rate in terms of the graph dimension, in which we improve upon previous bounds. (iv) A dichotomy for sample compression in multiclass categorization problems: If a non-trivial compression exists then a compression of logarithmic size exists. (v) A compactness theorem for multiclass categorization problems.

Towards a Theoretical Analysis of PCA for Heteroscedastic Data

Principal Component Analysis (PCA) is a method for estimating a subspace given noisy samples. It is useful in a variety of problems ranging from dimensionality reduction to anomaly detection and the visualization of high dimensional data. PCA performs well in the presence of moderate noise and even with missing data, but is also sensitive to outliers. PCA is also known to have a phase transition when noise is independent and identically distributed; recovery of the subspace sharply declines at a threshold noise variance. Effective use of PCA requires a rigorous understanding of these behaviors. This paper provides a step towards an analysis of PCA for samples with heteroscedastic noise, that is, samples that have non-uniform noise variances and so are no longer identically distributed. In particular, we provide a simple asymptotic prediction of the recovery of a one-dimensional subspace from noisy heteroscedastic samples. The prediction enables: a) easy and efficient calculation of the asymptotic performance, and b) qualitative reasoning to understand how PCA is impacted by heteroscedasticity (such as outliers).

Fast Training of Convolutional Neural Networks via Kernel Rescaling

Training deep Convolutional Neural Networks (CNN) is a time consuming task that may take weeks to complete. In this article we propose a novel, theoretically founded method for reducing CNN training time without incurring any loss in accuracy. The basic idea is to begin training with a pre-train network using lower-resolution kernels and input images, and then refine the results at the full resolution by exploiting the spatial scaling property of convolutions. We apply our method to the ImageNet winner OverFeat and to the more recent ResNet architecture and show a reduction in training time of nearly 20% while test set accuracy is preserved in both cases.

Image Based Camera Localization: an Overview

Recently, virtual reality, augmented reality, robotics, self-driving cars et al attractive much attention of industrial community, in which image based camera localization is a key task. It is urgent to give an overview of image based camera localization. In this paper, an overview of image based camera localization is presented. It will be useful to not only researchers but also engineers.

Optimistic Semi-supervised Least Squares Classification

The goal of semi-supervised learning is to improve supervised classifiers by using additional unlabeled training examples. In this work we study a simple self-learning approach to semi-supervised learning applied to the least squares classifier. We show that a soft-label and a hard-label variant of self-learning can be derived by applying block coordinate descent to two related but slightly different objective functions. The resulting soft-label approach is related to an idea about dealing with missing data that dates back to the 1930s. We show that the soft-label variant typically outperforms the hard-label variant on benchmark datasets and partially explain this behaviour by studying the relative difficulty of finding good local minima for the corresponding objective functions.

The Weak Efficient Market Hypothesis in Light of Statistical Learning

We make an unprecedented evaluation of statistical learning methods to forecast daily returns. Using a randomization test to adjust for data snooping, several models are found statistically significant on the tested equity indices: CSI 300, FTSE, and S&P 500. A best Sharpe ratio portfolio has abnormal returns on the S&P 500, breaking even with the market at 10 bps in round trip costs. The returns produce statistically significant intercept for factor regression models, qualifying as a new anomalous 3-day crisis persistency factor. These results open the path towards a standardized usage of statistical learning methods in finance.

R-Linear Convergence of Limited Memory Steepest Descent

The limited memory steepest descent method (LMSD) proposed by Fletcher is an extension of the Barzilai-Borwein ‘two-point step size’ strategy for steepest descent methods for solving unconstrained optimization problems. It is known that the Barzilai-Borwein strategy yields a method with an R-linear rate of convergence when it is employed to minimize a strongly convex quadratic. This paper extends this analysis for LMSD, also for strongly convex quadratics. In particular, it is shown that the method is R-linearly convergent for any choice of the history length parameter. The results of numerical experiments are provided to illustrate behaviors of the method that are revealed through the theoretical analysis.

Dynamically enriched topological orders in driven two-dimensional systems

NMR lineshape of $^{29}$Si in single-crystal silicon

Sparse Channel Estimation for Massive MIMO with 1-bit Feedback per Dimension

Enhancing Secrecy with Multi-Antenna Transmission in Millimeter Wave Vehicular Communication Systems

Transfer from Simulation to Real World through Learning Deep Inverse Dynamics Model

Supermarket Queueing System in the Heavy Traffic Regime. Short Queue Dynamics

Improved Parallel Construction of Wavelet Trees and Rank/Select Structures

Cooperative Strategies for Wireless-Powered Communications

Pattern avoidance and fiber bundle structures on Schubert varieties

Capacity bounds for distributed storage

Quantum automata cannot detect biased coins, even in the limit

Visual Place Recognition with Probabilistic Vertex Voting

Monotone Empirical Bayes Estimators for the Reproduction Number in Borel-Tanner Distribution

Finding Bidder-Optimal Core Points Quickly

Robust self-testing of many-qubit states

On Seneta-Heyde Scaling for a stable branching random walk

Minimax Filter: Learning to Preserve Privacy from Inference Attacks

An efficient multiple imputation algorithm for control-based and delta-adjusted pattern mixture models using SAS

QCMA hardness of ground space connectivity for commuting Hamiltonians

New families of Strictly optimal Frequency hopping sequence sets

Combinatorial differential operators in: Faà di Bruno formula, enumeration of ballot paths, enriched rooted trees and increasing rooted trees

Subspace clustering based on low rank representation and weighted nuclear norm minimization

Maximum entropy models for generation of expressive music

Composite likelihood inference for spatio-temporal data on multicolor cell growth

Correlations between real and complex zeros of a random polynomial

Law of large numbers for the SIR model with random vertex weights on Erdős-Rényi graph

The Analysis of Local Motion and Deformation in Image Sequences Inspired by Physical Electromagnetic Interaction

A Model of Virtual Carrier Immigration in Digital Images for Region Segmentation

The Virtual Electromagnetic Interaction between Digital Images for Image Matching with Shifting Transformation

Optimizing Memory Efficiency for Deep Convolutional Neural Networks on GPUs

RetiNet: Automatic AMD identification in OCT volumetric data

Analyzing the Affect of a Group of People Using Multi-modal Framework

An Inter-User Interference Suppression Method in Full-Duplex Networks

Multi-Task Curriculum Transfer Deep Learning of Clothing Attributes

Deep Fruit Detection in Orchards

Recovering asymmetric communities in the stochastic block model

Light Field Compression with Disparity Guided Sparse Coding based on Structural Key Views

Smallest not $C_{2l+1}$-colourable graphs of odd-girth $2k+1$

Bayesian models for data missing not at random in health examination surveys

A $q$-Robinson-Schensted-Knuth Algorithm and a $q$-polymer

Local asymptotic normality property for fractional Gaussian noise under high-frequency observations

Localization in High-Dimensional Monte Carlo Filtering

Structure Properties of Koch Networks Based on Networks Dynamical Systems

Generating captions without looking beyond objects

Dynamic R&D Competition under Uncertainty and Strategic Disclosure

Backward stochastic differential equations with Young drift

Discovering Small Target Sets in Social Networks: A Fast and Effective Algorithm

Post Selection Inference with Kernels

Fair user traffic association in cache equipped cellular networks

Burst Transmission Symbol Synchronization in the Presence of Cycle Slip Arising from Different Clock Frequencies

Exploring the Entire Regularization Path for the Asymmetric Cost Linear Support Vector Machine

Dividing goods and bads under additive utilities

Semi-supervised Discovery of Informative Tweets During the Emerging Disasters

Language Models with GloVe Word Embeddings

Detecting Unseen Falls from Wearable Devices using Channel-wise Ensemble of Autoencoders

Large subgraphs in pseudo-random graphs

Technical Report: Improved Fourier Reconstruction using Jump Information with Applications to MRI

SentiHood: Targeted Aspect Based Sentiment Analysis Dataset for Urban Neighbourhoods

Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging

Sharp exponential inequalities in survey sampling: conditional Poisson sampling schemes

Deep disentangled representations for volumetric reconstruction

Video Depth-From-Defocus

Change-point detection in high-dimensional covariance structure

Computing the Expected Value and Variance of Geometric Measures

Decentralized Coded Caching with Distinct Cache Capacities

Introduction to the ‘Industrial Benchmark’

On Probabilistic Checking in Perfect Zero Knowledge

Robust Scheduling for Flexible Processing Networks

Domain-specific Question Generation from a Knowledge Base

Lyndon word decompositions and pseudo orbits on q-nary graphs

A Continuous Model of Cortical Connectivity

Disparity of clustering coefficients in the Holme-Kim network model

Recursive Diffeomorphism-Based Regression for Shape Functions

Wilson loop expectations in $SU(N)$ lattice gauge theory

Cooperation driven by success-driven group formation

Variational approximation of functionals defined on 1-dimensional connected sets: the planar case