Bike sharing systems consist of a fleet of bikes placed in a network of docking stations. These bikes can then be rented and returned to any of the docking stations after usage. Predicting unrealized bike demand at locations currently without bike stations is important for effectively designing and expanding bike sharing systems. We predict pairwise bike demand for New York City’s Citi Bike system. Since the system is driven by daily commuters we focus only on the morning rush hours between 7:00 AM to 11:00 AM during weekdays. We use taxi usage, weather and spatial variables as covariates to predict bike demand, and further analyze the influence of precipitation and day of week. We show that aggregating stations in neighborhoods can substantially improve predictions. The presented model can assist planners by predicting bike demand at a macroscopic level, between pairs of neighborhoods.

In this work we present a theoretical approach (not currently implemented), to the problem of predicting agent behavior. The ultimate goal of this work is to learn models that can be used to predict the future actions of intelligent agents, based on previously recorded data on those agents’ behavior. We believe that we can improve the predictive accuracy of our models by assuming that an agent reasons about the actions it takes, and trying to explicitly model that reasoning process. Here, we model an agent’s reasoning process as a form of Monte-Carlo search, and attempt to learn a state evaluation function that, when used with this planning algorithm, yields a similar distribution of actions given the current state of the world as we observe in the data. While it is simple to simulate Monte-Carlo search given an evaluation function, it is much more difficult to determine an evaluation function that will generate a certain behavior. Here we will use Expectation-Maximization to find a maximum likelihood estimate of the parameters of the evaluation function, treating the actual steps taken in planning each action as unobserved data.

In the presented research project, a software and hardware infrastructure for parking space focussed inter-modal route planning in a public pilot region in Berlin is developed. One central topic is the development of a prediction system which gives an estimated occupancy for the parking spaces in the pilot region for a given date and time in the future. Occupancy data will be collected online by roadside parking sensors developed within the project. The occupancy prediction will be implemented using “Neural Gas” machine learning in combination with a proposed method which uses data threads to improve the prediction quality. In this paper, a short overview of the whole research project is given. Furthermore, the concept of the software framework and the learning methods are presented and first collected data is shown. The prediction method using data threads is explained in more detail.

Algorithm selection (AS) techniques — which involve choosing from a set of algorithms the one expected to solve a given problem instance most efficiently — have substantially improved the state-of-the-art in solving many prominent AI problems, such as SAT, CSP, ASP, MAXSAT, and QBF.Although several AS procedures have been introduced,not too surprisingly, none of them dominates all others across all AS scenarios.Furthermore, these procedures have parameters whose optimal values vary across AS scenarios.This holds specifically for the machine learning techniques that form the core of current AS proceduresand for their hyperparameters. Therefore, to successfully apply AS to new problems, algorithms and benchmark sets, two questions need to be answered:(i) how to select an AS approach and (ii) how to set its parameters effectively.We address both of these problems simultaneously by using automated algorithm configuration.Specifically, we demonstrate that we can use algorithm configurators to automatically configure clasp folio 2,which implements a large variety of different AS approaches and their respective parameters in a single highly parameterized algorithm framework.We demonstrate that this approach, dubbed auto folio, can significantly improve the performance of clasp folio 2 on 11 out of the 12 scenarios from the Algorithm Selection Library and leads to new state-of-the-art algorithm selectors for 8 of these scenarios.

We aim to profile characteristics of areas of variant units across a district, city or a country. Studying attributes of areas can be very useful in several situations. In the past, research has focused mainly on studying specific char- acteristics of areas using a few selected attributes. In this paper we propose an alternative view on neighbourhood profiles. Instead of characterising a neighbourhood through a set of attributes such as those collected by the census, we propose use of a low-dimensional fea- ture representation, or embedding, created from one or more input sources. The purpose of the embeddings is having a generic representation for entities that can do well across several downstream tasks such as regression for attributes prediction.

