113 年 國立成功大學數據科學研究所《計算機概論（含資料結構）》

核心觀念

Stack（堆疊）是一種遵循 後進先出（Last In, First Out, LIFO）原則的線性資料結構。

堆疊具有唯一的操作端，稱為頂端（top）：

• 新元素只能從頂端加入，稱為 push。
• 元素只能從頂端移除，稱為 pop。
• 讀取頂端元素但不移除，稱為 peek 或 top。

因此，堆疊的元素新增與刪除都限制在同一端。

解題方法

判斷敘述是否符合堆疊的基本定義即可。

題目敘述指出：

A stack data structure allows elements to be added or removed only at one end.

意思是：「堆疊資料結構只允許在其中一端加入或移除元素。」

這正是堆疊的定義。假設依序加入元素 $A$、$B$、$C$：

$$\text{push}(A),\ \text{push}(B),\ \text{push}(C)$$

此時堆疊頂端為 $C$。執行移除操作時，必須依序移除：

核心觀念

監督式學習（supervised learning）的特徵，是利用「帶有標籤的資料」進行模型訓練。

訓練資料通常表示為：

$$\mathcal{D}=\{(x_i,y_i)\}_{i=1}^{n}$$

其中：

• $x_i$：輸入特徵或觀察資料。
• $y_i$：對應的正確答案，也就是標籤（label）。
• 模型透過大量的 $(x_i,y_i)$ 配對資料，學習輸入與輸出之間的關係。

例如，使用已標示「貓」或「狗」的圖片訓練分類模型，圖片是輸入 $x_i$，貓／狗則是標籤 $y_i$。模型的目標是學習函數 $f_\theta$，使預測值 $f_\theta(x_i)$ 盡量接近正確標籤 $y_i$。

解題方法

判斷此敘述是否符合監督式學習的定義即可。

題目敘述為：

In supervised learning, the algorithm is trained with labeled data.

其中關鍵字是「supervised learning」與「labeled data」。監督式學習必須提供輸入資料及其對應的正確標籤，模型根據標籤計算預測誤差，再調整參數以降低損失函數，例如：

核心觀念

本題考查 Binary Search（二元搜尋）的時間複雜度，以及 Big-O 表示法。

二元搜尋要求資料已經排序。每次比較後，會排除目前搜尋範圍約一半的元素，因此搜尋範圍大小會依序變為：

$$n,\ \frac{n}{2},\ \frac{n}{4},\ \frac{n}{8},\ldots$$

若經過 $k$ 次比較後剩下最多一個元素，則有：

$$\frac{n}{2^k}\leq 1$$

因此：

$$2^k\geq n$$ $$k\geq \log_2 n$$

所以二元搜尋的最壞情況時間複雜度為：

$$\Theta(\log n)$$

---

解題方法

二元搜尋每一輪都將搜尋區間縮小為原本的一半。假設原始資料有 $n$ 筆，最多需要進行 $k$ 次比較：

$$\frac{n}{2^k}\leq 1$$

解得：

$$k=\lceil\log_2 n\rceil$$

每次比較只需常數時間，因此總執行時間為：

$$T(n)=\Theta(\log n)$$

這表示二元搜尋的最壞情況不是 $n\log n$，而是對數時間。

---

題目敘述判斷

敘述：

A binary search algorithm has a worst-case time complexity of $O(n\log n)$.

核心觀念

本題考查 linked list（鏈結串列）的種類與 traversal（走訪）方向。

鏈結串列由節點組成，每個節點通常包含：

1. 資料欄位（data）
2. 指標欄位（link），用來指向其他節點

走訪時，必須依照節點中的指標逐一取得後續節點。因此，鏈結串列能否雙向走訪，取決於其節點所設計的指標方向。

• 單向鏈結串列（singly linked list）：每個節點只有一個 next 指標，只能由前往後走訪。
• 雙向鏈結串列（doubly linked list）：每個節點同時具有 next 與 prev 指標，可向前、向後走訪。
• 循環鏈結串列（circular linked list）：尾端指標連回某個節點，能依指標方向循環走訪；若為雙向循環鏈結串列，也能雙向走訪。

解題方法

判斷敘述是否正確時，不能只以單向鏈結串列作為所有鏈結串列的代表，而應檢查敘述是否適用於整個資料結構類別。

題目敘述為：

A linked list can only be traversed in one direction.

其意思是：「鏈結串列只能沿一個方向走訪。」

單向鏈結串列確實只能沿著 next 指標走訪：

$$\text{head} \rightarrow \text{node}_1 \rightarrow \text{node}_2 \rightarrow \cdots$$

但雙向鏈結串列的節點具有兩個方向的指標：

核心觀念

本題考查機器學習中的「過度擬合」（overfitting）。

過度擬合是指模型過度適應訓練資料，不僅學到資料中的一般規律，也把資料中的隨機雜訊、異常值或偶然特徵一併記住。因此，模型在訓練資料上的表現很好，但在未看過的測試資料上表現較差，泛化能力不足。

