(Day 26) 最小生成樹 (Minimum Spanning Tree)
在前幾天，我們學習了最短路徑問題 (Shortest Path)，例如 Dijkstra、Bellman-Ford、Floyd-Warshall、A*，今天要介紹的則是圖論中的另一個核心問題 —— 最小生成樹 (Minimum Spanning Tree, MST)
(Day 26) 長短期記憶網路 (Long Short-Term Memory)
目錄
在前一篇，我們介紹了循環神經網路 (RNN)，並指出了它在處理序列資料時的強大之處：透過「隱藏狀態」將前後資訊連結起來。然而，我們同時也看到了 RNN 的最大瓶頸——梯度消失與梯度爆炸，使得它在長距離依賴 (long-term dependency) 的學習上表現不佳。
為了解決這個問題，1997 年 Sepp Hochreiter 和 Jürgen Schmidhuber 提出了 長短期記憶網路 (LSTM)。LSTM 是 RNN 的改良版本，透過特殊的「記憶單元 (Memory Cell)」與「門控機制 (Gating Mechanism)」，大幅減緩了梯度消失的問題，成為自然語言處理 (NLP) 與序列建模的經典架構之一。
LSTM 的核心概念
LSTM 的設計目標是:
- 保留長期資訊（避免梯度消失導致遺忘）
- 選擇性遺忘不必要的資訊（避免無限累積造成干擾）
- 動態決定何時輸入、何時輸出資訊
它在傳統 RNN 的基礎上，加入了兩個關鍵設計:
- 記憶單元 (Cell State): 一條專門的「資訊高速公路」，允許資訊長距離傳遞。
- 門控機制 (Gates): 透過 sigmoid 函數控制「資訊是否允許通過」，讓模型能選擇性記住或忘記。
LSTM 的結構
一個 LSTM 單元 (cell) 主要包含三個門與一個記憶單元:
-
遺忘門 (Forget Gate)
- 決定要保留多少過去資訊。
- 公式:
$$ f_t = \sigma(W_f \cdot [h_{t-1}, x_t] + b_f) $$
- $f_t$ 越接近 0，表示忘得越多；越接近 1，表示保留越多。
-
輸入門 (Input Gate)
- 決定要加入多少新的資訊。
- 公式:
$$ i_t = \sigma(W_i \cdot [h_{t-1}, x_t] + b_i) $$
$$ \tilde{C}t = \tanh(W_C \cdot [h{t-1}, x_t] + b_C) $$
-
更新記憶單元 (Cell State Update)
- 結合遺忘門與輸入門，更新記憶單元。
- 公式:
$$ C_t = f_t \odot C_{t-1} + i_t \odot \tilde{C}_t $$
-
輸出門 (Output Gate)
- 決定輸出的隱藏狀態。
- 公式:
$$ o_t = \sigma(W_o \cdot [h_{t-1}, x_t] + b_o) $$
$$ h_t = o_t \odot \tanh(C_t) $$
其中:
- $x_t$: 當前時間步的輸入
- $h_{t-1}$: 上一時間步的隱藏狀態
- $C_{t-1}$: 上一時間步的記憶單元
- $\sigma$: sigmoid 函數（輸出範圍 [0,1]）
- $\odot$: 逐元素相乘
這樣的設計，讓 LSTM 能精確控制「要記住什麼、要忘掉什麼、要輸出什麼」。
直觀理解
可以把 LSTM 想成一個「高級筆記本」:
- 遺忘門: 擦掉過期的內容 (例如: 幾天前的天氣，對今天的心情分析可能沒用)。
- 輸入門: 記錄新資訊 (例如: 今天心情很好)。
- 記憶單元: 長期保存有價值的內容 (例如: 這個人通常喜歡週末出門）。
- 輸出門: 決定當下要提供什麼資訊 (例如: 根據前文輸出「可能會去旅行」）。
這樣一來，LSTM 就能在長序列中保持「重要資訊」，而不會像傳統 RNN 那樣很快就遺忘。
LSTM 與 RNN 的比較
| 特性 | RNN | LSTM |
|---|---|---|
| 記憶方式 | 單一隱藏狀態 $h_t$ | 記憶單元 $C_t$ + 隱藏狀態 $h_t$ |
| 長期依賴 | 容易梯度消失 | 能有效捕捉長距離依賴 |
| 訓練穩定性 | 差 | 較好 |
| 計算成本 | 較低 | 較高 (參數更多) |
| 常見應用 | 短序列 | 長序列、語言模型、翻譯 |
LSTM 的優點
- 緩解梯度消失問題: 透過記憶單元，能長距離保留資訊。
- 動態記憶: 能夠選擇性地「記住或忘記」，比 RNN 靈活。
- 泛化能力強: 在語言、語音、時間序列任務中普遍表現優秀。
LSTM 的缺點
- 計算成本高: 每個 LSTM 單元包含多個門與記憶更新，參數量大。
- 難以並行化: 序列必須逐步計算，無法像 Transformer 那樣一次處理整個序列。
- 在長序列上仍有限制: 雖然比 RNN 好，但仍難以處理超長依賴。
結語
長短期記憶網路 (LSTM) 是序列建模領域的一個重大突破，它在 RNN 的基礎上引入記憶單元與門控機制，解決了梯度消失的難題，使得模型能夠捕捉長距離依賴。
雖然今天 Transformer 已經在 NLP 等領域逐漸取代 LSTM，但在許多應用中（如時間序列、邊緣運算環境），LSTM 依舊有不可忽視的價值。對深度學習的學習者來說，LSTM 是一個必經的里程碑，因為它不僅解釋了「如何記住過去」，也揭示了「如何選擇性遺忘」的重要性。