# 使用自我調整提升進行分類和預測

James McCaffrey

## 自我調整增強演算法

``````[0] (D = 0.10) Detroit   Home   Large    Win
[1] (D = 0.10) Detroit   Away   Medium   Win
[2] (D = 0.10) Buffalo   Home   Small    Win
[3] (D = 0.10) Buffalo   Home   Medium   Win
[4] (D = 0.10) Atlanta   Away   Large    Win
[5] (D = 0.10) Chicago   Home   Medium   Win
[6] (D = 0.10) Chicago   Away   Small    Lose
[7] (D = 0.10) Chicago   Home   Small    Lose
[8] (D = 0.10) Atlanta   Away   Medium   Lose
[9] (D = 0.10) Detroit   Away   Large    Lose
``````

``````[0] (a = 0.00) (e = -1.0) IF Opponent IS Buffalo THEN Result IS Win
[1] (a = 0.00) (e = -1.0) IF Opponent IS Chicago THEN Result IS Lose
[2] (a = 0.00) (e = -1.0) IF Opponent IS Detroit THEN Result IS Win
[3] (a = 0.00) (e = -1.0) IF Field IS Home THEN Result IS Win
[4] (a = 0.00) (e = -1.0) IF Field IS Away THEN Result IS Lose
[5] (a = 0.00) (e = -1.0) IF Spread IS Small THEN Result IS Lose
[6] (a = 0.00) (e = -1.0) IF Spread IS Medium THEN Result IS Win
[7] (a = 0.00) (e = -1.0) IF Spread IS Large THEN Result IS Win
``````

``````set t=0
while not done loop
update all learners' epsilons (weighted errors)
find best (smallest epsilon) unused learner
compute and save the alpha of best learner using its epsilon
update the D weights for each training item using the best learner
normalize the D weights so they sum to 1.0
++t
end loop
``````

``````[0] (a = 0.00) (e = 0.00) IF Opponent IS Buffalo THEN Result IS Win
[1] (a = 0.00) (e = 0.10) IF Opponent IS Chicago THEN Result IS Lose
[2] (a = 0.00) (e = 0.10) IF Opponent IS Detroit THEN Result IS Win
[3] (a = 0.00) (e = 0.10) IF Field IS Home THEN Result IS Win
[4] (a = 0.00) (e = 0.20) IF Field IS Away THEN Result IS Lose
[5] (a = 0.00) (e = 0.10) IF Spread IS Small THEN Result IS Lose
[6] (a = 0.00) (e = 0.10) IF Spread IS Medium THEN Result IS Win
[7] (a = 0.00) (e = 0.10) IF Spread IS Large THEN Result IS Win
``````

``````alpha = 0.5 * log((1.0 - epsilon) / epsilon)
``````

``````D(new) = D(old) * exp(-alpha * actualY * predictedY)
``````

``````D(new) = 0.10 * exp(-6.91 * (+1) * (+1))
= 0.10 * exp(-6.91)
= 0.0000997758
``````

``````[0] (D = 0.1000) Detroit   Home   Large    Win
[1] (D = 0.1000) Detroit   Away   Medium   Win
[2] (D = 0.0001) Buffalo   Home   Small    Win
[3] (D = 0.0001) Buffalo   Home   Medium   Win
[4] (D = 0.1000) Atlanta   Away   Large    Win
[5] (D = 0.1000) Chicago   Home   Medium   Win
[6] (D = 0.1000) Chicago   Away   Small    Lose
[7] (D = 0.1000) Chicago   Home   Small    Lose
[8] (D = 0.1000) Atlanta   Away   Medium   Lose
[9] (D = 0.1000) Detroit   Away   Large    Lose
``````

``````[0] (D = 0.1249) Detroit   Home   Large    Win
[1] (D = 0.1249) Detroit   Away   Medium   Win
[2] (D = 0.0001) Buffalo   Home   Small    Win
[3] (D = 0.0001) Buffalo   Home   Medium   Win
[4] (D = 0.1249) Atlanta   Away   Large    Win
[5] (D = 0.1249) Chicago   Home   Medium   Win
[6] (D = 0.1249) Chicago   Away   Small    Lose
[7] (D = 0.1249) Chicago   Home   Small    Lose
[8] (D = 0.1249) Atlanta   Away   Medium   Lose
[9] (D = 0.1249) Detroit   Away   Large    Lose
``````

## 程式的整體結構