常見特徵如下：

• 模型複雜度過高；
• 訓練誤差很低；
• 測試誤差相對較高；
• 模型捕捉到資料中的 noise，而非真正具有普遍性的規律。

解題方法

判斷敘述是否正確時，檢查它是否符合過度擬合的定義：

1. 敘述指出模型「太複雜」；
2. 敘述指出模型捕捉到資料中的「雜訊」；
3. 這兩點正是過度擬合的典型成因與現象。

因此，此敘述符合過度擬合的標準定義。

以模型誤差表示，若模型複雜度增加，通常會使訓練誤差持續下降；但當模型開始記住雜訊時，測試誤差反而上升：

$$\text{Training Error} \downarrow,\qquad \text{Testing Error} \uparrow$$

核心觀念

本題考查排序演算法的「穩定性（stable）」。

若兩筆資料的排序鍵值相同，排序前後仍維持其原本相對順序，則稱該排序演算法具有穩定性。例如：

原始順序	鍵值
$A$	5
$B$	5

若排序後仍為 $A,B$，則穩定；若變成 $B,A$，則不穩定。

QuickSort 的核心流程是選擇一個 pivot，將資料分割成：

• 小於 pivot 的部分
• 等於 pivot 的部分
• 大於 pivot 的部分

接著對子區間遞迴排序。標準 QuickSort 通常採用原地（in-place）交換元素，交換過程可能改變相同鍵值資料的相對順序。

解題方法

判斷排序演算法是否穩定，最直接的方法是觀察：

1. 演算法是否會交換元素。
2. 相同鍵值的元素是否可能因交換而跨越彼此。
3. 能否構造出相同鍵值元素順序被改變的反例。

考慮資料：

$$[(2,A),(1,X),(2,B)]$$

其中括號前的數字是排序鍵值，字母用來區分兩筆鍵值同為 $2$ 的資料。原本相同鍵值元素的順序是：

$$(2,A)\ \text{在}\ (2,B)\ \text{之前}$$

若 QuickSort 選擇最後一個元素 $(2,B)$ 作為 pivot，並採用常見的分割方式，分割過程中的交換可能使 $(2,A)$ 與 $(2,B)$ 的位置互換。排序結果可能為：

$$[(1,X),(2,B),(2,A)]$$

核心觀念

本題考查排序陣列上的二分搜尋法（Binary Search）。

二分搜尋法的前提是：陣列 arr 已經按照遞增順序排列。每一次搜尋都檢查目前搜尋範圍的中間元素：

• 若 arr[mid] == target，找到目標，回傳索引。
• 若 arr[mid] < target，因為陣列遞增，中點左側的元素皆小於目標，應捨棄左半部。
• 若 arr[mid] > target，中點右側的元素皆大於目標，應捨棄右半部。

搜尋範圍以兩個索引表示：

$$[left,\ right]$$

中點計算為：

$$mid = left + \frac{right-left}{2}\text{ 的整數商}$$

程式中使用：

mid = left + (right - left) // 2

這種寫法比 (left + right) // 2 更能避免索引相加時的整數溢位問題。

---

解題方法

當 arr[mid] < target 時：

由於陣列已排序，對所有 $i \leq mid$，皆有：

$$arr[i] \leq arr[mid] < target$$

因此索引 $0$ 到 $mid$ 的元素都不可能是目標，新的搜尋範圍必須從 mid + 1 開始：

left = mid + 1

當 arr[mid] > target 時：

由於陣列已排序，對所有 $i \geq mid$，皆有：

$$arr[i] \geq arr[mid] > target$$

因此索引 $mid$ 到右端的元素都不可能是目標，新的搜尋範圍必須截止於 mid - 1：

right = mid - 1

完成後的函式如下：

核心觀念

Hash table（雜湊表）是一種以「鍵值」快速儲存與搜尋資料的資料結構。它使用雜湊函數 $h(k)$ 將鍵值 $k$ 轉換為陣列索引：

$$h(k) \rightarrow 0,1,\ldots,m-1$$

其中 $m$ 是雜湊表的容量。資料通常以 $(key, value)$ 的形式儲存，例如：

• key：學號、姓名或資料編號
• value：對應的成績、資料內容或記憶體位置

理想情況下，插入、搜尋與刪除的平均時間複雜度皆為：

$$O(1)$$

但不同鍵值可能經過雜湊函數後得到相同索引，這種情況稱為 collision（碰撞）：

$$k_1 \ne k_2,\qquad h(k_1)=h(k_2)$$

碰撞是雜湊表必須處理的核心問題。

解題方法

回答本題可分成兩部分：

1. 說明雜湊表的定義與運作方式。
2. 說明發生碰撞時，如何將多筆資料安排在同一個雜湊表中。

雜湊函數通常希望具備以下特性：

• 計算快速。
• 能將鍵值平均分散到各個索引。
• 不同鍵值產生相同索引的機率盡量低。

