前剪枝演算法

① R語言-17決策樹

是一個預測模型，分為回歸決策樹和分類決策樹，根據已知樣本訓練出一個樹模型，從而根據該模型對新樣本因變數進行預測，得到預測值或預測的分類

從根節點到葉節點的一條路徑就對應著一條規則．整棵決策樹就對應著一組表達式規則。葉節點就代表該規則下得到的預測值。如下圖決策樹模型則是根據房產、結婚、月收入三個屬性得到是否可以償還貸款的規則。

核心是如何從眾多屬性中挑選出具有代表性的屬性作為決策樹的分支節點。

最基本的有三種度量方法來選擇屬性

1. 信息增益（ID3演算法）

信息熵

一個信源發送出什麼符號是不確定的，衡量它可以根據其出現的概率來度量。概率大，出現機會多，不確定性小；反之不確定性就大。不確定性函數f是概率P的 減函數 。兩個獨立符號所產生的不確定性應等於各自不確定性之和，即f(P1,P2)=f(P1)+f(P2)，這稱為可加性。同時滿足這兩個條件的函數f是對數函數，即

在信源中，考慮的不是某一單個符號發生的不確定性，而是要考慮這個信源所有可能發生情況的平均不確定性。因此，信息熵被定義為

決策樹分類過程

2、增益率（C4.5演算法）
由於信息增益的缺點是：傾向於選擇具有大量值的屬性，因為具有大量值的屬性每個屬性對應數據量少，傾向於具有較高的信息純度。因此增益率使用【信息增益/以該屬性代替的系統熵（類似於前面第一步將play換為該屬性計算的系統熵】這個比率，試圖克服這種缺點。
g(D,A)代表D數據集A屬性的信息增益，

3. 基尼指數（CART演算法）

基尼指數：

表示在樣本集合中一個隨機選中的樣本被分錯的概率。越小表示集合中被選中的樣本被分錯的概率越小，也就是說集合的純度越高。

假設集合中有K個類別，則：

說明:

1. pk表示選中的樣本屬於k類別的概率，則這個樣本被分錯的概率是(1-pk)

2. 樣本集合中有K個類別，一個隨機選中的樣本可以屬於這k個類別中的任意一個，因而對類別就加和

3. 當為二分類是，Gini(P) = 2p(1-p)

基尼指數是將屬性A做二元劃分，所以得到的是二叉樹。當為離散屬性時，則會將離散屬性的類別兩兩組合，計算基尼指數。

舉個例子：

如上面的特徵Temperature，此特徵有三個特徵取值： 「Hot」，「Mild」， 「Cool」，
當使用「學歷」這個特徵對樣本集合D進行劃分時，劃分值分別有三個，因而有三種劃分的可能集合，劃分後的子集如下：

對於上述的每一種劃分，都可以計算出基於 劃分特徵= 某個特徵值 將樣本集合D劃分為兩個子集的純度：

決策數分類過程

先剪枝 ：提前停止樹的構建對樹剪枝，構造樹時，利用信息增益、統計顯著性等，當一個節點的劃分導致低於上述度量的預定義閾值時，則停止進一步劃分。但閾值的確定比較困難。
後剪枝 ：更為常用，先得到完全生長的樹，再自底向上，用最下面的節點的樹葉代替該節點
CART使用代價復雜度剪枝演算法 ：計算每個節點剪枝後與剪枝前的代價復雜度，如果剪去該節點，代價復雜度較小（復雜度是樹的結點與樹的錯誤率也就是誤分類比率的函數），則剪去。
C4.5採用悲觀剪枝 ：類似代價復雜度，但CART是利用剪枝集評估代價復雜度，C4.5是採用訓練集加上一個懲罰評估錯誤率

決策樹的可伸縮性