In most urban area, traffic issue related to parking (e.g. economic(time) and environmental loss in finding a parking space) has been significant, and parking management strategies to set optimal price are often necessary for the parking agencies. In order to revise parking fee appropriately without a reduction of parking demand, a pricing procedure in accordance with characteristic of parking utilization is expected. On the other hand, a large amount of parking data is accumulated automatically with introduction of online parking systems. In this study, we analyze massive parking accounting data, whose data size is22.5 million accounting data in the past year about 1,050 parking lots,and discuss the characteristics of parking utilization. Moreover parking duration model is developed from the accounting data for each cluster to estimate the parking demand (i.e., parking time) after changing price. As an example of appropriate price procedure, we evaluate the setting of an upper limitation of parking charge with parking demand patterns calculated from the accounting data and the parking duration model.

Kernel means are frequently used to represent probability distributions in machine learning problems. In particular, the well known kernel density estimator and the kernel mean embedding both have the form of a kernel mean. Unfortunately, kernel means are faced with scalability issues. A single point evaluation of the kernel density estimator, for example, requires a computation time linear in the training sample size. To address this challenge, we present a method to efficiently construct a sparse approximation of a kernel mean. We do so by first establishing an incoherence-based bound on the approximation error, and then noticing that, for the case of radial kernels, the bound can be minimized by solving the $k$-center problem. The outcome is a linear time construction of a sparse kernel mean, which also lends itself naturally to an automatic sparsity selection scheme. We show the computational gains of our method by looking at three problems involving kernel means: Euclidean embedding of distributions, class proportion estimation, and clustering using the mean-shift algorithm.

We study optimal estimation for sparse principal component analysis when the number of non-zero elements is small but on the same order as the dimension of the data. We employ approximate message passing (AMP) algorithm and its state evolution to analyze what is the information theoretically minimal mean-squared error and the one achieved by AMP in the limit of large sizes. For a special case of rank one and large enough density of non-zeros Deshpande and Montanari [1] proved that AMP is asymptotically optimal. We show that both for low density and for large rank the problem undergoes a series of phase transitions suggesting existence of a region of parameters where estimation is information theoretically possible, but AMP (and presumably every other polynomial algorithm) fails. The analysis of the large rank limit is particularly instructive.

The stochastic gradient (SG) method can minimize an objective function composed of a large number of differentiable functions, or solve a stochastic optimization problem, to a moderate accuracy. The block coordinate descent/update (BCD) method, on the other hand, handles problems with multiple blocks of variables by updating them one at a time; when the blocks of variables are easier to update individually than together, BCD has a lower per-iteration cost. This paper introduces a method that combines the features of SG and BCD for problems with many components in the objective and with multiple (blocks of) variables. Specifically, a block stochastic gradient (BSG) method is proposed for solving both convex and nonconvex programs. At each iteration, BSG approximates the gradient of the differentiable part of the objective by randomly sampling a small set of data or sampling a few functions from the sum term in the objective, and then, using those samples, it updates all the blocks of variables in either a deterministic or a randomly shuffled order. Its convergence for both convex and nonconvex cases are established in different senses. In the convex case, the proposed method has the same order of convergence rate as the SG method. In the nonconvex case, its convergence is established in terms of the expected violation of a first-order optimality condition. The proposed method was numerically tested on problems including stochastic least squares and logistic regression, which are convex, as well as low-rank tensor recovery and bilinear logistic regression, which are nonconvex.

Motivated by the task of hyperparameter optimization, we introduce the non-stochastic best-arm identification problem. Within the multi-armed bandit literature, the cumulative regret objective enjoys algorithms and analyses for both the non-stochastic and stochastic settings while to the best of our knowledge, the best-arm identification framework has only been considered in the stochastic setting. We introduce the non-stochastic setting under this framework, identify a known algorithm that is well-suited for this setting, and analyze its behavior. Next, by leveraging the iterative nature of standard machine learning algorithms, we cast hyperparameter optimization as an instance of non-stochastic best-arm identification, and empirically evaluate our proposed algorithm on this task. Our empirical results show that, by allocating more resources to promising hyperparameter settings, we typically achieve comparable test accuracies an order of magnitude faster than baseline methods.