然而，只要鍵值數量大於表格容量，根據鴿籠原理，碰撞必然發生。因此不能只依賴「避免碰撞」，而必須設計 collision resolution（碰撞處理）方法。

碰撞處理方法一：分離鏈結法

Separate chaining（分離鏈結法）是在每個陣列位置建立一個串列、鏈結串列或其他容器。

假設雜湊函數為：

$$h(k)=k\bmod 7$$

插入鍵值 $10$、$17$、$24$：

$$h(10)=3,\qquad h(17)=3,\qquad h(24)=3$$

三個鍵值都發生碰撞，因此可將它們放在索引 $3$ 的鏈結串列中：

$$\text{table}[3]\rightarrow 10\rightarrow 17\rightarrow 24$$

搜尋鍵值時，先計算雜湊值找到對應位置，再沿著該位置的串列逐一比對鍵值。

其平均時間複雜度與負載因子有關。負載因子定義為：

$$\alpha=\frac{n}{m}$$

其中 $n$ 是資料筆數，$m$ 是雜湊表容量。若雜湊函數分布均勻，鏈結串列的平均長度約為 $\alpha$，因此搜尋平均為：

$$O(1+\alpha)$$

最壞情況下，所有鍵值都落在同一個位置，搜尋會退化為：

$$O(n)$$

分離鏈結法的優點是表格容量不必大於資料筆數，且刪除資料相對簡單；缺點是需要額外的鏈結結構與指標空間，資料的記憶體位置也較不連續。

碰撞處理方法二：開放定址法

Open addressing（開放定址法）要求所有資料都直接存放在雜湊表陣列內。發生碰撞時，依照探測規則尋找其他空位置。

線性探測

Linear probing（線性探測）在碰撞後依序檢查下一個位置：

$$h_i(k)=(h(k)+i)\bmod m,\qquad i=0,1,2,\ldots$$

若 $h(k)=3$，索引 $3$ 已被占用，便檢查 $4$、$5$、$6$，再循環回到 $0$。

核心觀念

本題考查 Red-Black Tree（紅黑樹）的平衡性質，以及其高度為 $O(\log n)$ 的原因。

紅黑樹必須滿足以下重要條件：

1. 每個節點為紅色或黑色。
2. 根節點為黑色。
3. NULL 葉節點視為黑色。
4. 紅色節點不可有紅色子節點。
5. 從任一節點到其所有後代 NULL 葉節點的路徑，包含相同數量的黑色節點，此數量稱為 black-height。

其中，第 5 項確保每條路徑的黑色節點數相同；第 4 項則限制紅色節點不能連續出現。兩者共同保證最長路徑不會超過最短路徑的兩倍。

解題方法

設從根到最近 NULL 葉節點的路徑包含 $b$ 個黑色節點。

由於紅黑樹具有相同 black-height 的性質，任何根到 NULL 葉節點的路徑都必須包含相同數量的黑色節點，即都是 $b$ 個黑色節點。

• 最短路徑至少包含 $b$ 個黑色節點，因此長度至少為 $b$。
• 因為紅色節點不能連續，最長路徑中最多只能在每個黑色節點之間插入一個紅色節點。

因此，最長路徑至多包含：

$$b \text{ 個黑色節點} + b \text{ 個紅色節點} = 2b$$

所以：

$$\text{最長路徑} \leq 2 \times \text{最短路徑}$$

選項 B 所描述的「所有路徑具有相同數量的黑色節點」是紅黑樹維持此高度比例的核心平衡性質；選項 C 則負責限制紅色節點的連續數量。

選項分析

A. Every node is either red or black

錯誤。這只是紅黑樹的顏色定義，表示每個節點必須標記為紅色或黑色，但沒有規定不同路徑上的黑色節點數，也沒有直接限制樹的高度。

核心觀念

「維度詛咒」（Curse of Dimensionality）是指資料的特徵維度增加時，資料空間的體積快速膨脹，導致資料變得稀疏；模型若要維持相同的學習品質、覆蓋密度或估計精度，通常需要大量增加訓練資料，某些情況下甚至呈指數成長。

以每個特徵分成 $k$ 個區間為例，若共有 $d$ 個特徵，整個特徵空間需要的區域數量為：

$$k^d$$

當維度 $d$ 增加時，$k^d$ 會呈指數成長。例如每個特徵分成 $10$ 個區間：

• $d=2$ 時，需要 $10^2=100$ 個區域；
• $d=5$ 時，需要 $10^5=100,000$ 個區域；
• $d=10$ 時，需要 $10^{10}$ 個區域。

若資料量沒有同步大幅增加，許多區域便沒有資料點，模型難以準確學習整個空間的分布。

解題方法

判斷此題的關鍵是掌握「維度增加造成資料需求快速上升」這個核心定義。題目詢問的是 Curse of Dimensionality 的一般意義，而不是某個由高維資料衍生出的個別問題。

因此，直接尋找描述以下現象的選項：

特徵數量增加，模型為維持相同表現而需要更多資料，且資料需求可能呈指數成長。