ID3C4.5CART都是為較小的數據集設計，都限制訓練元祖停留再內存中，為了解決可伸縮性，提出了其它演算法如
RainForest(雨林）：對每個屬性維護一個AVC集，描述該結點的訓練元組，所以只要將AVC集放在內存即可
BOAT自助樂觀演算法：利用統計學，創造給定訓練數據的較小樣本，每個樣本構造一個樹，導致多顆樹，再利用它們構造1顆新樹。優點是可以增量的更新，當插入或刪除數據，只需決策樹更新，而不用重新構造。

決策樹的可視化挖掘
PBC系統可允許用戶指定多個分裂點，導致多個分支，傳統決策樹演算法數值屬性都是二元劃分。並且可以實現交互地構建樹。

rpart是採用cart演算法，連續型「anova」;離散型「class」;

2）進行剪枝的函數：prune()

3）計算MAE評估回歸樹模型誤差，這里將樣本劃分成了訓練集和測試集，testdata為測試集
rt.mae為根據訓練集得到的決策樹模型對測試集因變數預測的結果與測試集因變數實際值得到平均絕對誤差

② 決策樹的決策樹的剪枝

剪枝是決策樹停止分支的方法之一，剪枝有分預先剪枝和後剪枝兩種。預先剪枝是在樹的生長過程中設定一個指標，當達到該指標時就停止生長，這樣做容易產生「視界局限」，就是一旦停止分支，使得節點N成為葉節點，就斷絕了其後繼節點進行「好」的分支操作的任何可能性。不嚴格的說這些已停止的分支會誤導學習演算法，導致產生的樹不純度降差最大的地方過分靠近根節點。後剪枝中樹首先要充分生長，直到葉節點都有最小的不純度值為止，因而可以克服「視界局限」。然後對所有相鄰的成對葉節點考慮是否消去它們，如果消去能引起令人滿意的不純度增長，那麼執行消去，並令它們的公共父節點成為新的葉節點。這種「合並」葉節點的做法和節點分支的過程恰好相反，經過剪枝後葉節點常常會分布在很寬的層次上，樹也變得非平衡。後剪枝技術的優點是克服了「視界局限」效應，而且無需保留部分樣本用於交叉驗證，所以可以充分利用全部訓練集的信息。但後剪枝的計算量代價比預剪枝方法大得多，特別是在大樣本集中，不過對於小樣本的情況，後剪枝方法還是優於預剪枝方法的。

③ 模型剪枝

深度學習網路模型從卷積層到全連接層存在著大量冗餘的參數，大量神經元激活值趨近於0，將這些神經元去除後可以表現出同樣的模型表達能力，這種情況被稱為過參數化，而對應的技術則被稱為模型剪枝。

網路剪枝的過程主要分以下幾步：

在實踐過程中我們可以感受到大的網路比小的網路更容易訓練，而且也有越來越多的實驗證明大的網路比小的網路更容易收斂到全局最優點而不會遇到局部最優點和鞍點的問題。解釋這一想像的一個假設是大樂透假設（Lottery Ticket Hypothesis）。

在下圖中，首先我們使用一個大的網路然後隨機初始化一組參數，這組參數用紅色表示，然後訓練後得到紫色的參數，接著進行網路剪枝。我們再嘗試使用剪枝的網路結構隨機初始化一組參數然後訓練發現這種方式沒能取得剪枝得到的效果，而如果用大的網路中對應的初始化參數來初始化這個剪枝的網路結構然後再進行訓練，就發現可以取得較好的效果：

大樂透假設可以用來解釋這個現象，在買大樂透時買得越多就越容易中獎，同樣的這里我們假設一個大的網路中包含很多小的網路，這些小的網路結構有的可以訓練成功而有的不可以訓練成功，只要有一個訓練成功，整個大的網路結構就可以訓練成功，因此我們可以把多餘的網路結構剪枝掉。

與大樂透假設不同的是《Rethinking the Value of Network Pruning》這篇得出了與其看似矛盾的假設。在下表中的實驗中使用了不同的模型進行試驗，表中Fined-tuned表示剪枝後的模型，Scratch-E和Scratch-B表示隨機初始化剪枝網路的參數後訓練的模型，只是Scratch-B訓練了更多的epoch。可以看到隨機初始化剪枝網路的參數後訓練的模型也取得了不錯的效果，這樣就看起來和大樂透假設的實驗結果相矛盾。事實上兩篇paper的作者均對這種結果進行了回應，可以在網上找到回應的內容，這里不做贅述。

在進行網路剪枝時我們可以選擇剪枝權重或者剪枝神經元。下圖中進行了權重的剪枝：

剪枝權重的問題是會造成網路結構的不規則，在實際操作中很難去實現也很難用GPU去加速。下圖展示了對AlexNet進行weight pruning後使用不同的GPU加速的效果，折線表示了對每一層的權重的剪枝的比例，被剪掉的權重大約佔比95%左右，然後使用不同GPU加速發現加速效果並不好，這是因為剪枝做成了網路結構的不規則，因此難以用GPU進行加速。在進行實驗需要使用weight pruning時可以使用將被剪枝的權重設置成0的方法。

而使用Neuron pruning就不會遇到上述問題，Neuron pruning後的網路結構仍然是規則的，因此仍然可以使用GPU進行加速。

其中重點在於兩個，一個是如何評估一個連接的重要性，另一個是如何在剪枝後恢復模型的性能。

由於特徵的輸出是由輸入與權重相乘後進行加權，權重的幅度越小，對輸出的貢獻越小，因此一種最直觀的連接剪枝方法就是基於權重的幅度，如L1/L2范數的大小。這樣的方法只需要三個步驟就能完成剪枝

當然這類框架還有可以改進之處，比如Dynamic network surgery框架[4]觀察到一些在當前輪迭代中雖然作用很小，但是在其他輪迭代中又可能重要，便在剪枝的基礎上增加了一個spliciing操作，即對一些被剪掉的權重進行恢復，如下：

基於權重幅度的方法原理簡單，但這是比較主觀的經驗，即認為權重大就重要性高，事實上未必如此。而另一種經典的連接剪枝方法就是基於優化目標，根據剪枝對優化目標的影響來對其重要性進行判斷，以最優腦損傷(Optimal Brain Damage, OBD)方法為代表，這已經是上世紀90年代的技術了。

Optimal Brain Damage首先建立了一個誤差函數的局部模型來預測擾動參數向量對優化目標造成的影響。具體來說用泰勒級數來近似目標函數E，參數向量U的擾動對目標函數的改變使用泰勒展開後如下：

其中gi是優化目標對參數u的梯度，而h是優化目標對參數u的海森矩陣。對模型剪枝的過程是希望找到一個參數集合，使得刪除掉這個參數集合之後損失函數E的增加最小，由於上面的式子需要求解損失函數的海森矩陣H，這是一個維度為參數量平方的矩陣，幾乎無法進行求解，為此需要對問題進行簡化，這建立在幾個基本假設的前提上：

經過簡化後只剩下了第二項，只需要計算H矩陣的對角項。它可以基於優化目標對連接權重的導數進行計算，復雜度就與梯度計算相同了，如下：

計算完之後就可以得到連接對優化目標改變的貢獻，這就是它的重要性，因此可以進行剪枝，整個流程如下：

相對於連接權重剪枝，粗粒度剪枝其實更加有用，它可以得到不需要專門的演算法支持的精簡小模型。對濾波器進行剪枝和對特徵通道進行剪枝最終的結果是相同的，篇幅有限我們這里僅介紹特徵通道的剪枝演算法代表。

通道剪枝演算法有三個經典思路。第一個是基於 重要性因子 ，即評估一個通道的有效性，再配合約束一些通道使得模型結構本身具有稀疏性，從而基於此進行剪枝。第二個是利用 重建誤差 來指導剪枝，間接衡量一個通道對輸出的影響。第三個是基於 優化目標的變化 來衡量通道的敏感性。下面我們重點介紹前兩種。

Network Trimming通過激活的稀疏性來判斷一個通道的重要性，認為擁有更高稀疏性的通道更應該被去除。它使用batch normalization中的縮放因子γ來對不重要的通道進行裁剪，如下圖：

具體實現起來，就是在目標方程中增加一個關於γ的正則項，從而約束某些通道的重要性。

類似的框架還有

與基於權重幅度的方法來進行連接剪枝一樣，基於重要性因子的方法主觀性太強，而另一種思路就是基於輸出重建誤差的通道剪枝演算法，它們根據輸入特徵圖的各個通道對輸出特徵圖的貢獻大小來完成剪枝過程，可以直接反映剪枝前後特徵的損失情況。

如上圖，基於重建誤差的剪枝演算法，就是在剪掉當前層B的若干通道後，重建其輸出特徵圖C使得損失信息最小。假如我們要將B的通道從c剪枝到c'，要求解的就是下面的問題，第一項是重建誤差，第二項是正則項。

第一步：選擇候選的裁剪通道。

我們可以對輸入特徵圖按照卷積核的感受野進行多次隨機采樣，獲得輸入矩陣X，權重矩陣W，輸出Y。然後將W用訓練好的模型初始化，逐漸增大正則因子，每一次改變都進行若干次迭代，直到beta穩定，這是一個經典的LASSO回歸問題求解。

第二步：固定beta求解W，完成最小化重建誤差，需要更新使得下式最小。

這類方法採用訓練的方式，結合各種regularizer來讓網路的權重變得稀疏，於是可以將接近於0的值剪掉。Learning Structured Sparsity in Deep Neural Networks 用group Lasso進行結構化稀疏，包括filters, channels, filter shapes, depth。Data-Driven Sparse Structure Selection for Deep Neural Networks(ECCV2018)通過引入可學習的mask，用APG演算法來稀疏mask達到結構化剪枝。A Systematic DNN Weight Pruning Framework using Alternating Direction Method of Multipliers(ECCV2018) 的思想類似，用約束優化中的經典演算法ADMM來求解。由於每個通道的輸出都會經過BN，可以巧妙地直接稀疏BN的scaling factor，比如 Learning Efficient Convolutional Networks through Network Slimming(ICCV2017) 採用L1 regularizer，Rethinking the Smaller-Norm-Less-Informative Assumption in Channel Pruning of Convolution Layers(ICLR2018) 則採用ISTA來進行稀疏。MorphNet: Fast & Simple Resource-Constrained Structure Learning of Deep Networks(CVPR2018) 也是直接利用L1 regularizer，但是結合了MobileNet中的width-multiplier，加上了shink-expand操作，能夠更好的滿足資源限制。

通常來說，模型在剪枝完後進行推理時不會發生變化，即對於所有的輸入圖片來說都是一樣的計算量，但是有的樣本簡單，有的樣本復雜，以前我們給大家介紹過動態推理框架，它們可以對不同的輸入樣本圖配置不同的計算量，剪枝框架也可以採用這樣的思路，以Runtime Neural Pruning [12]為代表。

有採用各種剪枝方法的就有和這些剪枝方法對著乾的。Recovering from Random Pruning: On the Plasticity of Deep Convolutional Neural Networks 就表明了度量標准都沒啥用，隨機賽高。Rethinking the Value of Network Pruning(ICLR2019) 則表示剪枝策略實際上是為了獲得網路結構，挑戰了傳統的 train-prune-finetune的剪枝流程。Pruning from Scratch 則直接用Network Slimming的方法對訓練過程中的剪枝結構進行了一波分析，發現直接採用random初始化的網路權重能夠獲得更豐富的剪枝結構。

剪枝中我們通常遵循一些基本策略：比如在提取低級特徵的參數較少的第一層中剪掉更少的參數，對冗餘性更高的FC層剪掉更多的參數。然而，由於深度神經網路中的層不是孤立的，這些基於規則的剪枝策略並不是最優的，也不能從一個模型遷移到另一個模型，因此AutoML方法的應用也是非常自然的，AutoML for Model Compression(AMC)是其中的代表

從AMC: AutoML for Model Compression and Acceleration on Mobile Devices[ECCV2018]開始將強化學習引入剪枝，剪枝的研究開始套上各種Auto的帽子，玩法更是層出不窮。AutoSlim: Towards One-Shot Architecture Search for Channel Numbers先訓練出一個slimmable model（類似NAS中的SuperNet Once for All: Train One Network and Specialize it for Efficient Deployment），繼而通過貪心的方式逐步對網路進行裁剪。

Network Pruning via Transformable Architecture Search(NIPS2019) 則把NAS可導的一套遷移過來做剪枝。Approximated Oracle Filter Pruning for Destructive CNN Width Optimization(ICML2019)平行操作網路的所有層，用二分搜索的方式確定每層的剪枝數。Fine-Grained Neural Architecture Search 把NAS的粒度降到了通道，包含了空的操作即剪枝。還有各種拿進化來做的也就不提了。
此外，還有基於信息瓶頸的方法Compressing Neural Networks using the Variational Information Bottleneck(ICML2018)，聚類的方法Centripetal SGD for Pruning Very Deep Convolutional Networks with Complicated Structure(CPVR2019)，等等等等等......

一脈梳理下來感覺做純的剪枝感覺很難了，對比人工設計的結構和准則，NAS出來的模型可以又小巧精度又高，剪枝也逐漸受其影響快、准、狠地尋找結構。這些效果好的結構和權重背後到底還藏著些什麼

常見論文
https://www.cnblogs.com/wujianming-110117/p/12702802.html
https://zhuanlan.hu.com/p/157562088
https://zhuanlan.hu.com/p/48269250
https://zhuanlan.hu.com/p/330575000

④ 決策樹剪枝(Decision Tree Pruning)

決策樹的剪枝是將生成的樹進行簡化，以避免過擬合。

在決策樹完美分割學習樣例之前，停止決策樹的生長。這種提早停止樹生長的方法，稱為預剪枝方法。
在構造決策樹的同時進行剪枝。所有決策樹的構建方法，都是在無法進一步降低熵的情況下才會停止創建分支的過程，為了避免過擬合，可以設定一個閾值，熵減小的數量小於這個閾值，即使還可以繼續降低熵，也停止繼續創建分支。
預剪枝可能會過早停止，降低決策樹的准確度。

(1) 作為葉結點或作為根結點需要含的最少樣本個數
(2) 決策樹的層數
(3) 結點的經驗熵小於某個閾值才停止

後剪枝是在決策樹生長完成之後，對樹進行剪枝，得到簡化版的決策樹。後剪枝是目前最普遍的做法。
後剪枝的剪枝過程是刪除一些子樹，然後用其葉子節點代替，這個葉子節點所標識的類別通過大多數原則(majority class criterion)確定。所謂大多數原則，是指剪枝過程中, 將一些子樹刪除而用葉節點代替,這個葉節點所標識的類別用這棵子樹中大多數訓練樣本所屬的類別來標識,所標識的類稱為majority class。

對於完全決策樹中的每一個非葉子節點的子樹，我們嘗試著把它替換成一個葉子節點，然後比較這替換前後兩棵決策樹在測試數據集中的表現，如果替換後的決策樹在測試數據集中的錯誤比較少(小於等於），那麼該子樹就可以被替換成葉子節點。該演算法以自底向上(bottom-up)的方式遍歷所有的子樹，直至沒有任何子樹可以替換使得測試數據集的表現得以改進時，演算法就可以終止。

CCP 方法主要包含兩個步驟:
(1)從原始決策樹 T0 開始生成一個子樹序列 T0 , T 1 , … , Tn .其中 ,T0為原始的整個決策樹，Ti +1從 Ti 產生 , Tn 為根節點 。
在步驟 1 中 ,生成子樹序列{T0 , T1 , …, Tn}的基本思想是從 T 0 開始, 裁剪 Ti 中關於訓練數據集誤差增加最小的分枝來得到 Ti+1 .
(2)從第 1 步產生的子樹序列中 ,根據樹的真實誤差估計選擇最佳決策樹 。如何從第 1 步產生的子樹序列 T0 , T1 , T2 , …中選擇出 1 棵最佳決策樹是 CCP 方法第 2 步的關鍵 .通常採用的方法有兩種, 一種是 K折交叉驗證(K-fold cross-validation),另一種是基於獨立剪枝數據集 .

PEP 方法是 Quinlan（決策樹發明者）為了克服 REP 方法需要獨立剪枝數據集的缺點而提出的 ,它不需要分離的剪枝數據集 .為了提高對未來事例的預測可靠性 , PEP 方法對誤差估計增加了連續性校正(continuitycorrection).
該方法是唯一一個自頂向下(Top-down)的剪枝演算法。

⑤ 用python實現紅酒數據集的ID3,C4.5和CART演算法

ID3演算法介紹
ID3演算法全稱為迭代二叉樹3代演算法（Iterative Dichotomiser 3）
該演算法要先進行特徵選擇，再生成決策樹，其中特徵選擇是基於「信息增益」最大的原則進行的。
但由於決策樹完全基於訓練集生成的，有可能對訓練集過於「依賴」，即產生過擬合現象。因此在生成決策樹後，需要對決策樹進行剪枝。剪枝有兩種形式，分別為前剪枝（Pre-Pruning）和後剪枝（Post-Pruning），一般採用後剪枝。
信息熵、條件熵和信息增益
信息熵：來自於香農定理，表示信息集合所含信息的平均不確定性。信息熵越大，表示不確定性越大，所含的信息量也就越大。
設x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, ...x_n}x
1

,x
2

,x
3

,...x
n

為信息集合X的n個取值，則x i x_ix
i

的概率：
P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,...,n
P(X=i)=p
i

,i=1,2,3,...,n

信息集合X的信息熵為：
H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i}
H(X)=−
i=1
∑
n