``````using System;
using System.Collections.Generic;
{
class Program
{
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin adaptive boosting classification demo\n");
string[] features = new string[] { "Opponent", "Field", "Spread",
"Result" };
string[][] values = new string[4][];
values[0] = new string[] { "Atlanta", "Buffalo", "Chicago",
"Detroit" }; // opponent
values[1] = new string[] { "Home", "Away" };  // Field
values[2] = new string[] { "Small ", "Medium", "Large " };
// Note: Spaces added
values[3] = new string[] { "Lose", "Win" };
// The dependent/predicted variable
string[][] rawTrain = new string[10][];
rawTrain[0] = new string[] { "Detroit", "Home", "Large ", "Win" };
rawTrain[1] = new string[] { "Detroit", "Away", "Medium", "Win" };
rawTrain[2] = new string[] { "Buffalo", "Home", "Small ", "Win" };
rawTrain[3] = new string[] { "Buffalo", "Home", "Medium", "Win" };
rawTrain[4] = new string[] { "Atlanta", "Away", "Large ", "Win" };
rawTrain[5] = new string[] { "Chicago", "Home", "Medium", "Win" };
rawTrain[6] = new string[] { "Chicago", "Away", "Small ", "Lose" };
rawTrain[7] = new string[] { "Chicago", "Home", "Small ", "Lose" };
rawTrain[8] = new string[] { "Atlanta", "Away", "Medium", "Lose" };
rawTrain[9] = new string[] { "Detroit", "Away", "Large ", "Lose" };
Console.WriteLine("Raw (string) training data for team seattle:\n");
Console.WriteLine("Opponent Field  Spread   Result");
Console.WriteLine("===============================");
ShowMatrix(rawTrain);
Console.WriteLine("\nConverting and storing training data");
int[][] train = RawTrainToInt(rawTrain, values);
Console.WriteLine("Training data in int form:\n");
ShowMatrix(train, true);
Console.WriteLine(
"\nCreating weak categorical stump learners from training data");
List<Learner> learners = MakeLearners(values, train);
Console.WriteLine("Completed.
Weak learners are:\n");
for (int i = 0; i < learners.Count; ++i)
Console.WriteLine("[" + i + "] " + Description(learners[i],
features, values));
Console.WriteLine("\nInitializing list of best learner indexes");
List<int> bestLearners = new List<int>();  // Indexes of good weak learners
Console.WriteLine(
"\nUsing adaptive boosting to find best  learners and alphas");
MakeModel(train, values, learners, bestLearners);
Console.WriteLine("\nModel completed");
int numGood = bestLearners.Count;
Console.Write("Algorithm found " + numGood + " good learners ");
Console.WriteLine("and associated alpha values");
Console.WriteLine("\nThe good learners and their alpha value are:");
for (int i = 0; i < bestLearners.Count; ++i)
{
int lrn = bestLearners[i];
Console.Write("[" + lrn + "] " +
learners[lrn].alpha.ToString("F2") + "  ");
}
Console.Write("\nPredicting outcome when Opponent = Detroit, ");
Console.WriteLine("Field = Home, Spread = Small\n");
int[] unknownTuple = new int[] { 3, 0, 0 }; // Detroit, Home, Small
int Y = Classify(unknownTuple, learners, bestLearners);
Console.Write("Predicted Y = " + Y + " => ");
Console.WriteLine("seattle will " + YValueToString(Y, values));
Console.WriteLine("\nEnd\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
// (Many) static methods here
} // Class Program
public class Learner  // Weak learner
{
// Definition code here
}
} // ns
``````

Main 方法首先為特徵「Opponent」、「Field」、「Spread」和「Result」設置了硬編碼字串。 然後，Main 中的代碼為每個特徵設置了硬編碼值： “Atlanta,” “Buffalo,” “Chicago,” “Detroit,” “Home,” “Away,” “Small,” “Medium,” “Large,” “Lose” and “Win.” To keep my output tidy, I used a hack and inserted a blank space at the end of “Small” and “Large.”

Main 方法最後預測具有以下一組輸入的 Seattle 的結果：Opponent 為「Detroit」、Field 為「Home」且 Spread 為「Small」。 在本例中，Classify 的傳回值為 -0.72，這解釋為「Lose」。

## 創建弱學習器

``````public int feature;
public int value;
public int predicted;
public double error;
public double epsilon;
public double alpha;
``````

error 欄位是 double 類型，是與訓練資料的弱學習器關聯的原始誤差率。 例如，如果弱學習器的 feature = 0、value = 3 且 predicted = +1（表示如果 Opponent 為 Detroit 時，則結果為 Win），那麼圖 1 中訓練資料的原始誤差率為 0.33，因為有三分之一的訓練資料項目被錯誤預測。 請注意，原始誤差將同等對待每個訓練項。 結果證明，本文中所演示的自我調整增強演算法實際上並不需要原始誤差欄位，因此可忽略該欄位，但我認為此資訊很有用。

epsilon 欄位是加權誤差項。 弱學習器的 epsilon 是考慮分配給每個訓練項的內部 D 權重的誤差項。 自我調整增強演算法使用 epsilon 值計算 Alpha 權重。 總之，有兩組權重用在自我調整增強分類中。 Alpha 權重為每個弱學習器分配重要性，並用於確定總體預測。 epsilon 誤差是與弱學習器關聯的內部誤差，用於計算 Alpha 權重。 每個訓練元組都有一個內部權重（在自我調整增強文獻資料中稱為 D），用於計算 epsilon 誤差。

``````initialize an empty result list of learners
for each feature loop
for each value of curr feature loop
scan training data to determine most likely -1, +1 result
if no most likely result, skip curr value
create a new learner object with feature, value, predicted
add learner object to result list
end each value
end each feature
for each learner in result list
for each training data item
if learner isn't applicable to data, skip curr data item
compute raw error rate
store raw error into learner
end each training data item
end each learner
``````

## 總結

Dr. James McCaffrey   供職于 Volt Information Sciences Inc.，負責管理華盛頓地區雷蒙德市沃什灣 Microsoft 總部園區的軟體工程師技術培訓。 他參與過多項 Microsoft 產品的研發工作，其中包括 Internet Explorer 和 MSN Search。 他是《.NET Test Automation Recipes》（Apress，2006）的作者，你可以通過以下電子郵箱位址與他聯繫：jammc@microsoft.com