符合此定義的是選項 A。

高維度除了造成資料稀疏，也可能引發距離度量失效、近鄰關係不明顯、模型訓練困難，以及過度擬合風險增加等問題；但這些多屬於維度詛咒的結果或相關現象，不是本題最完整的定義。

選項分析

A. The phenomenon where models require exponentially more data as the number of features increases

核心觀念

本題考查卷積神經網路（Convolutional Neural Network, CNN）相較於傳統神經網路的主要結構特徵。

CNN 的核心設計包括：

• 局部感受野（local receptive fields）：每個神經元只連接輸入資料中的局部區域。
• 權重共享（weight sharing）：同一組卷積核在不同位置重複使用。
• 池化（pooling）：降低特徵圖的空間尺寸，提升特徵的穩定性。

其中，局部感受野使 CNN 能有效捕捉影像中的邊緣、紋理與局部形狀等空間特徵。

解題方法

傳統全連接神經網路通常將每一層的神經元與前一層所有神經元相連。若輸入為影像，這種連接方式會忽略像素之間的空間鄰近關係，且參數數量非常龐大。

CNN 則使用卷積運算。以一維情況表示，卷積核 $w$ 在輸入 $x$ 上滑動時，某一位置的輸出可寫為：

$$y_i=\sum_{j=0}^{k-1}w_jx_{i+j}+b$$

其中 $k$ 是卷積核大小。可見，輸出 $y_i$ 只使用輸入中的一小段局部資料，而非整個輸入，因此形成局部感受野。

所以，題目所問「區別於傳統神經網路的特徵」，應選擇 CNN 特有的局部連接結構。

選項分析

A. Recurrent connections（循環連接）

核心觀念

本題考查 A* 演算法與 Dijkstra 演算法在最短路徑搜尋上的差異。

A* 對每個待探索節點計算：

$$f(n)=g(n)+h(n)$$

其中：

• $g(n)$：起點到目前節點 $n$ 的實際累積成本。
• $h(n)$：節點 $n$ 到目標節點的估計成本，稱為啟發式函數（heuristic）。
• $f(n)$：經過節點 $n$ 的預估總成本。

Dijkstra 演算法只根據目前已知的實際距離選擇節點，相當於：

$$h(n)=0$$

A* 額外利用 $h(n)$ 判斷「哪個方向較接近目標」，因此通常能減少不必要的搜尋範圍。

解題方法

比較兩種演算法的節點選擇策略：

• Dijkstra：選擇目前 $g(n)$ 最小的節點，會向各個方向擴展。
• A*：選擇 $f(n)=g(n)+h(n)$ 最小的節點，會優先探索預估較接近目標的方向。

當啟發式函數具有良好估計能力，且不高估實際剩餘成本時，A* 通常比 Dijkstra 更快找到目標。其主要優勢在於 利用啟發式資訊縮小搜尋範圍。

因此正確選項為 B。

選項分析

A. A* is guaranteed to find the shortest path

錯誤。

A* 是否保證找到最短路徑，取決於啟發式函數與邊權重等條件。若 $h(n)$ 是 admissible heuristic，即：

$$h(n)\leq h^*(n)$$

其中 $h^*(n)$ 是節點 $n$ 到目標的實際最低成本，A* 才能在適當條件下保證找到最短路徑。

核心觀念

本題考查資訊理論中的 熵（entropy） 定義。

對離散隨機變數 $X$，若其可能結果為 $x_1,x_2,\ldots,x_n$，發生機率分別為 $p(x_1),p(x_2),\ldots,p(x_n)$，則 Shannon entropy 定義為：

$$H(X)=-\sum_{i=1}^{n}p(x_i)\log_2 p(x_i)$$

熵表示隨機變數結果所包含的平均資訊量，也可理解為結果發生前的不確定程度。結果越難預測，熵越高；結果越確定，熵越低。

例如：

• 若 $X$ 必定為某一結果，則 $H(X)=0$。
• 若 $X$ 有兩個結果且機率均為 $1/2$，則

$$H(X)=-2\left(\frac12\log_2\frac12\right)=1\text{ bit}$$

---

解題方法

判斷本題的關鍵，是辨認「entropy」描述的是資訊本身的不確定性，而不是傳輸系統的效能。

資訊理論中的熵主要回答：

在得知隨機結果之前，我們對該結果有多大的不確定性？

因此，熵與「系統的混亂程度、隨機性或不確定性」有關，最符合的選項是 B。

---

選項分析

A. The rate of information transmission over a noisy channel

此選項描述的是資訊在雜訊通道中的傳輸速率，通常與資料傳輸率、通道傳輸速率有關。

熵不直接表示每秒傳送多少位元，因此 A 錯誤。

B. The degree of disorder or randomness in a system

核心觀念

本題考查的是「時間序列機器學習」的資料設計與前處理，重點不只是蒐集越多資料，而是確保：