p
i

logp
i

條件熵：指已知某個隨機變數的情況下，信息集合的信息熵。
設信息集合X中有y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, ...y_m}y
1

,y
2

,y
3

,...y
m

組成的隨機變數集合Y，則隨機變數（X，Y）的聯合概率分布為
P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij}
P(x=i,y=j)=p
ij

條件熵：
H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)}
H(X∣Y)=
j=1
∑
m

p(y
j

)H(X∣y
j

)
由
H ( X ∣ y j ) = − ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log ⁡ p ( x i ∣ y j ) H(X|y_j) = - \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)}
H(X∣y
j

)=−
j=1
∑
m

p(y
j

)
i=1
∑
n

p(x
i

∣y
j

)logp(x
i

∣y
j

)
和貝葉斯公式：
p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j)
p(x
i

y
j

)=p(x
i

∣y
j

)p(y
j

)
可以化簡條件熵的計算公式為:
H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log ⁡ p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}}
H(X∣Y)=
j=1
∑
m

i=1
∑
n

p(x
i

,y
j

)log
p(x
i

,y
j

)
p(x
i

)

信息增益：信息熵-條件熵，用於衡量在知道已知隨機變數後，信息不確定性減小越大。
d ( X , Y ) = H ( X ) − H ( X ∣ Y ) d(X,Y) = H(X) - H(X|Y)
d(X,Y)=H(X)−H(X∣Y)

