\documentclass[
    american,a4paper
    ]{scrartcl}
    
    \usepackage[a4paper,margin=2cm,includefoot]{geometry}

    % ##########################################
    % # Choose the language for the document by editing below line
    % # de = German
    % # en = English
    \newcommand{\lang}{en}
    % ##########################################

    \usepackage{babel}
    \usepackage[utf8]{inputenc} 
    \usepackage{csquotes}
    \usepackage{enumitem}
    \usepackage{ifthen}
    \usepackage{lipsum}
    \usepackage{datetime}
    \usepackage{amsfonts}
    
    \include{translatedHeadings}
    \newcommand{\xmax}{x_{\max}} 

    \ifthenelse{\equal{en}{\lang}}
    {
        \selectlanguage{american} 
    }{
        \ifthenelse{\equal{de}{\lang}}
        {
            \selectlanguage{ngerman}
        }
        {\selectlanguage{american}}        
    }

    \usepackage[
        bibencoding=utf8, 
        style=alphabetic
    ]{biblatex}

    \bibliography{bibliography}
    
    
    \usepackage{amsmath}
    \title{
        % ##########################################
        % # Insert the title of your paper/thesis here
        % ###### 
        % Coming up with a good title is hard.
        % It should:
        %  1. capture the contents of the your work
        %  2. not be to broad or generic
        %  3. stick to the truth and don't not oversell
        %  4. use established terms and wordings
        %  5. make people curious about your work
        %  6. use current buzzwords if possilbe (but do it right)
        %  7. not use too many buzzwords :-)
        Modern Bayesian Optimization
        % ##########################################
        \\  \Large{\paperSubTitle{\lang}}} % don't touch this line

    \author{
        % ##########################################
        % # Your name goes here
        % ######
        % wWll, that should be obvious, right? 
        Han Liang Wee Eric\\
        {\small PhD Student, NUS}
        % ##########################################
        }
    \date{\formatdate{28}{04}{2021}}
    \pdfinfo
    { /Title (Modern Bayesian Optimization)
    /Author (Han Liang Wee Eric)
    %  /CreationDate (D:YYYYMMDDhhmmss) % this is the format used by pdf for date/time
    %  /Subject (...)
    %  /Keywords ()
    }
    \begin{document}
      \maketitle
        \begin{abstract}

            % ##########################################
            % # Include your Abstract here 
            % ######
            % I would strongly suggest to start working on the abstract only 
            % after you have answered the 4 questions in Section 1, as this will
            % make it much easier for you to come up with an abstract that
            % is to the point, short, and still summarizing all the most crucial 
            % results of your work.
            %
            % The abstract should include the following points:
            %  - a short but to the point introduction of the problem area
            %  - what is the topic/problem, tackled in your work? 
            %  - why is the topic/problem of your work relevant? Why should the 
            %    reader care about it?
            %  - what are the results/answers of your work?
            %  - how did you gain your results and what is their quality?
            %                %  
            % It should NOT be:
            %  - too long/verbose
            %  - too short
            Bayesian Optimization (BO) has been successful (i.e. AlphaGo) in addressing expensive low-dimensional black-box optimization in small continuous search spaces. 
            Modern application of machine learning often requires dealing with high-dimensional, often large datasets. 
            In addition, search spaces for these problems are not always continuous and are sometimes discrete.
            The research goal is to understand and propose methods to enable the successful application of BO in the digital age.
            In this paper, recent research experiences and future research direction is discussed.
            First, BO and its successes and motivation for this research are briefly discussed.
            Here, we also discuss one of the recent publications dealing with adapting BO to higher dimensions.
            Finally, we present one future research direction in adapting BO to discrete search spaces: combinatorial Bayesian Optimization.
            % ##########################################

        \end{abstract}

        \section{Research Statement}

        \paragraph{Introduction to Bayesian Optimization.}
        Bayesian Optimization (BO) is a popular method for sequential global optimization, and is suited to situations in which the objective black-box function $f$ is expensive to evaluate \cite{snoek2012practical,mockus1994application}. 
        For example, we consider finding $\xmax = \arg \max_{x \in {\mathcal X}} f(x)$ for some function $f$.
        If $f$ is known and known/assumed to be convex, we can simply apply convex optimization. 
        However, $f$ is not known exactly and/or evaluations expensive and/or noisy in many real problems such as hyperparameter optimization.
        BO can overcome such conditions to find $\xmax$ with the \textit{least} possible number of observations by making two key assumptions:
        surrogate model that will capture our prior beliefs on $f$ and acquisition function that can be inexpensively optimized.
        BO translates the original problem to yet another optimization problem.
        Gaussian Processes (GP) are commonly used as the surrogate because it allows us to model the prior and marginal log-likelihood.
        \paragraph{Motivation.}
        BO has found success in many areas; 
        most notably in automatically tuning the game playing hyperparameters of AlphaGo \cite{chen2018bayesian}.
        BO enhanced the playing power of AlphaGo while decreasing resources needed for manual tuning.
        However, such success have been often found in low dimensional \cite{wang2013bayesian} continuous spaces \cite{7352306} with small datasets \cite{ambikasaran2015fast}.
        \paragraph{Active Research.}
        From the lines of inquiry, we discuss possible research directions below:
        \begin{itemize}
            \item \underline{Scaling to higher dimensions:} two approaches via making additional assumptions,
            \begin{itemize}
                \item \underline{Low effective dimensionality,} only few dimensions significantly affect $f$ \cite{chen2012joint}.
                \item \underline{Additive structure,} small subsets of variables interact with each other \cite{kandasamy2015high}.
            \end{itemize}
            \item \underline{Adapting to discrete spaces:} various approaches to tackle the problem,
            \begin{itemize}
                \item \underline{Replace/adapt surrogate model} with random forests or another suitable model \cite{hutter2013evaluation}.
                \item \underline{Introduce smoothness}, attempting to coerce discrete spaces into continous spaces \cite{oh2019combinatorial}.
                \item \underline{Feature engineering}, through feature expansion of discrete with continous variables \cite{daxberger2019mixed}.
            \end{itemize}
            \item \underline{Scaling to more observations:} two common approaches,
            \begin{itemize}
                \item \underline{Replace surrogate model}, similar to above, with another suitable model \cite{hutter2011sequential}.
                \item \underline{Introduce efficient matrix operations}, such as sparsification of covariance matrix \cite{seeger2003fast}.
            \end{itemize}
        \end{itemize}
        We are also interested in other adjacent directions, such as: improving the robustness of BO methods.
        
        We recently discussed a method via the additive structure assumption \cite{han2020high}, 
        where we facilitate faster model learning by \emph{reducing the model complexity} while retaining the \emph{sample-efficiency} of existing additive methods.
        Specifically, we constrain the underlying additive structure to trees, so we facilitate scalable learning of the structure learning and optimization of the acquisition function.
        We show that our method is competitive on datasets, and the computation can be significantly reduced while maintaining optimization performance.
        \section{Research Proposal}
        Here, we focus our discussion on adapting BO to discrete spaces. 
        Most BO methods are focused on continuous search spaces due to the underlying assumption of using GPs as the prior, 
        which relies on the smoothness defined by a kernel to model uncertainty. 
        Real-world problems can have a mix of both ordinal and categorical variables, presenting the following issues, that BO is suited to solve:
        \begin{enumerate}
            \item black-box objectives for which gradient-based optimizers are not amenable.
            \item expensive evaluation procedures for which methods with low sample efficiency.
            \item noisy and highly non-linear objectives for which simple and exact solutions are inaccurate.
        \end{enumerate}
        There have been attempts to adapt BO to this problem by simply using continuous kernels and augment the result to become discrete. 
        However, some combinations of discrete variables are impossible configurations, and it is difficult for the model to capture.

        \begin{description}[style=unboxed]
            \item [\questionOne{\lang}] 
                % ##########################################
                % # Question 1: What is the problem you want to address in your work? / 
                %               Was ist das Problem, welches Sie in Ihrer Arbeit bearbeiten wollen?
                % ######
                % The goal of this question is to clearly state what your work is about. 
                % What is the problem it is supposed to solve?
                %
                % Answering this question is particular important during the early phases 
                % of your work, in order to gain further insight and understanding about what 
                % your work is going to cover and address.  
                %
                % Answer this question very briefly by stating the problem or research 
                % question that you want to address/solve in your work.
                % 
                % Your answer should: 
                %  - only be 1 sentence (2 sentences max)
                %  - not cover a statement why the topic is relevant 
                %    for the industry (this is address by the next question)
                %  - properly use common terms and buzzwords of IT today (similar to the 
                %    rules for the abstract)
                %
                % Please acknowledge: the answer to this question should not cover why the 
                % problem is important or relevant to anyone (e.g. industry). This will 
                % be addressed with the next question.
                Combinatorial Bayesian Optimization, to extend BO to discrete spaces.
                Our method should also work on mixed spaces, ie. both continuous and discrete spaces.
                % ##########################################

            \item [\questionTwo{\lang}]
                % ##########################################
                % # Question 2: Why is it a problem? / Warum ist es ein Problem?
                % ######
                % The goal of this question is to describe why your work is relevant. 
                % Why should the reader care? Why is this the problem (of question 1)
                % worth investigating?
                %
                % Answering this question is particular important during the early phases 
                % of your work, in order to gain further insight and understanding of the 
                % problem domain you are addressing. Further, it is a good checkpoint to 
                % ensure that you are addressing issues that are not just theoretical but 
                % have real-world applications. 
                %
                % Your answer should: 
                %  - be 3 - 5 sentences 
                %  - give a broader overview of the domain/area where your problem occurs
                %  -- who has this problem?
                %  -- what is the impact of it?
                %  -- which conditions need to be fulfilled for the problem to occur?
                %  -- etc.
                %  - describe the benefit of having the problem resolved
                Optimization in structured domains using BO was raised in \cite{NeurIPS2017};
                BO has sample efficiency and global optimum convergence advantages when compared to other approaches such as evolution or genetic algorithms.
                An application would be deciding on a deep neural network architecture where the parameters may depend on the number of layers \cite{bengio2009learning}.
                There have been attempts to tackle this problem simply using continuous kernels in BO and augment the result to become discrete.
                However, some combinations of discrete variables are impossible configurations that are complex for the model to capture.
                It faces the problem of combinatorial explosion, as instead of modelling the structural dependencies, 
                BO embed the discrete variables into a $\mathbb{R}^d$ box.
                These methods work but heavily rely on discretization.
                % ##########################################

            \item [\questionThree{\lang}]
                % ##########################################
                % # Question 3: What is the solution you developed in your work? / 
                %               Was ist die Lösung die sie entwickelt haben?
                % ######
                % The goal of this question is to describe the results of your work 
                % ans/or solution to the problem of your work.
                % 
                % It is hard/impossible to answer this question in the early phases of 
                % your work, as usually you do not have results, yet. However, you can 
                % already state first ideas that you may have in order to discuss them 
                % with your supervisor. 
                %
                % Your answer should:
                %  - clearly state all results of your work, that are relevant to your 
                %    research problem. 
                %  - not oversell your results, stick you what you actually have 
                %    accomplished"
                %  - give credit where credit is due. If you created your results based 
                %    on the work of others, give them the credit.
                %  - if none of your ideas did not produce any usable solution, state 
                %    so - these attempts are also results! By documenting them, it may 
                %    prevent others from trying them as well. 
                We focus on the important considerations of: allowing information sharing via encoding relationships between the variables (both ordinal and categorical),
                efficiently optimize the discrete variables (selection of the next discrete values) with high sample and computational efficiency,
                encode the constraints between the variables, allowing the model to exploit them. 
                We extend COMBO \cite{oh2019combinatorial}, where GP surrogate model is defined over the graph using Graph Fourier Transform (GFT).
                Instead of using an ordered sub-graph for every continuous variable, we do not discretize, considering the continuous variables outside of the graph structure.
                It might be possible to define a kernel grammar over continuous and discrete variables by treating them separately. 
                % ##########################################

            \item [\questionFour{\lang}]
                % ##########################################
                % # Question 4: Why is it a solution? / Warum ist es eine Lösung?
                % ######
                % The goal of this question is to describe who you developed your results 
                % and what the quality of them are.
                % 
                % Your answer should:
                %  - short and to the point
                %  - clearly state how you developed your results
                %  -- what is the chain of reasoning that led to your results/solution
                %  -- what statistics, literature, studies, or other literature did you 
                %     base your assumptions on?
                %  - clearly state the quality and applicability of your results
                %  -- reflect your work objectively - there is no perfection in this 
                %     world, so your work is not perfect as well. Be aware of that!
                %  -- how did you ensure that your results are accurate? did you:
                %  --- perform experiments? 
                %  --- apply any logical deductions?
                %  --- mathematical proofs? 
                %  --- implement a "proof of concept" implementation and evaluate? 
                %  --- etc.
                %  - clearly state the shortcomings of your work
                %  -- be hones and objective about your own work. 
                %  -- In which cases/scenarios are your results applicable?
                COMBO uses hamming distance on both continuous and discrete variables, which works well on discrete variables.
                Hamming distance is an unnatural metric on continuous spaces, which should be instead modelled using a continuous distribution.
                There might be some penalty associated with GFT, such as performance issues, which might need to be addressed.
                % ##########################################
        \end{description}
        
        \sectionSource{\lang}
        \sectionSourceDescription{\lang}

        % ##########################################
        % # Overview of identified relevant work
        % ######
        % The goal of this section is to provide an overview of the relevant and significant 
        % related work identified so far. Make sure that your cited sources are of appropriate
        % quality!
        % 
        % Please include:
        %  - a citation of the source using Latex facilities (incl. a generated list of 
        %    references)
        %  - a brief descriptions of the source and a statement why this is relevant for 
        %    your work (1-2 sentences)
        % 
        \begin{description}
            \item[\cite{pmlr-v124-swersky20a}] Use generative model to generate candidates for acquisition optimization. Implementation at \url{https://github.com/google-research/google-research/tree/master/amortized_bo}.
            \item[\cite{daxberger2019mixed}] Decouples the continuous and discrete components of the function using feature expansion. No implementation published.
            \item[\cite{oh2019combinatorial}] Use a combinatorial graph to quantify smoothness on combinatorial search spaces. Implementation at \url{https://github.com/QUVA-Lab/COMBO}.
            \item[\cite{baptista2018bayesian}] Uses second order regression modelling of the interactions. Implementation at \url{https://github.com/baptistar/BOCS}.
            \item[\cite{pmlr-v70-jenatton17a}] Use a surrogate tree model where GPs are at the leafs. No implementation published.
        \end{description}
        Other related methods:
        \begin{enumerate}
            \item Traditional methods; generally not sample efficient and may not converge to global optimum (although sometimes, convergence is guaranteed).
            \begin{enumerate}
                \item Local search methods such as random optimization, hill climbing, simulated annealing, etc.
                \item Evolutionary algorithms.
            \end{enumerate}
            \item Related BO methods; generally unable to handle general constraints over the discrete variables.
            \begin{enumerate}
                \item SMAC \cite{hutter2011sequential} is a BO that uses random forests as a surrogate model, which accommodates mixed variable inputs. However, there are limitations as the frequentist uncertainty estimate provided by random forests may suffer from variance degradation.
                \item TPE \cite{bergstra2013making} uses a non-parametric kernel density estimator to identify inputs, likely to improve upon and unlikely to perform worse than the best input found so far.
            \end{enumerate}
            \item Hyperband \cite{li2017hyperband} is a variant of random search that exploits cheap but less accurate approximations of the objective to allocate resources for function evaluations dynamically.
            \item BOHB \cite{falkner2018bohb} is the model-based counterpart of Hyperband, based on TPE.
            \item Arc-Kernel \cite{swersky2014raiders} is a kernel designed to encode information about which parameters are relevant in a given structure. 
        \end{enumerate}
        % ##########################################
      \section*{Acknowledgements}
      We adapted this research template from \cite{Stefan2018}.
      This work is done in collaboration with my PhD supervisor, Prof. Scarlett Jonathan. 
      His patience and guidance are greatly appreciated, without which the research would not be possible; 
      to family and friends who are of great support.
      \newpage
      \printbibliography
    \end{document}