在資料科學領域，社交網路分析和圖論已成為文字分析的重要工具。藉由分析節點和邊的關係，可以揭示文字中隱藏的社群結構、角色互動和語義關聯。本文將深入探討這些技術的應用，並以具體案例說明其價值。首先，我們將介紹社群探索方法，例如 Louvain 方法，並以 MDN 的社交網路分析案例說明如何發現和詮釋社群結構。接著，我們將探討圖論如何應用於文字分析，例如分析文字中的實體、關係和語義，並以莎士比亞的《仲夏夜之夢》為例進行說明。最後，我們將討論正式語言的概念及其在自然語言處理中的應用，並介紹正則語言、上下文無關語言和上下文相關語言等不同型別的語言，以及它們在描述語言結構和語法方面的作用。
社交網路分析中的社群探索
在社交網路分析中，社群探索是一個重要的研究領域。透過對社交網路中的節點和邊的分析，可以發現社交網路中的社群結構和規律。這些社群結構可以反映社交網路中的群體行為和關係模式。
社群探索方法
有多種方法可以用於社交網路中的社群探索，包括Louvain方法、K-means方法和階層聚類方法等。Louvain方法是一種根據模組度的社群探索方法，透過最大化模組度來發現社交網路中的社群結構。
社交網路中的社群結構
在社交網路中，社群結構可以反映社交網路中的群體行為和關係模式。例如，在一個社交網路中，可能存在多個社群，每個社群代表了一個不同的群體或興趣小組。這些社群可以透過社交網路分析工具來發現和分析。
案例研究：MDN的社交網路分析
在MDN的社交網路分析中，使用Louvain方法發現了8個社群。這些社群包括了不同角色和人物的集合，例如Oberon和Puck的社群、其他精靈的社群、戲中戲角色的人物的社群等。這些社群的發現可以反映MDN社交網路中的群體行為和關係模式。
社群結構分析
在MDN的社交網路分析中，發現了以下社群結構：
- Oberon和Puck的社群：這個社群包括了Oberon和Puck兩個角色，反映了他們在MDN中的特殊地位。
- 其他精靈的社群：這個社群包括了其他所有精靈角色，反映了他們在MDN中的群體行為和關係模式。
- 戲中戲角色的人物的社群：這個社群包括了戲中戲角色的人物，例如Prologue、Moonshine、Lion等，反映了他們在MDN中的群體行為和關係模式。
社群結構的意義
MDN的社交網路分析中發現的社群結構可以反映MDN中的群體行為和關係模式。這些社群結構可以用於理解MDN中的角色和人物之間的關係和行為模式。
graph LR
A[Oberon] --> B[Puck]
C[其他精靈] --> D[戲中戲角色]
E[Prologue] --> F[Moonshine]
G[Lion] --> H[Philostrate]
I[Theseus] --> J[Quince]
K[Snug] --> L[Snout]
M[Flute] --> N[Wall]
O[Thisbe] --> P[Pyramus]
Q[Helena] --> R[Hippolyta]
圖表翻譯：
上述Mermaid圖表展示了MDN的社交網路結構，其中包括了不同角色和人物之間的關係和行為模式。這個圖表可以用於理解MDN中的群體行為和關係模式。
圖論在文字分析中的應用
圖論是一個強大的工具，能夠用於分析文字中的關係和結構。在這一節中，我們將探討圖論在文字分析中的應用，包括使用圖論來分析文字中的實體、關係和語義。
8.4.1.8 可能的改進
在前面的例子中，我們使用了圖論技術來分析莎士比亞的《仲夏夜之夢》。然而，這種方法非常簡單，因為我們沒有區分地址和提及，而是收集了命名實體並使用它們而不考慮其功能。另外，我們省略了間接地址。例如，在奧伯龍的臺詞（第二幕，第一場）中：
“你怎麼能這樣，為了羞恥，泰坦妮亞， 用希波呂塔來衡量我的信用， 知道我知道你對特修斯的愛？”
奧伯龍直接地址泰坦妮亞，提及希波呂塔和特修斯，然後間接地址希波呂塔（“thy”、“thou”）和提及特修斯（“him”）。在這裡，需要核心ference檢測來更好地理解地址和提及。
8.5 進一步閱讀
8.5.1 文獻
圖論教材在數學和電腦程式碼方面有所不同。Newman [17]是一本優秀的教材，具有公式但沒有定理和證明，也沒有程式碼。作者認為對於有興趣的讀者，CLRS（Cormen、Leiserson、Rivest和Stein）[6]是最好的書籍。第6章專門介紹圖論。Leiserson的YouTube講座是優秀的。對於有興趣的讀者，圖論的數學理論在Diestel [7]中以非常友好的方式展開。法語讀者應該參考Berge的書籍，例如[2]。它們是永恆的經典，具有清晰和優雅的風格。
除了圖論的先驅，Berge還是Oulipo小組的成員，並發表了一個短篇故事，其中一個犯罪是由玄貓解決的：誰殺死了Densmore公爵？([3]，英文譯本[4]）。圖論用於建模受害者的前妻的共存關係，解決方案由玄貓的證詞給出，以便只有她才能是兇手。
Mihalcea [15, 16]專門介紹圖論在自然語言處理中的應用。它討論了圖論在語義和句法中的使用，並描述了應用，例如摘要、關鍵字提取、主題識別、機器翻譯和問答。
8.5.2 LaTeX
要繪製圖論，使用tikz套件是一個非常強大的工具，具有豐富的檔案。
8.5.3 科幻小說
Egon的Schild的Ladder（2002）涉及量子圖論。一個實驗原本打算創造一種新的真空，只存在幾個納秒，但出了差錯。這個“novovacuum”以光速的一半擴張，吞噬了居住的太陽系。科學家們想摧毀它，並發現它攜帶著生命。就像一個評論者所建議的，這本小說是一種變體的弗蘭肯斯坦，在恆星尺度上。
8.6 練習
練習7-1：使用WordNet進行消歧 有了ChatGPT的幫助，我們準備了一個包含100個句子的語料函式庫，使用“bank”這個詞。其中50個句子指的是金融機構的含義，另外50個句子指的是河流沿岸的含義。 一些句子是無歧義的： 銀行與當地慈善機構合作，支援社群倡議。 我們沿著河岸發現了一個海狸壩。 銀行的工作人員總是很有禮貌和幫助。 鴨子和雁通常聚集在河岸。 其他句子是模糊的，因為銀行（金融機構）也是一棟可以包含自然元素或從事非金融活動的建築，或者因為河岸可以被守衛，如果它碰巧是一個國家邊界等等， 老柳樹傾斜在河岸上。 銀行的安全措施包括監控攝像頭和報警系統。 使用WordNet的圖結構來消歧這些句子。
練習7-2：找到古蘭經和聖經中最中心的詞 解析英文古蘭經和聖經譯本，使用依存句法解析器。對於每本章，構建一個由玄貓連線的名詞/專有名詞圖。取最大的連線圖。
Formal Languages
Formal languages是一種用於描述自然語言的數學工具。它們由一組字母（alphabet）組成，利用這些字母可以建立出無限多的字串（string）。在自然語言處理中，Formal languages被用於描述語言的結構和語法。
基本定義
讓我們從基本定義開始。一個Formal language由一組字母（alphabet）Σ組成。一個字串（string）是從Σ中選取的字母的序列。例如，如果Σ = {a, b, c}，則字串"abc"是從Σ中選取的字母的序列。
字串的運算
Formal languages中有一個重要的運算：字串的連線（concatenation）。連線兩個字串可以得到一個新的字串。例如，如果我們有兩個字串"ab"和"cd"，則連線後得到的字串是"abcd"。
Formal Language的定義
一個Formal Language是Σ上所有字串的集合，包括空字串ε。這個集合被稱為Σ∗。Σ∗有一個代數結構：對於任何兩個字串w和w’，我們可以定義一個連線運算，使得w和w’連線後得到一個新的字串。
Formal Languages在自然語言處理中的應用
Formal languages在自然語言處理中有許多應用。例如，它們可以用於描述語言的語法和結構，或者用於自動化語言翻譯和語言生成等任務。
例子
例如，假設我們有一個Formal language，字母表Σ = {a, b, c}。我們可以定義一個語法規則，規定字串必須以"a"開頭，以"b"結尾。根據這個規則，我們可以生成出許多字串，例如"ab"、“acb”、“abb"等。
圖表翻譯：
上述Mermaid圖表描述了Formal Language的基本概念和其在自然語言處理中的應用。從左到右，圖表展示了Formal Language的定義、字母表Σ、字串的連線、語法規則和語言結構，最終到達自然語言處理的應用。這個圖表幫助我們理解Formal Language的核心概念和其在自然語言處理中的重要性。
9.3 正式語法
正式語法是電腦科學中的一個基本概念，用於描述語言的語法結構。在本節中，我們將介紹正式語法的基本定義和性質。
9.3.1 字母表和字串
給定一個字母表Σ，Σ上的字串是指由Σ中的元素組成的有限序列。例如，如果Σ = {a, b}，則"ab"和"ba"都是Σ上的字串。Σ上的所有字串的集合稱為Σ∗。
Σ∗是一個單元代數結構，其中的單元元素是空字串ε。對於任何字串w，ε · w = w · ε = w。這意味著ε是Σ∗中對於字串連線運算的單元元素。
9.3.2 單元代數結構
Σ∗是一個單元代數結構，但它不是一個群、環或體。因為Σ∗中沒有逆元素，例如，對於字串"abc”，沒有任何字串可以與其連線得到空字串ε。
9.3.3 正式語言
正式語言是Σ∗的子集。正式語言可以是有限的，也可以是無限的。例如，{a, b}是Σ = {a, b}上的一個有限正式語言，而{a^n | n ≥ 0}是Σ = {a}上的一個無限正式語言。
9.3.4 ℘(Σ∗)
℘(Σ∗)是Σ∗的所有子集的集合。℘(Σ∗)包含了所有可能的正式語言。例如，{a, b}和{a^n | n ≥ 0}都是℘(Σ∗)中的元素。
9.3.5 字串連線
對於任何兩個字串u和v，u和v的連線是指將u和v相連的結果。例如，“ab"和"cd"的連線是"abcd”。
9.3.6 單元元素
空字串ε是Σ∗中對於字串連線運算的單元元素。對於任何字串w，ε · w = w · ε = w。
9.3.7 例子
(N₀, +)是自然數集，包括0，具有加法運算。這是一個單元代數結構，其中的單元元素是0。
graph LR
A[字母表Σ] --> B[Σ上的字串]
B --> C[Σ∗]
C --> D[正式語言]
D --> E[℘(Σ∗)]
E --> F[字串連線]
F --> G[單元元素]
內容解密：
在上面的mermaid圖中，我們展示了正式語法的基本概念。字母表Σ是正式語法的基礎，Σ上的字串是指由Σ中的元素組成的有限序列。Σ∗是Σ上的所有字串的集合，具有字串連線運算和單元元素ε。正式語言是Σ∗的子集，℘(Σ∗)是Σ∗的所有子集的集合。
圖表翻譯：
上面的mermaid圖表展示了正式語法的基本概念。從左到右，圖表展示了字母表Σ、Σ上的字串、Σ∗、正式語言、℘(Σ∗)、字串連線和單元元素。這個圖表幫助我們瞭解正式語法的基本結構和關係。
語言與字元集的基礎概念
在計算理論中，語言（Language）是指一組字串的集合，這些字串是由某個字元集（Alphabet）中的元素組成。字元集是一個有限的非空集合，例如Σ = {0, 1}。Σ的冪集，表示為℘(Σ)，是所有可能的Σ的子集的集合。
℘(Σ∗) 的基礎
現在，讓我們考慮Σ∗，它代表所有可能的Σ上的字串的集合，包括空字串ε。Σ∗是一個無限集，因為可以建構出任意長度的字串。℘(Σ∗)代表所有可能的Σ∗的子集的集合，也就是說，它包含所有可能的Σ上的語言的集合。
℘(Σ∗) 的基數
℘(Σ∗) 的基數是連續的，與實數集R的基數相同，通常表示為ℵ₁（aleph-one）。這意味著℘(Σ∗) 的元素數量遠遠大於Σ∗本身的元素數量，後者是可數無限的（ℵ₀）。
語言運算
在℘(Σ∗) 中，有幾個重要的運算：
- 補集：給定一個語言L，補集L̄包含所有不屬於L的Σ∗中的字串。
- 串接：給定兩個語言L₁和L₂，串接L₁ · L₂包含所有形式為w₁w₂的字串，其中w₁ ∈ L₁且w₂ ∈ L₂。
- 聯合：給定兩個語言L₁和L₂，聯合L₁ ∪ L₂包含所有屬於L₁或L₂的字串。
- 交集：給定兩個語言L₁和L₂，交集L₁ ∩ L₂包含所有同時屬於L₁和L₂的字串。
- 自由單oid：給定一個語言L，自由單oidL∗包含所有可以由L中的字串透過串接任意次而形成的字串，包括空字串ε。
這些運算在形式語言理論和計算理論中扮演著重要的角色，尤其是在語言的定義、分析和轉換中。
內容解密
上述概念和運算是形式語言理論的基礎。透過這些工具，可以定義和分析各種形式語言，包括正則語言、上下文無關語言和上下文相關語言。這些語言在電腦科學中有廣泛的應用，包括編譯器設計、自然語言處理和模式識別。
flowchart TD
A[字元集Σ] --> B[Σ∗: 所有可能的Σ上的字串]
B --> C[℘(Σ∗): 所有可能的Σ上的語言]
C --> D[語言運算: 補集、串接、聯合、交集、自由單oid]
D --> E[形式語言理論的基礎]
E --> F[電腦科學中的應用]
圖表翻譯
此圖表展示了從字元集Σ到℘(Σ∗)的過程，然後介紹了語言運算，最終指出這些概念在形式語言理論和電腦科學中的重要性。每一步驟都建立在前一步的基礎上，展示了從基本概念到實際應用的邏輯流程。
正式語法與語言描述
在前一節中，我們定義了一種形式語言為 Σ∗ 的子集。現在，讓我們來探討如何描述這種子集。如果語言是有限的，我們可以透過列舉所有元素來明確定義它，例如 𝐿 = {𝜖, 𝑎𝑏, 𝑎𝑏𝑎𝑏}，這被稱為語言的外延描述。但是，如果語言是無限的或非常龐大呢？或者，我們想要描述某種自然語言的所有可能的語法句子？從技術上講，這個集合並不是真正的無限，因為我們沒有無限的時間來說出一個句子，也沒有無限的空間來書寫它。然而，它確實非常龐大，因為給定任何句子，我們總是可以透過新增更多元素來產生一個更長的句子。
為了定義形式語言，諾姆·喬姆斯基引入了一種稱為形式語法的工具。形式語法是指在字母表 Σ 上的一個四元組 (Σ, 𝑁, 𝑅, 𝑆)，其中 𝑁 是不出現在 Σ 中的符號集合，稱為非終端符號，𝑅 是生產規則的集合，而 𝑆 是 𝑁 中的一個元素，稱為起始符號。在這個背景下，Σ 中的元素被稱為終端符號。
生產規則是一個四元組 (𝐶𝐿, 𝐴, 𝐶𝑅, 𝐵)，其中 𝐶𝐿 ∈ (𝑁 ∪ Σ)∗（左上文），𝐴 ∈ 𝑁（非終端符號），𝐶𝑅 ∈ (𝑁 ∪ Σ)∗（右上文），𝐵 ∈ (𝑁 ∪ Σ)∗。這些規則定義瞭如何從一個字串生成另一個字串，從而構建語言的元素。
內容解密：
上述內容描述了形式語法的基本概念，包括非終端符號、生產規則和起始符號。形式語法提供了一種描述語言的方法，尤其是對於無限或非常龐大的語言。透過定義一組生產規則和起始符號，我們可以生成語言中的所有可能的字串。
圖表翻譯：
graph LR
A[語言] -->|描述|> B[形式語法]
B -->|生產規則|> C[字串生成]
C -->|語言元素|> D[語言]
D -->|語言描述|> A
這個圖表描述了語言、形式語法和字串生成之間的關係。語言可以透過形式語法來描述，形式語法透過生產規則來生成字串，從而構建語言的元素。這個過程可以迴圈地描述語言的結構和生成。
正式語言與生成語法
正式語言是指一組符合特定規則的字串集合。這些規則通常由生成語法定義，生成語法是一組能夠產生正式語言的規則。生成語法由四個部分組成：終端符號集（Σ）、非終端符號集（N）、生產規則集（R）和起始符號（S）。
生產規則
生產規則是生成語法的核心部分，它定義瞭如何將非終端符號轉換為終端符號或其他非終端符號。生產規則的形式為 𝐶𝐿 𝐴𝐶𝑅 → 𝐵，其中 𝐴 是非終端符號，𝐶𝐿、𝐶𝑅 和 𝐵 是終端符號或非終端符號的字串。
生成語法的種類
根據生產規則的限制，生成語法可以分為四種型別：
- 無限制語法（Type 0）：沒有對生產規則的限制。
- 上下文相關語法（Type 1）：生產規則的形式為 𝐶𝐿 𝐴𝐶𝑅 → 𝐵，其中 𝐶𝐿 和 𝐶𝑅 是非空字串。
- 上下文無關語法（Type 2）：生產規則的形式為 𝐴 → 𝐵，其中 𝐴 是非終端符號，𝐵 是終端符號或非終端符號的字串。
- 正規語法（Type 3）：生產規則的形式為 𝐴 → 𝑎𝐵 或 𝐴 → 𝑎，其中 𝐴 和 𝐵 是非終端符號，𝑎 是終端符號。
生成語法的應用
生成語法在電腦科學中有廣泛的應用，例如：
- 編譯器設計：生成語法可以用來定義程式語言的語法和語義。
- 自然語言處理：生成語法可以用來分析和生成自然語言的句子。
- 模式識別：生成語法可以用來識別和分類模式。
正則語法與上下文敏感語法
在計算理論中，語法是用來定義形式語言的產生規則。根據語法的型別不同，可以分為不同的類別。以下是語法類別的定義：
類別1：上下文敏感語法
如果語法中的重寫規則可以寫成 𝐶𝐿𝐵𝐶𝑅 → 𝐶𝐿𝐵′𝐶𝑅 的形式，即左邊和右邊的重寫規則具有相同的左和右上下文，那麼這種語法被稱為類別1或上下文敏感語法。
類別2：上下文無關語法
如果語法中的重寫規則可以寫成 𝐴 → 𝛼 的形式，其中 𝐴 是一個非終端符號，𝛼 是一個字串，那麼這種語法被稱為類別2或上下文無關語法。在這種語法中，重寫規則不依賴於左和右上下文。
類別3：正則語法
如果語法中的重寫規則可以寫成 𝐴 → 𝛼𝐵 或 𝐴 → 𝛼 的形式，其中 𝐴 和 𝐵 是非終端符號，𝛼 是一個字串，那麼這種語法被稱為類別3或正則語法。在這種語法中，重寫規則只依賴於左上下文。
這些語法類別之間的關係是：類別1包含類別2，類別2包含類別3。也就是說，任何上下文無關語法都可以被視為是一種上下文敏感語法，而任何正則語法都可以被視為是一種上下文無關語法。
內容解密：
在計算理論中，語法的類別決定了它的表達能力和複雜度。上下文敏感語法可以用來描述更複雜的語言，但它的重寫規則也更為複雜。上下文無關語法則可以用來描述更簡單的語言，但它的重寫規則也更為簡單。正則語法是最簡單的一種語法類別，它可以用來描述正規表示式。
圖表翻譯：
graph LR
A[類別1：上下文敏感語法] --> B[類別2：上下文無關語法]
B --> C[類別3：正則語法]
style A fill:#f9f,stroke:#333,stroke-width:4px
style B fill:#f9f,stroke:#333,stroke-width:4px
style C fill:#f9f,stroke:#333,stroke-width:4px
這個圖表顯示了語法類別之間的關係。類別1包含類別2，類別2包含類別3。
自然語言的語法型別
在語言學中，自然語言的語法型別一直是個有趣的研究話題。語言可以被分為不同型別，包括正則語言（regular languages）、上下文無關語言（context-free languages）和上下文相關語言（context-sensitive languages）。這些型別的區別在於語言的產生規則和語法結構的複雜度。
正則語言
正則語言是最簡單的一種語言型別，其語法規則可以用有限狀態自動機（finite state automaton）來描述。這類語言的特點是其語法規則簡單，通常不涉及巢狀結構或複雜的語法關係。在自然語言中，正則語言相對較少見，因為大多數自然語言都具有更複雜的語法結構。
上下文無關語言
上下文無關語言是一種比正則語言更複雜的語言型別，其語法規則可以用上下文無關語法（context-free grammar）來描述。這類語言的特點是其語法規則可以用遞迴的方式來定義，允許巢狀結構和更複雜的語法關係。英語被認為是一種上下文無關語言，因為它的語法規則可以用上下文無關語法來描述。
上下文相關語言
上下文相關語言是一種最複雜的語言型別，其語法規則需要考慮語言的上下文資訊。這類語言的特點是其語法規則涉及到語言的上下文關係，需要用更複雜的語法結構來描述。是否存在上下文相關語言仍然是個有爭議的話題。
自然語言的語法型別
研究表明，英語可以被視為是一種上下文無關語言。這是因為英語的語法規則可以用上下文無關語法來描述，允許巢狀結構和更複雜的語法關係。其他自然語言也可能被視為上下文無關語言或上下文相關語言，取決於其語法結構的複雜度和語法規則的特點。
9.4 正則語言
正則語言是一種簡單的形式語言，具有良好的行為：正則語言的聯合、交集、克林閉包和補集都是正則語言。然而，讀者應該避免以下混淆：說正則語言的集合包含在其他語言的集合中（例如，脈絡自由語言），並不意味著我們對語言作為詞彙集合有相同的包含關係。正則語言可以用正則形式文法、正規表示式和有限狀態自動機來描述。
9.4.1 正規表示式
從數學上講，正規表示式是形式語言的描述。技術上，它看起來像一個詞彙加上特殊符號。有些作者稱這些符號為元字母表。克林首先在1951年的一份RAND公司報告中介紹了正規表示式，該報告關於神經網路中的事件。
9.4.1.1 抽象語法
正規表示式的基本語法使用括號、連線（用 · 表示）、聯合（用 ∪ 表示）、星號運算子（*）、空詞彙（𝜖）。例如，如果我們想描述一個語言，其詞彙以 𝑎𝑏 開始，以 𝑏𝑎 結束，中間部分任意，我們可以寫成：
(𝑎 · 𝑏 · ((𝑎 ∗) ∪ (𝑏 ∗)) ∗ · 𝑏 · 𝑎)
9.4.1.2 POSIX語法
POSIX正規表示式的語法和語義在POSIX.1-2017標準的第9章中描述。由於它們旨在用於程式語言，因此字母表Σ是固定的：它是Unicode編碼。形式語言詞彙是字串；形式語言連線簡單是字串連線。字元之間的選擇用以下方式表示：
- 選擇a、b和c之間的字元，寫成[abc]；
- 使用Unicode的程式碼空間順序，字元範圍內的選擇，寫成[a-z]。
flowchart TD
A[正規表示式] --> B[抽象語法]
B --> C[POSIX語法]
C --> D[字元選擇]
D --> E[字元範圍]
內容解密：
上述流程圖描述了正規表示式的基本結構。抽象語法和POSIX語法是正規表示式的兩種不同表達方式。字元選擇和字元範圍是POSIX語法中用於描述字元之間選擇的兩種方式。
圖表翻譯：
此圖表顯示了正規表示式的結構。正規表示式可以使用抽象語法或POSIX語法來描述。POSIX語法中，字元選擇和字元範圍是用於描述字元之間選擇的兩種方式。這種結構使得正規表示式可以用於描述複雜的字元模式。
從技術架構視角來看，社交網路分析中的社群探索方法，如 Louvain 方法，有效揭示了網路中隱藏的社群結構。分析段落中提到的 MDN 案例研究，清楚地展現了 Louvain 方法如何應用於識別不同角色群體，例如 Oberon 與 Puck 的特殊關係，以及戲中戲角色的社群歸屬。然而，目前的分析方法仍存在侷限性，例如未能區分直接地址和間接提及，這也限制了對網路關係更細緻的理解。展望未來，整合核心ference 解析技術將是重要的發展方向，它能幫助更精確地捕捉角色間的互動模式，從而提升社群探索的深度和準確性。玄貓認為，隨著自然語言處理技術的進步，圖論和社群探索方法將在文字分析領域發揮更大的作用，例如語義消歧和關鍵字提取等應用，值得持續關注。