1. 資料具有預測下一期股價的資訊。
2. 資料時間對齊正確。
3. 前處理不引入未來資訊，避免資料洩漏。
4. 股票分割、配息等公司行動已被正確調整。
5. 訓練資料、驗證資料與測試資料符合真實交易時間順序。

直接預測股價 $P_{t+1}$ 容易受到不同股票價格尺度影響，因此實務上通常改預測報酬率：

$$r_{t+1}=\frac{P_{t+1}-P_t}{P_t}$$

也可使用對數報酬率：

$$r_{t+1}=\ln\left(\frac{P_{t+1}}{P_t}\right)$$

其中 $P_t$ 為第 $t$ 日的收盤價。模型的輸入是過去一段時間的資料，目標是預測未來的報酬率、價格變化量，或上漲與下跌方向。

---

解題方法

一、蒐集的資料類型

1. 市場交易資料

最基本的資料包括每日或每分鐘的：

• 開盤價（Open）
• 最高價（High）
• 最低價（Low）
• 收盤價（Close）
• 成交量（Volume）
• 成交金額
• 買賣價差、委買委賣量等市場微結構資料

若資料頻率為日資料，可將第 $t$ 日的資料表示為：

$$x_t=(O_t,H_t,L_t,C_t,V_t)$$

其中 $O_t,H_t,L_t,C_t,V_t$ 分別代表開盤價、最高價、最低價、收盤價與成交量。

2. 技術指標

由歷史價格與成交量計算技術指標，例如：

• 移動平均線（Moving Average）
• 指數移動平均線（EMA）
• 相對強弱指標（RSI）
• 隨機指標（KD）
• 移動平均收斂發散指標（MACD）
• 布林通道（Bollinger Bands）
• 歷史波動率
• 過去 $k$ 日報酬率

例如，$k$ 日移動平均為：

$$MA_t^{(k)}=\frac{1}{k}\sum_{i=0}^{k-1}C_{t-i}$$

技術指標必須只使用當時已知的資料，不能使用未來價格計算。

3. 公司基本面資料

可蒐集：

• 營收、毛利、營業利益
• 每股盈餘（EPS）
• 本益比（P/E）
• 股東權益報酬率（ROE）
• 負債比率
• 現金流量
• 資產負債表與損益表資料

基本面資料發布時間不一定等於財報所涵蓋的期間，因此必須使用「實際公開日期」對齊，而不能直接以財報季度結束日對齊。

4. 宏觀經濟資料

可納入：

• 利率與央行政策
• 匯率
• 通貨膨脹率
• 失業率
• GDP 成長率
• 大盤指數
• 商品價格，例如原油、黃金
• 國際市場指數

若預測台灣股票，也可加入加權指數、櫃買指數、美元兌新台幣匯率與美國主要股價指數。

5. 新聞與市場情緒資料

可蒐集：

• 財經新聞標題與內文
• 公司公告
• 法說會文字稿
• 社群媒體討論
• 分析師評等
• 搜尋熱度

文字資料可透過自然語言處理轉換為數值，例如情緒分數：

$$s_t\in[-1,1]$$

其中較接近 $1$ 表示正面情緒，較接近 $-1$ 表示負面情緒。

6. 公司行動與特殊事件

必須記錄：

• 股票分割
• 現金股利與股票股利
• 增資、減資
• 下市、合併
• 財報發布
• 除權息日

這些事件會直接影響價格序列，若未處理，模型可能把價格跳動誤認為市場訊號。

---

二、資料前處理

1. 時間排序與資料對齊

先依照股票代碼與時間排序，確保每筆資料的時間順序正確。不同資料來源的頻率可能不同，例如：

• 股價是每日資料；
• 財報是季度資料；
• 利率可能是每日或每月資料；
• 新聞是事件發生時即時產生。

應將資料統一到相同時間頻率，例如每日收盤後資料。對於季度財報，應將最新一份「當時已公開」的財報值延伸到下一次財報發布前，而不能使用尚未發布的財報內容。

2. 調整股票分割與股利

若股票一拆二，歷史價格會出現不合理的斷裂。因此應使用調整後價格，常見的調整方式為：

• 前復權：以目前價格為基準調整歷史價格；
• 後復權：以早期價格為基準調整後續價格。

模型通常使用調整後收盤價計算報酬率，避免股票分割與除權息造成虛假的價格變化。

3. 缺失值處理

資料缺失的原因可能包括停牌、交易日不同、資料來源中斷或財報尚未發布。可採用：

• 對價格資料保留交易日，不任意填補不存在的交易；
• 對短期缺失使用前值填補；
• 對宏觀資料使用最近一次已知值；
• 對基本面資料使用最近一期已公開資料；
• 缺失比例過高的欄位直接刪除；
• 增加缺失指示變數，讓模型知道該值是填補而來。

不可將未交易日直接視為股價為零，否則會產生虛假的暴跌。

4. 離群值與異常值處理

核心觀念

本題考查的是將股票價格預測問題轉換為時間序列監督式學習問題，並依資料特性選擇適合的機器學習演算法。

股票資料具有以下特徵：

