Bài 7: Toán học Rời rạc — Logic, Đồ thị, và Thuật toán

Series: Toán học trong AI/ML & Deep Learning

Topics: discrete-math graph GNN dynamic-programming tokenization

🎯 Tại sao Toán học Rời rạc quan trọng?

Thế giới số là rời rạc: token, pixel, graph node — không liên tục. Toán học rời rạc xây dựng nền tảng cho thuật toán, cấu trúc dữ liệu, và suy luận logic mà AI cần.

1. Lý thuyết Đồ thị — Dữ liệu có cấu trúc quan hệ

Mạng xã hội:          Phân tử thuốc:         Knowledge Graph:
  A──B                   C                       Paris ──capital_of──> France
  │  │                  / \                      │
  C──D                 N   O                     located_in
                        \  │                     │
                         C─C                     Europe

import networkx as nx
import numpy as np

# Tạo đồ thị
G = nx.karate_club_graph()   # dataset chuẩn trong GNN
print(f"Nodes: {G.number_of_nodes()}")   # 34
print(f"Edges: {G.number_of_edges()}")   # 78

# Adjacency matrix — biểu diễn đồ thị dạng ma trận
A = nx.adjacency_matrix(G).toarray()
print(f"Adjacency matrix shape: {A.shape}")  # (34, 34)

# Degree của mỗi node (số kết nối)
degrees = dict(G.degree())
print(f"Max degree node: {max(degrees, key=degrees.get)}")

# Thuật toán tìm đường ngắn nhất
path = nx.shortest_path(G, source=0, target=33)
print(f"Shortest path 0→33: {path}")

2. Graph Neural Networks — Học trên Đồ thị

GNN áp dụng neural network lên cấu trúc đồ thị qua message passing:

\[h_v^{(k+1)} = \text{UPDATE}\left(h_v^{(k)},\ \text{AGGREGATE}\left(\{h_u^{(k)} : u \in \mathcal{N}(v)\}\right)\right)\]

import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv
from torch_geometric.datasets import Planetoid

# Load dataset Cora (citation network)
dataset = Planetoid(root='/tmp/Cora', name='Cora')
data = dataset[0]

print(f"Nodes     : {data.num_nodes}")          # 2,708 papers
print(f"Edges     : {data.num_edges}")           # 10,556 citations
print(f"Features  : {data.num_features}")        # 1,433 (bag-of-words)
print(f"Classes   : {dataset.num_classes}")      # 7

# 2-layer GCN
class GCN(torch.nn.Module):
    def __init__(self, in_channels, hidden, out_channels):
        super().__init__()
        self.conv1 = GCNConv(in_channels, hidden)
        self.conv2 = GCNConv(hidden, out_channels)
    
    def forward(self, x, edge_index):
        # Layer 1: aggregate from neighbors
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, p=0.5, training=self.training)
        
        # Layer 2
        x = self.conv2(x, edge_index)
        return F.log_softmax(x, dim=1)

model = GCN(dataset.num_features, 16, dataset.num_classes)
print(f"\nModel: {sum(p.numel() for p in model.parameters())} params")

Ứng dụng GNN:

Khám phá thuốc (phân tử = đồ thị)
Gợi ý sản phẩm (user-item graph)
Phát hiện gian lận (transaction graph)
Code analysis (AST graph)

3. Dynamic Programming — Tối ưu qua cấu trúc con

Nguyên lý: Chia bài toán lớn thành các bài toán con gối nhau, lưu kết quả để tái sử dụng.

# Edit distance (Levenshtein) — dùng trong fuzzy matching, BLEU score
def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    # dp[i][j] = edit distance giữa s1[:i] và s2[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    
    # Fill DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]               # no op
            else:
                dp[i][j] = 1 + min(dp[i-1][j],        # delete
                                   dp[i][j-1],         # insert
                                   dp[i-1][j-1])       # replace
    return dp[m][n]

print(edit_distance("kitten", "sitting"))   # 3
print(edit_distance("Hello", "Hello"))      # 0

Viterbi Algorithm — Sequence decoding

# Viterbi: tìm sequence tốt nhất trong HMM / CRF
# Dùng trong NER, POS tagging