python代碼實現
import numpy as np
import math

def calShannonEnt(dataSet):
""" 計算信息熵 """
labelCountDict = {}
for d in dataSet:
label = d[-1]
if label not in labelCountDict.keys():
labelCountDict[label] = 1
else:
labelCountDict[label] += 1
entropy = 0.0
for l, c in labelCountDict.items():
p = 1.0 * c / len(dataSet)
entropy -= p * math.log(p, 2)
return entropy

def filterSubDataSet(dataSet, colIndex, value):
"""返回colIndex特徵列label等於value，並且過濾掉改特徵列的數據集"""
subDataSetList = []
for r in dataSet:
if r[colIndex] == value:
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
subDataSetList.append(newR)
return np.array(subDataSetList)

def chooseFeature(dataSet):
""" 通過計算信息增益選擇最合適的特徵"""
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeatureIndex = -1
for i in range(featureNum):
uniqueValues = np.unique(dataSet[:, i])
condition_entropy = 0.0

for v in uniqueValues: #計算條件熵
subDataSet = filterSubDataSet(dataSet, i, v)
p = 1.0 * len(subDataSet) / len(dataSet)
condition_entropy += p * calShannonEnt(subDataSet)
infoGain = entropy - condition_entropy #計算信息增益

if infoGain >= bestInfoGain: #選擇最大信息增益
bestInfoGain = infoGain
bestFeatureIndex = i
return bestFeatureIndex

def creatDecisionTree(dataSet, featNames):
""" 通過訓練集生成決策樹 """
featureName = featNames[:] # 拷貝featNames，此處不能直接用賦值操作，否則新變數會指向舊變數的地址
classList = list(dataSet[:, -1])
if len(set(classList)) == 1: # 只有一個類別
return classList[0]
if dataSet.shape[1] == 1: #當所有特徵屬性都利用完仍然無法判斷樣本屬於哪一類，此時歸為該數據集中數量最多的那一類
return max(set(classList), key=classList.count)

bestFeatureIndex = chooseFeature(dataSet) #選擇特徵
bestFeatureName = featNames[bestFeatureIndex]
del featureName[bestFeatureIndex] #移除已選特徵列
decisionTree = {bestFeatureName: {}}

featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex])) #已選特徵列所包含的類別， 通過遞歸生成決策樹
for v in featureValueUnique:
FeatureName = featureName[:]
subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)
decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, FeatureName)
return decisionTree