1. 時間順序不可打亂：較早的資料用來預測較晚的資料。
2. 高度非線性：價格可能受到成交量、技術指標、總體經濟與市場情緒共同影響。
3. 時間相依性：近期價格、報酬率與交易量可能影響未來走勢。
4. 雜訊與非穩定性高：股票價格通常難以直接預測，預測報酬率或漲跌方向通常比直接預測價格更合理。

若預測下一交易日價格，可定義：

$$\hat{P}_{t+1}=f(X_t)$$

其中 $P_{t+1}$ 是下一日股票價格，$X_t$ 是截至第 $t$ 日可取得的特徵，例如歷史價格、成交量與技術指標。

實務上常改預測報酬率：

$$r_{t+1}=\frac{P_{t+1}-P_t}{P_t}$$

或使用對數報酬率：

$$r_{t+1}=\ln\left(\frac{P_{t+1}}{P_t}\right)$$

如此可降低不同股價尺度造成的影響，使資料通常更接近平穩序列。

---

解題方法

一、先明確定義預測目標

可依需求將問題分成兩種：

• 迴歸問題：預測下一日或未來一段期間的報酬率。
• 分類問題：預測股價上漲或下跌。

分類目標可定義為：

$$y_{t+1}= \begin{cases} 1, & r_{t+1}>0\\ 0, & r_{t+1}\leq 0 \end{cases}$$

若題目要求「預測股價」，建議以報酬率作為模型輸出，再還原價格：

$$\hat{P}_{t+1}=P_t(1+\hat{r}_{t+1})$$

---

二、建立特徵

特徵必須只使用預測時點以前已知的資料，例如：

• 過去 $k$ 日的開盤價、最高價、最低價、收盤價；
• 過去 $k$ 日的成交量；
• 移動平均線，例如 $MA_5$、$MA_{20}$；
• 指數移動平均線；
• 相對強弱指標 RSI；
• MACD；
• 波動度；
• 市場指數與產業指數；
• 利率、匯率或其他總體經濟變數。

例如，輸入向量可以寫成：

$$X_t=[r_t,r_{t-1},\ldots,r_{t-k+1},V_t,MA_{5,t},MA_{20,t},RSI_t,\ldots]$$

其中 $V_t$ 表示成交量相關特徵。

---

演算法選擇

一、梯度提升樹：XGBoost 或 LightGBM

若資料主要由技術指標、成交量與其他表格特徵組成，首選可為梯度提升樹，例如 XGBoost 或 LightGBM。

其核心概念是逐步建立多棵決策樹，讓後續樹模型修正前面模型的預測誤差：

$$\hat{y}_i^{(m)} = \hat{y}_i^{(m-1)}+f_m(x_i)$$

其中 $f_m$ 是第 $m$ 棵決策樹。

選擇理由如下：

1. 能處理價格與技術指標之間的非線性關係。
2. 能捕捉特徵交互作用，例如「成交量放大且短期均線上穿長期均線」。
3. 對表格型資料通常具有良好表現。
4. 不需要像神經網路一樣使用大量資料。
5. 可透過特徵重要度分析模型判斷依據，解釋性較佳。

因此，XGBoost 或 LightGBM 適合作為主要模型，也適合作為深度學習模型的比較基準。

---

二、LSTM 或 GRU

若希望直接利用較長的歷史序列，可選擇長短期記憶網路 LSTM 或 GRU。

LSTM 透過輸入閘、遺忘閘與輸出閘控制資訊流，基本形式為：

$$f_t=\sigma(W_f x_t+U_f h_{t-1}+b_f)$$ $$i_t=\sigma(W_i x_t+U_i h_{t-1}+b_i)$$ $$\tilde{c}_t=\tanh(W_c x_t+U_c h_{t-1}+b_c)$$ $$c_t=f_t\odot c_{t-1}+i_t\odot\tilde{c}_t$$ $$h_t=o_t\odot\tanh(c_t)$$

其中 $c_t$ 是記憶狀態，$h_t$ 是隱藏狀態。

選擇理由如下：

核心觀念

本題考查的是機器學習模型的評估方法，重點不只是計算預測誤差，還要考慮股票資料具有時間序列特性：

1. 未來資料不可用來預測過去，必須避免資料洩漏（data leakage）。
2. 訓練集、驗證集、測試集應依時間先後切分。
3. 評估指標須配合預測目標：預測股價數值屬於迴歸問題，預測漲跌方向屬於分類問題。
4. 實際投資績效不能只看統計誤差，還要考慮交易成本、滑價與風險。

---

解題方法

一、依時間切分資料

假設使用 $t$ 日以前的資料預測 $t+1$ 日股價，資料應按照時間切分：

• 訓練集：較早期資料，用來學習模型參數。
• 驗證集：訓練集之後的資料，用來選擇模型、超參數與特徵。
• 測試集：最晚期、模型從未看過的資料，只用於最後評估。

例如：

$$\text{Training} \rightarrow \text{Validation} \rightarrow \text{Testing}$$

