2 people like it.

AdaBoost in F#

I have provided a class that implements adaptive boosting (AdaBoost) which is a very elegant technique to create a strong classifier from a set of weak classifiers. The strong classifier is the sign of the weighted average of the best N weak classifiers where N is a user specified parameter. The training process consists of N selection rounds. During each round, the training samples are given a weight distribution. The classifier selected is the one that has the least error which is equal to the weighted average of incorrectly classified samples. Training samples that have been incorrectly classified are given a larger weight for the next round. This increases the likelihood of drafting a weak classifier that can help with as yet misclassified samples. 

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70: 
71: 
72: 
73: 
74: 
75: 

namespace AdaBooster

    type LabelType = 
        | NEG = -1
        | POS = 1

    type AdaBooster(trainingSamples : (obj * LabelType) [], weakClassifiers : (obj -> LabelType) [], weakClassifierMaxCount : int) =
        
        let trainingSamplesCount = trainingSamples.Length
        let weakClassifierCount = weakClassifiers.Length

        let weightMatrix = Array2D.create trainingSamplesCount weakClassifierMaxCount 1.0

        let scoutingMatrix = Array2D.create trainingSamplesCount weakClassifierCount 0

        let mutable strongClassifier: (int * float) list = []

        let initializeScoutingMatrix = 
            for j in 0 .. weakClassifiers.Length - 1 do
                for i in 0 .. trainingSamplesCount - 1 do
                    let (sample, label) = trainingSamples.[i]
                    scoutingMatrix.[i, j] <- 
                        if ( weakClassifiers.[j] sample ) <> label then 1 else 0

        let calculateError weakClassifierIndex weights = 
            weights     
            |> List.mapi (fun i wt -> float scoutingMatrix.[i, weakClassifierIndex] * wt)
            |> List.sum

        let selectBestWeakClassifier weights weakClassifierIndices = 
            weakClassifierIndices
            |> List.map (fun weakClassifierIndex -> (weakClassifierIndex, calculateError weakClassifierIndex weights))
            |> List.minBy (fun (x, y) -> y)

        let rec train m weights weakClassifierIndices =

            if m >= weakClassifierMaxCount then []
            else

                let nextM = m + 1 
                let (bestWeakClassifierIndex, classifierWeight) = selectBestWeakClassifier weights weakClassifierIndices
                let error = classifierWeight / List.sum weights
                let weakClassifierCoefficient = 0.5 * log ((1.0 - error) / error)
                let wm1 = sqrt(( 1.0 - error) / error)

                let newWeights =
                    weights 
                    |> List.mapi ( fun i wm -> if scoutingMatrix.[ i, bestWeakClassifierIndex]  = 1 then wm * wm1 else wm / wm1)

                for i in 0 .. (trainingSamplesCount - 1) do 
                    weightMatrix.[i, m] <- weights.[i]

                let weakClassifiersToScanNext = 
                    weakClassifierIndices 
                    |> List.filter (fun index -> index <> bestWeakClassifierIndex)

                (bestWeakClassifierIndex, weakClassifierCoefficient) :: train nextM newWeights weakClassifiersToScanNext

        member this.Predict sample  = 
            strongClassifier 
            |> List.sumBy (fun (weakClassifierIndex,  weakClassifierCoefficient) ->  weakClassifierCoefficient * float ( weakClassifiers.[weakClassifierIndex] sample) )
            |> (fun x -> if x > 0.0 then (x, LabelType.POS) else (x,LabelType.NEG))

        member this.Train  = 
            let initialWeights = List.init trainingSamplesCount (fun x -> 1.0)
            
            strongClassifier <- train 0 initialWeights [0 .. (weakClassifierCount - 1)]
            strongClassifier

    
        member this.ScoutingMatrix = 
            scoutingMatrix

        member this.WeightMatrix = 
            weightMatrix
Multiple items
type AdaBooster =
  new : trainingSamples:(obj * LabelType) [] * weakClassifiers:(obj -> LabelType) [] * weakClassifierMaxCount:int -> AdaBooster
  member Predict : sample:obj -> float * LabelType
  member ScoutingMatrix : int [,]
  member Train : (int * float) list
  member WeightMatrix : float [,]

Full name: AdaBooster.AdaBooster

--------------------
new : trainingSamples:(obj * LabelType) [] * weakClassifiers:(obj -> LabelType) [] * weakClassifierMaxCount:int -> AdaBooster
LabelType.NEG: LabelType = -1
LabelType.POS: LabelType = 1
val trainingSamples : (obj * LabelType) []
type obj = System.Object

Full name: Microsoft.FSharp.Core.obj
type LabelType =
  | NEG = -1
  | POS = 1

Full name: AdaBooster.LabelType
val weakClassifiers : (obj -> LabelType) []
val weakClassifierMaxCount : int
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val trainingSamplesCount : int
property System.Array.Length: int
val weakClassifierCount : int
val weightMatrix : float [,]
module Array2D

from Microsoft.FSharp.Collections
val create : length1:int -> length2:int -> value:'T -> 'T [,]

Full name: Microsoft.FSharp.Collections.Array2D.create
val scoutingMatrix : int [,]
val mutable strongClassifier : (int * float) list
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = System.Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val initializeScoutingMatrix : unit
val j : int32
val i : int32
val sample : obj
val label : LabelType
val calculateError : (int -> float list -> float)
val weakClassifierIndex : int
val weights : float list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val mapi : mapping:(int -> 'T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.mapi
val i : int
val wt : float
val sum : list:'T list -> 'T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.List.sum
val selectBestWeakClassifier : (float list -> int list -> int * float)
val weakClassifierIndices : int list
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val minBy : projection:('T -> 'U) -> list:'T list -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.List.minBy
val x : int
val y : float
val train : (int -> float list -> int list -> (int * float) list)
val m : int
val nextM : int
val bestWeakClassifierIndex : int
val classifierWeight : float
val error : float
val weakClassifierCoefficient : float
val log : value:'T -> 'T (requires member Log)

Full name: Microsoft.FSharp.Core.Operators.log
val wm1 : float
val sqrt : value:'T -> 'U (requires member Sqrt)

Full name: Microsoft.FSharp.Core.Operators.sqrt
val newWeights : float list
val wm : float
val weakClassifiersToScanNext : int list
val filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter
val index : int
val this : AdaBooster
member AdaBooster.Predict : sample:obj -> float * LabelType

Full name: AdaBooster.AdaBooster.Predict
val sumBy : projection:('T -> 'U) -> list:'T list -> 'U (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.List.sumBy
val x : float
member AdaBooster.Train : (int * float) list

Full name: AdaBooster.AdaBooster.Train
val initialWeights : float list
val init : length:int -> initializer:(int -> 'T) -> 'T list

Full name: Microsoft.FSharp.Collections.List.init
member AdaBooster.ScoutingMatrix : int [,]

Full name: AdaBooster.AdaBooster.ScoutingMatrix
member AdaBooster.WeightMatrix : float [,]

Full name: AdaBooster.AdaBooster.WeightMatrix

More information

Link:http://fssnip.net/hD
Posted:11 years ago
Author:Suzanna
Tags: adaboost

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.