def classify(decisionTree, featnames, featList):
""" 使用訓練所得的決策樹進行分類 """
classLabel = None
root = decisionTree.keys()[0]
firstGenDict = decisionTree[root]
featIndex = featnames.index(root)
for k in firstGenDict.keys():
if featList[featIndex] == k:
if isinstance(firstGenDict[k], dict): #若子節點仍是樹，則遞歸查找
classLabel = classify(firstGenDict[k], featnames, featList)
else:
classLabel = firstGenDict[k]
return classLabel
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
76
77
78
79
80
81
82
83
84
下面用鳶尾花數據集對該演算法進行測試。由於ID3演算法只能用於標稱型數據，因此用在對連續型的數值數據上時，還需要對數據進行離散化，離散化的方法稍後說明，此處為了簡化，先使用每一種特徵所有連續性數值的中值作為分界點，小於中值的標記為1，大於中值的標記為0。訓練1000次，統計准確率均值。

from sklearn import datasets
from sklearn.model_selection import train_test_split

iris = datasets.load_iris()
data = np.c_[iris.data, iris.target]

scoreL = []
for i in range(1000): #對該過程進行10000次
trainData, testData = train_test_split(data) #區分測試集和訓練集

featNames = iris.feature_names[:]
for i in range(trainData.shape[1] - 1): #對訓練集每個特徵，以中值為分界點進行離散化
splitPoint = np.mean(trainData[:, i])
featNames[i] = featNames[i]+'<='+'{:.3f}'.format(splitPoint)
trainData[:, i] = [1 if x <= splitPoint else 0 for x in trainData[:, i]]
testData[:, i] = [1 if x <= splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
print 'score: ', np.mean(scoreL)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
輸出結果為：score: 0.7335，即准確率有73%。每次訓練和預測的准確率分布如下：

數據離散化
然而，在上例中對特徵值離散化的劃分點實際上過於「野蠻」，此處介紹一種通過信息增益最大的標准來對數據進行離散化。原理很簡單，當信息增益最大時，說明用該點劃分能最大程度降低數據集的不確定性。
具體步驟如下：

對每個特徵所包含的數值型特徵值排序
對相鄰兩個特徵值取均值，這些均值就是待選的劃分點
用每一個待選點把該特徵的特徵值劃分成兩類，小於該特徵點置為1， 大於該特徵點置為0，計算此時的條件熵，並計算出信息增益
選擇信息使信息增益最大的劃分點進行特徵離散化
實現代碼如下：

def filterRawData(dataSet, colIndex, value, tag):
""" 用於把每個特徵的連續值按照區分點分成兩類，加入tag參數，可用於標記篩選的是哪一部分數據"""
filterDataList = []
for r in dataSet:
if (tag and r[colIndex] <= value) or ((not tag) and r[colIndex] > value):
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
filterDataList.append(newR)
return np.array(filterDataList)

def dataDiscretization(dataSet, featName):
""" 對數據每個特徵的數值型特徵值進行離散化 """
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)

for featIndex in range(featureNum): #對於每一個特徵
uniqueValues = sorted(np.unique(dataSet[:, featIndex]))
meanPoint = []

for i in range(len(uniqueValues) - 1): # 求出相鄰兩個值的平均值
meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)
bestInfoGain = 0.0
bestMeanPoint = -1
for mp in meanPoint: #對於每個劃分點
subEntropy = 0.0 #計算該劃分點的信息熵
for tag in range(2): #分別劃分為兩類
subDataSet = filterRawData(dataSet, featIndex, mp, tag)
p = 1.0 * len(subDataSet) / len(dataSet)
subEntropy += p * calShannonEnt(subDataSet)

## 計算信息增益
infoGain = entropy - subEntropy
## 選擇最大信息增益
if infoGain >= bestInfoGain:
bestInfoGain = infoGain
bestMeanPoint = mp
featName[featIndex] = featName[featIndex] + "<=" + "{:.3f}".format(bestMeanPoint)
dataSet[:, featIndex] = [1 if x <= bestMeanPoint else 0 for x in dataSet[:, featIndex]]
return dataSet, featName
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
重新對數據進行離散化，並重復該步驟1000次，同時用sklearn中的DecisionTreeClassifier對相同數據進行分類，分別統計平均准確率。運行代碼如下:

from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt
scoreL = []
scoreL_sk = []
for i in range(1000): #對該過程進行1000次
featNames = iris.feature_names[:]
trainData, testData = train_test_split(data) #區分測試集和訓練集
trainData_tmp = .(trainData)
testData_tmp = .(testData)
discritizationData, discritizationFeatName= dataDiscretization(trainData, featNames) #根據信息增益離散化
for i in range(testData.shape[1]-1): #根據測試集的區分點離散化訓練集
splitPoint = float(discritizationFeatName[i].split('<=')[-1])
testData[:, i] = [1 if x<=splitPoint else 0 for x in testData[:, i]]
decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

clf = DecisionTreeClassifier('entropy')
clf.fit(trainData[:, :-1], trainData[:, -1])
clf.predict(testData[:, :-1])
scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))

print 'score: ', np.mean(scoreL)
print 'score-sk: ', np.mean(scoreL_sk)
fig = plt.figure(figsize=(10, 4))
plt.subplot(1,2,1)
pd.Series(scoreL).hist(grid=False, bins=10)
plt.subplot(1,2,2)
pd.Series(scoreL_sk).hist(grid=False, bins=10)
plt.show()
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
兩者准確率分別為：
score: 0.7037894736842105
score-sk: 0.7044736842105263

准確率分布如下：

兩者的結果非常一樣。
（但是。。為什麼根據信息熵離散化得到的准確率比直接用均值離散化的准確率還要低啊？？哇的哭出聲。。）

最後一次決策樹圖形如下：

決策樹剪枝
由於決策樹是完全依照訓練集生成的，有可能會有過擬合現象，因此一般會對生成的決策樹進行剪枝。常用的是通過決策樹損失函數剪枝，決策樹損失函數表示為:
C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T|
C
a

(T)=
t=1
∑
T

N
t

H
t

(T)+α∣T∣

其中，H t ( T ) H_t(T)H
t

(T)表示葉子節點t的熵值，T表示決策樹的深度。前項∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T)∑
t=1
T

N
t

H
t

(T)是決策樹的經驗損失函數當隨著T的增加，該節點被不停的劃分的時候，熵值可以達到最小，然而T的增加會使後項的值增大。決策樹損失函數要做的就是在兩者之間進行平衡，使得該值最小。
對於決策樹損失函數的理解，如何理解決策樹的損失函數? - 陶輕松的回答 - 知乎這個回答寫得挺好，可以按照答主的思路理解一下

