Scalable Geographically Weighted Regression (ScaGWR) google
While a number of studies have developed fast geographically weighted regression (GWR) algorithms for large samples, none of them achieves the linear-time estimation that is considered requisite for big data analysis in machine learning, geostatistics, and related domains. Against this backdrop, this study proposes a scalable geographically weighted regression (ScaGWR) for large datasets. The key development is the calibration of the model through a pre-compression of the matrices and vectors whose size depends on the sample size, prior to the execution of leave-one-out cross-validation (LOOCV) that is the heaviest computational step in conventional GWR. This pre-compression allows us to run the proposed GWR extension such that its computation time increases linearly with sample size, whereas conventional GWR algorithms take at most quad-quadratic-order time. With this development, the ScaGWR can be calibrated with more than one million samples without parallelization. Moreover, the ScaGWR estimator can be regarded as an empirical Bayesian estimator that is more stable than the conventional GWR estimator. This study compared the ScaGWR with the conventional GWR in terms of estimation accuracy, predictive accuracy, and computational efficiency using a Monte Carlo simulation. Then, we apply these methods to a residential land analysis in the Tokyo Metropolitan Area. The code for ScaGWR is available in the R package scgwr, and is going to be incorporated into another R package, GWmodel. …

Contextual Bandits via RAndom Projection (CBRAP) google
Contextual bandits with linear payoffs, which are also known as linear bandits, provide a powerful alternative for solving practical problems of sequential decisions, e.g., online advertisements. In the era of big data, contextual data usually tend to be high-dimensional, which leads to new challenges for traditional linear bandits mostly designed for the setting of low-dimensional contextual data. Due to the curse of dimensionality, there are two challenges in most of the current bandit algorithms: the first is high time-complexity; and the second is extreme large upper regret bounds with high-dimensional data. In this paper, in order to attack the above two challenges effectively, we develop an algorithm of Contextual Bandits via RAndom Projection (\texttt{CBRAP}) in the setting of linear payoffs, which works especially for high-dimensional contextual data. The proposed \texttt{CBRAP} algorithm is time-efficient and flexible, because it enables players to choose an arm in a low-dimensional space, and relaxes the sparsity assumption of constant number of non-zero components in previous work. Besides, we provide a linear upper regret bound for the proposed algorithm, which is associated with reduced dimensions. …

Trainable Time Warping (TTW) google
DTW calculates the similarity or alignment between two signals, subject to temporal warping. However, its computational complexity grows exponentially with the number of time-series. Although there have been algorithms developed that are linear in the number of time-series, they are generally quadratic in time-series length. The exception is generalized time warping (GTW), which has linear computational cost. Yet, it can only identify simple time warping functions. There is a need for a new fast, high-quality multisequence alignment algorithm. We introduce trainable time warping (TTW), whose complexity is linear in both the number and the length of time-series. TTW performs alignment in the continuous-time domain using a sinc convolutional kernel and a gradient-based optimization technique. We compare TTW and GTW on 85 UCR datasets in time-series averaging and classification. TTW outperforms GTW on 67.1% of the datasets for the averaging tasks, and 61.2% of the datasets for the classification tasks. …

PT-ISABB google
Asymmetric Distributed Constraint Optimization Problems (ADCOPs) have emerged as an important formalism in multi-agent community due to their ability to capture personal preferences. However, the existing search-based complete algorithms for ADCOPs can only use local knowledge to compute lower bounds, which leads to inefficient pruning and prohibits them from solving large scale problems. On the other hand, inference-based complete algorithms (e.g., DPOP) for Distributed Constraint Optimization Problems (DCOPs) require only a linear number of messages, but they cannot be directly applied into ADCOPs due to a privacy concern. Therefore, in the paper, we consider the possibility of combining inference and search to effectively solve ADCOPs at an acceptable loss of privacy. Specifically, we propose a hybrid complete algorithm called PT-ISABB which uses a tailored inference algorithm to provide tight lower bounds and a tree-based complete search algorithm to exhaust the search space. We prove the correctness of our algorithm and the experimental results demonstrate its superiority over other state-of-the-art complete algorithms. …