PATENT ABSTRACT
A simple yet powerful Bayesian model of linear regression is disclosed for methods and systems of machine learning. Unlike previous treatments that have either considered finding hyperparameters through maximum likelihood or have used a simple prior that makes the computation tractable but can lead to overfitting in high dimensions, the disclosed methods use a combination of linear algebra and numerical integration to work a full posterior over hyperparameters in a model with a prior that naturally avoids overfitting. The resulting algorithm is efficient enough to be practically useful. The approach can be viewed as a fully Bayesian version of the discriminative regularized least squares algorithm.

PATENT DESCRIPTION
CROSS-REFERENCE TO RELATED APPLICATION(S) 
       [0001]    This application claims priority under 35 U.S.C. § 119(e) to U.S. Provisional Patent Application No. 60/866,399 filed Nov. 17, 2006, which is hereby incorporated by reference in its entirety. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    This invention pertains in general to machine learning, and in particular to a Bayesian model of linear regression. 
         [0004]    2. Description of the Related Art 
         [0005]    Linear regression is a simple yet powerful approach to learning from data. The simplest algorithm for regression is ordinary least squares (OLS), which yields a hyperplane that minimizes the squared error between predictions and labels on a training set. In high dimensions with few examples, ordinary least squares can overfit badly, and needs to be regularized to produce sensible solutions. Additionally, it is often desirable to work in a Bayesian setting in order to produce confidence estimates and incorporate prior knowledge in our predictions. 
         [0006]    In general, the Bayesian machine learning community frequently makes use of analytic Gaussian integrals, approximations such as using maximum likelihood to approximate a posterior with its maximum value, and Markov Chain Monte Carlo sampling, but does not make much use of modern tools for direct numerical low-dimensional integrations. 
       SUMMARY 
       [0007]    Embodiments of the invention provide methods and systems of performing a Bayesian linear regression that includes regularization, where arbitrary priors are placed over both the scale of the linear function and the noise level. Through a combination of analytic Gaussian integration, singular value decomposition, and numerical integration over the hyperparameters, we can evaluate the posterior directly, without making approximations such as maximum likelihood or Monte Carlo sampling from the hyperparameters. 
         [0008]    According to one aspect of the invention, the method starts with vague priors over the hyperparameters, and the data automatically cause the posterior to be well-concentrated around excellent regression results. In particular, the ratio of the noise and scale parameters act as a regularizer, and this ratio concentrates around values that a non-Bayesian regularized least-squares algorithm automatically selects via leave-one-out cross validation. 
         [0009]    Another embodiment of the present invention provides a machine-readable medium (e.g., one or more compact disks, diskettes, servers, memory sticks, or hard drives) encoded with instructions, that when executed by one or more processors, cause the processor to carry out a process for Bayesian linear regression. This process can be, for example, similar to or a variation of the previously described method. 
         [0010]    Another embodiment of the present invention provides a Bayesian linear regression system. The system functionality (e.g., such as that of the previously described method or a variation thereof) can be implemented with a number of means, such as software (e.g., executable instructions encoded on one or more computer-readable mediums), hardware (e.g., gate level logic or one or more ASICs), firmware (e.g., one or more microcontrollers with I/O capability and embedded routines for carrying out the functionality described herein), or some combination thereof. In one particular case, the system is implemented in a computing environment such as a desktop or laptop computer, with an executable Bayesian Linear Regression module or set of modules stored therein. 
         [0011]    Embodiments of the invention are particularly well-suited to machine learning situations with many variables relative to the number of examples. The resulting model is efficient enough to be practically useful, and it avoids overfitting in high dimensions. 
         [0012]    The features and advantages described in this summary and the following detailed description are not all-inclusive. Many additional features and advantages will be apparent to one of ordinary skill in the art in view of the drawings, detailed description, and claims. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0013]      FIG. 1  is a block diagram illustrating a computing environment configured in accordance with an embodiment of the present invention. 
           [0014]      FIG. 2  is a flowchart illustrating a method of predicting data points and confidence intervals in accordance with an embodiment of the present invention. 
           [0015]      FIG. 3  shows the average mean-square error of ordinary least squares, regularized least squares, and the Bayesian linear regression model in accordance with one embodiment, averaged over 50 replications, and a one standard deviation interval on each side of the average. 
           [0016]      FIG. 4A  shows the prior distribution for noise parameter σ 2  and scale parameter λ 2 , in accordance with one embodiment. 
           [0017]      FIG. 4B  shows the posterior distribution after training with 16 points, in accordance with one embodiment. 
           [0018]      FIG. 4C  shows the posterior distribution after training with 128 points, in accordance with one embodiment. 
           [0019]      FIG. 4D  shows the posterior distribution after training with 1024 points, in accordance with one embodiment. 
           [0020]      FIG. 5A  is a graph of the prior and posterior distributions of the ratio of noise and scale parameters σ 2 /λ 2  for a training set size of 16, in accordance with one embodiment. 
           [0021]      FIG. 5B  is a graph of the leave-one-out errors resulting from the use of various λ RLS  with a training set size of 16, in accordance with one embodiment. 
           [0022]      FIG. 5C  is a graph of the prior and posterior distributions of the ratio of noise and scale parameters σ 2 /λ 2  for a training set size of 64, in accordance with one embodiment. 
           [0023]      FIG. 5D  is a graph of the leave-one-out errors resulting from the use of various λ RLS  with a training set size of 64, in accordance with one embodiment. 
           [0024]      FIG. 5E  is a graph of the prior and posterior distributions of the ratio of noise and scale parameters σ 2 /λ 2  for a training set size of 256, in accordance with one embodiment. 
           [0025]      FIG. 5F  is a graph of the leave-one-out errors resulting from the use of various λ RLS  with a training set size of 256, in accordance with one embodiment. 
           [0026]      FIG. 5G  is a graph of the prior and posterior distributions of the ratio of noise and scale parameters σ 2 /λ 2  for a training set size of 1024, in accordance with one embodiment. 
           [0027]      FIG. 5H  is a graph of the leave-one-out errors resulting from the use of various λ RLS  with a training set size of 1024, in accordance with one embodiment. 
       
    
    
       [0028]    The figures depict embodiments of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following discussion that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein. 
       DETAILED DESCRIPTION OF THE EMBODIMENTS  
       [0029]    In Section 1, a system overview is presented of the computing environment configured in accordance with an embodiment of the invention. In Section 2, a methodology is presented for the use of a Bayesian linear regression model. In Section 3, some mathematical preliminaries are briefly discussed. Section 4 introduces a model in accordance with one embodiment of the invention. Section 5 discusses the analytic derivations, and provides the pieces of the model that can be evaluated analytically. Section 6 demonstrates how to evaluate the remaining parts computationally. Section 7 compares the described model to related work in the field. Section 8 describes a computational experiment illustrating the properties of the model and method in accordance with one embodiment. 
       1. System Overview 
       [0030]      FIG. 1  is a block diagram illustrating a computing environment  10  configured in accordance with an embodiment of the present invention. 
         [0031]    As can be seen with this example, the computing environment  10  includes a processor  101  operatively coupled via a bus  119  to a memory  107 , a storage device  103  for storing an Bayesian Linear Regression (BLR) module  105  (and other executable code, such as an operating system and applications), a keyboard  113 , a graphics adapter  109 , a pointing device  117 , and a network adapter  115 . A display  111  is operatively coupled to the graphics adapter  109 . 
         [0032]    The processor  101  may be any processor or set of processors capable of executing various operating systems (e.g., UNIX) and applications/drivers (e.g., MATLAB) of the computing environment  10 . Numerous suitable processors can be used, as will be apparent in light of this disclosure. The memory  107  may be, for example, firmware ROM, RAM, and/or flash memory, and holds instructions and data used by the processor  101 . The storage device  103  is a hard disk drive in one embodiment, but can also be any other device capable of persistently storing data, such as a memory stick and/or a solid-state memory device. The storage device  103  can hold multiple files containing executable code and/or data, as is typically done. The computing environment  10  operates to load an executable file into memory  107  and execute it using the processor  101 . In the embodiment shown, the Bayesian Linear Regression module  105  is stored in storage device  103  as executable code, and is loaded into memory  107  for execution by the processor  101  as one or more processes. 
         [0033]    The files stored on the storage device  103  can be, for example, in the MATLAB format (sometimes referred to as M-files). Other file formats may also be stored on storage device  103  in any file types necessary for the computing environment to properly operate. Such files are typical of computing environments that employ Microsoft operating systems. Other file formats, such as those utilized by Apple Macintosh and UNIX based computers will be apparent in light of this disclosure. 
         [0034]    The pointing device  117  may be a mouse, track ball, or other such user input device, and is used in combination with the keyboard  113  to allow the user to interact with the computing environment  10  (e.g. input data and respond to prompts), as is typically done. The graphics adapter  109  displays images and other information on the display  111 . The network adapter  115  communicatively couples the computing environment  10  with an external network such as the Internet or LAN, or combination thereof (e.g., via conventional wired or wireless technology), if so desired and as is typically done. 
         [0035]    The computing environment  10  is adapted to execute computer program modules for performing Bayesian linear regression, including the BLR module  105 . Structure and functionality of the BLR module  105  will be discussed in further detail with reference to  FIGS. 2 through 5H . As will be apparent in light of this disclosure, the computing environment  10  can be implemented via processing systems such as a general purpose desktop or laptop computer, or a special-purpose processing system configured to carryout the Bayesian linear regression as described herein. Other computationally intensive processes can be limited as needed to reserve processing power for Bayesian linear regression processing as discussed herein, although a standard user desktop environment can also be running. 
       2. Methodology 
       [0036]    In the following sections, the derivation of the Bayesian linear regression model used within the BLR module  105  will be described.  FIG. 2  is a flowchart illustrating a method of predicting data points and confidence intervals in accordance with an embodiment of the present invention. 
         [0037]    According to one embodiment, the method begins with receiving a training set of data  201  within the BLR module  105 . This data is used to train a BLR model for use in a given application. Applications include but are not limited to face recognition, handwriting recognition, voice recognition, speech recognition, pose recognition, motion detection, gesture recognition, and image recognition, and other machine learning tasks. For example, in the application of handwriting recognition, the training set of data may include a variety of samples of handwritten letters and numbers. In some cases, there may be few training data points, but in other cases, there may be many training data points. The training points may be low dimensional or high dimensional, depending on the application. 
         [0038]    In step  202 , the BLR model is built  202 . The formation as well as the function and benefits of the BLR model are described in greater detail below in the following sections. Generally, independent scaled priors are placed on a scale parameter and a noise parameter  203 . The hyperhyperparamters that control the scaled priors on the scale parameter and noise parameter are determined  204 . Formulas are derived for p(y|σ 2 , λ 2 ) and p(y*, y|σ 2 , λ 2 ) in step  205 . In step  206 , the scale parameter and noise parameter are determined through singular value decomposition and adaptive numerical integration, as described in detail in section 6. 
         [0039]    After the BLR module  105  has been trained, the BLR module applies the BLR model to predict future data points  207 . In step  208 , the confidence intervals on the predicted data points are computed. Because the BLR model is fully Bayesian, the confidence intervals on the outputs can be obtained in a principled way, without the errors introduced by other methods. 
         [0040]    Then, the predicted data points and confidence intervals can be output  209 . For example, the predicted data points and confidence intervals can be output to display  111  for a user to view, or the predicted data points and confidence intervals can be output to a storage device  103 , or to another storage device coupled to the computing environment  10 , such as through network adapter  115 . 
       3. Mathematical Preliminaries 
       [0041]    In this section, some mathematical preliminaries will be described. We are given n labeled training points in d dimensions. The data matrix X is n by d; its ith row is x i  (a row vector). The training labels are given by y (an n-dimensional column vector). We frequently discuss making a new “test” point (x*×y*). We treat X as fixed and do not place a generative model over it, and we omit X (and x*) from conditioning formulas. We will frequently refer (when discussing computational complexity) to k=min{n, d} and  k =max {n,d}. 
         [0042]    We review the following well-known Gaussian integrals. For a one-dimensional y, 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∫ 
                       l 
                       h 
                     
                      
                     
                       
                         exp 
                          
                         
                           ( 
                           
                             
                               - 
                               
                                 1 
                                 2 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   ay 
                                   2 
                                 
                                 + 
                                 
                                   2 
                                    
                                   by 
                                 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                        
                       
                          
                         y 
                       
                     
                   
                   = 
                     
                    
                   
                     
                       ∫ 
                       l 
                       h 
                     
                      
                     
                       
                         exp 
                          
                         
                           ( 
                           
                             
                               - 
                               
                                 1 
                                 2 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   
                                     a 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         + 
                                         
                                           
                                             a 
                                             
                                               - 
                                               1 
                                             
                                           
                                            
                                           b 
                                         
                                       
                                       ) 
                                     
                                   
                                   2 
                                 
                                 - 
                                 
                                   
                                     a 
                                     
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                     b 
                                     2 
                                   
                                 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                        
                       
                          
                         y 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       exp 
                       ( 
                       
                         
                           b 
                           2 
                         
                         
                           2 
                            
                           a 
                         
                       
                       ) 
                     
                      
                     
                       
                         ∫ 
                         l 
                         h 
                       
                        
                       
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 - 
                                 
                                   1 
                                   2 
                                 
                               
                                
                               
                                 
                                   a 
                                    
                                   
                                     ( 
                                     
                                       y 
                                       + 
                                       
                                         
                                           a 
                                           
                                             - 
                                             1 
                                           
                                         
                                          
                                         b 
                                       
                                     
                                     ) 
                                   
                                 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                            
                           y 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       exp 
                       ( 
                       
                         
                           b 
                           2 
                         
                         
                           2 
                            
                           a 
                         
                       
                       ) 
                     
                      
                     
                       
                         2 
                         a 
                       
                     
                      
                     
                       
                         ∫ 
                         
                           
                             
                               a 
                               2 
                             
                           
                            
                           
                             ( 
                             
                               l 
                               + 
                               
                                 
                                   a 
                                   
                                     - 
                                     1 
                                   
                                 
                                  
                                 b 
                               
                             
                             ) 
                           
                         
                         
                           
                             
                               a 
                               2 
                             
                           
                            
                           
                             ( 
                             
                                 
                             
                              
                             
                               h 
                               + 
                               
                                 
                                   a 
                                   
                                     - 
                                     1 
                                   
                                 
                                  
                                 b 
                               
                             
                             ) 
                           
                         
                       
                        
                       
                         
                           exp 
                            
                           
                             ( 
                             
                               - 
                               
                                 u 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                            
                           u 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       exp 
                       ( 
                       
                         
                           b 
                           2 
                         
                         
                           2 
                            
                           a 
                         
                       
                       ) 
                     
                      
                     
                       
                         
                           2 
                            
                           π 
                         
                         a 
                       
                     
                      
                     
                       ( 
                       
                         
                           
                             1 
                             2 
                           
                            
                           
                             erf 
                             ( 
                             
                               
                                 
                                   a 
                                   2 
                                 
                               
                                
                               
                                 ( 
                                 
                                   h 
                                   + 
                                   
                                     
                                       a 
                                       
                                         - 
                                         1 
                                       
                                     
                                      
                                     b 
                                   
                                 
                                 ) 
                               
                             
                             ) 
                           
                         
                         - 
                       
                     
                   
                 
               
             
             
               
                 
                     
                    
                   
                     
                       1 
                       2 
                     
                      
                     
                       erf 
                       ( 
                       
                         
                           
                             a 
                             2 
                           
                         
                          
                         
                           ( 
                           
                             l 
                             + 
                             
                               
                                 a 
                                 
                                   - 
                                   1 
                                 
                               
                                
                               b 
                             
                           
                           ) 
                         
                       
                       ) 
                     
                   
                   ) 
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         
                           
                             2 
                              
                             π 
                           
                           a 
                         
                       
                        
                       
                         exp 
                         ( 
                         
                           
                             b 
                             2 
                           
                           
                             2 
                              
                             a 
                           
                         
                         ) 
                       
                        
                       
                         1 
                         2 
                       
                        
                       
                         erf 
                          
                         
                           ( 
                           
                             
                               
                                 a 
                                 2 
                               
                             
                              
                             
                               ( 
                               
                                 u 
                                 + 
                                 
                                   
                                     a 
                                     
                                       - 
                                       1 
                                     
                                   
                                    
                                   b 
                                 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                     
                      
                     
                       | 
                       
                         u 
                         = 
                         l 
                       
                       
                         u 
                         = 
                         h 
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    For a d-dimensional w, 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∫ 
                       
                         ℝ 
                         d 
                       
                     
                      
                     
                       
                         exp 
                          
                         
                           ( 
                           
                             
                               - 
                               
                                 1 
                                 2 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   
                                     w 
                                     t 
                                   
                                    
                                   Aw 
                                 
                                 + 
                                 
                                   2 
                                    
                                   
                                     b 
                                     t 
                                   
                                    
                                   w 
                                 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                        
                       
                          
                         w 
                       
                     
                   
                   = 
                     
                    
                   
                     
                       ∫ 
                       
                         ℝ 
                         d 
                       
                     
                      
                     
                       exp 
                        
                       
                         ( 
                         
                           
                             - 
                             
                               1 
                               2 
                             
                           
                            
                           
                             ( 
                             
                               
                                 
                                    
                                   
                                     w 
                                     + 
                                     
                                       
                                         A 
                                         
                                           - 
                                           1 
                                         
                                       
                                        
                                       b 
                                     
                                   
                                    
                                 
                                 A 
                                 2 
                               
                               - 
                               
                                 
                                   b 
                                   t 
                                 
                                  
                                 
                                   A 
                                   
                                     - 
                                     1 
                                   
                                 
                                  
                                 b 
                               
                             
                             ) 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         ( 
                         
                           2 
                            
                           π 
                         
                         ) 
                       
                       
                         d 
                         2 
                       
                     
                      
                     
                       
                          
                         A 
                          
                       
                       
                         - 
                         
                           1 
                           2 
                         
                       
                     
                      
                     
                       
                         exp 
                          
                         
                           ( 
                           
                             
                               1 
                               2 
                             
                              
                             
                               b 
                               t 
                             
                              
                             
                               A 
                               
                                 - 
                                 1 
                               
                             
                              
                             b 
                           
                           ) 
                         
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
       4. Bayesian Linear Regression Model 
       [0043]    In this section, we describe the formation of a Bayesian linear regression model that can reside in the BLR module  105 , and can be used, for example, to predict data points and associated confidence intervals according to the method of  FIG. 2 . We consider a linear regression model for data points x i ∈           1×d  with labels y i ∈          We hypothesize a hyperplane w∈           d×1  with an isotropic Gaussian prior: 
         [0000]    
       
         
           
             
               p 
                
               
                 ( 
                 
                   w 
                   | 
                   
                     λ 
                     2 
                   
                 
                 ) 
               
             
             = 
             
               
                 
                   ( 
                   
                     2 
                      
                     
                       πλ 
                       2 
                     
                   
                   ) 
                 
                 
                   
                     - 
                     d 
                   
                   / 
                   2 
                 
               
                
               
                 exp 
                 ( 
                 
                   - 
                   
                     
                       
                          
                         w 
                          
                       
                       2 
                     
                     
                       2 
                        
                       
                         λ 
                         2 
                       
                     
                   
                 
                 ) 
               
             
           
         
       
     
         [0000]    Additionally, there is Gaussian noise in the output value (y i =x i w+N(0, σ 2 )): 
         [0000]    
       
         
           
             
               p 
                
               
                 ( 
                 
                   
                     
                       y 
                       i 
                     
                     | 
                     w 
                   
                   , 
                   
                     σ 
                     2 
                   
                 
                 ) 
               
             
             = 
             
               
                 
                   ( 
                   
                     2 
                      
                     
                       πσ 
                       2 
                     
                   
                   ) 
                 
                 
                   - 
                   
                     1 
                     2 
                   
                 
               
                
               
                 exp 
                 ( 
                 
                   - 
                   
                     
                       
                         ( 
                         
                           
                             y 
                             i 
                           
                           - 
                           
                             
                               x 
                               i 
                             
                              
                             w 
                           
                         
                         ) 
                       
                       2 
                     
                     
                       2 
                        
                       
                         σ 
                         2 
                       
                     
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         
                           y 
                           | 
                           w 
                         
                         , 
                         
                           σ 
                           2 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         1 
                       
                       n 
                     
                      
                     
                       p 
                        
                       
                         ( 
                         
                           
                             
                               y 
                               i 
                             
                             | 
                             w 
                           
                           , 
                           
                             σ 
                             2 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       
                         ( 
                         
                           2 
                            
                           
                             πσ 
                             2 
                           
                         
                         ) 
                       
                       
                         
                           - 
                           n 
                         
                         / 
                         2 
                       
                     
                      
                     
                       
                         exp 
                         ( 
                         
                           - 
                           
                             
                               
                                  
                                 
                                   y 
                                   - 
                                   Xw 
                                 
                                  
                               
                               2 
                             
                             
                               2 
                                
                               
                                 σ 
                                 2 
                               
                             
                           
                         
                         ) 
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
         [0044]    So far, this approach is similar to the treatment present in Rasmussen and Williams.  Gaussian Processes for Machine Learning.  MIT Press, 2006, (Section 2.1.1). When the hyperparameters are known constants, the posterior distribution of w is Gaussian. In our approach, we place independent scaled inverse—χ 2  priors on the scale parameter λ 2  and noise parameter σ 2 : 
         [0000]    
       
         
           
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         λ 
                         2 
                       
                       ) 
                     
                   
                   = 
                     
                    
                   
                     
                       
                         
                           ( 
                           
                             
                               v 
                               λ 
                             
                             / 
                             2 
                           
                           ) 
                         
                         
                           
                             v 
                             λ 
                           
                           / 
                           2 
                         
                       
                       
                         Γ 
                          
                         
                           ( 
                           
                             
                               v 
                               λ 
                             
                             / 
                             2 
                           
                           ) 
                         
                       
                     
                      
                     
                       
                         
                           λ 
                           0 
                           
                             v 
                             λ 
                           
                         
                          
                         
                           ( 
                           
                             λ 
                             2 
                           
                           ) 
                         
                       
                       
                         - 
                         
                           ( 
                           
                             
                               
                                 v 
                                 λ 
                               
                               / 
                               2 
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                      
                     
                       exp 
                       ( 
                       
                         - 
                         
                           
                             
                               v 
                               λ 
                             
                              
                             
                               λ 
                               0 
                               2 
                             
                           
                           
                             2 
                              
                             
                               λ 
                               2 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         σ 
                         2 
                       
                       ) 
                     
                   
                   = 
                     
                    
                   
                     
                       
                         
                           ( 
                           
                             
                               v 
                               σ 
                             
                             / 
                             2 
                           
                           ) 
                         
                         
                           
                             v 
                             σ 
                           
                           / 
                           2 
                         
                       
                       
                         Γ 
                          
                         
                           ( 
                           
                             
                               v 
                               σ 
                             
                             / 
                             2 
                           
                           ) 
                         
                       
                     
                      
                     
                       
                         
                           σ 
                           0 
                           
                             v 
                             σ 
                           
                         
                          
                         
                           ( 
                           
                             σ 
                             2 
                           
                           ) 
                         
                       
                       
                         - 
                         
                           ( 
                           
                             
                               
                                 v 
                                 σ 
                               
                               / 
                               2 
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                      
                     
                       exp 
                       ( 
                       
                         - 
                         
                           
                             
                               v 
                               σ 
                             
                              
                             
                               σ 
                               0 
                               2 
                             
                           
                           
                             2 
                              
                             
                               σ 
                               2 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         
                           σ 
                           2 
                         
                         , 
                         
                           λ 
                           2 
                         
                       
                       ) 
                     
                   
                   = 
                     
                    
                   
                     
                       p 
                        
                       
                         ( 
                         
                           σ 
                           2 
                         
                         ) 
                       
                     
                      
                     
                       
                         p 
                          
                         
                           ( 
                           
                             λ 
                             2 
                           
                           ) 
                         
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
         [0045]    The joint probability is p(y, w, σ 2 , λ 2 )=p(y|w, σ 2 )p(w|λ 2 )p(σ 2 )p(λ 2 ). When we want to make a prediction at a new data point x*, the joint becomes 
         [0000]        p ( y*, y, w, σ   2 , λ 2 )= p ( y*|w, σ   2 ) p ( y|w, σ   2 ) p ( w|λ   2 ) p (σ 2 ) p (λ 2 ) 
         [0046]    We are interested in the posterior distribution of the scale parameters and the posterior distribution of the output at a new test point x*: 
         [0000]    
       
         
           
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         
                           σ 
                           2 
                         
                         , 
                         
                           
                             λ 
                             2 
                           
                           | 
                           y 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       p 
                        
                       
                         ( 
                         
                           
                             σ 
                             2 
                           
                           , 
                           
                             λ 
                             2 
                           
                           , 
                           y 
                         
                         ) 
                       
                     
                     
                       p 
                        
                       
                         ( 
                         y 
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       1 
                       
                         p 
                          
                         
                           ( 
                           y 
                           ) 
                         
                       
                     
                      
                     
                       ∫ 
                       
                         
                           p 
                            
                           
                             ( 
                             
                               y 
                               , 
                               w 
                               , 
                               
                                 σ 
                                 2 
                               
                               , 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                            
                           w 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       
                         p 
                          
                         
                           ( 
                           
                             
                               σ 
                               2 
                             
                             , 
                             
                               λ 
                               2 
                             
                           
                           ) 
                         
                       
                       
                         p 
                          
                         
                           ( 
                           y 
                           ) 
                         
                       
                     
                      
                     
                       ∫ 
                       
                         
                           p 
                            
                           
                             ( 
                             
                               
                                 y 
                                 | 
                                 w 
                               
                               , 
                               
                                 σ 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                           p 
                            
                           
                             ( 
                             
                               w 
                               | 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                            
                           w 
                         
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         
                           y 
                           * 
                         
                         | 
                         y 
                       
                       ) 
                     
                   
                   = 
                     
                    
                   
                     
                       1 
                       
                         p 
                          
                         
                           ( 
                           y 
                           ) 
                         
                       
                     
                      
                     
                       ∫ 
                       
                         
                           ( 
                           
                             ∫ 
                             
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       * 
                                     
                                     , 
                                     y 
                                     , 
                                     w 
                                     , 
                                     
                                       σ 
                                       2 
                                     
                                     , 
                                     
                                       λ 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                  
                                 w 
                               
                             
                           
                           ) 
                         
                          
                         
                            
                           
                             σ 
                             2 
                           
                         
                          
                         
                            
                           
                             λ 
                             2 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       1 
                       
                         p 
                          
                         
                           ( 
                           y 
                           ) 
                         
                       
                     
                      
                     
                       ∫ 
                       
                         
                           p 
                            
                           
                             ( 
                             
                               
                                 σ 
                                 2 
                               
                               , 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                           ( 
                           
                             ∫ 
                             
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     
                                       
                                         y 
                                         * 
                                       
                                       | 
                                       w 
                                     
                                     , 
                                     
                                       σ 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       | 
                                       w 
                                     
                                     , 
                                     
                                       σ 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                   
                     
                         
                        
                       
                         p 
                          
                         
                           ( 
                           
                             w 
                             | 
                             
                               λ 
                               2 
                             
                           
                           ) 
                         
                          
                         
                            
                           w 
                         
                       
                       ) 
                     
                      
                     
                        
                       
                         σ 
                         2 
                       
                     
                      
                     
                        
                       
                         λ 
                         2 
                       
                     
                   
                   , 
                 
               
             
           
         
       
     
         [0000]    where the parentheses indicate the order of integration for tractability (integrals whose limits are not given go from −∞ to ∞ in the dimensions of w and from 0 to ∞ for σ 2  and λ 2 ). The normalizer in both cases is: 
         [0000]    
       
         
           
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       y 
                       ) 
                     
                   
                   = 
                   
                     ∫ 
                     
                       
                         p 
                          
                         
                           ( 
                           
                             y 
                             , 
                             w 
                             , 
                             
                               σ 
                               2 
                             
                             , 
                             
                               λ 
                               2 
                             
                           
                           ) 
                         
                       
                        
                       
                          
                         w 
                       
                        
                       
                          
                         
                           σ 
                           2 
                         
                       
                        
                       
                          
                         
                           λ 
                           2 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     ∫ 
                     
                       
                         ( 
                         
                           ∫ 
                           
                             
                               p 
                                
                               
                                 ( 
                                 
                                   y 
                                   , 
                                   w 
                                   , 
                                   
                                     σ 
                                     2 
                                   
                                   , 
                                   
                                     λ 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                                
                               w 
                             
                           
                         
                         ) 
                       
                        
                       
                          
                         
                           σ 
                           2 
                         
                       
                        
                       
                          
                         
                           λ 
                           2 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     ∫ 
                     
                       
                         p 
                          
                         
                           ( 
                           
                             
                               σ 
                               2 
                             
                             , 
                             
                               λ 
                               2 
                             
                           
                           ) 
                         
                       
                        
                       
                         ( 
                         
                           ∫ 
                           
                             
                               p 
                                
                               
                                 ( 
                                 
                                   
                                     y 
                                     | 
                                     w 
                                   
                                   , 
                                   
                                     σ 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                               p 
                                
                               
                                 ( 
                                 
                                   w 
                                   | 
                                   
                                     λ 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                                
                               w 
                             
                           
                         
                         ) 
                       
                        
                       
                          
                         
                           σ 
                           2 
                         
                       
                        
                       
                         
                            
                           
                             λ 
                             2 
                           
                         
                         . 
                       
                     
                   
                 
               
             
           
         
       
     
         [0047]    The scaled inverse—χ 2  priors on σ 2  and λ 2  are controlled by hyperhyperparameters v σ , σ 0   2 , v 80  and λ 0   2 . The prior for σ 0   2  has mean and variance as given by Gelman, Carlin, Stem, and Rubin,  Bayesian Data Analysis,  Chapman &amp; Hall/CRC, second edition, 2004: 
         [0000]    
       
         
           
             
               E 
                
               
                 ( 
                 
                   σ 
                   2 
                 
                 ) 
               
             
             = 
             
               
                 
                   v 
                   σ 
                 
                 
                   
                     v 
                     σ 
                   
                   - 
                   2 
                 
               
                
               
                 σ 
                 0 
                 2 
               
             
           
         
       
       
         
           
             
               var 
                
               
                 ( 
                 
                   σ 
                   2 
                 
                 ) 
               
             
             = 
             
               
                 
                   2 
                    
                   
                     v 
                     σ 
                     2 
                   
                 
                 
                   
                     
                       ( 
                       
                         
                           v 
                           σ 
                         
                         - 
                         2 
                       
                       ) 
                     
                     2 
                   
                    
                   
                     ( 
                     
                       
                         v 
                         σ 
                       
                       - 
                       4 
                     
                     ) 
                   
                 
               
                
               
                 
                   σ 
                   0 
                   4 
                 
                 . 
               
             
           
         
       
     
         [0000]    Rather than work with v σ  and σ 0   2  directly, we invert these formulas to specify our hyperhyperparameters in terms of the desired mean and variance: 
         [0000]    
       
         
           
             
               v 
               σ 
             
             = 
             
               2 
                
               
                 ( 
                 
                   
                     
                       
                         E 
                          
                         
                           ( 
                           
                             σ 
                             2 
                           
                           ) 
                         
                       
                       2 
                     
                     
                       var 
                        
                       
                         ( 
                         
                           σ 
                           2 
                         
                         ) 
                       
                     
                   
                   + 
                   2 
                 
                 ) 
               
             
           
         
       
       
         
           
             
               σ 
               0 
               2 
             
             = 
             
               2 
                
               
                 E 
                  
                 
                   ( 
                   
                     σ 
                     2 
                   
                   ) 
                 
               
                
               
                 
                   
                     
                       v 
                       σ 
                     
                     / 
                     2 
                   
                   - 
                   1 
                 
                 
                   v 
                   σ 
                 
               
             
           
         
       
     
         [0048]    A precisely analogous situation holds for λ 2 . We set E(σ 2 )=var(y) and E(λ 2 ) to be the average variance (across the dimensions) of X, and set the variances to be c times the respective means, for some c. In our experiments, c=100, although the results are highly insensitive to the choice of c. The idea is to set the hyperhyperparameters&#39; expected values to a very rough guess, and keep the variance large enough that we are not relying on the guess being accurate. The data will substantially sharpen the distributions of σ 2  and λ 2 . Because we integrate numerically over σ 2  and λ 2 , the precise functional form of their priors is not critical, and straightforward modifications to the techniques discussed here allow the incorporation of arbitrary prior knowledge about σ 2  and λ 2 . 
       5. Analytic Derivations 
       [0049]    In the following description, we derive formulas for 
         [0000]    p(y|σ 2 , λ 2 ) and p(y*, y|σ 2 , λ 2 ) by marginalizing over w, a Gaussian integration. The posterior distribution and expectation of y* are related to these quantities by 
         [0000]    
       
         
           
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         
                           l 
                           &lt; 
                           
                             y 
                             * 
                           
                           &lt; 
                           h 
                         
                         | 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       p 
                        
                       
                         ( 
                         
                           
                             l 
                             &lt; 
                             
                               y 
                               * 
                             
                             &lt; 
                             h 
                           
                           , 
                           y 
                         
                         ) 
                       
                     
                     
                       p 
                        
                       
                         ( 
                         y 
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       ∫ 
                       
                         
                           p 
                            
                           
                             ( 
                             
                               
                                 σ 
                                 2 
                               
                               , 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                           ( 
                           
                             
                               ∫ 
                               l 
                               h 
                             
                              
                             
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       * 
                                     
                                     , 
                                     
                                       y 
                                       | 
                                       
                                         σ 
                                         2 
                                       
                                     
                                     , 
                                     
                                       λ 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                  
                                 
                                   y 
                                   * 
                                 
                               
                             
                           
                           ) 
                         
                          
                         
                            
                           
                             σ 
                             2 
                           
                         
                          
                         
                            
                           
                             λ 
                             2 
                           
                         
                       
                     
                     
                       ∫ 
                       
                         
                           p 
                            
                           
                             ( 
                             
                               
                                 σ 
                                 2 
                               
                               , 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                           p 
                            
                           
                             ( 
                             
                               
                                 y 
                                 | 
                                 
                                   σ 
                                   2 
                                 
                               
                               , 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                            
                           
                             σ 
                             2 
                           
                         
                          
                         
                            
                           
                             λ 
                             2 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                   
                     E 
                      
                     
                       ( 
                       
                         
                           y 
                           * 
                         
                         | 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∫ 
                       
                         
                           p 
                            
                           
                             ( 
                             
                               
                                 σ 
                                 2 
                               
                               , 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                           ( 
                           
                             ∫ 
                             
                               
                                 y 
                                 * 
                               
                                
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       * 
                                     
                                     , 
                                     
                                       y 
                                       | 
                                       
                                         σ 
                                         2 
                                       
                                     
                                     , 
                                     
                                       λ 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                  
                                 
                                   y 
                                   * 
                                 
                               
                             
                           
                           ) 
                         
                          
                         
                            
                           
                             σ 
                             2 
                           
                         
                          
                         
                            
                           
                             λ 
                             2 
                           
                         
                       
                     
                     
                       ∫ 
                       
                         
                           p 
                            
                           
                             ( 
                             
                               
                                 σ 
                                 2 
                               
                               , 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                           p 
                            
                           
                             ( 
                             
                               
                                 y 
                                 | 
                                 
                                   σ 
                                   2 
                                 
                               
                               , 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                          
                         
                            
                           
                             σ 
                             2 
                           
                         
                          
                         
                            
                           
                             λ 
                             2 
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    The integration over w is a Gaussian integral, analytically tractable, 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           p 
                            
                           
                             ( 
                             
                               
                                 y 
                                 | 
                                 
                                   σ 
                                   2 
                                 
                               
                               , 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                         = 
                           
                          
                         
                           ∫ 
                           
                             
                               p 
                                
                               
                                 ( 
                                 
                                   
                                     y 
                                     | 
                                     w 
                                   
                                   , 
                                   
                                     σ 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                               p 
                                
                               
                                 ( 
                                 
                                   w 
                                   | 
                                   
                                     λ 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                                
                               w 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           ∫ 
                           
                             
                               
                                 ( 
                                 
                                   2 
                                    
                                   
                                     πλ 
                                     2 
                                   
                                 
                                 ) 
                               
                               
                                 
                                   - 
                                   d 
                                 
                                 / 
                                 2 
                               
                             
                              
                             
                               
                                 ( 
                                 
                                   2 
                                    
                                   
                                     πσ 
                                     2 
                                   
                                 
                                 ) 
                               
                               
                                 
                                   - 
                                   n 
                                 
                                 / 
                                 2 
                               
                             
                              
                             
                               exp 
                               ( 
                               
                                 
                                   - 
                                   
                                     
                                       
                                          
                                         
                                           y 
                                           - 
                                           Xw 
                                         
                                          
                                       
                                       2 
                                     
                                     
                                       2 
                                        
                                       
                                         σ 
                                         2 
                                       
                                     
                                   
                                 
                                 - 
                                 
                                   
                                     
                                        
                                       w 
                                        
                                     
                                     2 
                                   
                                   
                                     2 
                                      
                                     
                                       λ 
                                       2 
                                     
                                   
                                 
                               
                               ) 
                             
                              
                             
                                
                               w 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           ∫ 
                           
                             
                               
                                 ( 
                                 
                                   2 
                                    
                                   
                                     πλ 
                                     2 
                                   
                                 
                                 ) 
                               
                               
                                 
                                   - 
                                   d 
                                 
                                 / 
                                 2 
                               
                             
                              
                             
                               
                                 ( 
                                 
                                   2 
                                    
                                   
                                     πσ 
                                     2 
                                   
                                 
                                 ) 
                               
                               
                                 
                                   - 
                                   n 
                                 
                                 / 
                                 2 
                               
                             
                              
                             
                               exp 
                               ( 
                               
                                 
                                   - 
                                   
                                     1 
                                     
                                       2 
                                        
                                       
                                         σ 
                                         2 
                                       
                                     
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       
                                         y 
                                         t 
                                       
                                        
                                       y 
                                     
                                     - 
                                     
                                       2 
                                        
                                       
                                         y 
                                         t 
                                       
                                        
                                       Xw 
                                     
                                     + 
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                               
                              
                             
                               
                                 
                                   w 
                                   t 
                                 
                                 ( 
                                 
                                   
                                     
                                       X 
                                       t 
                                     
                                      
                                     X 
                                   
                                   + 
                                   
                                     
                                       
                                         σ 
                                         2 
                                       
                                       
                                         λ 
                                         2 
                                       
                                     
                                      
                                     I 
                                   
                                 
                                 ) 
                               
                                
                               w 
                             
                             ) 
                           
                           ) 
                         
                          
                         
                            
                           w 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             
                               ( 
                               
                                 2 
                                  
                                 
                                   πλ 
                                   2 
                                 
                               
                               ) 
                             
                             
                               
                                 - 
                                 d 
                               
                               / 
                               2 
                             
                           
                            
                           
                             
                               ( 
                               
                                 2 
                                  
                                 
                                   πσ 
                                   2 
                                 
                               
                               ) 
                             
                             
                               
                                 - 
                                 
                                   ( 
                                   
                                     n 
                                     - 
                                     d 
                                   
                                   ) 
                                 
                               
                               / 
                               2 
                             
                           
                            
                           
                             
                                
                               
                                 
                                   
                                     X 
                                     t 
                                   
                                    
                                   X 
                                 
                                 + 
                                 
                                   
                                     
                                       σ 
                                       2 
                                     
                                     
                                       λ 
                                       2 
                                     
                                   
                                    
                                   I 
                                 
                               
                                
                             
                             
                               - 
                               
                                 1 
                                 2 
                               
                             
                           
                           × 
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           exp 
                           ( 
                           
                             
                               - 
                               
                                 1 
                                 
                                   2 
                                    
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   
                                     y 
                                     t 
                                   
                                    
                                   y 
                                 
                                 - 
                                 
                                   
                                     y 
                                     t 
                                   
                                    
                                   
                                     
                                       X 
                                       ( 
                                       
                                         
                                           
                                             X 
                                             t 
                                           
                                            
                                           X 
                                         
                                         + 
                                         
                                           
                                             
                                               σ 
                                               2 
                                             
                                             
                                               λ 
                                               2 
                                             
                                           
                                            
                                           I 
                                         
                                       
                                       ) 
                                     
                                     
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                     X 
                                     t 
                                   
                                    
                                   y 
                                 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             
                               ( 
                               
                                 2 
                                  
                                 
                                   πλ 
                                   2 
                                 
                               
                               ) 
                             
                             
                               
                                 - 
                                 d 
                               
                               / 
                               2 
                             
                           
                            
                           
                             
                               ( 
                               
                                 2 
                                  
                                 
                                   πσ 
                                   2 
                                 
                               
                               ) 
                             
                             
                               
                                 - 
                                 
                                   ( 
                                   
                                     n 
                                     - 
                                     d 
                                   
                                   ) 
                                 
                               
                               / 
                               2 
                             
                           
                            
                           
                             
                                
                               
                                 G 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                               
                                
                             
                             
                               - 
                               
                                 1 
                                 2 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     1 
                                     
                                       2 
                                        
                                       
                                         σ 
                                         2 
                                       
                                     
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       
                                         y 
                                         t 
                                       
                                        
                                       y 
                                     
                                     - 
                                     
                                       
                                         y 
                                         t 
                                       
                                        
                                       
                                         XG 
                                         
                                           σ 
                                           , 
                                           λ 
                                         
                                         
                                           - 
                                           1 
                                         
                                       
                                        
                                       
                                         X 
                                         t 
                                       
                                        
                                       y 
                                     
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                           , 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   
                     
                       where 
                        
                       
                           
                       
                        
                       
                         G 
                         
                           σ 
                           , 
                           λ 
                         
                       
                     
                     ≡ 
                     
                       
                         
                           X 
                           t 
                         
                          
                         X 
                       
                       + 
                       
                         
                           
                             σ 
                             2 
                           
                           
                             λ 
                             2 
                           
                         
                          
                         
                           I 
                           . 
                           
                               
                           
                            
                           Similarly 
                         
                       
                     
                   
                   , 
                   
                     for 
                      
                     
                         
                     
                      
                     p 
                      
                     
                       ( 
                       
                         
                           y 
                           * 
                         
                         , 
                         
                           y 
                           | 
                           
                             σ 
                             2 
                           
                         
                         , 
                         
                           λ 
                           2 
                         
                       
                       ) 
                     
                   
                   , 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           p 
                            
                           
                             ( 
                             
                               
                                 y 
                                 * 
                               
                               , 
                               
                                 y 
                                 | 
                                 
                                   σ 
                                   2 
                                 
                               
                               , 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                         = 
                           
                          
                         
                           
                             ∫ 
                             
                               ℝ 
                               d 
                             
                           
                            
                           
                             
                               p 
                                
                               
                                 ( 
                                 
                                   
                                     
                                       y 
                                       * 
                                     
                                     | 
                                     w 
                                   
                                   , 
                                   
                                     σ 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                               p 
                                
                               
                                 ( 
                                 
                                   
                                     y 
                                     | 
                                     w 
                                   
                                   , 
                                   
                                     σ 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                               p 
                                
                               
                                 ( 
                                 
                                   w 
                                   | 
                                   
                                     λ 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                                
                               w 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           ∫ 
                           
                             
                               
                                 ( 
                                 
                                   2 
                                    
                                   
                                     πλ 
                                     2 
                                   
                                 
                                 ) 
                               
                               
                                 
                                   - 
                                   d 
                                 
                                 / 
                                 2 
                               
                             
                              
                             
                               
                                 ( 
                                 
                                   2 
                                    
                                   
                                     πσ 
                                     2 
                                   
                                 
                                 ) 
                               
                               
                                 
                                   - 
                                   
                                     ( 
                                     
                                       n 
                                       + 
                                       1 
                                     
                                     ) 
                                   
                                 
                                 / 
                                 2 
                               
                             
                             × 
                             
                               exp 
                               ( 
                               
                                 - 
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           y 
                                           * 
                                         
                                         - 
                                         
                                           
                                             x 
                                             * 
                                           
                                            
                                           w 
                                         
                                       
                                       ) 
                                     
                                     2 
                                   
                                   
                                     2 
                                      
                                     
                                       σ 
                                       2 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           
                             exp 
                             ( 
                             
                               - 
                               
                                 
                                   
                                     ∑ 
                                     i 
                                   
                                    
                                   
                                     
                                       ( 
                                       
                                         
                                           y 
                                           i 
                                         
                                         - 
                                         
                                           
                                             x 
                                             i 
                                           
                                            
                                           w 
                                         
                                       
                                       ) 
                                     
                                     2 
                                   
                                 
                                 
                                   2 
                                    
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                             
                             ) 
                           
                            
                           
                             exp 
                             ( 
                             
                               - 
                               
                                 
                                   
                                      
                                     w 
                                      
                                   
                                   2 
                                 
                                 
                                   2 
                                    
                                   
                                     λ 
                                     2 
                                   
                                 
                               
                             
                             ) 
                           
                            
                           
                              
                             w 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           ∫ 
                           
                             
                               
                                 ( 
                                 
                                   2 
                                    
                                   
                                     πλ 
                                     2 
                                   
                                 
                                 ) 
                               
                               
                                 
                                   - 
                                   d 
                                 
                                 / 
                                 2 
                               
                             
                              
                             
                               
                                 ( 
                                 
                                   2 
                                    
                                   
                                     πσ 
                                     2 
                                   
                                 
                                 ) 
                               
                               
                                 
                                   - 
                                   
                                     ( 
                                     
                                       n 
                                       + 
                                       1 
                                     
                                     ) 
                                   
                                 
                                 / 
                                 2 
                               
                             
                             × 
                           
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           exp 
                           ( 
                           
                             
                               - 
                               
                                 1 
                                 
                                   2 
                                    
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   y 
                                   * 
                                   2 
                                 
                                 + 
                                 
                                   
                                     y 
                                     t 
                                   
                                    
                                   y 
                                 
                                 - 
                                 
                                   2 
                                    
                                   
                                     ( 
                                     
                                       
                                         
                                           y 
                                           * 
                                         
                                          
                                         
                                           x 
                                           * 
                                         
                                       
                                       + 
                                       
                                         
                                           y 
                                           t 
                                         
                                          
                                         X 
                                       
                                     
                                     ) 
                                   
                                    
                                   w 
                                 
                                 + 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                               
                              
                             
                               
                                 
                                   w 
                                   t 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       
                                         x 
                                         * 
                                         t 
                                       
                                        
                                       
                                         x 
                                         * 
                                       
                                     
                                     + 
                                     
                                       
                                         X 
                                         t 
                                       
                                        
                                       X 
                                     
                                     + 
                                     
                                       
                                         
                                           σ 
                                           2 
                                         
                                         
                                           λ 
                                           2 
                                         
                                       
                                        
                                       I 
                                     
                                   
                                   ) 
                                 
                               
                                
                               w 
                             
                             ) 
                           
                           ) 
                         
                          
                         
                            
                           w 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             
                               ( 
                               
                                 2 
                                  
                                 
                                   πλ 
                                   2 
                                 
                               
                               ) 
                             
                             
                               
                                 - 
                                 d 
                               
                               / 
                               2 
                             
                           
                            
                           
                             
                               ( 
                               
                                 2 
                                  
                                 
                                   πσ 
                                   2 
                                 
                               
                               ) 
                             
                             
                               
                                 - 
                                 
                                   ( 
                                   
                                     n 
                                     - 
                                     d 
                                     + 
                                     1 
                                   
                                   ) 
                                 
                               
                               / 
                               2 
                             
                           
                            
                           
                             
                                
                               
                                 Z 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                               
                                
                             
                             
                               - 
                               
                                 1 
                                 2 
                               
                             
                           
                           × 
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           exp 
                           ( 
                           
                             
                               - 
                               
                                 1 
                                 
                                   2 
                                    
                                   
                                     σ 
                                     2 
                                   
                                 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   y 
                                   * 
                                   2 
                                 
                                 + 
                                 
                                   
                                     y 
                                     t 
                                   
                                    
                                   y 
                                 
                                 - 
                                 
                                   
                                     ( 
                                     
                                       
                                         
                                           y 
                                           * 
                                         
                                          
                                         
                                           x 
                                           * 
                                         
                                       
                                       + 
                                       
                                         
                                           y 
                                           t 
                                         
                                          
                                         X 
                                       
                                     
                                     ) 
                                   
                                    
                                   
                                     
                                       Z 
                                       
                                         σ 
                                         , 
                                         λ 
                                       
                                       
                                         - 
                                         1 
                                       
                                     
                                     ( 
                                     
                                       
                                         
                                           x 
                                           * 
                                           t 
                                         
                                          
                                         
                                           y 
                                           * 
                                         
                                       
                                       + 
                                     
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                             
                                 
                                
                               
                                 
                                   X 
                                   t 
                                 
                                  
                                 y 
                               
                               ) 
                             
                             ) 
                           
                           ) 
                         
                         . 
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    where Z σ,λ ≡x* t x*+G σ,λ . Since x* t x* is a rank −1 matrix, the following “update formulas” apply, 
         [0000]    
       
         
           
             
                
               
                 Z 
                 
                   σ 
                   , 
                   λ 
                 
               
                
             
             = 
             
               
                  
                 
                   
                     
                       x 
                       * 
                       t 
                     
                      
                     
                       x 
                       * 
                     
                   
                   + 
                   
                     G 
                     
                       σ 
                       , 
                       λ 
                     
                   
                 
                  
               
               = 
               
                 
                   ( 
                   
                     1 
                     + 
                     
                       
                         x 
                         * 
                       
                        
                       
                         G 
                         
                           σ 
                           , 
                           λ 
                         
                         
                           - 
                           1 
                         
                       
                        
                       
                         x 
                         * 
                         t 
                       
                     
                   
                   ) 
                 
                  
                 
                    
                   
                     G 
                     
                       σ 
                       , 
                       λ 
                     
                   
                    
                 
               
             
           
         
       
       
         
           
             
               Z 
               
                 σ 
                 , 
                 λ 
               
               
                 - 
                 1 
               
             
             = 
             
               
                 
                   ( 
                   
                     
                       
                         x 
                         * 
                         t 
                       
                        
                       
                         x 
                         * 
                       
                     
                     + 
                     
                       G 
                       
                         σ 
                         , 
                         λ 
                       
                     
                   
                   ) 
                 
                 
                   - 
                   1 
                 
               
               = 
               
                 
                   G 
                   
                     σ 
                     , 
                     λ 
                   
                   
                     - 
                     1 
                   
                 
                 - 
                 
                   
                     
                       G 
                       
                         σ 
                         , 
                         λ 
                       
                       
                         - 
                         1 
                       
                     
                      
                     
                       x 
                       * 
                       t 
                     
                      
                     
                       x 
                       * 
                     
                      
                     
                       G 
                       
                         σ 
                         , 
                         λ 
                       
                       
                         - 
                         1 
                       
                     
                   
                   
                     1 
                     + 
                     
                       
                         x 
                         * 
                       
                        
                       
                         G 
                         
                           σ 
                           , 
                           λ 
                         
                         
                           - 
                           1 
                         
                       
                        
                       
                         x 
                         * 
                         t 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             and 
              
             
                 
             
              
             thus 
           
         
       
       
         
           
             
               
                 Z 
                 
                   σ 
                   , 
                   λ 
                 
                 
                   - 
                   1 
                 
               
                
               
                 x 
                 * 
                 t 
               
             
             = 
             
               
                 
                   G 
                   
                     σ 
                     , 
                     λ 
                   
                   
                     - 
                     1 
                   
                 
                  
                 
                   x 
                   * 
                   t 
                 
               
               - 
               
                 
                   
                     G 
                     
                       σ 
                       , 
                       λ 
                     
                     
                       - 
                       1 
                     
                   
                    
                   
                     x 
                     * 
                     t 
                   
                    
                   
                     x 
                     * 
                   
                    
                   
                     G 
                     
                       σ 
                       , 
                       λ 
                     
                     
                       - 
                       1 
                     
                   
                    
                   
                     x 
                     * 
                     t 
                   
                 
                 
                   1 
                   + 
                   
                     
                       x 
                       * 
                     
                      
                     
                       G 
                       
                         σ 
                         , 
                         λ 
                       
                       
                         - 
                         1 
                       
                     
                      
                     
                       x 
                       * 
                       t 
                     
                   
                 
               
             
           
         
       
     
         [0000]    
       
         
           
             
               
                 
                   = 
                     
                    
                   
                     
                       G 
                       
                         σ 
                         , 
                         λ 
                       
                       
                         - 
                         1 
                       
                     
                      
                     
                       
                         x 
                         * 
                         t 
                       
                        
                       
                         ( 
                         
                           1 
                           
                             1 
                             + 
                             
                               
                                 x 
                                 * 
                               
                                
                               
                                 G 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                                 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 x 
                                 * 
                                 t 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   
                     1 
                     - 
                     
                       
                         x 
                         * 
                       
                        
                       
                         Z 
                         
                           σ 
                           , 
                           λ 
                         
                         
                           - 
                           1 
                         
                       
                        
                       
                         x 
                         * 
                         t 
                       
                     
                   
                   = 
                     
                    
                   
                     1 
                     - 
                     
                       
                         
                           x 
                           * 
                         
                          
                         
                           G 
                           
                             σ 
                             , 
                             λ 
                           
                           
                             - 
                             1 
                           
                         
                          
                         
                           x 
                           * 
                           t 
                         
                       
                       
                         1 
                         + 
                         
                           
                             x 
                             * 
                           
                            
                           
                             G 
                             
                               σ 
                               , 
                               λ 
                             
                             
                               - 
                               1 
                             
                           
                            
                           
                             x 
                             * 
                             t 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     1 
                     
                       1 
                       + 
                       
                         
                           x 
                           * 
                           t 
                         
                          
                         
                           G 
                           
                             σ 
                             , 
                             λ 
                           
                           
                             - 
                             1 
                           
                         
                          
                         
                           x 
                           * 
                           t 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   
                     
                       y 
                       t 
                     
                      
                     
                       XZ 
                       
                         σ 
                         , 
                         λ 
                       
                       
                         - 
                         1 
                       
                     
                      
                     
                       x 
                       * 
                       t 
                     
                   
                   = 
                     
                    
                   
                     
                       
                         
                           y 
                           t 
                         
                          
                         
                           XG 
                           
                             σ 
                             , 
                             λ 
                           
                           
                             - 
                             1 
                           
                         
                          
                         
                           x 
                           * 
                           t 
                         
                       
                       
                         1 
                         + 
                         
                           
                             x 
                             * 
                           
                            
                           
                             G 
                             
                               σ 
                               , 
                               λ 
                             
                             
                               - 
                               1 
                             
                           
                            
                           
                             x 
                             * 
                             t 
                           
                         
                       
                     
                     . 
                   
                 
               
             
           
         
       
     
       Hence 
       [0050]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             y 
                             * 
                             2 
                           
                           - 
                           
                             
                               ( 
                               
                                 
                                   
                                     y 
                                     * 
                                   
                                    
                                   
                                     x 
                                     * 
                                     t 
                                   
                                 
                                 + 
                                 
                                   
                                     y 
                                     t 
                                   
                                    
                                   X 
                                 
                               
                               ) 
                             
                              
                             
                               
                                 Z 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                                 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 ( 
                                 
                                   
                                     
                                       y 
                                       * 
                                     
                                      
                                     
                                       x 
                                       * 
                                     
                                   
                                   + 
                                   
                                     
                                       X 
                                       t 
                                     
                                      
                                     y 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         = 
                           
                          
                         
                           
                             ( 
                             
                               
                                 - 
                                 
                                   y 
                                   t 
                                 
                               
                                
                               
                                 XZ 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                                 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 X 
                                 t 
                               
                                
                               y 
                             
                             ) 
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           ( 
                           
                             
                               
                                 ( 
                                 
                                   1 
                                   - 
                                   
                                     
                                       x 
                                       * 
                                     
                                      
                                     
                                       Z 
                                       
                                         σ 
                                         , 
                                         λ 
                                       
                                       
                                         - 
                                         1 
                                       
                                     
                                      
                                     
                                       x 
                                       * 
                                       t 
                                     
                                   
                                 
                                 ) 
                               
                                
                               
                                 y 
                                 * 
                                 2 
                               
                             
                             - 
                             
                               2 
                                
                               
                                 y 
                                 * 
                               
                                
                               
                                 x 
                                 * 
                               
                                
                               
                                 Z 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                                 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 X 
                                 t 
                               
                                
                               y 
                             
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           ( 
                           
                             
                               
                                 - 
                                 
                                   y 
                                   t 
                                 
                               
                                
                               
                                 XG 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                                 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 X 
                                 t 
                               
                                
                               y 
                             
                             + 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                             
                            
                           
                             
                               
                                 y 
                                 t 
                               
                                
                               
                                 XG 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                                 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 x 
                                 * 
                                 t 
                               
                                
                               
                                 x 
                                 * 
                               
                                
                               
                                 G 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                                 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 X 
                                 t 
                               
                                
                               y 
                             
                             
                               1 
                               + 
                               
                                 
                                   x 
                                   * 
                                 
                                  
                                 
                                   G 
                                   
                                     σ 
                                     , 
                                     λ 
                                   
                                   
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                   x 
                                   * 
                                   t 
                                 
                               
                             
                           
                           ) 
                         
                         + 
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           ( 
                           
                             
                               
                                 y 
                                 * 
                                 2 
                               
                               - 
                               
                                 2 
                                  
                                 
                                   y 
                                   * 
                                 
                                  
                                 
                                   x 
                                   * 
                                 
                                  
                                 
                                   G 
                                   
                                     σ 
                                     , 
                                     λ 
                                   
                                   
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                   X 
                                   t 
                                 
                                  
                                 y 
                               
                             
                             
                               1 
                               + 
                               
                                 
                                   x 
                                   * 
                                 
                                  
                                 
                                   G 
                                   
                                     σ 
                                     , 
                                     λ 
                                   
                                   
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                   x 
                                   * 
                                   t 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         
                           = 
                             
                            
                           
                             
                               
                                 - 
                                 
                                   y 
                                   t 
                                 
                               
                                
                               
                                 XG 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                                 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 X 
                                 t 
                               
                                
                               y 
                             
                             - 
                             
                               
                                 
                                   ( 
                                   
                                     
                                       y 
                                       * 
                                     
                                     - 
                                     
                                       
                                         x 
                                         * 
                                       
                                        
                                       
                                         G 
                                         
                                           σ 
                                           , 
                                           λ 
                                         
                                         
                                           - 
                                           1 
                                         
                                       
                                        
                                       
                                         X 
                                         t 
                                       
                                        
                                       y 
                                     
                                   
                                   ) 
                                 
                                 2 
                               
                               
                                 1 
                                 + 
                                 
                                   
                                     x 
                                     * 
                                   
                                    
                                   
                                     G 
                                     
                                       σ 
                                       , 
                                       λ 
                                     
                                     
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                     x 
                                     * 
                                     t 
                                   
                                 
                               
                             
                           
                         
                         , 
                       
                     
                   
                 
               
             
             
               
                 
                   which 
                    
                   
                       
                   
                    
                   simplifies 
                    
                   
                       
                   
                    
                   
                     p 
                      
                     
                       ( 
                       
                         
                           y 
                           * 
                         
                         , 
                         
                           y 
                           | 
                           
                             σ 
                             2 
                           
                         
                         , 
                         
                           λ 
                           2 
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   
                     
                       
                         
                           p 
                            
                           
                             ( 
                             
                               
                                 y 
                                 * 
                               
                               , 
                               
                                 y 
                                 | 
                                 
                                   σ 
                                   2 
                                 
                               
                               , 
                               
                                 λ 
                                 2 
                               
                             
                             ) 
                           
                         
                         = 
                           
                          
                         
                           
                             
                               ( 
                               
                                 2 
                                  
                                 
                                   πλ 
                                   2 
                                 
                               
                               ) 
                             
                             
                               
                                 - 
                                 d 
                               
                               / 
                               2 
                             
                           
                            
                           
                             
                               ( 
                               
                                 2 
                                  
                                 
                                   πσ 
                                   2 
                                 
                               
                               ) 
                             
                             
                               
                                 - 
                                 
                                   ( 
                                   
                                     n 
                                     - 
                                     d 
                                     + 
                                     1 
                                   
                                   ) 
                                 
                               
                               / 
                               2 
                             
                           
                            
                           
                             
                                
                               
                                 Z 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                               
                                
                             
                             
                               - 
                               
                                 1 
                                 2 
                               
                             
                           
                           × 
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     1 
                                     
                                       2 
                                        
                                       
                                         σ 
                                         2 
                                       
                                     
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       
                                         y 
                                         t 
                                       
                                        
                                       y 
                                     
                                     - 
                                     
                                       
                                         y 
                                         t 
                                       
                                        
                                       
                                         XG 
                                         
                                           σ 
                                           , 
                                           λ 
                                         
                                         
                                           - 
                                           1 
                                         
                                       
                                        
                                       
                                         X 
                                         t 
                                       
                                        
                                       y 
                                     
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                           × 
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 - 
                                 
                                   1 
                                   
                                     2 
                                      
                                     
                                       σ 
                                       2 
                                     
                                   
                                 
                               
                                
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         y 
                                         * 
                                       
                                       - 
                                       
                                         
                                           x 
                                           * 
                                         
                                          
                                         
                                           G 
                                           
                                             σ 
                                             , 
                                             λ 
                                           
                                           
                                             - 
                                             1 
                                           
                                         
                                          
                                         
                                           X 
                                           t 
                                         
                                          
                                         y 
                                       
                                     
                                     ) 
                                   
                                   2 
                                 
                                 
                                   1 
                                   + 
                                   
                                     
                                       x 
                                       * 
                                     
                                      
                                     
                                       G 
                                       
                                         σ 
                                         , 
                                         λ 
                                       
                                       
                                         - 
                                         1 
                                       
                                     
                                      
                                     
                                       x 
                                       * 
                                       t 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             
                               ( 
                               
                                 2 
                                  
                                 
                                   πλ 
                                   2 
                                 
                               
                               ) 
                             
                             
                               
                                 - 
                                 d 
                               
                               / 
                               2 
                             
                           
                            
                           
                             
                               ( 
                               
                                 2 
                                  
                                 
                                   πσ 
                                   2 
                                 
                               
                               ) 
                             
                             
                               
                                 - 
                                 
                                   ( 
                                   
                                     n 
                                     - 
                                     d 
                                   
                                   ) 
                                 
                               
                               / 
                               2 
                             
                           
                            
                           
                             
                                
                               
                                 G 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                               
                                
                             
                             
                               - 
                               
                                 1 
                                 2 
                               
                             
                           
                           × 
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   - 
                                   
                                     1 
                                     
                                       2 
                                        
                                       
                                         σ 
                                         2 
                                       
                                     
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       
                                         y 
                                         t 
                                       
                                        
                                       y 
                                     
                                     - 
                                     
                                       
                                         y 
                                         t 
                                       
                                        
                                       
                                         XG 
                                         
                                           σ 
                                           , 
                                           λ 
                                         
                                         
                                           - 
                                           1 
                                         
                                       
                                        
                                       
                                         X 
                                         t 
                                       
                                        
                                       y 
                                     
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                           × 
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           
                             
                               ( 
                               
                                 2 
                                  
                                 
                                   
                                     πσ 
                                     2 
                                   
                                    
                                   
                                     ( 
                                     
                                       1 
                                       + 
                                       
                                         
                                           x 
                                           * 
                                         
                                          
                                         
                                           G 
                                           
                                             σ 
                                             , 
                                             λ 
                                           
                                           
                                             - 
                                             1 
                                           
                                         
                                          
                                         
                                           x 
                                           * 
                                           t 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             
                               - 
                               
                                 1 
                                 2 
                               
                             
                           
                            
                           
                             
                               exp 
                                
                               
                                 ( 
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           y 
                                           * 
                                         
                                         - 
                                         
                                           
                                             x 
                                             * 
                                           
                                            
                                           
                                             G 
                                             
                                               σ 
                                               , 
                                               λ 
                                             
                                             
                                               - 
                                               1 
                                             
                                           
                                            
                                           
                                             X 
                                             t 
                                           
                                            
                                           y 
                                         
                                       
                                       ) 
                                     
                                     2 
                                   
                                   
                                     2 
                                      
                                     
                                       
                                         σ 
                                         2 
                                       
                                        
                                       
                                         ( 
                                         
                                           1 
                                           + 
                                           
                                             
                                               x 
                                               * 
                                             
                                              
                                             
                                               G 
                                               
                                                 σ 
                                                 , 
                                                 λ 
                                               
                                               
                                                 - 
                                                 1 
                                               
                                             
                                              
                                             
                                               x 
                                               * 
                                               t 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                             . 
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
       Therefore, 
       [0051]    
       
         
           
             
               
                 
                   ∫ 
                   l 
                   h 
                 
                  
                 
                   
                     p 
                      
                     
                       ( 
                       
                         
                           y 
                           * 
                         
                         , 
                         
                           y 
                           | 
                           
                             σ 
                             2 
                           
                         
                         , 
                         
                           λ 
                           2 
                         
                       
                       ) 
                     
                   
                    
                   
                      
                     
                       y 
                       * 
                     
                   
                 
               
               = 
               
                 
                   
                     
                       ( 
                       
                         2 
                          
                         
                           πλ 
                           2 
                         
                       
                       ) 
                     
                     
                       
                         - 
                         d 
                       
                       / 
                       2 
                     
                   
                    
                   
                     
                       ( 
                       
                         2 
                          
                         
                           πσ 
                           2 
                         
                       
                       ) 
                     
                     
                       
                         - 
                         
                           ( 
                           
                             n 
                             - 
                             d 
                           
                           ) 
                         
                       
                       / 
                       2 
                     
                   
                    
                   
                     
                        
                       
                         G 
                         
                           σ 
                           , 
                           λ 
                         
                       
                        
                     
                     
                       - 
                       
                         1 
                         2 
                       
                     
                   
                   × 
                   
                     exp 
                      
                     
                       ( 
                       
                         
                           - 
                           
                             1 
                             
                               2 
                                
                               
                                 σ 
                                 2 
                               
                             
                           
                         
                          
                         
                           ( 
                           
                             
                               
                                 y 
                                 t 
                               
                                
                               y 
                             
                             - 
                             
                               
                                 y 
                                 t 
                               
                                
                               
                                 XG 
                                 
                                   σ 
                                   , 
                                   λ 
                                 
                                 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 X 
                                 t 
                               
                                
                               y 
                             
                           
                           ) 
                         
                       
                       ) 
                     
                   
                    
                   
                     1 
                     2 
                   
                    
                   
                     erf 
                   
                    
                   
                     ( 
                     
                       
                         u 
                         - 
                         
                           m 
                           
                             σ 
                             , 
                             λ 
                           
                         
                       
                       
                         
                           2 
                            
                           
                             v 
                             
                               σ 
                               , 
                               λ 
                             
                           
                         
                       
                     
                     ) 
                   
                 
                  
                 
                   | 
                   
                     u 
                     = 
                     l 
                   
                   
                     u 
                     = 
                     h 
                   
                 
                  
                 
                   
 
                 
                  
                 
                   
                     where 
                      
                     
                         
                     
                      
                     
                       m 
                       
                         σ 
                         , 
                         λ 
                       
                     
                   
                   ≡ 
                   
                     
                       x 
                       * 
                     
                      
                     
                       G 
                       
                         σ 
                         , 
                         λ 
                       
                       
                         - 
                         1 
                       
                     
                      
                     
                       X 
                       t 
                     
                      
                     y 
                      
                     
                         
                     
                      
                     and 
                      
                     
                         
                     
                      
                     
                       v 
                       
                         σ 
                         , 
                         λ 
                       
                     
                   
                   ≡ 
                   
                     
                       σ 
                       2 
                     
                      
                     
                       ( 
                       
                         1 
                         + 
                         
                           
                             x 
                             * 
                           
                            
                           
                             G 
                             
                               σ 
                               , 
                               λ 
                             
                             
                               - 
                               1 
                             
                           
                            
                           
                             x 
                             * 
                             t 
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             , 
             
               
 
             
              
             
               
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∫ 
                     R 
                   
                    
                   
                     
                       y 
                       * 
                     
                      
                     
                       p 
                        
                       
                         ( 
                         
                           
                             y 
                             * 
                           
                           , 
                           
                             y 
                             | 
                             
                               σ 
                               2 
                             
                           
                           , 
                           
                             λ 
                             2 
                           
                         
                         ) 
                       
                     
                      
                     
                        
                       
                         y 
                         * 
                       
                     
                   
                 
               
               = 
               
                 
                   
                     ( 
                     
                       2 
                        
                       
                         πλ 
                         2 
                       
                     
                     ) 
                   
                   
                     
                       - 
                       d 
                     
                     / 
                     2 
                   
                 
                  
                 
                   
                     ( 
                     
                       2 
                        
                       
                         πσ 
                         2 
                       
                     
                     ) 
                   
                   
                     
                       - 
                       
                         ( 
                         
                           n 
                           - 
                           d 
                         
                         ) 
                       
                     
                     / 
                     2 
                   
                 
                  
                 
                   
                      
                     
                       G 
                       
                         σ 
                         , 
                         λ 
                       
                     
                      
                   
                   
                     - 
                     
                       1 
                       2 
                     
                   
                 
                 × 
                 
                   exp 
                    
                   
                     ( 
                     
                       
                         - 
                         
                           1 
                           
                             2 
                              
                             
                               σ 
                               2 
                             
                           
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               y 
                               t 
                             
                              
                             y 
                           
                           - 
                           
                             
                               y 
                               t 
                             
                              
                             
                               XG 
                               
                                 σ 
                                 , 
                                 λ 
                               
                               
                                 - 
                                 1 
                               
                             
                              
                             
                               X 
                               t 
                             
                              
                             y 
                           
                         
                         ) 
                       
                     
                     ) 
                   
                 
                  
                 
                   
                     ( 
                     
                       
                         x 
                         * 
                       
                        
                       
                         G 
                         
                           σ 
                           , 
                           λ 
                         
                         
                           - 
                           1 
                         
                       
                        
                       
                         X 
                         t 
                       
                        
                       y 
                     
                     ) 
                   
                   . 
                 
               
             
           
         
       
     
       6. Computational Methods 
       [0052]    We want to compute: 
         [0000]    
       
         
           
             
               p 
                
               
                 ( 
                 y 
                 ) 
               
             
             = 
             
               ∫ 
               
                 
                   p 
                    
                   
                     ( 
                     
                       
                         σ 
                         2 
                       
                       , 
                       
                         λ 
                         2 
                       
                     
                     ) 
                   
                 
                  
                 
                   ( 
                   
                     ∫ 
                     
                       
                         p 
                          
                         
                           ( 
                           
                             
                               y 
                               | 
                               w 
                             
                             , 
                             
                               σ 
                               2 
                             
                           
                           ) 
                         
                       
                        
                       
                         p 
                          
                         
                           ( 
                           
                             w 
                             | 
                             
                               λ 
                               2 
                             
                           
                           ) 
                         
                       
                        
                       
                          
                         w 
                       
                     
                   
                   ) 
                 
                  
                 
                    
                   
                     σ 
                     2 
                   
                 
                  
                 
                    
                   
                     λ 
                     2 
                   
                 
               
             
           
         
       
       
         
           
             
               p 
                
               
                 ( 
                 
                   
                     l 
                     ≤ 
                     
                       y 
                       * 
                     
                     ≤ 
                     h 
                   
                   | 
                   y 
                 
                 ) 
               
             
             = 
             
               
                 1 
                 
                   p 
                    
                   
                     ( 
                     y 
                     ) 
                   
                 
               
                
               
                 ∫ 
                 
                   
                     p 
                      
                     
                       ( 
                       
                         
                           σ 
                           2 
                         
                         , 
                         
                           λ 
                           2 
                         
                       
                       ) 
                     
                   
                    
                   
                     ( 
                     
                       
                         ∫ 
                         l 
                         h 
                       
                        
                       
                         
                           ( 
                           
                             ∫ 
                             
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       * 
                                     
                                     , 
                                     
                                       y 
                                       | 
                                       w 
                                     
                                     , 
                                     
                                       σ 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                 p 
                                  
                                 
                                   ( 
                                   
                                     w 
                                     | 
                                     
                                       λ 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                  
                                 w 
                               
                             
                           
                           ) 
                         
                          
                         
                            
                           
                             y 
                             * 
                           
                         
                       
                     
                     ) 
                   
                    
                   
                      
                     
                       σ 
                       2 
                     
                   
                    
                   
                      
                     
                       λ 
                       2 
                     
                   
                 
               
             
           
         
       
       
         
           
             
               E 
                
               
                 ( 
                 
                   
                     y 
                     * 
                   
                   | 
                   y 
                 
                 ) 
               
             
             = 
             
               
                 1 
                 
                   p 
                    
                   
                     ( 
                     y 
                     ) 
                   
                 
               
                
               
                 ∫ 
                 
                   
                     p 
                      
                     
                       ( 
                       
                         
                           σ 
                           2 
                         
                         , 
                         
                           λ 
                           2 
                         
                       
                       ) 
                     
                   
                    
                   
                     ( 
                     
                       ∫ 
                       
                         
                           
                             y 
                             * 
                           
                            
                           
                             ( 
                             
                               ∫ 
                               
                                 
                                   p 
                                    
                                   
                                     ( 
                                     
                                       
                                         y 
                                         * 
                                       
                                       , 
                                       
                                         y 
                                         | 
                                         w 
                                       
                                       , 
                                       
                                         σ 
                                         2 
                                       
                                     
                                     ) 
                                   
                                 
                                  
                                 
                                   p 
                                    
                                   
                                     ( 
                                     
                                       w 
                                       | 
                                       
                                         λ 
                                         2 
                                       
                                     
                                     ) 
                                   
                                 
                                  
                                 
                                    
                                   w 
                                 
                               
                             
                             ) 
                           
                         
                          
                         
                            
                           
                             y 
                             * 
                           
                         
                       
                     
                     ) 
                   
                    
                   
                      
                     
                       σ 
                       2 
                     
                   
                    
                   
                     
                        
                       
                         λ 
                         2 
                       
                     
                     . 
                   
                 
               
             
           
         
       
     
         [0053]    We have explicit formulas from the previous section for the integrals over w and y*. These formulas are in terms of y, X, and x*, which are fixed, and G σ,λ  and G σ,λ   −1  which vary with σ 2 ,λ 2 . 
         [0054]    The efficient computation of the σ 2 , λ 2  integrals rests on two pillars: the singular value decomposition and adaptive numerical integration. The first makes the computation of the integrand cheap, while the second computes the integrals themselves from multiple evaluations of the integrand. 
         [0055]    6.1 Singular Value Decomposition 
         [0056]    We can form the singular value decomposition, USV t =X where U∈           n×k , S∈           k×k , V∈           d×k  in O(ndk) time. As presented here, our discussion and implementation simultaneously addresses the d&lt;n and d&gt;n cases. If only one of these cases is desired, a somewhat simpler formula can be used, as would be apparent to one of ordinary skill in the art. 
         [0000]    
       
         
           
             
               
                 
                   
                     G 
                     
                       σ 
                       , 
                       λ 
                     
                   
                   = 
                   
                     
                       
                         X 
                         t 
                       
                        
                       X 
                     
                     + 
                     
                       
                         
                           σ 
                           2 
                         
                         
                           λ 
                           2 
                         
                       
                        
                       
                         I 
                         d 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       
                         V 
                         ( 
                         
                           
                             S 
                             2 
                           
                           + 
                           
                             
                               
                                 σ 
                                 2 
                               
                               
                                 λ 
                                 2 
                               
                             
                              
                             
                               I 
                               k 
                             
                           
                         
                         ) 
                       
                        
                       
                         V 
                         t 
                       
                     
                     + 
                     
                       
                         
                           σ 
                           2 
                         
                         
                           λ 
                           2 
                         
                       
                        
                       
                         ( 
                         
                           
                             I 
                             d 
                           
                           - 
                           
                             VV 
                             t 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               G 
               
                 σ 
                 , 
                 λ 
               
               
                 - 
                 1 
               
             
             = 
             
               
                 
                   
                     V 
                     ( 
                     
                       
                         S 
                         2 
                       
                       + 
                       
                         
                           
                             σ 
                             2 
                           
                           
                             λ 
                             2 
                           
                         
                          
                         
                           I 
                           k 
                         
                       
                     
                     ) 
                   
                   
                     - 
                     1 
                   
                 
                  
                 
                   V 
                   t 
                 
               
               + 
               
                 
                   
                     λ 
                     2 
                   
                   
                     σ 
                     2 
                   
                 
                  
                 
                   ( 
                   
                     
                       I 
                       d 
                     
                     - 
                     
                       VV 
                       t 
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
                
               
                 G 
                 
                   σ 
                   , 
                   λ 
                 
               
                
             
             = 
             
               
                  
                 
                   
                     S 
                     2 
                   
                   + 
                   
                     
                       
                         σ 
                         2 
                       
                       
                         λ 
                         2 
                       
                     
                      
                     
                       I 
                       k 
                     
                   
                 
                  
               
                
               
                 
                   ( 
                   
                     
                       σ 
                       2 
                     
                     
                       λ 
                       2 
                     
                   
                   ) 
                 
                 
                   d 
                   - 
                   k 
                 
               
             
           
         
       
     
         [0000]    The second term of G σ,λ vanishes when d=k, since VV t =I d  in this case. This allows various numerical quantities related to G σ,λ to be computed rapidly. With U, S, V pre-computed, |G σ,λ | O(k) time. With U t y∈           k×1  and x*V∈           1×k  pre-computed, 
         [0000]    
       
         
           
             
               
                 y 
                 t 
               
                
               
                 XG 
                 
                   σ 
                   , 
                   λ 
                 
                 
                   - 
                   1 
                 
               
                
               
                 X 
                 t 
               
                
               y 
             
             = 
             
               
                 
                   ( 
                   
                     
                       U 
                       t 
                     
                      
                     y 
                   
                   ) 
                 
                 t 
               
                
               
                 
                   
                     S 
                     2 
                   
                   ( 
                   
                     
                       S 
                       2 
                     
                     + 
                     
                       
                         σ 
                         2 
                       
                       
                         λ 
                         2 
                       
                     
                   
                   ) 
                 
                 
                   - 
                   1 
                 
               
                
               
                 ( 
                 
                   
                     U 
                     t 
                   
                    
                   y 
                 
                 ) 
               
             
           
         
       
       
         
           
             
               
                 x 
                 * 
               
                
               
                 G 
                 
                   σ 
                   , 
                   λ 
                 
                 
                   - 
                   1 
                 
               
                
               
                 X 
                 t 
               
                
               y 
             
             = 
             
               
                 ( 
                 
                   
                     x 
                     * 
                   
                    
                   V 
                 
                 ) 
               
                
               
                 
                   
                     S 
                     2 
                   
                   ( 
                   
                     
                       S 
                       2 
                     
                     + 
                     
                       
                         σ 
                         2 
                       
                       
                         λ 
                         2 
                       
                     
                   
                   ) 
                 
                 
                   - 
                   1 
                 
               
                
               
                 ( 
                 
                   
                     U 
                     t 
                   
                    
                   y 
                 
                 ) 
               
             
           
         
       
       
         
           
             
               
                 x 
                 * 
               
                
               
                 G 
                 
                   σ 
                   , 
                   λ 
                 
                 
                   - 
                   1 
                 
               
                
               
                 x 
                 * 
                 t 
               
             
             = 
             
               
                 ( 
                 
                   
                     x 
                     * 
                   
                    
                   V 
                 
                 ) 
               
                
               
                 
                   ( 
                   
                     
                       S 
                       2 
                     
                     + 
                     
                       
                         σ 
                         2 
                       
                       
                         λ 
                         2 
                       
                     
                   
                   ) 
                 
                 
                   - 
                   1 
                 
               
                
               
                 
                   ( 
                   
                     
                       x 
                       * 
                     
                      
                     V 
                   
                   ) 
                 
                 t 
               
             
           
         
       
     
         [0000]    are also O(k) time. 
         [0057]    Via the singular value decomposition, we reduce the computation to two-dimensional integrals of functions of σ 2  and λ 2  which we can evaluate in O(k) time. To find the normalizing constant, p(y), we need to evaluate the integral 
         [0000]    
       
         
           
             
               p 
                
               
                 ( 
                 y 
                 ) 
               
             
             = 
             
               C 
                
               
                 ∫ 
                 
                   
                     
                       ( 
                       
                         σ 
                         2 
                       
                       ) 
                     
                     
                       
                         - 
                         
                           
                             
                               v 
                               σ 
                             
                             + 
                             n 
                             - 
                             k 
                           
                           2 
                         
                       
                       - 
                       1 
                     
                   
                    
                   
                     
                       ( 
                       
                         λ 
                         2 
                       
                       ) 
                     
                     
                       
                         - 
                         
                           
                             
                               v 
                               λ 
                             
                             + 
                             k 
                           
                           2 
                         
                       
                       - 
                       1 
                     
                   
                    
                   
                     
                        
                       
                         
                           S 
                           2 
                         
                         + 
                         
                           
                             σ 
                             2 
                           
                           
                             λ 
                             2 
                           
                         
                       
                        
                     
                     
                       - 
                       
                         1 
                         2 
                       
                     
                   
                   × 
                   
                     exp 
                     ( 
                     
                       
                         - 
                         
                           
                             
                               v 
                               λ 
                             
                              
                             
                               λ 
                               0 
                               2 
                             
                           
                           
                             2 
                              
                             
                               λ 
                               2 
                             
                           
                         
                       
                       - 
                       
                         
                           1 
                           
                             2 
                              
                             
                               σ 
                               2 
                             
                           
                         
                          
                         
                           ( 
                           
                             
                               
                                 v 
                                 σ 
                               
                                
                               
                                 σ 
                                 0 
                                 2 
                               
                             
                             + 
                             
                               
                                  
                                 y 
                                  
                               
                               2 
                             
                             - 
                             
                               
                                 
                                   ( 
                                   
                                     
                                       U 
                                       t 
                                     
                                      
                                     y 
                                   
                                   ) 
                                 
                                 t 
                               
                                
                               
                                 
                                   
                                     S 
                                     2 
                                   
                                   ( 
                                   
                                     
                                       S 
                                       2 
                                     
                                     + 
                                     
                                       
                                         σ 
                                         2 
                                       
                                       
                                         λ 
                                         2 
                                       
                                     
                                   
                                   ) 
                                 
                                 
                                   - 
                                   1 
                                 
                               
                                
                               
                                 ( 
                                 
                                   
                                     U 
                                     t 
                                   
                                    
                                   y 
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                     ) 
                   
                    
                   
                      
                     
                       σ 
                       2 
                     
                   
                    
                   
                     
                        
                       
                         λ 
                         2 
                       
                     
                     . 
                   
                 
               
             
           
         
       
     
         [0000]    where both σ 2  and λ 2  go from zero to infinity. Similarly, to find p (1≦y*≦h|y) , we need to evaluate 
         [0000]    
       
         
           
             
               p 
                
               
                 ( 
                 
                   
                     l 
                     ≤ 
                     
                       y 
                       * 
                     
                     ≤ 
                     h 
                   
                   | 
                   y 
                 
                 ) 
               
             
             = 
             
               
                 
                   C 
                   
                     p 
                      
                     
                       ( 
                       y 
                       ) 
                     
                   
                 
                  
                 
                   ∫ 
                   
                     
                       
                         ( 
                         
                           σ 
                           2 
                         
                         ) 
                       
                       
                         
                           - 
                           
                             
                               
                                 v 
                                 σ 
                               
                               + 
                               n 
                               - 
                               k 
                             
                             2 
                           
                         
                         - 
                         1 
                       
                     
                      
                     
                       
                         ( 
                         
                           λ 
                           2 
                         
                         ) 
                       
                       
                         
                           - 
                           
                             
                               
                                 v 
                                 λ 
                               
                               + 
                               k 
                             
                             2 
                           
                         
                         - 
                         1 
                       
                     
                      
                     
                       
                          
                         
                           
                             S 
                             2 
                           
                           + 
                           
                             
                               σ 
                               2 
                             
                             
                               λ 
                               2 
                             
                           
                         
                          
                       
                       
                         - 
                         
                           1 
                           2 
                         
                       
                     
                     × 
                     
                       exp 
                       ( 
                       
                         
                           - 
                           
                             
                               
                                 v 
                                 λ 
                               
                                
                               
                                 λ 
                                 0 
                                 2 
                               
                             
                             
                               2 
                                
                               
                                 λ 
                                 2 
                               
                             
                           
                         
                         - 
                         
                           
                             1 
                             
                               2 
                                
                               
                                 σ 
                                 2 
                               
                             
                           
                            
                           
                             ( 
                             
                               
                                 
                                   v 
                                   σ 
                                 
                                  
                                 
                                   σ 
                                   0 
                                   2 
                                 
                               
                               + 
                               
                                 
                                    
                                   y 
                                    
                                 
                                 2 
                               
                               - 
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         U 
                                         t 
                                       
                                        
                                       y 
                                     
                                     ) 
                                   
                                   t 
                                 
                                  
                                 
                                   
                                     
                                       S 
                                       2 
                                     
                                     ( 
                                     
                                       
                                         S 
                                         2 
                                       
                                       + 
                                       
                                         
                                           σ 
                                           2 
                                         
                                         
                                           λ 
                                           2 
                                         
                                       
                                     
                                     ) 
                                   
                                   
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       U 
                                       t 
                                     
                                      
                                     y 
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                       ) 
                     
                     × 
                     
                       1 
                       2 
                     
                      
                     
                       erf 
                       ( 
                       
                         
                           u 
                           - 
                           
                             m 
                             
                               σ 
                               , 
                               λ 
                             
                           
                         
                         
                           
                             2 
                              
                             
                               v 
                               
                                 σ 
                                 , 
                                 λ 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
                
               
                 | 
                 
                   u 
                   = 
                   l 
                 
                 
                   u 
                   = 
                   h 
                 
               
                
               
                 
                    
                   
                     σ 
                     2 
                   
                 
                  
                 
                    
                   
                     λ 
                     2 
                   
                 
               
             
           
         
       
       
         
           where 
         
       
       
         
           
             
               m 
               
                 σ 
                 , 
                 λ 
               
             
             = 
             
               
                 ( 
                 
                   
                     x 
                     * 
                   
                    
                   V 
                 
                 ) 
               
                
               
                 
                   S 
                   ( 
                   
                     
                       S 
                       2 
                     
                     + 
                     
                       
                         σ 
                         2 
                       
                       
                         λ 
                         2 
                       
                     
                   
                   ) 
                 
                 
                   - 
                   1 
                 
               
                
               
                 ( 
                 
                   
                     U 
                     t 
                   
                    
                   y 
                 
                 ) 
               
             
           
         
       
       
         
           
             
               v 
               
                 σ 
                 , 
                 λ 
               
             
             = 
             
               
                 
                   σ 
                   2 
                 
                 ( 
                 
                   1 
                   + 
                   
                     
                       ( 
                       
                         
                           x 
                           * 
                         
                          
                         V 
                       
                       ) 
                     
                      
                     
                       
                         ( 
                         
                           
                             S 
                             2 
                           
                           + 
                           
                             
                               σ 
                               2 
                             
                             
                               λ 
                               2 
                             
                           
                         
                         ) 
                       
                       
                         - 
                         1 
                       
                     
                      
                     
                       
                         ( 
                         
                           
                             x 
                             * 
                           
                            
                           V 
                         
                         ) 
                       
                       t 
                     
                   
                 
                 ) 
               
               + 
               
                 
                   
                     λ 
                     2 
                   
                    
                   
                     ( 
                     
                       
                         
                            
                           
                             x 
                             * 
                           
                            
                         
                         2 
                       
                       - 
                       
                         
                            
                           
                             
                               x 
                               * 
                             
                              
                             V 
                           
                            
                         
                         2 
                       
                     
                     ) 
                   
                 
                 . 
               
             
           
         
       
     
         [0000]    In all our integrals, both the numerator and the denominator contain a factor of 
         [0000]    
       
         
           
             
               C 
               ≡ 
               
                 
                   
                     ( 
                     
                       2 
                        
                       π 
                     
                     ) 
                   
                   
                     
                       - 
                       n 
                     
                     / 
                     2 
                   
                 
                  
                 
                   
                     
                       ( 
                       
                         
                           v 
                           λ 
                         
                         / 
                         2 
                       
                       ) 
                     
                     
                       
                         v 
                         λ 
                       
                       / 
                       2 
                     
                   
                   
                     Γ 
                      
                     
                       ( 
                       
                         
                           v 
                           λ 
                         
                         / 
                         2 
                       
                       ) 
                     
                   
                 
                  
                 
                   λ 
                   0 
                   
                     v 
                     λ 
                   
                 
                  
                 
                   
                     
                       ( 
                       
                         
                           v 
                           σ 
                         
                         / 
                         2 
                       
                       ) 
                     
                     
                       
                         v 
                         σ 
                       
                       / 
                       2 
                     
                   
                   
                     Γ 
                      
                     
                       ( 
                       
                         
                           v 
                           σ 
                         
                         / 
                         2 
                       
                       ) 
                     
                   
                 
                  
                 
                   σ 
                   0 
                   
                     v 
                     σ 
                   
                 
               
             
             , 
           
         
       
     
         [0000]    which cancels for all quantities of interest. 
         [0058]    6.2 Integration 
         [0059]    The techniques employed for our two-dimensional integrals are fairly standard to numerical analysts, though possibly unfamiliar to the machine learning community. Our integrals are of the form 
         [0000]    
       
         
           
             
               ∫ 
               0 
               ∞ 
             
              
             
               
                 ∫ 
                 0 
                 ∞ 
               
                
               
                 
                   f 
                    
                   
                     ( 
                     
                       α 
                       , 
                       β 
                     
                     ) 
                   
                 
                  
                 
                   α 
                   
                     
                       - 
                       
                         e 
                         α 
                       
                     
                     - 
                     1 
                   
                 
                  
                 
                   β 
                   
                     
                       - 
                       
                         e 
                         β 
                       
                     
                     - 
                     1 
                   
                 
                  
                 
                     
                 
                  
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     k 
                   
                    
                   
                       
                   
                    
                   
                     
                       
                         ( 
                         
                           
                             s 
                             i 
                             2 
                           
                           + 
                           
                             α 
                             β 
                           
                         
                         ) 
                       
                       
                         - 
                         
                           1 
                           2 
                         
                       
                     
                      
                     
                       exp 
                       ( 
                       
                         a 
                         - 
                         
                           b 
                           
                             2 
                              
                             α 
                           
                         
                         - 
                         
                           c 
                           
                             2 
                              
                             β 
                           
                         
                         + 
                         
                           
                             1 
                             
                               2 
                                
                               α 
                             
                           
                            
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               k 
                             
                              
                             
                                 
                             
                              
                             
                               
                                 v 
                                 i 
                                 2 
                               
                               
                                 
                                   s 
                                   i 
                                   2 
                                 
                                 + 
                                 
                                   α 
                                   β 
                                 
                               
                             
                           
                         
                       
                       ) 
                     
                      
                     
                        
                       α 
                     
                      
                     
                        
                       β 
                     
                   
                 
               
             
           
         
       
     
         [0000]    where e α , e β , s b   2 , v i , a, b, c are constants and ƒ(α, β) is some function of α=σ 2 , β=λ 2  and auxiliary parameters specified by the application:
       for p(y) one takes ƒ=1.   for p (l&lt;y*&lt;h|y)  one takes       
 
         [0000]    
       
         
           
             
               f 
                
               
                 ( 
                 
                   
                     σ 
                     2 
                   
                   , 
                   
                     λ 
                     2 
                   
                 
                 ) 
               
             
             = 
             
               
                 
                   1 
                   
                     2 
                      
                     
                       p 
                        
                       
                         ( 
                         y 
                         ) 
                       
                     
                   
                 
                  
                 
                   erf 
                   ( 
                   
                     
                       u 
                       - 
                       
                         m 
                         
                           σ 
                           , 
                           λ 
                         
                       
                     
                     
                       
                         2 
                          
                         
                           v 
                           
                             σ 
                             , 
                             λ 
                           
                         
                       
                     
                   
                   ) 
                 
               
                
               
                 | 
                 
                   u 
                   = 
                   l 
                 
                 
                   u 
                   = 
                   h 
                 
               
               . 
             
           
         
       
       
         
           
             for E(y*|y) one takes 
           
         
       
     
         [0000]    
       
         
           
             
               f 
                
               
                 ( 
                 
                   
                     σ 
                     2 
                   
                   , 
                   
                     λ 
                     2 
                   
                 
                 ) 
               
             
             = 
             
               
                 1 
                 
                   p 
                    
                   
                     ( 
                     y 
                     ) 
                   
                 
               
                
               
                 
                   m 
                   
                     σ 
                     , 
                     λ 
                   
                 
                 . 
               
             
           
         
       
     
         [0063]    The quantities of interest are ratios of integrals of the form above, so the α constant in the exponent is arbitrary, and it is set later to avoid numerical problems. We describe our integration scheme for a general ƒ. In our implementation, we substitute the appropriate ƒ in place. 
         [0064]    We note that singularities in the integrand can create trouble. The singularities occur at the extremes, α=0,α=∞,β=0,β=∞, causing one or more of the factors to become infinite while another vanishes. For the problems we consider, this results in the integrand vanishing. While appropriate branches can check for the extreme value cases, overflows and underflows in computed intermediate quantities are an issue even for non-extreme values. We reformulate our integrals in a log-based form, allowing product terms to combine as sums: 
         [0000]    
       
         
           
             
               ∫ 
               0 
               ∞ 
             
              
             
               
                 ∫ 
                 0 
                 ∞ 
               
                
               
                 
                   f 
                    
                   
                     ( 
                     
                       α 
                       , 
                       β 
                     
                     ) 
                   
                 
                  
                 
                   exp 
                   ( 
                   
                     
                       
                         - 
                         
                           ( 
                           
                             
                               e 
                               α 
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                        
                       log 
                        
                       
                           
                       
                        
                       α 
                     
                     - 
                     
                       b 
                       
                         2 
                          
                         α 
                       
                     
                     - 
                     
                       
                         ( 
                         
                           
                             e 
                             β 
                           
                           + 
                           1 
                         
                         ) 
                       
                        
                       log 
                        
                       
                           
                       
                        
                       β 
                     
                     - 
                     
                       c 
                       
                         2 
                          
                         β 
                       
                     
                   
                   ) 
                 
                 × 
                 
                   exp 
                   ( 
                   
                     
                       
                         - 
                         
                           1 
                           2 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           k 
                         
                          
                         
                             
                         
                          
                         
                           log 
                           ( 
                           
                             
                               s 
                               i 
                               2 
                             
                             + 
                             
                               α 
                               β 
                             
                           
                           ) 
                         
                       
                     
                     + 
                     
                       
                         1 
                         
                           2 
                            
                           α 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           k 
                         
                          
                         
                             
                         
                          
                         
                           
                             v 
                             i 
                             2 
                           
                           
                             
                               s 
                               i 
                               2 
                             
                             + 
                             
                               α 
                               β 
                             
                           
                         
                       
                     
                   
                   ) 
                 
                  
                 
                     
                 
                  
                 
                    
                   α 
                 
                  
                 
                     
                 
                  
                 
                   
                      
                     β 
                   
                   . 
                 
               
             
           
         
       
     
         [0000]    In the integrals above, the separation of factors into separate exponentials is only a typesetting consideration. In our implementation, we have used a single exponentiation. 
         [0065]    We compactify the region of integration with the following substitutions: 
         [0000]    
       
         
           
             
               α 
               = 
               
                 
                   α 
                   p 
                 
                  
                 
                   
                     1 
                     + 
                     χ 
                   
                   
                     1 
                     - 
                     χ 
                   
                 
               
             
             , 
             
               
                 d 
                  
                 
                     
                 
                  
                 α 
               
               = 
               
                 
                   
                     2 
                      
                     
                       α 
                       p 
                     
                   
                   
                     
                       ( 
                       
                         1 
                         - 
                         χ 
                       
                       ) 
                     
                     2 
                   
                 
                  
                 d 
                  
                 
                     
                 
                  
                 χ 
               
             
           
         
       
       
         
           
             
               β 
               = 
               
                 
                   β 
                   p 
                 
                  
                 
                   
                     1 
                     + 
                     η 
                   
                   
                     1 
                     - 
                     η 
                   
                 
               
             
             , 
             
               
                 d 
                  
                 
                     
                 
                  
                 β 
               
               = 
               
                 
                   
                     2 
                      
                     
                       β 
                       p 
                     
                   
                   
                     
                       ( 
                       
                         1 
                         - 
                         η 
                       
                       ) 
                     
                     2 
                   
                 
                  
                 d 
                  
                 
                     
                 
                  
                 η 
               
             
           
         
       
     
         [0000]    with x·η∈[−1, 1]. This is a typical practice for computing improper integrals that is discussed, for example, in Burden and Faires.  Numerical Analysis.  Brooks/Cole, seventh edition, 2004, which is incorporated herein by reference. Thus substituted, the integrals become 
         [0000]    
       
         
           
             
               ∫ 
               
                 - 
                 1 
               
               1 
             
              
             
               
                 ∫ 
                 
                   - 
                   1 
                 
                 1 
               
                
               
                 
                   f 
                   ( 
                   
                     
                       
                         α 
                         p 
                       
                        
                       
                         
                           1 
                           + 
                           χ 
                         
                         
                           1 
                           - 
                           χ 
                         
                       
                     
                     , 
                     
                       
                         β 
                         p 
                       
                        
                       
                         
                           1 
                           + 
                           η 
                         
                         
                           1 
                           - 
                           η 
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   exp 
                    
                   
                     ( 
                     a 
                     ) 
                   
                 
                 × 
                 
                   exp 
                   ( 
                   
                       
                   
                    
                   
                     
                       
                         - 
                         
                           e 
                           α 
                         
                       
                        
                       log 
                        
                       
                           
                       
                        
                       
                         α 
                         p 
                       
                     
                     - 
                     
                       
                         ( 
                         
                           
                             e 
                             α 
                           
                           + 
                           1 
                         
                         ) 
                       
                        
                       
                         log 
                          
                         
                           ( 
                           
                             1 
                             + 
                             χ 
                           
                           ) 
                         
                       
                     
                     + 
                     
                       
                         ( 
                         
                           
                             e 
                             α 
                           
                           - 
                           1 
                         
                         ) 
                       
                        
                       
                         log 
                          
                         
                           ( 
                           
                             1 
                             - 
                             χ 
                           
                           ) 
                         
                       
                     
                     - 
                     
                       
                         b 
                          
                         
                           ( 
                           
                             1 
                             - 
                             χ 
                           
                           ) 
                         
                       
                       
                         2 
                          
                         
                           
                             α 
                             p 
                           
                            
                           
                             ( 
                             
                               1 
                               + 
                               χ 
                             
                             ) 
                           
                         
                       
                     
                   
                   ) 
                 
                 × 
                 
                   exp 
                   ( 
                   
                       
                   
                    
                   
                     
                       
                         - 
                         
                           e 
                           β 
                         
                       
                        
                       log 
                        
                       
                           
                       
                        
                       
                         β 
                         p 
                       
                     
                     - 
                     
                       
                         ( 
                         
                           
                             e 
                             β 
                           
                           + 
                           1 
                         
                         ) 
                       
                        
                       
                         log 
                          
                         
                           ( 
                           
                             1 
                             + 
                             η 
                           
                           ) 
                         
                       
                     
                     + 
                     
                       
                         ( 
                         
                           
                             e 
                             β 
                           
                           - 
                           1 
                         
                         ) 
                       
                        
                       
                         log 
                          
                         
                           ( 
                           
                             1 
                             - 
                             η 
                           
                           ) 
                         
                       
                     
                     - 
                     
                       
                         c 
                          
                         
                           ( 
                           
                             1 
                             - 
                             η 
                           
                           ) 
                         
                       
                       
                         2 
                          
                         
                           
                             β 
                             p 
                           
                            
                           
                             ( 
                             
                               1 
                               + 
                               η 
                             
                             ) 
                           
                         
                       
                     
                   
                   ) 
                 
                 × 
                 
                   exp 
                   ( 
                   
                     
                       
                         - 
                         
                           1 
                           2 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           k 
                         
                          
                         
                             
                         
                          
                         
                           log 
                            
                           
                             ( 
                             
                               
                                 s 
                                 i 
                                 2 
                               
                               + 
                               
                                 
                                   
                                     
                                       α 
                                       p 
                                     
                                      
                                     
                                       ( 
                                       
                                         1 
                                         + 
                                         χ 
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       1 
                                       - 
                                       η 
                                     
                                     ) 
                                   
                                 
                                 
                                   
                                     
                                       β 
                                       p 
                                     
                                      
                                     
                                       ( 
                                       
                                         1 
                                         + 
                                         η 
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       1 
                                       - 
                                       χ 
                                     
                                     ) 
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                     + 
                     
                       
                         
                           1 
                           - 
                           χ 
                         
                         
                           2 
                            
                           
                             
                               α 
                               p 
                             
                              
                             
                               ( 
                               
                                 1 
                                 + 
                                 χ 
                               
                               ) 
                             
                           
                         
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           k 
                         
                          
                         
                             
                         
                          
                         
                           
                             v 
                             i 
                             2 
                           
                           
                             
                               s 
                               i 
                               2 
                             
                             + 
                             
                               
                                 
                                   
                                     α 
                                     p 
                                   
                                    
                                   
                                     ( 
                                     
                                       1 
                                       + 
                                       χ 
                                     
                                     ) 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     1 
                                     - 
                                     η 
                                   
                                   ) 
                                 
                               
                               
                                 
                                   
                                     β 
                                     p 
                                   
                                    
                                   
                                     ( 
                                     
                                       1 
                                       + 
                                       η 
                                     
                                     ) 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     1 
                                     - 
                                     χ 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                   ) 
                 
                  
                 
                     
                 
                  
                 
                    
                   χ 
                 
                  
                 
                   
                      
                     η 
                   
                   . 
                 
               
             
           
         
       
     
         [0066]    This form of the integrals is computed by the low-dimensional numerical integration library libcubature, as described by Johnson and Brown. libcubature, 2005, available at http://wwar.phy.duke.edu/˜rgb/libcubature—0.1.0.tgz., which is incorporated herein by reference, which is based on the Genz-Malik embedded cubature rule described in Gene and Malik. An adaptive algorithm for numerical integration over an n-dimensional rectangular region.  J. of Comp. and Appl. Math.,  6:295-302, 1980, which is also incorporated herein by reference. (It is noted that a simpler tool such as Matlab&#39;s dblquad function is not sufficient for this task, and will lead to integrals which either do not converge or are orders of magnitude slower.) This computation is an adaptive routine which computes a trial integral from the sum of points in the center and corners of the integration region, and then refines this estimate according a local error estimate based on additional function evaluations. One pathology of such schemes is that if the first N (for some N) sampled values of the integrand are exactly 0, the algorithm has no sensible choice but to conclude that the integrand is the 0 function and return 0. This is a substantial problem for our p(y) integral, since concentration of probability mass is something to be expected in certain regimes. We take advantage of the fact that in libcubature, the first point probed is always the center of the integration region (x=η=0). 
         [0067]    There are three arbitrary parameters in our formulation, the substitution parameters α p , β p &gt;0 (the integrals are independent of their values) and α (its contribution vanishes when ratios are taken). We fix these values by taking (α p , β p ) to be the minimizer of 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       - 
                       
                         e 
                         α 
                       
                     
                      
                     log 
                      
                     
                         
                     
                      
                     α 
                   
                   - 
                   
                     b 
                     
                       2 
                        
                       α 
                     
                   
                   - 
                   
                     
                       e 
                       β 
                     
                      
                     log 
                      
                     
                         
                     
                      
                     β 
                   
                   - 
                   
                     c 
                     
                       2 
                        
                       β 
                     
                   
                   - 
                   
                     
                       1 
                       2 
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         k 
                       
                        
                       
                           
                       
                        
                       
                         log 
                         ( 
                         
                           
                             s 
                             i 
                             2 
                           
                           + 
                           
                             α 
                             β 
                           
                         
                         ) 
                       
                     
                   
                   + 
                   
                     
                       1 
                       
                         2 
                          
                         α 
                       
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         k 
                       
                        
                       
                           
                       
                        
                       
                         
                           v 
                           i 
                           2 
                         
                         
                           
                             s 
                             i 
                             2 
                           
                           + 
                           
                             α 
                             β 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    which ensures that the value of the non-ƒ part of the integrand is as large as possible at x=η=0. We set a to be the minimum value of (1), which has the effect of avoiding numerical over/underflows by providing a natural scale in the exponent. 
         [0068]    We can compute p(y), E(y*|y), or p(l&lt;y*&lt;h) with a single integral. We can compute functions of the cumulative distribution function (CDF), such as the median or a confidence interval by computing multiple integrals and using a secant search. 
       7. Comparison to Related Work 
       [0069]    The Bayesian linear regression (BLR) model disclosed herein is linked to the non-Bayesian regularized least squares (RLS) algorithm, where w is found via minimization: 
         [0000]    
       
         
           
             
               
                 min 
                 
                   w 
                   ∈ 
                   
                     ℝ 
                     d 
                   
                 
               
                
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                     
                 
                  
                 
                   
                     ( 
                     
                       
                         y 
                         i 
                       
                       - 
                       
                         
                           x 
                           i 
                         
                          
                         w 
                       
                     
                     ) 
                   
                   2 
                 
               
             
             + 
             
               
                 1 
                 2 
               
                
               
                 λ 
                 RLS 
               
                
               
                 
                   
                      
                     w 
                      
                   
                   2 
                 
                 . 
               
             
           
         
       
     
         [0000]    It is well-known that w can be found by solving a k dimensional system of equations; thus the mathematics are omitted here. After taking an singular value decomposition of X (in O(ndk) time), we can find the w for an arbitrary value of λ RLS  in only O(kd) time. Furthermore, we can also compute the vector of leave-one-out errors in O(n 2 d) time, via the formula: 
         [0000]    
       
         
           
             LOOE 
             = 
             
               
                 
                   
                     ( 
                     
                       
                         XX 
                         t 
                       
                       + 
                       
                         
                           λ 
                           RLS 
                         
                          
                         I 
                       
                     
                     ) 
                   
                    
                   y 
                 
                 
                   diag 
                    
                   
                     ( 
                     
                       
                         XX 
                         t 
                       
                       + 
                       
                         
                           λ 
                           RLS 
                         
                          
                         I 
                       
                     
                     ) 
                   
                 
               
               . 
             
           
         
       
     
         [0070]    In other words, if n&lt;d, we can optimize the leave-one-out error over the regularization parameter λ RLS  essentially the same amount of time it takes to construct a w for a single value of λ RLS . In the Bayesian model presented herein, performing the singular value decomposition up front means that we can evaluate the Bayesian Linear Regression integrand for a single value of the parameters σ 2  and λ 2  in O(k) time. As described in the next section, the regularized least-squares regularization parameter λ RLS  plays essentially the same role as the ratio σ 2 /λ 2  in our Bayesian linear regression model disclosed herein. 
         [0071]    In Gelman, Carlin, Stem, and Rubin.  Bayesian Data Analysis.  Chapman &amp; Hall/CRC, second edition, 2004, (Sections 14.1-14.5), Gelman et al. consider an alternate fully Bayesian model of linear regression. In the terminology of this description, they remove the scale parameter λ which controls the norm of w, and choose a noninformative scale prior over noise levels: 
         [0000]      p(w, σ 2 )∝σ −2 . 
         [0000]    This model has the advantage that it is fully analytically tractable. The posterior prediction for a new point p(y)*|y) is a multivariate t distribution with center X(X t X) −1 X t y and n−d degrees of freedom. The model works best when n&gt;&gt;d, and the posterior becomes improper when d&lt;n, so this model is not suited to machine learning situations with many variables relative to the number of examples. The mean prediction under this model is the same as the prediction made by ordinary (unregularized) least squares (OLS). 
         [0072]    All the algorithms discussed here require O(  k k 2 ) time upfront to manipulate the training data. For OLS or RLS, we can regress a new point in O(d) time. For the Bayesian linear regression model disclosed herein, we need to perform O(dk) work upfront (to form x*G σ,λ   −1 X t y), then perform a two-dimensional integral where the integrand takes O(k) time to evaluate. 
       8. Experiments 
       [0073]    We compare OLS (which is equivalent to the Gelman model when n&gt;d), RLS, and the Bayesian linear regression model described herein (BLR) on a regression task, the pumadyn-8 nm dataset, provided by Zoubin Ghahramani, at 
         [0000]    http://www.cs.toronto.edu/ ˜ delve/data/pumadyn/desc.html. The pumadyn-8 nm dataset is one of eight datasets in the pumadyn family. All of the datasets are variations on a realistic simulation of the dynamics of a Puma 560 robot arm. The task in analyzing these datasets is to predict the angular acceleration of one of the robot arm&#39;s links based on the inputs including angular positions, velocities and torques of the robot arm. The pumadyn-8 nm dataset includes 8 inputs, it is non-linear, and it has medium unpredictability/noise. The data consists of 8192 examples in 8 dimensions. Because the task (predicting the angular acceleration of a robot arm link) is known to be nonlinear, we “lift” the 8 dimensional data by taking second and third degree polynomial features, resulting in a 164 dimensional input space. We constructed 50 random permutations of the dataset. For each permutation, we took a test set of 1024 points, and nested training sets of 8, 16, 32, 64, 128, 256, 512, and 1024 points. 
         [0074]      FIG. 3  shows the average mean-square error of OLS, RLS, and BLR methods, averaged over the 50 replications, and a one standard deviation interval on each side of the average. For large training set sizes, the methods perform equivalently. The OLS method performs very poorly for small training set sizes, overfitting badly, which leads to a high average mean-square error. RLS and BLR are comparable over the entire range. There is some evidence that BLR is slightly more accurate with very few data points. This is plausible, because BLR is averaging over all hypotheses according to their likelihood, rather than being forced to commit to a single regularization constant. 
         [0075]      FIG. 4A  shows the prior distribution for σ 2  and λ 2 , in accordance with one embodiment.  FIGS. 4B-D  shows the posterior distributions after training with 16, 128, and 1024 points (for a single realization), respectively. As the training sets increase in size, the posterior becomes progressively more sharply peaked. 
         [0076]    As discussed above in Section 7, there is a close relationship between λ RLS , the regularization parameter for regularized least squares, and the ratio σ 2 /λ 2  in BLR. In  FIGS. 5A-H , it is shown that for small training set sizes, BLR tends to focus attention on ratios of σ 2 /λ 2  that would have small LOO errors were they are used as λ RLS . For large training set sizes, all regularizers up to some critical value have close to optimal LOO errors, and BLR tends to concentrate around this critical point. Both algorithms automatically choose smaller amounts of regularization as the training set size increases. At test time, the algorithm is orders of magnitude slower than OLS or RLS, but fast enough to be usable, especially with small training sets. In our experiment, when n=8, testing cost 0.0012 seconds per data point. The testing costs are roughly linear in n for n&lt;d, and essentially constant for n&gt;d. 
         [0077]    Thus, it is shown that the fully Bayesian model for linear regression is well suited to scenarios with many dimensions and few examples. We have shown empirically how the data causes a vague hyperparameter prior to become peaked around desirable values. Our method relies on a combination of techniques: numerical integration to explicitly integrate over the hyperparameters and the SVD to make evaluating the integrand fast. Our method is orders of magnitude slower at evaluating new test points than methods that estimate the posterior as a delta function. However, it is fast enough to use, especially if only a few data points are available, and we retain the key advantages of a fully Bayesian treatment: we can obtain confidence intervals in a principled way, and easily minimize the expected regret under an arbitrary loss function. 
         [0078]    Reference in the specification to “one embodiment” or to “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiments is included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment. 
         [0079]    Some portions of the detailed description that follows are presented in terms of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of steps (instructions) leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical, magnetic or optical signals capable of being stored, transferred, combined, compared and otherwise manipulated. It is convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like. Furthermore, it is also convenient at times, to refer to certain arrangements of steps requiring physical manipulations of physical quantities as modules or code devices, without loss of generality. 
         [0080]    However, all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussion, it is appreciated that throughout the description, discussions utilizing terms such as “determining” or “computing” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system memories or registers or other such information storage, transmission or display devices. 
         [0081]    Certain aspects of the present invention include process steps and instructions described herein in the form of an algorithm. It should be noted that the process steps and instructions of the present invention could be embodied in software, firmware or hardware, and when embodied in software, could be downloaded to reside on and be operated from different platforms used by a variety of operating systems. 
         [0082]    The present invention also relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computer selectively activated or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a computer readable storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, application specific integrated circuits (ASICs), or any type of media suitable for storing electronic instructions, and each coupled to a computer system bus. Furthermore, the computers referred to in the specification may include a single processor or may be architectures employing multiple processor designs for increased computing capability. 
         [0083]    The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus. Various general-purpose systems may also be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear from the description below. In addition, the present invention is not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the present invention as described herein, and any references below to specific languages are provided for disclosure of enablement and best mode of the present invention. 
         [0084]    In addition, the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.