C4.5演算法
ID3演算法通過信息增益來進行特徵選擇會有一個比較明顯的缺點：即在選擇的過程中該演算法會優先選擇類別較多的屬性（這些屬性的不確定性小，條件熵小，因此信息增益會大），另外，ID3演算法無法解決當每個特徵屬性中每個分類都只有一個樣本的情況（此時每個屬性的條件熵都為0）。
C4.5演算法ID3演算法的改進，它不是依據信息增益進行特徵選擇，而是依據信息增益率，它添加了特徵分裂信息作為懲罰項。定義分裂信息：
S p l i t I n f o ( X , Y ) = − ∑ i n ∣ X i ∣ ∣ X ∣ log ⁡ ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|}
SplitInfo(X,Y)=−
i
∑
n

∣X∣
∣X
i

∣

log
∣X∣
∣X
i

∣

則信息增益率為：
G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)}
GainRatio(X,Y)=
SplitInfo(X,Y)
d(X,Y)

關於ID3和C4.5演算法
在學習分類回歸決策樹演算法時，看了不少的資料和博客。關於這兩個演算法，ID3演算法是最早的分類演算法，這個演算法剛出生的時候其實帶有很多缺陷：

無法處理連續性特徵數據
特徵選取會傾向於分類較多的特徵
沒有解決過擬合的問題
沒有解決缺失值的問題
即該演算法出生時是沒有帶有連續特徵離散化、剪枝等步驟的。C4.5作為ID3的改進版本彌補列ID3演算法不少的缺陷：

通過信息最大增益的標准離散化連續的特徵數據
在選擇特徵是標准從「最大信息增益」改為「最大信息增益率」
通過加入正則項系數對決策樹進行剪枝
對缺失值的處理體現在兩個方面：特徵選擇和生成決策樹。初始條件下對每個樣本的權重置為1。
特徵選擇：在選取最優特徵時，計算出每個特徵的信息增益後，需要乘以一個**「非缺失值樣本權重占總樣本權重的比例」**作為系數來對比每個特徵信息增益的大小
生成決策樹：在生成決策樹時，對於缺失的樣本我們按照一定比例把它歸屬到每個特徵值中，比例為該特徵每一個特徵值占非缺失數據的比重
關於C4.5和CART回歸樹
作為ID3的改進版本，C4.5克服了許多缺陷，但是它自身還是存在不少問題：

C4.5的熵運算中涉及了對數運算，在數據量大的時候效率非常低。
C4.5的剪枝過於簡單
C4.5隻能用於分類運算不能用於回歸
當特徵有多個特徵值是C4.5生成多叉樹會使樹的深度加深
————————————————
版權聲明：本文為CSDN博主「Sarah Huang」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/weixin_44794704/article/details/89406612

⑥ 關於剪枝的資料

1、果樹修剪有冬剪和夏剪兩種。2、修剪主要是剪除徒長枝、下垂枝、背上枝、過密枝、病蟲枝和弱小枝，修剪可以控制結果量，使果樹結果質量得到提高。3、修剪是為果樹整形，梨樹為三主枝疏散分層形，桃為三主枝開心形，石榴為自然圓頭形。4、夏季修剪在6月至8月，只要你覺得密，可以從分枝處剪掉一部分小枝，能透光就形，但別把結果枝剪了，否則就吃不到果子了。5、冬季修剪以短剪為主，就是把枝條從頂部剪去一部分，3分之1 或2分之1 ，目的是促進果樹生長，減少結果，也可以剪去部分結果枝，因為果樹的結果有一個因果關系，結多了果子就小了。
果樹春季復剪，是對冬剪的補充和完善，一般在果樹萌芽後能清楚地辨認出花芽時進行，最好在花蕾膨大前完成。果樹春季復剪要先剪成年樹、弱樹或開花早的品種，後剪幼齡樹、旺樹和開花晚的品種。另外果樹春季復剪要因品種、樹齡和樹勢等具體情況而定。其次要在修剪口塗愈傷防腐膜防止水分蒸發和營養消耗。
對於盛果期的大樹，要選留飽滿和葉片多的花芽，去掉瘦弱和葉片少的花芽。按生長枝和結果枝為3:1的比例，使其負載更趨合理。對於花量多的大樹，要適當疏除弱枝和弱芽，多留壯枝和壯芽，更新衰老和過密的枝條。對花芽少的幼齡樹，要多留花芽，疏除過密的營養枝；冬剪要配合清園，除將病弱枝帶出園外集中燒毀以外還要進行全園普噴護樹將軍消毒殺菌保護樹體安全越冬。

⑦ 模型壓縮：剪枝演算法

過參數化主要是指在訓練階段，在數學上需要進行大量的微分求解，去捕抓數據中的微小變化信息，一旦完成迭代式的訓練之後，網路模型推理的時候就不需要這么多參數。而剪枝演算法正是基於過參數化的理論基礎而提出的。

剪枝演算法核心思想就是減少網路模型中參數量和計算量，同時盡量保證模型的性能不受影響。

那在AI框架中，實際上剪枝主要作用在右下角的端側模型推理應用場景中，為的就是讓端側模型更小，無論是平板、手機、手錶、耳機等小型IOT設備都可以輕松使用AI模型。而實際在訓練過程更多體現在剪枝演算法和框架提供的剪枝API上面。

實際上大部分剛接觸剪枝演算法的時候，都會從從宏觀層面去劃分剪枝技術，主要是分為Drop Out和Drop Connect兩種經典的剪枝演算法，如下圖所示。

1）Drop Out：隨機的將一些神經元的輸出置零，稱之為神經元剪枝。

2）Drop Connect：隨機將部分神經元間的連接Connect置零，使得權重連接矩陣變得稀疏。

下面會把剪枝的更多種方式呈現出來，可能會稍微復雜哈。從剪枝的粒度來劃分，可以分為結構化剪枝和非結構化剪枝，2個剪枝結構方法。下面來看看具體的剪枝方法有4種：

細粒度剪枝、向量剪枝、核剪枝在參數量與模型性能之間取得了一定的平衡，但是網路模型單層的神經元之間的組合結構發生了變化，需要專門的演算法或者硬體結構來支持稀疏的運算，這種叫做 結構化剪枝（Unstructured Pruning） 。

其中，非結構化剪枝能夠實現更高的壓縮率，同時保持較高的模型性能，然而會帶來網路模型稀疏化，其稀疏結構對於硬體加速計算並不友好，除非底層硬體和計算加速庫對稀疏計算有比較好的支持，否則剪枝後很難獲得實質的性能提升。