不可隨機打散後切分，因為隨機切分可能使訓練資料包含測試期間附近的資訊，造成模型間接看見未來。

若資料量足夠，可採用 walk-forward validation（滾動式驗證）：

1. 使用第 $1$ 至 $T_1$ 天訓練，預測 $T_1+1$ 天。
2. 將資料擴充至 $T_2$ 天重新訓練，預測 $T_2+1$ 天。
3. 持續向前滾動，收集所有預測結果。
4. 在整個測試期間計算總體表現。

此方法較符合實際交易中「只能使用當時以前資訊」的情境。

二、迴歸指標

若模型直接預測股價 $\hat{y}_t$，真實股價為 $y_t$，可使用以下指標。

1. 平均絕對誤差

$$MAE=\frac{1}{n}\sum_{t=1}^{n}|y_t-\hat{y}_t|$$

MAE 表示平均預測差距，單位與股價相同，容易解釋，且相較於平方誤差不容易受到極端值嚴重影響。

2. 均方根誤差

$$RMSE=\sqrt{\frac{1}{n}\sum_{t=1}^{n}(y_t-\hat{y}_t)^2}$$

RMSE 會放大大型預測錯誤，因此適合重視重大誤差的情況。若模型出現少數非常離譜的預測，RMSE 通常會明顯上升。

3. 平均絕對百分比誤差

$$MAPE=\frac{100\%}{n}\sum_{t=1}^{n} \left|\frac{y_t-\hat{y}_t}{y_t}\right|$$

MAPE 可表示相對誤差比例，但當 $y_t$ 接近零時會不穩定。股票價格通常為正值，但仍應注意低價股造成的比例誤差偏大問題。

4. $R^2$

$$R^2=1-\frac{\sum_{t=1}^{n}(y_t-\hat{y}_t)^2} {\sum_{t=1}^{n}(y_t-\bar{y})^2}$$

其中 $\bar{y}$ 為測試資料真實股價的平均值。$R^2$ 衡量模型相較於「永遠預測平均值」的改善程度，但不宜單獨作為投資模型的判斷依據。

三、漲跌方向指標

股票預測即使數值誤差不小，只要能正確預測漲跌方向，仍可能具備交易價值。因此可另外定義：

$$d_t= \begin{cases} 1, & y_t-y_{t-1}>0\\ 0, & y_t-y_{t-1}\leq 0 \end{cases}$$

模型預測方向為 $\hat{d}_t$，則可計算：

1. 方向準確率

核心觀念

本題考查的是「以時間序列資料建立機器學習預測模型」的完整流程，重點不在指定某一種演算法，而在於能否正確處理：

1. 預測目標的定義。
2. 股票資料的特徵設計。
3. 訓練、驗證與測試資料的時間順序。
4. 過度擬合與資料洩漏。
5. 模型評估及實際部署限制。

股票價格具有高噪聲、非平穩、容易受外部事件影響等特性，因此模型不應只追求訓練資料上的預測準確率，更要重視未來資料上的泛化能力與實際交易效果。

與直接預測價格相比，通常預測報酬率較合理。令第 $t$ 日收盤價為 $P_t$，則隔日對數報酬率為：

$$r_{t+1}=\ln\left(\frac{P_{t+1}}{P_t}\right)$$

若要做分類，也可以定義隔日漲跌標籤：

$$y_{t+1}= \begin{cases} 1, & r_{t+1}>0\\ 0, & r_{t+1}\leq 0 \end{cases}$$

如此可將問題設計成：

• 回歸問題：預測 $r_{t+1}$ 或 $P_{t+1}$。
• 分類問題：預測隔日上漲或下跌的機率。

解題方法

一、明確定義預測目標

先決定預測範圍，例如使用第 $t$ 日收盤前可取得的資料，預測第 $t+1$ 日報酬率：

$$\hat r_{t+1}=f(X_t)$$

其中 $X_t$ 是截至第 $t$ 日所建立的特徵向量。

若採回歸模型，可使用均方誤差作為損失函數：

$$\mathrm{MSE} = \frac{1}{n}\sum_{i=1}^{n}(r_i-\hat r_i)^2$$

若採分類模型，則可使用交叉熵損失：

$$L = -\frac{1}{n} \sum_{i=1}^{n} \left[ y_i\log(\hat p_i) + (1-y_i)\log(1-\hat p_i) \right]$$

其中 $\hat p_i$ 是模型預測上漲的機率。

二、蒐集與整理資料

可使用的資料包括：

• 開盤價、最高價、最低價、收盤價。
• 成交量與成交金額。
• 大盤指數及同產業指數。
• 技術指標，例如移動平均線、波動率、相對強弱指標。
• 公司財務資料，例如營收、獲利、負債比。
• 總體經濟資料，例如利率、匯率、通膨率。
• 新聞或社群情緒資料。

資料整理時必須處理缺失值、異常值、除權息與股票分割等事件。價格資料應使用還原股價，避免因股利或分割造成虛假的價格跳動。