def viterbi(obs, states, start_p, trans_p, emit_p):
    """
    obs    : chuỗi quan sát
    states : các trạng thái ẩn
    start_p: xác suất khởi đầu P(state₀)
    trans_p: P(stateᵢ | stateᵢ₋₁)
    emit_p : P(obsᵢ | stateᵢ)
    """
    T = len(obs)
    S = len(states)
    
    dp = [[0.0] * S for _ in range(T)]
    path = [[0] * S for _ in range(T)]
    
    # Init
    for s in range(S):
        dp[0][s] = start_p[s] * emit_p[s][obs[0]]
    
    # Forward
    for t in range(1, T):
        for s in range(S):
            probs = [dp[t-1][prev] * trans_p[prev][s] * emit_p[s][obs[t]]
                     for prev in range(S)]
            dp[t][s] = max(probs)
            path[t][s] = np.argmax(probs)
    
    # Backtrack
    best_path = [np.argmax(dp[T-1])]
    for t in range(T-1, 0, -1):
        best_path.insert(0, path[t][best_path[0]])
    
    return [states[s] for s in best_path]

4. BPE Tokenization — Greedy Algorithm

Byte Pair Encoding (BPE) dùng greedy merging để xây dựng vocabulary:

from collections import Counter

def bpe_train(corpus, num_merges):
    """
    BPE: lặp lại merge cặp ký tự phổ biến nhất
    Đây là thuật toán Greedy — luôn chọn merge tốt nhất tại bước hiện tại
    """
    # Khởi đầu: split words thành ký tự
    vocab = {}
    for word in corpus.split():
        chars = tuple(word) + ('</w>',)
        vocab[chars] = vocab.get(chars, 0) + 1
    
    merges = []
    
    for _ in range(num_merges):
        # Đếm tần suất các cặp
        pairs = Counter()
        for word, freq in vocab.items():
            for i in range(len(word) - 1):
                pairs[(word[i], word[i+1])] += freq
        
        if not pairs:
            break
        
        # Merge cặp phổ biến nhất
        best_pair = max(pairs, key=pairs.get)
        merges.append(best_pair)
        
        # Cập nhật vocab
        new_vocab = {}
        for word, freq in vocab.items():
            new_word = []
            i = 0
            while i < len(word):
                if i < len(word) - 1 and (word[i], word[i+1]) == best_pair:
                    new_word.append(word[i] + word[i+1])
                    i += 2
                else:
                    new_word.append(word[i])
                    i += 1
            new_vocab[tuple(new_word)] = freq
        vocab = new_vocab
        
        print(f"Merge: {best_pair[0] + best_pair[1]}")
    
    return merges

# Demo
corpus = "low lower newest widest lowest"
bpe_train(corpus, num_merges=5)
# Merge: lo  (l+o)
# Merge: low (lo+w)
# ...

5. Tree-of-Thought — Cây quyết định trong LLM

Câu hỏi phức tạp
        │
   ┌────┴────┐
 Hướng A  Hướng B  Hướng C
   │         │         │
  A1  A2    B1  B2    C1 C2
   │         │
  ★         ✗  ← backtrack
  (tốt nhất)

# Pseudo-code Tree-of-Thought reasoning
def tree_of_thought(question, depth=3, branching=3):
    """
    Mỗi bước: generate branching sub-thoughts,
    evaluate, chọn best để expand tiếp
    """
    root = {"thought": question, "score": 1.0, "children": []}
    
    def expand(node, current_depth):
        if current_depth == 0:
            return
        
        # Generate sub-thoughts (dùng LLM)
        sub_thoughts = llm_generate(
            node["thought"],
            n=branching,
            prompt="Continue reasoning:"
        )
        
        for thought in sub_thoughts:
            # Evaluate quality (dùng LLM as critic)
            score = llm_evaluate(thought)
            child = {"thought": thought, "score": score, "children": []}
            node["children"].append(child)
        
        # Chỉ expand top-k thoughts (BFS/DFS)
        best_child = max(node["children"], key=lambda x: x["score"])
        expand(best_child, current_depth - 1)
    
    expand(root, depth)
    return extract_best_path(root)   # backtrack qua tree

6. Checklist

Biểu diễn được đồ thị bằng adjacency matrix
Giải thích GNN làm gì với “message passing”
Implement được DP đơn giản (fibonacci, edit distance)
Hiểu BPE tokenization là greedy algorithm
Phân biệt được BFS vs DFS và khi nào dùng cái nào

🔗 Series

← Bài 6: Lý thuyết Thông tin
→ Bài 8: Giải tích Số