濾波器剪枝（Filter-level）主要改變網路中的濾波器組和特徵通道數目，所獲得的模型不需要專門的演算法和硬體就能夠運行，被稱為 結構化剪枝（Structured Pruning） 。結構化剪枝又可進一步細分：可以是channel-wise，也可以是filter-wise，還可以是在shape-wise。

結構化剪枝與非結構化剪枝恰恰相反，可以方便改變網路模型的結構特徵，從而達到壓縮模型的效果，例如知識蒸餾中的student網路模型、NAS搜索或者如VGG19和VGG16這種裁剪模型，也可以看做變相的結構化剪枝行為。

雖然剪枝演算法的分類看上去很多，但是核心思想還是對神經網路模型進行剪枝，目前剪枝演算法的總體流程大同小異，可以歸結為三種：標准剪枝、基於子模型采樣的剪枝、以及基於搜索的剪枝，如下圖所示。

標准剪枝是目前最流行的剪枝流程，在Tensorflow、Pytroch都有標準的介面。主要包含三個部分：訓練、剪枝、以及微調。

1） 訓練 ：首先是對網路模型進行訓練。在剪枝流程中，訓練部分主要指預訓練，訓練的目的是為剪枝演算法獲得在特定基礎SOTA任務上訓練好的原始模型。

3） 微調 ：微調是恢復被剪枝操作影響的模型表達能力的必要步驟。結構化模型剪枝會對原始模型結構進行調整，因此剪枝後的模型參數雖然保留了原始的模型參數，但是由於模型結構的改變，剪枝後模型的表達能力會受到一定程度的影響。實現上，微調網路模型，參數在計算的時候先乘以該Mask，Mask為1的參數值將繼續訓練通過BP調整梯度，而Mask為0的部分因為輸出始終為0則不對後續部分產生影響。

4） 再剪枝 ：再剪枝過程將微調之後的網路模型再送到剪枝模塊中，再次進行模型結構評估和執行剪枝演算法。目的是使得每次剪枝都在性能更優的模型上面進行，不斷迭代式地進行優化剪枝模型，直到模型能夠滿足剪枝目標需求。

最後輸出模型參數儲存的時候，因為有大量的稀疏，所以可以重新定義儲存的數據結構， 僅儲存非零值以及其矩陣位置。重新讀取模型參數的時候，就可以還原矩陣。

除標准剪枝之外，基於子模型采樣的剪枝《EagleEye: Fast sub-net evaluation for efficient neural network pruning》最近也表現出比較好的剪枝效果。得到訓練好的模型之後，進行子模型采樣過程。一次子模型采樣過程為：

1）對訓練好的原模型中可修剪的網路結構，按照剪枝目標進行采樣，采樣過程可以是隨機的，也可以按照網路結構的重要性或者通過KL散度計算進行概率采樣。

2）對采樣後的網路結構進行剪枝，得到采樣子模型。子模型采樣過程通常進行 次，得到 個子模型（ ≥1）, 之後對每一個子模型進行性能評估。子模型評估結束之後，選取最優的子模型進行微調以得倒最後的剪枝模型。

基於搜索的剪枝主要依靠強化學習等一系列無監督學習或者半監督學習演算法，也可以是神經網路結構搜索相關理論。

給定剪枝目標之後，基於搜索的剪枝在網路結構中搜索較優的子結構，這個搜索過程往往伴隨著網路參數的學習過程，因此一些基於搜索的剪枝演算法在剪枝結束後不需要再進行微調。

這幾年神經網路剪枝pruning作為模型壓縮技術的四小龍之一，正在受到越來越多的關注。當然，各種更好的pruning參數選取方法一定還會層出不窮。另外，從趨勢來看，以下幾個方向值得關註：

打破固定假設 ：挑戰已有的固有的假設，例如ICLR2019會議的best paper彩票假說《The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks 》的出現。還有一開始提到的對於over-parameterization，與重用已有參數是否有有益的反思非常有意思。這樣的工作會給剪枝演算法非常大的啟發，從而根本改變解決問題的思路。

自動化剪枝 ：隨著AutoML的大潮，越來越多的演算法開始走向自動化。模型壓縮能拉下嗎？當然不能。經過前面的介紹我們知道，像ADC，RNP，N2N Learning這些工作都是試圖將剪枝中部分工作自動化。如量化中的《HAQ: Hardware-Aware Automated Quantization》考慮網路中不同層信息的冗餘程度不一樣，所以自動化使用混合量化比特進行壓縮。

與NAS融合 ：如前面模型剪枝流程中提到，剪枝演算法與神經網路搜索NAS的界限已經模糊了。NAS有針對結構化剪枝進行搜索方法，如One-Shot Architecture Search是先有一個大網路，然後做減法。NAS與模型壓縮兩個一開始看似關系不是那麼大的分支，在近幾年的發展過程中因為下游任務和部署場景的需求，最後似乎會走到一塊去。這兩個分支今天有了更多的交集，也必將擦出更多的火花。

與GAN融合 ：這幾年機器學習最火熱的分支之一GAN，正在不斷滲透到已有領域，在pruning中也開始有它的身影。如2019年《Towards Optimal Structured CNN Pruning via Generative Adversarial Learning》讓generator生成裁剪後網路，discrimintor來判別是否屬於原網路還是裁剪後網路，從而進行更有效的網路結構化裁剪。

硬體稀疏性支持 ：剪枝會給神經網路模型帶來稀疏性特徵，參數稀疏性在計算中會有大量的索引，所以並不能加速。現在雖然有像cuSPARSE這樣的計算庫，但底層硬體AI晶元本身設計並不是專門為稀疏數據處理打造的。如果能將稀疏計算和處理能力做進晶元那必將極大提高計算效率。僅2021年中國就推出了10+款基於ASIC的AI加速晶元，相信針對稀疏性場景的支持在未來會有所突破。

模型壓縮演算法中針對已有的模型，有：張量分解，模型剪枝，模型量化。針對新構建的網路，有：知識蒸餾，緊湊網路設計等方法。

剪枝只是模型壓縮方法中的一種，它與其它模型壓縮方法並不沖突，因此會與量化、蒸餾、NAS、強化學習等方法慢慢融合，這些都是很值得研究的方向。另外在上面的發展來看，打破固有的假設定義，與NAS、GAN、AutoML、RL等技術進行相互的融合，可能到最後會模糊purning方式，出現新的範式或者壓縮模式也是很吸引的。

⑧ 棋類游戲的演算法有哪些

棋類游戲的演算法有哪些