三、建立特徵

特徵必須只使用預測當下已經知道的資訊。例如，可建立過去 $k$ 日的報酬率：

$$r_{t-j+1} = \ln\left(\frac{P_{t-j+1}}{P_{t-j}}\right), \quad j=1,2,\ldots,k$$

也可計算移動平均：

$$MA_t^{(k)} = \frac{1}{k} \sum_{i=0}^{k-1}P_{t-i}$$

以及歷史波動率：

$$\sigma_t^{(k)} = \sqrt{ \frac{1}{k-1} \sum_{i=0}^{k-1} (r_{t-i}-\bar r_t)^2 }$$

常見特徵可包含：

• 過去 $1$ 日、$5$ 日、$20$ 日報酬率。
• 收盤價相對於移動平均線的偏離程度。
• 成交量變化率。
• 高低價差所代表的當日波動。
• 大盤與個股之間的相對報酬。
• 公司財務指標及其變化率。

所有標準化參數，例如平均值與標準差，都必須只用訓練資料估計：

$$x_t'=\frac{x_t-\mu_{\mathrm{train}}} {\sigma_{\mathrm{train}}}$$

不可使用整份資料計算 $\mu$ 與 $\sigma$，否則會把未來資訊帶入訓練流程。

四、選擇模型

可先建立簡單基準模型，再與複雜模型比較。

基準模型可設定為：

$$\hat P_{t+1}=P_t$$

或直接假設：

$$\hat r_{t+1}=0$$

接著可採用：

• 線性迴歸：解釋性高，適合建立基準。
• Logistic Regression：預測上漲機率。
• Random Forest 或 Gradient Boosting：適合處理非線性關係。
• LSTM 或 Transformer：適合處理較長的時間序列依賴。
• 集成模型：結合多個模型以降低單一模型的偏誤。

模型的選擇應依資料量、特徵型態、計算資源及解釋性需求決定。資料量有限時，直接使用深度學習模型容易過度擬合，先使用線性模型與樹模型比較較為穩妥。

五、依時間順序切分資料

股票資料不可隨機切分，因為隨機切分會使訓練資料含有測試期間之後的資訊。

正確方式是依時間切分：

$$\text{訓練集} \longrightarrow \text{驗證集} \longrightarrow \text{測試集}$$

例如：

• 前 $70\%$ 時間區間作為訓練集。
• 接續的 $15\%$ 作為驗證集。
• 最後 $15\%$ 作為測試集。

模型調參可使用滾動式驗證：

核心觀念

32 位元 IEEE 754 單精度浮點數的格式如下：

$$\boxed{1\text{ 位元符號位元} \mid 8\text{ 位元指數欄位} \mid 23\text{ 位元小數欄位}}$$

對於正常化數值，其實際值為：

$$(-1)^S \times (1.F)_2 \times 2^{E-127}$$

其中：

• $S$：符號位元
• $E$：指數欄位的無號整數值
• $127$：單精度浮點數的偏移值（bias）
• $F$：23 位元小數欄位
• $(1.F)_2$：隱含最高位 $1$ 的有效數字，也常稱為 mantissa 或 significand

解題方法

題目給出的 32 位元二進位碼為：

$$01000001001010000000000000000000$$

依照 IEEE 754 單精度格式切割：

$$\boxed{0 \mid 10000010 \mid 01010000000000000000000}$$

1. Sign

最左側 1 位元為：

$$S=0$$

因此數值為正數。

2. Exponent

接下來 8 位元為：

$$10000010_2$$

轉換成十進位：

$$10000010_2=128+2=130$$

因此指數欄位的儲存值為：

$$E=130$$

IEEE 754 單精度的 bias 為 $127$，所以實際指數為：

$$e=E-127=130-127=3$$

因此：

核心觀念

32-bit IEEE 754 單精度浮點數格式如下：

$$\boxed{\text{符號位 }1\text{ bit}\;|\;\text{指數 }8\text{ bits}\;|\;\text{小數部分 }23\text{ bits}}$$

對於正常化數，其數值公式為：

$$(-1)^s \times (1.f)_2 \times 2^{E-127}$$

其中：

• $s$：符號位
• $E$：以二進位表示的指數欄位，需扣除偏移值 $127$
• $f$：小數部分
• $1.f$：正常化二進位數的有效數字

解題方法

題目給出的 32-bit 位元為：

$$01000001001010000000000000000000$$

依 IEEE 754 格式切割：

$$\underbrace{0}_{符號位} \quad \underbrace{10000010}_{指數欄位} \quad \underbrace{01010000000000000000000}_{小數欄位}$$

1. 判斷正負號

符號位為：

$$s=0$$

因此數值為正數：

$$(-1)^0=1$$

2. 計算實際指數

指數欄位為：

$$(10000010)_2$$

換算成十進位：

$$(10000010)_2=128+2=130$$

單精度浮點數的偏移值為 $127$，因此實際指數為：

$$e=130-127=3$$

3. 計算有效數字

小數欄位為：