Abstract:
A method for performing structured learning for high-dimensional discrete graphical models includes estimating a high-order interaction neighborhood structure of each visible unit or a Markov blanket of each unit; once a high-order interaction neighborhood structure of each visible unit is identified, adding corresponding energy functions with respect to the high-order interaction of that unit into an energy function of High-order BM (HBM); and applying Maximum-Likelihood Estimation updates to learn the weights associated with the identified high-order energy functions. The system can effectively identify meaningful high-order interactions between input features for system output prediction, especially for early cancer diagnosis, biomarker discovery, sentiment analysis, automatic essay grading, Natural Language Processing, text summarization, document visualization, and many other data exploration problems in Big Data.

Description:
[0001]    The present application claims priority to Provisional Application Serial 61/811,443 filed 4122013, the content of which is incorporated by reference. 
     
    
     BACKGROUND 
       [0002]    Identifying high-order feature interactions is an important problem in machine learning and effective solutions to this problem have a large set of use scenarios. Particularly, in biomedical applications, interactions among multiple proteins play critical roles in many biological processes, and thus the identification of such high-order interactions itself becomes critical. Theoretically, fully-observable high-order Boltzmann Machines (HBM) are capable of identifying explicit high-order feature interactions. However, they have never been applied to any real problems because they have too many energy terms even for a fair number of features and the learning procedure is prohibitively slow. 
       SUMMARY 
       [0003]    In one aspect, a method for performing structured learning for high-dimensional discrete graphical models includes estimating a high-order interaction neighborhood structure of each visible unit or a Markov blanket of each unit; once a high-order interaction neighborhood structure of each visible unit is identified, adding corresponding energy functions with respect to the high-order interaction of that unit into an energy function of High-order BM (HBM); and applying Maximum-Likelihood Estimation updates to learn the weights associated with the identified high-order energy functions. 
         [0004]    In another aspect, an interpretable Sparse High-order Boltzmann Machine (SHBM) can be used with an efficient learning algorithm to learn an SHBM for Big-Data problems. The energy function of an HBM as in to have a combination of different orders of feature interactions up to a maximum order allowed. Sparsity constraints can be used on the feature interaction terms so as to construct a sparse model. The learning algorithm for SHBM can be decoupled into two steps: high-order interaction neighborhood estimation and interaction weight learning. An efficient sparse high-order logistic regression method, denoted as shooter, can be used for identifying interpretable high-order feature interactions and thus to determine the energy function of an SHBM. The shooter method greedily explores the structures among feature interactions via solving a set of l 1 -regularized logistic regression problems. Significant speed-up is enabled by organizing the search space within a tree structure as well as a block-wise expansion of the possible interactions conforming to the tree. Given the energy function determined by shooter, different sampling algorithms can be used that scale to large number of features and interactions in order to finally learn the interaction weights within an SHBM. 
         [0005]    Advantages of the system may include one or more of the following. Tests on both large synthetic and real datasets demonstrate that SHBM and its sub-routine shooter can effectively identify problem-inherent high-order feature interactions in large-scale settings, which has great potential to be applied to many Big-Data problems. The system can effectively identify meaningful high-order interactions between input features for system output prediction, especially for early cancer diagnosis, biomarker discovery, sentiment analysis, automatic essay grading, and other Natural Language Processing problems. The system is scalable to huge-dimensional datasets that are common in biomedical applications, information retrieval and Natural Language Processing. The system can be used for text summarization, document visualization, and many other data exploration problems in Big Data. The system can be used for graphical text summarization, where documents are represented with a graph, in which nodes correspond to discriminative words or phrases identified by the system, and interactions between nodes correspond to essential word or phrase interactions identified by the system. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0006]      FIG. 1  shows an exemplary process for identifying Interpretable High-Order Feature Interactions and for System Output Prediction. 
           [0007]      FIG. 2  shows an exemplary computer for identifying Interpretable High-Order Feature Interactions and for System Output Prediction. 
       
    
    
     DESCRIPTION 
       [0008]      FIG. 1  shows an efficient approach for learning a fully-observable high-order Boltzmann Machine based on sparse learning and contrastive divergence, resulting in an interpretable Sparse High-order Boltzmann Machine, denoted as SHBM. Experimental results on synthetic datasets and a real dataset demonstrate that SHBM can produce higher pseudo-log-likelihood and better reconstructions on test data than the state-of-the-art methods. In addition, we apply SHBM to a challenging bioinformatics problem of discovering complex Transcription Factor interactions. Compared to conventional Boltzmann Machine and directed Bayesian Network, SHBM can identify much more biologically meaningful interactions that are supported by recent biological studies. SHBM is the first working Boltzmann Machine with explicit high-order feature interactions applied to real-world problems. 
         [0009]    Turning now to  FIG. 1 , the system first receives multivariate categorical vectors such as chip-sequential signals for transcription factors or geneprotein expression signals from a microarray for tumor or blood samples ( 10 ). Next, the process performs unsupervised structure learning in graphical models as well as a discriminative high-order feature selection ( 20 ). In  20 , the process also optimizes the model with a Greedy Sparse High-Order Logistic Regression ( 30 ). In  30 , the process checks if i equals 1, then L1-regularized logistic regression is used to identify an i-th order discriminative input feature (0), and i is auto-incremented (1). Next, in 2, the process  30  multiplies each discriminative feature by all the other features to obtain i+1 order features. The process then concatenates all previously chosen features and the i+1 order features into a long feature vector. The process  30  may also split newly added features into uniformly distributed blocks ( 2 ). Next, the process  30  runs L1-penalized logistic regression to select a discriminative i+1 order features. The process then checks if a stopping criterion has been satisfied and if not, loops back to step 1 and otherwise exits. 
         [0010]    In one embodiment called Sparse High-Order IOgisTicrEgRession (SHOOTER) for both supervised discriminative high-order feature interaction identification (feature selection) and unsupervised feature interaction identification (structure learning in Graphical Models). We will describe SHOOTER for feature selection first. Given a dataset containing data samples with input feature vector x and discrete output target variable y (we will use binary target variable as a running example and the extension to a discrete case is simple), we want to identify single input features and high-order polynomial terms that are products of single feature values predictive of target variable. The search space containing an possible combinations of single features and high-order polynomial features is exponential in the number of input features, so we cannot solve this problem in a brute force way. In SHOOTER, we adopt a greedy approach I:tased on L1-regularized logistic regression. We use L1-regularized logistic regression to identify first-order discriminative input features first: then we multiply each of these first-order features by any other feature to obtain second-order features: concatenating all the first-order features and second-order features into a long feature vector, we run L1-penalized logistic regression again to select discriminative second-order features without penalizing first-order features; and we repeat this process until we reach the specified maximum order of feature interactions or we cannot improve the average conditional log-likelihood of the target variable given input features. We use a tree data structure to help our greedy feature selection, and we use Projected Scaled Sub-Gradient method to efficiently solve L1-regularized logistic regression 
         [0011]    For unsupervised structure learning in Graphical Models, specifically for learning the structure of Sparse High-Order Boltzmann Machine, we transform the joint log-likelihood maximization problem into a pseudo log-likelihood maximization problem, and we use SHOOTER to identify the high-order neighborhood of each variable separately, and then we use contrastive divergence based on damped mean-field updates or prolonged Gibb sampling to learn the parameters associated with first-order and high-order energy terms. 
         [0012]    Extension of SHOOTER to model discrete target variable is simple: instead of using L1-penalized logistic regression, we use L1-penalized multinomial logistic regression. 
         [0013]    Before we detail our implementation of the invention, a review of traditional fully observable Boltzmann Machines (BMs) and High-order BM (HBMs) is discussed next. A fully-observable BM is an undirected graphical model with symmetric connections between p visible units vε{0,1}. The joint probability distribution of a configuration v is defined as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       p 
                        
                       
                         ( 
                         v 
                         ) 
                       
                     
                     = 
                     
                       
                         1 
                         Z 
                       
                        
                       
                         exp 
                          
                         
                           ( 
                           
                             - 
                             
                               E 
                                
                               
                                 ( 
                                 v 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where Z=Σ u exp(−E(u)) is the partition function. The energy E(v) is defined as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       - 
                       
                         E 
                          
                         
                           ( 
                           v 
                           ) 
                         
                       
                     
                     = 
                     
                       
                         
                           ∑ 
                           ij 
                           
                               
                           
                         
                          
                         
                           
                             W 
                             ij 
                           
                            
                           
                             v 
                             i 
                           
                            
                           
                             v 
                             j 
                           
                         
                       
                       + 
                       
                         
                           ∑ 
                           i 
                           
                               
                           
                         
                          
                         
                           
                             b 
                             i 
                           
                            
                           
                             v 
                             i 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where b i  is the bias on unit v i , and W ij  is the connection weight between unit v i  and v j . The weights are updated via maximizing the log-likelihood of the observed input data using the following gradient descent 
         [0000]      Δ W   ij =ε(           v   j   v   j           −           v   i   v   j             ∞ ),
 
         [0000]    where is the learning rate,          •           data  is the expectation with respect to the data distribution and          •           ∞  is the expectation with respect to the model distribution. 
         [0014]    BMs are conventionally used to model pairwise interactions between input features. They have been extended in to model high-order interactions by incorporating higher-order energy functions. For example, the quadratic energy function as in eqn:bme can be replaced by a sum of energy functions with orders from 1 to m as follows: 
         [0000]    
       
         
           
             
               
                 - 
                 
                   E 
                    
                   
                     ( 
                     v 
                     ) 
                   
                 
               
               = 
               
                 
                   ∑ 
                   
                     j 
                     = 
                     1 
                   
                   m 
                 
                  
                 
                   
                     ∑ 
                     
                       
                         i 
                         1 
                       
                        
                       
                         i 
                         
                           2 
                            
                           
                               
                           
                         
                       
                        
                       … 
                        
                       
                           
                       
                        
                       
                         i 
                         j 
                       
                     
                     
                         
                     
                   
                    
                   
                     
                       W 
                       
                         
                           i 
                           1 
                         
                          
                         
                           i 
                           
                             2 
                              
                             
                                 
                             
                           
                         
                          
                         … 
                          
                         
                             
                         
                          
                         
                           i 
                           j 
                         
                       
                     
                      
                     
                       v 
                       
                         i 
                         1 
                       
                     
                      
                     
                       v 
                       
                         i 
                         
                           2 
                            
                           
                               
                           
                         
                       
                     
                      
                     … 
                      
                     
                         
                     
                      
                     
                       v 
                       
                         i 
                         j 
                       
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where W i     1     i     2     . . . i     j    is the weight for the order-j interaction among units v i     1   , v i     2   , . . . , and v i     j   . The derived model is the so-called High-order Boltzmann Machine (HBM), and its learning rule with respect to order-j interactions correspondingly becomes 
         [0000]      Δ W   i     1     i     2     . . . i     j   =ε(           v   i     1     v   i     2      . . . v   i     j               data −           v   i     1     v   i     2      . . . v   i     j               ∞ ).  (3)
 
         [0000]    However, due to the painfully slow Gibbs Sampling procedure to get samples from the model distribution, HBMs have never been applied to any interesting practical problems. 
         [0015]    Next, details in one of our methods for solving HBMs with sparsity constraint are discussed. In practice, it is typically infeasible for HBMs to include all possible energy functions of different orders. Thus, we need to perform structure learning, which is a challenging task for high-dimensional discrete graphical models. Following, the structure learning of HBMs could be conducted by minimizing the following l 1 -regularized negative log-likelihood 
         [0000]    
       
         
           
             
               
                 min 
                 w 
               
                
               
                 E 
                  
                 
                   ( 
                   v 
                   ) 
                 
               
             
             + 
             
               log 
                
               
                   
               
                
               Z 
             
             + 
             
               λ 
                
               
                 
                   
                      
                     W 
                      
                   
                   1 
                 
                 . 
               
             
           
         
       
     
         [0000]    That is, we constrain the HBM to have only a sparse set of all possible high-order interactions. However, calculating the above negative log-likelihood and its gradient is intractable. To address this, we convert the problem of minimizing the negative log-likelihood of observed data into that of minimizing the negative pseudo log-likelihood as proposed in. Specifically, we solve the following optimization function 
         [0000]    
       
         
           
             
               
                 
                   min 
                   W 
                 
                  
                 
                   
                     ∑ 
                     i 
                     
                         
                     
                   
                    
                   
                     log 
                      
                     
                         
                     
                      
                     
                       p 
                        
                       
                         ( 
                         
                           
                             
                               v 
                               i 
                             
                              
                             
                               v 
                               
                                 - 
                                 i 
                               
                             
                           
                           , 
                           W 
                         
                         ) 
                       
                     
                   
                 
               
               + 
               
                 λ 
                  
                 
                   
                      
                     W 
                      
                   
                   1 
                 
               
             
             , 
           
         
       
     
         [0000]    where v −i  is the set of visible units except v i . Essentially, the above optimization takes the form of a set of l 1 -regularized logistic regression problems that are not independent due to the shared parameters W. 
         [0016]    Due to the extremely large space of the parameters for the high-order interactions, we approximate the above pseudo log-likelihood further by utilizing a strategy proposed by Wainwright and propose the following decoupled 2-step method for learning a Sparse High-order Boltzmann Machine, denoted as SHBM. 
         [0017]    Step 1: high-order interaction neighborhood estimation: 
         [0018]    we first estimate the high-order interaction neighborhood structure of each visible unit, i.e., the Markov blanket of each unit. We formulate this problem as a high-order feature selection problem and propose a learning algorithm, denoted as shooter, as described in Section 3.2. In particular, for each visible unit (i.e., each feature), we consider a regression problem from all the other visible units and their high-order interactions. 
         [0019]    Step 2: SHBM weight learning: 
         [0020]    Once the high-order interaction neighborhood structure of each visible unit is identified, we add the corresponding energy functions with respect to the high-order interaction of that unit into the energy function of HBM. Then we use Maximum-Likelihood Estimation updates as in Equation 3 to learn the weights associated with the identified high-order energy functions, which requires drawing samples from the model distribution. In Section 4, we present Gibbs Sampling and Mean-Field updates for obtaining samples. Instead of drawing samples exactly from the equilibrium model distribution, we only perform sampling a few steps and use Contrastive Divergence (CD) to update the weights. 
         [0021]    Sparse High-Order Logistic Regression for SHBM is detailed next. First, we provide a brief overview of l 1 -regularized Logistic Regression. Given a dataset of n data points {x i , y i }, where x i εR p , y i ε{+1,−1}, and i=1, . . . , n, l 1 -regularized Logistic Regression, denoted as l 1 -LR, seeks a classification function ƒ(w,b) by solving the following t i -regularized optimization problem: 
         [0000]    
       
         
           
             
               
                 
                   min 
                   
                     w 
                     , 
                     b 
                   
                 
                  
                 
                   f 
                    
                   
                     ( 
                     
                       w 
                       , 
                       b 
                     
                     ) 
                   
                 
               
               = 
               
                 
                   
                     min 
                     
                       w 
                       , 
                       b 
                     
                   
                    
                   
                     L 
                      
                     
                       ( 
                       
                         w 
                         , 
                         b 
                       
                       ) 
                     
                   
                 
                 + 
                 
                   λ 
                    
                   
                     
                        
                       w 
                        
                     
                     1 
                   
                 
               
             
             , 
             
               
 
             
              
             where 
           
         
       
       
         
           
             
               
                 L 
                  
                 
                   ( 
                   
                     w 
                     , 
                     b 
                   
                   ) 
                 
               
               = 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                   log 
                    
                   
                     ( 
                     
                       1 
                       + 
                       
                         exp 
                          
                         
                           ( 
                           
                             - 
                             
                               
                                 y 
                                 i 
                               
                                
                               
                                 ( 
                                 
                                   
                                     
                                       w 
                                       T 
                                     
                                      
                                     
                                       x 
                                       i 
                                     
                                   
                                   + 
                                   b 
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                     ) 
                   
                 
               
             
             , 
           
         
       
     
         [0000]    and PwP 1  is the l 1 -norm of w. The sub-differential of ƒ(w,b) with respect to w j  is 
         [0000]      ∂ j   f ( w,b )=∇ j   L ( w,b )+λsign( w   j ),  (4)
 
         [0000]    where ∇ j L(w,b) is the standard gradient of the loss function L(w,b) with respect to w j . Since the pseudo-gradient of ƒ(w,b) is the sub-differential of ƒ(w,b) at w with minimum norm, and because the sub-differential in subdiff is separable in the variables w j &#39;s, the pseudo-gradient of ƒ(w,b) with respect to each variable w j  can be calculated in a closed form. 
         [0022]    Among many algorithms solving the above optimization problem (see for a comprehensive review), Projected Scaled Sub-Gradient (PSSG) method is one of the most efficient. In specific, in PSSG, during each iteration, the weight vector w is split into two sets: a working set that contains all sufficiently non-zero weights and an active set that is the complement of the working set. Then an L-BFGS update is performed on the working set and a diagonally-scaled pseudo-gradient update is performed on the active set so as to get the descent direction d. Finally, orthant projections are applied on both sets. The orthant projection P on weight vector w with the descent direction d takes the following form: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       P 
                        
                       
                         ( 
                         
                           w 
                           + 
                           d 
                         
                         ) 
                       
                     
                     j 
                   
                   = 
                   
                     { 
                     
                       
                         
                           0 
                         
                         
                           
                             
                               
                                 
                                   ifw 
                                   j 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       w 
                                       j 
                                     
                                     + 
                                     
                                       d 
                                       j 
                                     
                                   
                                   ) 
                                 
                               
                               &lt; 
                               0 
                             
                             , 
                           
                         
                       
                       
                         
                           
                             
                               w 
                               j 
                             
                             + 
                             
                               d 
                               j 
                             
                           
                         
                         
                           
                             otherwise 
                             , 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0000]    which ensures that some weights are set to exactly 0 and the weight updates never cross points of non-differentiability. 
         [0023]    For Sparse High-Order l 1 -Regularized Logistic Regression, we extend the conventional l 1 -LR to have both single features and multiplicative feature interactions of orders up to m as predictors with l 1  regularization, and this method is denoted as sparse high-order logistic regression (shooter). The optimization problem of shooter with feature interactions of maximum order m is as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         min 
                         
                           w 
                           , 
                           b 
                         
                       
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                           log 
                            
                           
                             { 
                             
                               1 
                               + 
                               
                                 exp 
                                 [ 
                                 
                                   - 
                                   
                                     
                                       y 
                                       i 
                                     
                                     ( 
                                     
                                       
                                         
                                           ∑ 
                                           
                                             k 
                                             = 
                                             1 
                                           
                                           m 
                                         
                                          
                                         
                                           
                                             ∑ 
                                             
                                               
                                                 j 
                                                 1 
                                               
                                               &lt; 
                                               
                                                 j 
                                                 2 
                                               
                                               &lt; 
                                               
                                                   
                                               
                                                
                                               … 
                                                
                                               
                                                   
                                               
                                               &lt; 
                                               
                                                 j 
                                                 k 
                                               
                                             
                                             
                                                 
                                             
                                           
                                            
                                           
                                             
                                               w 
                                               
                                                 
                                                   j 
                                                   1 
                                                 
                                                  
                                                 
                                                   j 
                                                   
                                                     2 
                                                      
                                                     
                                                         
                                                     
                                                   
                                                 
                                                  
                                                 … 
                                                  
                                                 
                                                     
                                                 
                                                  
                                                 
                                                   j 
                                                   k 
                                                 
                                               
                                             
                                              
                                             
                                               x 
                                               i 
                                               
                                                 j 
                                                 1 
                                               
                                             
                                              
                                             
                                               x 
                                               i 
                                               
                                                 j 
                                                 2 
                                               
                                             
                                              
                                             
                                                 
                                             
                                              
                                             … 
                                              
                                             
                                                 
                                             
                                              
                                             
                                               x 
                                               i 
                                               
                                                 j 
                                                 k 
                                               
                                             
                                           
                                         
                                       
                                       + 
                                       b 
                                     
                                     ) 
                                   
                                 
                                 ] 
                               
                             
                             } 
                           
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         m 
                       
                        
                       
                         
                           λ 
                           k 
                         
                          
                         
                           
                             ∑ 
                             
                               
                                 j 
                                 1 
                               
                               &lt; 
                               
                                 j 
                                 2 
                               
                               &lt; 
                               
                                   
                               
                                
                               … 
                                
                               
                                   
                               
                               &lt; 
                               
                                 j 
                                 k 
                               
                             
                             
                                 
                             
                           
                            
                           
                              
                             
                               w 
                               
                                 
                                   j 
                                   1 
                                 
                                  
                                 
                                   j 
                                   2 
                                 
                                  
                                 
                                   …j 
                                   k 
                                 
                               
                             
                              
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where x l   j  denotes the j-th feature of x i . Solving the problem in eqn:shooter directly is intractable even for fair feature set size p and small interaction order m (e.g. p=500, m=6). Thus, we propose a greedy block-wise optimization method to solve eqn:shooter. 
         [0024]    We decompose the above problem into several sub-problems and solve the sub-problems greedily from the lowest order  1  up to the maximum order m as follows. 
         [0025]    Step 1: 
         [0026]    First, we denote the set of all the single features as F 0   (1) , that is, 
         [0000]    
       
      
       F 
       0 
       (1) 
       ={x 
       j 
       |∀j} 
      
     
         [0000]    We use PSSG to solve the optimization problem as in Equation 7. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       min 
                       
                         
                           w 
                           
                             ( 
                             1 
                             ) 
                           
                         
                         , 
                         
                           b 
                           
                             ( 
                             1 
                             ) 
                           
                         
                       
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         n 
                       
                        
                       
                         log 
                          
                         
                           { 
                           
                             1 
                             + 
                             
                               exp 
                               [ 
                               
                                 - 
                                 
                                   
                                     y 
                                     i 
                                   
                                   ( 
                                   
                                     
                                       
                                         ∑ 
                                         
                                           
                                             x 
                                             i 
                                             j 
                                           
                                           ∈ 
                                           
                                             F 
                                             0 
                                             
                                               ( 
                                               1 
                                               ) 
                                             
                                           
                                         
                                         
                                             
                                         
                                       
                                        
                                       
                                         
                                           w 
                                           j 
                                           
                                             ( 
                                             1 
                                             ) 
                                           
                                         
                                          
                                         
                                           x 
                                           i 
                                           j 
                                         
                                       
                                     
                                     + 
                                     
                                       b 
                                       
                                         ( 
                                         1 
                                         ) 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               ] 
                             
                           
                           } 
                         
                       
                     
                   
                   + 
                   
                     
                       λ 
                       1 
                     
                      
                     
                       
                         ∑ 
                         
                           
                             x 
                             i 
                             j 
                           
                           ∈ 
                           
                             F 
                             0 
                             
                               ( 
                               1 
                               ) 
                             
                           
                         
                         
                             
                         
                       
                        
                       
                         
                            
                           
                             w 
                             j 
                             
                               ( 
                               1 
                               ) 
                             
                           
                            
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The discriminative single features are identified as the ones which have non-zero weights w j   (1)  across all the data points. We denote this set of identified single features by F (1) , that is, 
         [0000]        F   (1)   ={x   j   |x   j   εF   0   (1) ,w j   (1) ≠0}, where  j= 1, . . . ,p 1   ,p   1   =|F   (1) |.
 
         [0027]    Step 2: 
         [0028]    We multiply each discriminative feature in F (1)  with all the rest p−1 single features in F 0   (1)  to construct the set of all possible second-order feature interactions F 0   (2) , that is 
         [0000]        F   0   (2)   ={x   j     1     x   j     2     |x   j     1     εF   (1)   ,x   j     2     εF   0   (1)   ,j   1   ≠j   2 } 
         [0000]    We solve the optimization problem as in Equation 8 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       min 
                       
                         
                           w 
                           
                             ( 
                             2 
                             ) 
                           
                         
                         , 
                         
                           b 
                           
                             ( 
                             2 
                             ) 
                           
                         
                       
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         n 
                       
                        
                       
                         log 
                          
                         
                           { 
                           
                             1 
                             + 
                             
                               exp 
                               [ 
                               
                                 - 
                                 
                                   
                                     y 
                                     i 
                                   
                                   ( 
                                   
                                     
                                       
                                         ∑ 
                                         
                                           
                                             x 
                                             i 
                                             
                                               j 
                                               1 
                                             
                                           
                                           ∈ 
                                           
                                             F 
                                             
                                               ( 
                                               1 
                                               ) 
                                             
                                           
                                         
                                         
                                             
                                         
                                       
                                        
                                       
                                         
                                           w 
                                           
                                             j 
                                             1 
                                           
                                           
                                             ( 
                                             2 
                                             ) 
                                           
                                         
                                          
                                         
                                           x 
                                           i 
                                           
                                             j 
                                             1 
                                           
                                         
                                       
                                     
                                     + 
                                     
                                       
                                         ∑ 
                                         
                                           
                                             
                                               x 
                                               i 
                                               
                                                 j 
                                                 1 
                                               
                                             
                                              
                                             
                                               x 
                                               i 
                                               
                                                 j 
                                                 2 
                                               
                                             
                                           
                                           ∈ 
                                           
                                             F 
                                             0 
                                             
                                               ( 
                                               2 
                                               ) 
                                             
                                           
                                         
                                         
                                             
                                         
                                       
                                        
                                       
                                         
                                           w 
                                           
                                             
                                               j 
                                               1 
                                             
                                              
                                             
                                               j 
                                               2 
                                             
                                           
                                           
                                             ( 
                                             2 
                                             ) 
                                           
                                         
                                          
                                         
                                           x 
                                           i 
                                           
                                             j 
                                             1 
                                           
                                         
                                          
                                         
                                           x 
                                           i 
                                           
                                             j 
                                             2 
                                           
                                         
                                       
                                     
                                     + 
                                     
                                       b 
                                       
                                         ( 
                                         2 
                                         ) 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               ] 
                             
                           
                           } 
                         
                       
                     
                   
                   + 
                   
                     
                       λ 
                       1 
                     
                      
                     
                       
                         ∑ 
                         
                           
                             x 
                             i 
                             
                               j 
                               1 
                             
                           
                           ∈ 
                           
                             F 
                             
                               ( 
                               1 
                               ) 
                             
                           
                         
                         
                             
                         
                       
                        
                       
                          
                         
                           w 
                           
                             j 
                             1 
                           
                           
                             ( 
                             2 
                             ) 
                           
                         
                          
                       
                     
                   
                   + 
                   
                     
                       λ 
                       2 
                     
                      
                     
                       
                         ∑ 
                         
                           
                             
                               x 
                               i 
                               
                                 j 
                                 1 
                               
                             
                              
                             
                               x 
                               i 
                               
                                 j 
                                 2 
                               
                             
                           
                           ∈ 
                           
                             F 
                             0 
                             
                               ( 
                               2 
                               ) 
                             
                           
                         
                         
                             
                         
                       
                        
                       
                         
                            
                           
                             w 
                             
                               
                                 j 
                                 1 
                               
                                
                               
                                 j 
                                 2 
                               
                             
                             
                               ( 
                               2 
                               ) 
                             
                           
                            
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0000]    so as to identify discriminative second-order feature interaction set F (2) , that is, 
         [0000]        F   (2)   ={x   j     1     x   j     2     |x   j     1     x   j     2     εF   0   (2)   ,w   j     1     j     2     (2) ≠0}.
 
         [0029]    Step 3: 
         [0030]    We multiply each discriminative (k−1)-th order feature interaction in set F (k−1)  with p−k+1 other single features in F 0   (1)  to construct the set of all possible k-th order interactions F 0   (k) , that is, 
         [0000]        F   0   (k)   ={x   j     1     x   j     2      . . . x   j     k     |x   j     1     x   j     2      . . . x   j     k−1     εF   (k−1)   ,x   j     k     εF   0   (1)   ,j   k   ≠j   k−q   ,∀q= 1 , . . . k− 1} 
         [0000]    Then from F 0   (k)  we identify discriminative feature interaction set F (k)  by solving the optimization problem as in Equation 9. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       min 
                       
                         
                           w 
                           
                             ( 
                             k 
                             ) 
                           
                         
                         , 
                         
                           b 
                           
                             ( 
                             k 
                             ) 
                           
                         
                       
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         n 
                       
                        
                       
                         log 
                          
                         
                           { 
                           
                             1 
                             + 
                             
                               exp 
                                
                               
                                 [ 
                                 
                                   - 
                                   
                                     
                                       y 
                                       i 
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           
                                             
                                               
                                                 
                                                   ∑ 
                                                   
                                                     q 
                                                     = 
                                                     1 
                                                   
                                                   
                                                     k 
                                                     - 
                                                     1 
                                                   
                                                 
                                                  
                                                 
                                                   
                                                     ∑ 
                                                     
                                                       
                                                         
                                                           x 
                                                           i 
                                                           
                                                             j 
                                                             1 
                                                           
                                                         
                                                          
                                                         
                                                           x 
                                                           i 
                                                           
                                                             j 
                                                             2 
                                                           
                                                         
                                                          
                                                         
                                                             
                                                         
                                                          
                                                         … 
                                                          
                                                         
                                                             
                                                         
                                                          
                                                         
                                                           x 
                                                           i 
                                                           
                                                             j 
                                                             q 
                                                           
                                                         
                                                       
                                                       ∈ 
                                                       
                                                         F 
                                                         
                                                           ( 
                                                           q 
                                                           ) 
                                                         
                                                       
                                                     
                                                     
                                                         
                                                     
                                                   
                                                    
                                                   
                                                     
                                                       w 
                                                       
                                                         
                                                           j 
                                                           1 
                                                         
                                                          
                                                         
                                                           j 
                                                           
                                                             2 
                                                              
                                                             
                                                               
                                                             
                                                           
                                                         
                                                          
                                                         … 
                                                          
                                                         
                                                             
                                                         
                                                          
                                                         
                                                           j 
                                                           q 
                                                         
                                                       
                                                       
                                                         ( 
                                                         k 
                                                         ) 
                                                       
                                                     
                                                      
                                                     
                                                       x 
                                                       i 
                                                       
                                                         j 
                                                         1 
                                                       
                                                     
                                                      
                                                     
                                                       x 
                                                       i 
                                                       
                                                         j 
                                                         2 
                                                       
                                                     
                                                      
                                                     
                                                         
                                                     
                                                      
                                                     … 
                                                      
                                                     
                                                         
                                                     
                                                      
                                                     
                                                       x 
                                                       i 
                                                       
                                                         j 
                                                         q 
                                                       
                                                     
                                                   
                                                 
                                               
                                               + 
                                             
                                           
                                         
                                         
                                           
                                             
                                               
                                                 
                                                   ∑ 
                                                   
                                                     
                                                       
                                                         x 
                                                         i 
                                                         
                                                           j 
                                                           1 
                                                         
                                                       
                                                        
                                                       
                                                         x 
                                                         i 
                                                         
                                                           j 
                                                           2 
                                                         
                                                       
                                                        
                                                       
                                                         …x 
                                                         i 
                                                         
                                                           j 
                                                           k 
                                                         
                                                       
                                                     
                                                     ∈ 
                                                     
                                                       F 
                                                       0 
                                                       
                                                         ( 
                                                         k 
                                                         ) 
                                                       
                                                     
                                                   
                                                   
                                                       
                                                   
                                                 
                                                  
                                                 
                                                   
                                                     w 
                                                     
                                                       
                                                         j 
                                                         1 
                                                       
                                                        
                                                       
                                                         j 
                                                         
                                                           2 
                                                            
                                                           
                                                               
                                                           
                                                         
                                                       
                                                        
                                                       … 
                                                        
                                                       
                                                           
                                                       
                                                        
                                                       
                                                         j 
                                                         q 
                                                       
                                                     
                                                     
                                                       ( 
                                                       k 
                                                       ) 
                                                     
                                                   
                                                    
                                                   
                                                     x 
                                                     i 
                                                     
                                                       j 
                                                       1 
                                                     
                                                   
                                                    
                                                   
                                                     x 
                                                     i 
                                                     
                                                       j 
                                                       2 
                                                     
                                                   
                                                    
                                                   
                                                       
                                                   
                                                    
                                                   … 
                                                    
                                                   
                                                       
                                                   
                                                    
                                                   
                                                     x 
                                                     i 
                                                     
                                                       j 
                                                       q 
                                                     
                                                   
                                                 
                                               
                                               + 
                                               
                                                 b 
                                                 
                                                   ( 
                                                   k 
                                                   ) 
                                                 
                                               
                                             
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ] 
                               
                             
                           
                           } 
                         
                       
                     
                   
                   + 
                   
                     
                       ∑ 
                       
                         q 
                         = 
                         1 
                       
                       
                         k 
                         - 
                         1 
                       
                     
                      
                     
                       
                         λ 
                         q 
                       
                        
                       
                         
                           ∑ 
                           
                             
                               
                                 x 
                                 i 
                                 
                                   j 
                                   1 
                                 
                               
                                
                               
                                 x 
                                 i 
                                 
                                   j 
                                   2 
                                 
                               
                                
                               
                                   
                               
                                
                               … 
                                
                               
                                   
                               
                                
                               
                                 x 
                                 i 
                                 
                                   j 
                                   q 
                                 
                               
                             
                             ∈ 
                             
                               F 
                               
                                 ( 
                                 q 
                                 ) 
                               
                             
                           
                           
                               
                           
                         
                          
                         
                            
                           
                             
                               w 
                               
                                 
                                   j 
                                   1 
                                 
                                  
                                 
                                   j 
                                   2 
                                 
                               
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                              
                             
                                 
                             
                              
                             … 
                              
                             
                                 
                             
                              
                             
                               j 
                               q 
                             
                           
                            
                         
                       
                     
                   
                   + 
                   
                     
                       λ 
                       k 
                     
                      
                     
                       
                         ∑ 
                         
                           
                             
                               x 
                               i 
                               
                                 j 
                                 1 
                               
                             
                              
                             
                               x 
                               i 
                               
                                 j 
                                 2 
                               
                             
                              
                             
                                 
                             
                              
                             … 
                              
                             
                                 
                             
                              
                             
                               x 
                               i 
                               
                                 j 
                                 k 
                               
                             
                           
                           ∈ 
                           
                             F 
                             0 
                             
                               ( 
                               k 
                               ) 
                             
                           
                         
                         
                             
                         
                       
                        
                       
                         
                            
                           
                             
                               w 
                               
                                 
                                   
                                     j 
                                     1 
                                   
                                    
                                   
                                     j 
                                     2 
                                   
                                 
                                  
                                 
                                     
                                 
                               
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                              
                             … 
                              
                             
                                 
                             
                              
                             
                               j 
                               k 
                             
                           
                            
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0000]    and the order-k discriminative feature interaction set F (k)  is identified as 
         [0000]        F   (k)   ={x   j     1     x   j     2      . . . x   j     k     |x   j     1     x   j     2      . . . x   j     k     εF   0   (k)   ,w   j     1     j     2     . . . j     k     (k) ≠0}
 
         [0031]    Note that in Equation 9 we include discriminative single features and discriminative lower-order interactions F (1) , . . . , F (k−1)  into the l 1 -regularized optimization problem for order k so as to optimally remove less important lower-order interactions when high-order interactions present. To speed up the optimization, we divide each identified discriminative feature interaction set F into equal-sized blocks, and we expand each block and solve the l 1 -regularized optimization problem for the particular block. 
         [0032]    The above greedy optimization approach sequentially identifies discriminative feature interactions of different orders that essentially form a tree structure, because each k-th order discriminative feature interactions must have at least one of its (k−1)-th order constituents belonging to F (k−1) , where k&gt;1. Although this greedy approach can only identify a sub-optimal solution to the original intractable optimization problem in eqn:shooter, it performs very well in practice as demonstrated by our experimental results. 
         [0033]    Sampling Methods for SHBM are detailed next. In this section, we present Contrastive Divergence (CD) learning based on Gibbs Sampling (GS) and damped Mean-Field updates (MF). The weight updates in SHBM based on CD are as follows, 
         [0000]      Δ W   i     1     i     2     . . . i     j   =ε(           v   i     1     v   i     2      . . . v   i     j               data −           v   i     1     v   i     2      . . . v   i     j               T ),  (10)
 
         [0000]    where          v i     1   v i     2    . . . v i     j              is calculated using the samples obtained from different sampling methods after T steps. Although CD updates do not exactly follow the gradient of data log-likelihood, it works well in practice. 
         [0034]    Gibbs sampling (GS) can be used within CD for drawing samples. To perform Gibbs Sampling, we initialize r (0)  to be a random data vector, and we sample each visible unit v j  sequentially using the conditional probability 
         [0000]        p   (t) ( v   j   |r   1   (t)   , . . . ,r   j−1   (t)   ,r   j+1   (t−1)   , . . . ,r   p   (t−1)    
         [0000]    to get the sample for unit v j  in step t, where j=1, . . . , p, t=1, . . . , T, and p is the total number of visible units. Then we use the statistics in the T-step samples to calculate the second term in Equation 10 for weight updates. 
         [0035]    However, standard GS cannot be performed in parallel due to the sequential sampling procedure over all the visible units. To speed up learning, we use mean-field approximations (MF) to calculate the sampled values for all the visible units in each step in parallel given the sample values in the previous step (please note that GS and MF have the same computational complexity without parallelization). In specific, we use the damped version of mean-field updates to draw samples to increase sampling stability. Starting from a random data vector r (0) , we calculate the t-step sample for each visible unit v j  as follows, 
         [0000]        r   j   (1)   =λr   j   (t−1) +(1−λ) p ( v   j =1 |v   −j   ,W ),
 
         [0000]    where t=1, . . . , T, and p(v i =1|v −j ,W) is the conditional probability of v i =1 given its neighborhood interactions. Please note that, unlike in GS, we can calculate r (t)  for all the visible units in parallel to speed up our computation because the calculation for r (t)  is only dependent on r (t−1) . In all our experiments, we set λ=0.2 for parameter learning based on Damped MF updates. 
         [0036]    As discussed above, SHBM is an interpretable sparse high-order Boltzmann machine, with a two-step learning process. In the first step of learning, a greedy sparse learning approach via L-regularized logistic regression to identify high-order feature interactions so as to identify interaction neighborhood structure for the SHBM. In the second step of SHBM, different sampling methods are used to learn the interaction weights in SHBM. Experimental results demonstrate that the SHBM outperforms other methods in identifying interaction neighborhood by exploring high-order interactions during classification. In addition, weight learning in SHBM produces better rankings among interactions and better generative models than other competing models. In particular, SHBM successfully identifies biologically meaningful and significant interactions from a real biological dataset, whereas other state-of-the-art methods miss such interactions. SHBM is also demonstrated to be scalable to very large problems, while the state-of-the-art method for high-order interactions fail. 
         [0037]    We can incorporate abundant group information of features to enhance the power of shooter, when limited data points are available. Moreover, we can add hidden units and gated hidden units to increase the generative power of SHBM for unsupervised feature interaction identification and for collaborative filtering applications. 
         [0038]    The invention may be implemented in hardware, firmware or software, or a combination of the three. Preferably the invention is implemented in a computer program executed on a programmable computer having a processor, a data storage system, volatile and non-volatile memory and/or storage elements, at least one input device and at least one output device. 
         [0039]    By way of example, a block diagram of a computer to support the system is discussed next. The computer preferably includes a processor, random access memory (RAM), a program memory (preferably a writable read-only memory (ROM) such as a flash ROM) and an input/output (I/O) controller coupled by a CPU bus. The computer may optionally include a hard drive controller which is coupled to a hard disk and CPU bus. Hard disk may be used for storing application programs, such as the present invention, and data. Alternatively, application programs may be stored in RAM or ROM. I/O controller is coupled by means of an I/O bus to an I/O interface. I/O interface receives and transmits data in analog or digital form over communication links such as a serial link, local area network, wireless link, and parallel link. Optionally, a display, a keyboard and a pointing device (mouse) may also be connected to I/O bus. Alternatively, separate connections (separate buses) may be used for I/O interface, display, keyboard and pointing device. Programmable processing system may be preprogrammed or it may be programmed (and reprogrammed) by downloading a program from another source (e.g., a floppy disk, CD-ROM, or another computer). 
         [0040]    Each computer program is tangibly stored in a machine-readable storage media or device (e.g., program memory or magnetic disk) readable by a general or special purpose programmable computer, for configuring and controlling operation of a computer when the storage media or device is read by the computer to perform the procedures described herein. The inventive system may also be considered to be embodied in a computer-readable storage medium, configured with a computer program, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions described herein. 
         [0041]    The invention has been described herein in considerable detail in order to comply with the patent Statutes and to provide those skilled in the art with the information needed to apply the novel principles and to construct and use such specialized components as are required. However, it is to be understood that the invention can be carried out by specifically different equipment and devices, and that various modifications, both as to the equipment details and operating procedures, can be accomplished without departing from the scope of the invention itself.