監督學習
感知機
-
概念：
-
感知機模型的基本形式是：
\(f(x) = sign(w \cdot x + b)\)
其中，\(x\) 是輸入樣本的特征向量，\(w\) 是權值向量，\(b\) 是偏置量，\(w \cdot x\) 表示向量 \(w\) 和 \(x\) 的點積，\(sign\) 函式表示符號函式，當輸入大于 0 時輸出 1，否則輸出 -1，
-
-
要求模型必須線性可分
K近鄰
-
基本思想：是對于一個新的輸入樣本，在訓練資料集中找出與之最鄰近的k個樣本，并將其預測結果作為該樣本的輸出，
-
步驟
- 計算測驗樣本與訓練樣本集中每個樣本的距離；
- 選取距離最近的k個訓練樣本；
對于分類問題，采用投票法，即將k個樣本中出現最多的類別作為預測結果；對于回歸問題，采用平均值，即將k個樣本的輸出值的平均值作為預測結果，
-
選取最近的k個樣本一般采用kd樹來進行實作，
kd樹采取方差最大的那一變數（的中位數）進行分割
kd樹的查詢首先尋找到該點所在的子節點的部分，然后逐漸向上遞回比較父節點和父節點的另一個子節點是否在某個領域（當前的最小距離）內具有交際，
樸素貝葉斯
- 假設每個特征之間相互獨立，即\(P(X_1,X_2,X_3,...,X_n|Y)=P(X_1|Y)*P(X_2|Y)*...*P(X_n|Y)\)
- 后驗概率最大化，無論是采用極大似然估計或者貝葉斯估計，都可以推匯出相應的公式，
- 假設有 \(n\) 個特征和 \(m\) 個類別，我們需要分類一個新的樣本 \(x\)，其中 \(x_i\) 表示第 \(i\) 個特征的取值，根據貝葉斯定理，可以計算出給定樣本 \(x\) 屬于第 \(j\) 個類別的后驗概率 \(P(C_j | x)\)，即：
?
其中，\(P(C_j)\) 表示類別 \(j\) 在訓練集中的先驗概率，\(P(x | C_j)\) 表示樣本 \(x\) 在給定類別 \(j\) 的條件下的概率密度函式（通常假設為高斯分布,或者直接使用頻率代替概率），\(P(x)\) 表示樣本 \(x\) 在所有類別下的概率，由于分母 \(P(x)\) 對于所有類別來說都是相同的，因此可以省略，只需要計算分子即可，此時，\(P(C_j | x)\) 可以看作樣本 \(x\) 屬于類別 \(j\) 的“置信度”，將樣本分配給概率最大的類別即可，
決策樹
- 分為三個步驟：特征選擇、樹的生成和剪枝，
- 需要了解下面幾個概念：
-
不同的決策樹演算法就是基于上述不同的指標來進行特征的選擇，
-
剪枝演算法：首先定義一個損失函式\(L(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|,其中T為子節點，N_t為子節點的樣本點數量，\)對于決策樹每一個子節點，如果多個子節點的損失大于父節點將他們吸收的損失，那么父節點就合并所有的子節點，并向上計算，可以通過遞回（或者非遞回）的動態規劃進行解決，
logitics和最大熵模型
類似感知機，只是將最終的函式由sign改為了logistics，
支持向量機
首先了解以下概念：
- 函式間隔.\(y|wx+b|\)
- 幾何間隔.\(y\frac{|wx+b|}{|w|}\)
- 線性支持向量機就是要最大幾何間隔，
- 拉格朗日對偶原理和拉格朗日乘子法，拉格朗日對偶
- 支持向量
- 合頁函式最優化求解和支持向量的原問題的等價性
- SMO啟發式方法
AdaBoost
假定具備一個弱分類器（該分類準確率僅僅比隨機猜測的概率高一些），AdaBoost通過綜合多種分類器的線性疊加，從而實作一個強分類器，
AdaBoost具有兩種等價的解釋：
- 通過調整訓練資料的權重(增加錯誤樣例的權重，減小正確樣例的權重)，從而訓練得到不同的弱分類器\(G_1,G_2...G_m和相應的權重\alpha_1...\alpha_m\),最終線性疊加得到\(f=\alpha_1G_1+...+\alpha_mG_m\).
- AdaBoost等價于不斷求解殘差的擬合，
EM演算法
EM演算法用的特別廣泛，需要完全理解它的推導程序，
- EM演算法的推導
- EM演算法求解高斯混合模型
- EM演算法的推廣，F函式，
隱馬爾可夫模型
- 三個基本問題：預測、評估和學習
- 前向、后向演算法
- 維特比演算法，本質上三個演算法都是動態規劃
- Baum-Welch演算法求解學習問題
條件隨機場
- 勢函式的定義和條件隨機場的定義
- 使用前向后向演算法求解概率
- 學習演算法，使用迭代尺度、擬牛頓進行學習
無監督學習
聚類演算法
- 層次化聚類
- k均值聚類
奇異值分解
矩陣的SVD分解，并對\(\Sigma\)進行截斷（取前k個奇異值）
主成分分析
SVD的應用
潛在語意分析
概率潛在語意分析
馬爾可夫蒙特卡洛方法
-
拒絕采樣法
-
Metropolis-Hasting采用法
- 初始化：給定樣本起始值 \(x^{(0)}\)
- 對于 \(t=1,2,\ldots,T\)，進行如下迭代：
從給定的候選分布 \(q(x^{(t)}|x^{(t-1)})\) 中抽取一個樣本 \(x^\prime\)
計算接受概率 $$\alpha=\min({1,\frac{p(x\prime)}{p(x)}\frac{q(x{(t-1)}|x\prime)}{q(x\prime|x)})}$$ - 以概率 \(\alpha\) 接受樣本 \(x^\prime\)，即 \(x^{(t)}=x^\prime\)，否則拒絕樣本 \(x^\prime\)，即 \(x^{(t)}=x^{(t-1)}\)
- 回傳樣本集合 \({x^{(1)},x^{(2)},\ldots,x^{(T)}}\)
其中，\(T\) 是迭代次數，\(x^{(t)}\) 表示第 \(t\) 次迭代后的樣本值，\(p(x)\) 表示目標概率分布，\(q(x^{(t)}|x^{(t-1)})\) 表示給定上一個狀態 \(x^{(t-1)}\) 的條件下，生成下一個狀態 \(x^{(t)}\) 的候選分布，\(\alpha\) 表示接受候選狀態的概率，即 \(x^{(t)}\) 作為下一個狀態的概率，\(\min{1,\cdots}\) 保證了接受概率不會大于 \(1\)，從而保證了接受的狀態總是有意義的，
-
吉布斯采用法
吉布斯采樣（Gibbs Sampling）是一種基于馬爾可夫鏈蒙特卡羅（MCMC）方法的采樣演算法，用于從多維分布中抽取樣本，它通過迭代更新每個維度的條件概率分布來得到樣本，吉布斯采樣的公式如下：
- 初始化：給定樣本起始值 \(x^{(0)}=(x_1^{(0)},x_2^{(0)},\ldots,x_n^{(0)})\)
對于 \(t=1,2,\ldots,T\)，進行如下迭代：
對于第 \(i\) 維，計算條件概率 \(p(x_i|x_1^{(t)},\ldots,x_{i-1}^{(t)},x_{i+1}^{(t-1)},\ldots,x_n^{(t-1)})\) - 從條件概率分布 \(p(x_i|x_1^{(t)},\ldots,x_{i-1}^{(t)},x_{i+1}^{(t-1)},\ldots,x_n^{(t-1)})\) 中抽取一個樣本，即 \(x_i^{(t+1)}\sim p(x_i|x_1^{(t)},\ldots,x_{i-1}^{(t)},x_{i+1}^{(t-1)},\ldots,x_n^{(t-1)})\)
- 回傳樣本集合 \({x^{(1)},x^{(2)},\ldots,x^{(T)}}\)
其中，\(T\) 是迭代次數，\(x_i^{(t)}\) 表示第 \(t\) 次迭代后第 \(i\) 維的值，\(p(x_i|x_1^{(t)},\ldots,x_{i-1}^{(t)},x_{i+1}^{(t-1)},\ldots,x_n^{(t-1)})\) 表示在給定其他維度取值的情況下第 \(i\) 維的條件概率分布，
吉布斯采樣的核心思想是，通過條件概率分布來描述多維分布的聯合概率分布，從而能夠通過單個維度的條件概率來更新樣本值，避免了計算聯合概率分布的復雜度，通過多次迭代，吉布斯采樣可以得到服從多維分布的樣本集合，從而可以用于估計多維分布的各種性質，需要注意的是，吉布斯采樣的收斂性和穩定性是需要保證的，否則會導致采樣結果不準確或者不收斂，針對不同的問題和資料分布，需要進行適當的調整和優化，
- 初始化：給定樣本起始值 \(x^{(0)}=(x_1^{(0)},x_2^{(0)},\ldots,x_n^{(0)})\)
潛在迪利克雷分配
PageRank演算法
\[PR(p_i) = \frac{1-d}{N} + d \sum_{p_j \in M(p_i)} \frac{PR(p_j)}{L(p_j)} \]其中，\(PR(p_i)\) 表示網頁 \(p_i\) 的PageRank值，\(d\) 是一個常數，稱為阻尼因子，通常取值為 0.85，\(N\) 是網頁總數，\(M(p_i)\) 表示指向網頁 \(p_i\) 的所有網頁集合，\(L(p_j)\) 表示網頁 \(p_j\) 指向的網頁數，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551075.html
標籤：其他
上一篇：[Week 18] 每日一題（C++，動態規劃，線段樹，數學）
下一篇：返回列表