棋類游戲通常包含三大要素：棋盤、棋子和游戲規則，其中游戲規則又包括勝負判定規則、落子的規則以及游戲的基本策略。下面我來給大家講講各類棋類游戲的演算法。

除了棋盤和棋子的建模，棋類游戲最重要的部分就是AI演算法的設計。目前棋類游戲的AI基本上就是帶啟發的搜索演算法，那麼常用的搜索演算法有哪些呢?

1. 博弈與博弈樹

博弈可以理解為有限參與者進行有限策略選擇的競爭性活動，比如下棋、打牌、競技、戰爭等。根據參與者種類和策略選擇的方式可以將博弈分成很多種，比如“二人零和、全信息、非偶然”博弈，也就是我們常說的零和博弈(Zero-sum Game)。所謂“零和”，就是有贏必有輸，不存在雙贏的結果。所謂“全信息”，是指參與博弈的雙方進行決策時能夠了解的信息是公開和透明的，不存在信息不對稱的情況。比如棋類游戲的棋盤和棋子狀態是公開的，下棋的雙方都可以看到當前所有棋子的位置，但是很多牌類游戲則不滿足全信息的條件，因為牌類游戲都不會公開自己手中的牌，也看不到對手手中的牌。所謂的“非偶然”，是指參與博弈的雙方的決策都是“理智”的行為，不存在失誤和碰運氣的情況。

在博弈過程中，任何一方都希望自己取得勝利，當某一方當前有多個行動方案可供選擇時，他總是挑選對自己最為有利同時對對方最為不利的那個行動方案。當然，博弈的另一方也會從多個行動方案中選擇一個對自己最有利的方案進行對抗。參與博弈的雙方在對抗或博弈的過程中會遇到各種狀態和移動(也可能是棋子落子)的選擇，博弈雙方交替選擇，每一次選擇都會產生一個新的棋局狀態。

假設兩個棋手(可能是兩個人，也可能是兩台計算機)MAX和MIN正在一個棋盤上進行博弈。當MAX做選擇時，主動權在MAX手中，MAX可以從多個可選決策方案中任選一個行動，一旦MAX選定某個行動方案後，主動權就轉移到了MIN手中。MIN也會有若干個可選決策方案，MIN可能會選擇任何一個方案行動，因此MAX必須對做好應對MIN的每一種選擇。如果把棋盤抽象為狀態，則MAX每選擇一個決策方案就會觸發產生一個新狀態，MIN也同樣，最終這些狀態就會形成一個狀態樹，這個附加了MAX和MIN的決策過程信息的狀態樹就是博弈樹(Game Tree)。

2. 極大極小值搜索演算法

極大極小值(Min-Max)搜索演算法是各種博弈樹搜索演算法中最基礎的搜索演算法。假如MAX和MIN兩個人在下棋，MAX會對所有自己可能的落子後產生的局面進行評估，選擇評估值最大的局面作為自己落子的選擇。這時候就該MIN落子，MIN當然也會選擇對自己最有利的局面，這就是雙方的博弈，即總是選擇最小化對手的'最大利益(令對手的最大利益最小化)的落子方法。作為一種博弈搜索演算法，極大極小值搜索演算法的名字就由此而來。

3. 負極大值搜索演算法

博弈樹的搜索是一個遞歸的過程，極大極小值演算法在遞歸搜索的過程中需要在每一步區分當前評估的是極大值節點還是極小值節點。1975年Knuth和Moore提出了一種消除MAX節點和MIN節點區別的簡化的極大極小值演算法，稱為負極大值演算法Negamax。該演算法的理論基礎是：

max(a,b) = -min(-a, -b)

簡單地將遞歸函數MiniMax()返回值取負再返回，就可以將所有的MIN 節點都轉化為MAX節點，對每個節點的搜索都嘗試讓節點值最大，這樣就將每一步遞歸搜索過程都統一起來。

4. “α-β”剪枝演算法

有很多資料將“α-β”剪枝演算法稱為“α-β”搜索演算法，實際上，它不是一種獨立的搜索演算法，而是一種嫁接在極大極小值演算法和負極大值演算法上的一種優化演算法。“α-β”剪枝演算法維護了一個搜索的極大極小值窗口：[α,β]。其中α表示在搜索進行到當前狀態時，博弈的MAX一方所追尋的最大值中最小的那個值(也就是MAX的最壞的情況)。在每一步的搜索中，如果MAX所獲得的極大值中最小的那個值比α大，則更新α值(用這個最小值代替α)，也就是提高α這個下限。

而β表示在搜索進行到當前狀態時，博弈的MIN一方的最小值中最大的那個值(也就是MIN的最壞的情況)。在每一步的搜索中，如果MIN所獲得的極小值中最大的那個值比β小，則更新β值(用這個最大值代替β)，也就是降低β這個上限。當某個節點的α≥β時，說明該節點的所有子節點的評估值既不會對MAX更有利，也不會對MIN更有利，也就是對MAX和MIN的選擇不會產生任何影響，因此就沒有必要再搜索這個節點及其所有子節點了。

5. 估值函數

對於很多啟發式搜索演算法，其“智力”的高低基本上是由估值函數(評估函數)所決定，棋類游戲的博弈樹搜索演算法也不例外。

估值函數的作用是把一個棋局量化成一個可直接比較的數字，這個數字在一定程度上能反映取勝的概率。棋局的量化需要考慮很多因素，量化結果是這些因素按照各種權重組合的結果。這些因素通常包括棋子的戰力(棋力)、雙方棋子佔領的空間、落子的機動性、威脅性(能吃掉對方的棋子)、形和勢等。

6. 置換表與哈希函數

置換表(transposition table)也是各種啟發式搜索演算法中常用的輔助演算法，它是一種以空間換時間的策略，使用置換表的目的就是提高搜索效率。一般情況下，置換表中的每一項代表者一個棋局中最好的落子方法，直接查找置換表獲得這個落子方法能避免耗時的重復搜索，這就是使用置換表能大幅提高搜索效率的原理。

使用置換表最大的問題是置換表的組織和查找的效率。一般來說，置換表越大，查找的命中率就越高。但這個關系不是絕對的，當置換表大小達到一定規模後，不僅不會再提高命中率，反而會因為耗時的查找操作影響演算法的效率。所以置換表不是越大越好，需要根據計算機的性能以及搜索的深度選擇一個合適的大小。此外，為了查找操作更高效，通常都會用可直接訪問的哈希表方式組織置換表，哈希函數的性能就成為影響置換表性能的重要因素。棋類游戲普遍採用Zobrist哈希演算法。