  Bayesian optimization is a popular method for solving the problem of global
optimization of an expensive-to-evaluate black-box function. It relies on a
probabilistic surrogate model of the objective function, upon which an
acquisition function is built to determine where next to evaluate the objective
function. In general, Bayesian optimization with Gaussian process regression
operates on a continuous space. When input variables are categorical or
discrete, an extra care is needed. A common approach is to use one-hot encoded
or Boolean representation for categorical variables which might yield a
combinatorial explosion problem. In this paper we present a method for Bayesian
optimization in a combinatorial space, which can operate well in a large
combinatorial space. The main idea is to use a random mapping which embeds the
combinatorial space into a convex polytope in a continuous space, on which all
essential process is performed to determine a solution to the black-box
optimization in the combinatorial space. We describe our combinatorial Bayesian
optimization algorithm and present its regret analysis. Numerical experiments
demonstrate that our method shows satisfactory performance compared to existing
methods.
