Margin-infused relaxed algorithm

Margin-infused relaxed algorithm (MIRA) is a <a href="/facts/Machine_learning/e0w0XJTu">machine learning</a> algorithm, an <a href="/facts/Online_algorithm/64TsU7Yz">online algorithm</a> for <a href="/facts/Multiclass_classification/aS7sV9EX">multiclass classification</a> problems. It is designed to learn a set of parameters (vector or matrix) by processing all the given training examples one-by-one and updating the parameters according to each training example, so that the current training example is classified correctly with a <a href="/facts/Margin_(machine_learning)/DI0QU6QQ">margin</a> against incorrect classifications at least as large as their loss. The change of the parameters is kept as small as possible.
A two-class version called binary MIRA simplifies the algorithm by not requiring the solution of a <a href="/facts/Quadratic_programming/ct4RIUgs">quadratic programming</a> problem (see below). When used in a one-vs-all configuration, binary MIRA can be extended to a multiclass learner that approximates full MIRA, but may be faster to train.
The flow of the algorithm looks as follows:

Algorithm MIRA
  Input: Training examples 
  
    
      
        T
        =
        {
        
          x
          
            i
          
        
        ,
        
          y
          
            i
          
        
        }
      
    
    {\displaystyle T=\{x_{i},y_{i}\}}

Output: Set of parameters 
  
    
      
        w
      
    
    {\displaystyle w}

i
      
    
    {\displaystyle i}
  
 ← 0, 
  
    
      
        
          w
          
            (
            0
            )
          
        
      
    
    {\displaystyle w^{(0)}}
  
 ← 0
  for 
  
    
      
        n
      
    
    {\displaystyle n}
  
 ← 1 to 
  
    
      
        N
      
    
    {\displaystyle N}

for 
  
    
      
        t
      
    
    {\displaystyle t}
  
 ← 1 to 
  
    
      
        
          |
        
        T
        
          |
        
      
    
    {\displaystyle |T|}

w
          
            (
            i
            +
            1
            )
          
        
      
    
    {\displaystyle w^{(i+1)}}
  
 ← update 
  
    
      
        
          w
          
            (
            i
            )
          
        
      
    
    {\displaystyle w^{(i)}}
  
 according to 
  
    
      
        {
        
          x
          
            t
          
        
        ,
        
          y
          
            t
          
        
        }
      
    
    {\displaystyle \{x_{t},y_{t}\}}

i
      
    
    {\displaystyle i}
  
 ← 
  
    
      
        i
        +
        1
      
    
    {\displaystyle i+1}

end for
  end for
  return 
  
    
      
        
          
            
              
                ∑
                
                  j
                  =
                  1
                
                
                  N
                  ×
                  
                    |
                  
                  T
                  
                    |
                  
                
              
              
                w
                
                  (
                  j
                  )
                
              
            
            
              N
              ×
              
                |
              
              T
              
                |
              
            
          
        
      
    
    {\displaystyle {\frac {\sum _{j=1}^{N\times |T|}w^{(j)}}{N\times |T|}}}

<ul><li>"←" denotes <a href="/facts/Assignment_(computer_science)/kLevAoyJ">assignment</a>. For instance, "largest ← item" means that the value of largest changes to the value of item.</li>
<li>"return" terminates the algorithm and outputs the following value.</li></ul>

The update step is then formalized as a <a href="/facts/Quadratic_programming/ct4RIUgs">quadratic programming</a> problem: Find 
 
 
 
 m
 i
 n
 ‖
 
 w
 
 (
 i
 +
 1
 )
 
 
 −
 
 w
 
 (
 i
 )
 
 
 ‖
 
 
 {\displaystyle min\|w^{(i+1)}-w^{(i)}\|}
 
, so that 
 
 
 
 s
 c
 o
 r
 e
 (
 
 x
 
 t
 
 
 ,
 
 y
 
 t
 
 
 )
 −
 s
 c
 o
 r
 e
 (
 
 x
 
 t
 
 
 ,
 
 y
 ′
 
 )
 ≥
 L
 (
 
 y
 
 t
 
 
 ,
 
 y
 ′
 
 )
  
 ∀
 
 y
 ′
 
 
 
 {\displaystyle score(x_{t},y_{t})-score(x_{t},y')\geq L(y_{t},y')\ \forall y'}
 
, i.e. the score of the current correct training 
 
 
 
 y
 
 
 {\displaystyle y}
 
 must be greater than the score of any other possible 
 
 
 
 
 y
 ′
 
 
 
 {\displaystyle y'}
 
 by at least the loss (number of errors) of that 
 
 
 
 
 y
 ′
 
 
 
 {\displaystyle y'}
 
 in comparison to 
 
 
 
 y
 
 
 {\displaystyle y}
 
.

Margin-infused relaxed algorithm open-in-new

Margin-infused relaxed algorithm