Ngôn ngữ quy ước (symbolic) và xác xuất thống kê (stochastic)

Lịch sử ngành xử lý ngôn ngữ tự nhiên (1957-1970): Nhị phái (symbolic và stochastic) xưng hùng 

Phần 1: Mô hình Ngôn ngữ quy ước (symbolic) và 2 phân nhánh của nó

Vào giai đoạn thập niên (1957 - 1975) lĩnh vực nghiên cứu xử lý ngôn ngữ tự nhiên đã chia thành 2 trường phái khác nhau, sử dụng 2 lý thuyết khác nhau gồm Ngôn ngữ quy ước (symbolic) và Xác xuất thống kê (stochastic) để phát triển các thuật toán xử lý ngôn ngữ tự nhiên, hình thành nên làm nền tảng cho lĩnh vực trí tuệ nhân tạo phát triển như hiện nay.

Nói sâu về mô hình ngôn ngữ quy ước (symbolic) một chút thì mô hình này có 2 nhánh rẽ: Một bên sử dụng lý thuyết ngôn ngữ hình thức (Formal Language Theory), còn phía bên kia sử dụng Lý thuyết cú pháp quy nạp (Generative Syntax Theory). Bài viết về lý thuyết ngôn ngữ hình thức (Formal Language Theory) bạn có thể xem tại đây: Các vị tổ khai sáng ngành xử lý ngôn ngữ tự nhiên

Lý thuyết cú pháp quy nạp (Generative Syntax Theory)

Lý thuyết cú pháp quy nạp (Generative Syntax Theory) được xuất phát từ nghiên cứu của Noam Chomsky, cho rằng: Ngôn ngữ tuy được sinh khởi từ trong tâm trí sâu thẩm của con người, nhưng nó được trình diễn trong một trật tự ngữ pháp có quy tắc. Mỗi loại ngôn ngữ đều có một hệ thống cú pháp riêng, gồm: quy tắc cú pháp, quy tắc phụ thuộc, và quy tắc xác định cấu trúc câu. Ví dụ: câu đẳng lập, câu phụ thuộc, câu hỏi, câu phủ định, và nhiều loại câu khác... 

Từ lý thuyết cú pháp quy nạp (Generative Syntax Theory), các nhà nghiên cứu thuộc trường phái này nhận định: Khả năng sáng tạo ngôn ngữ của con người là vô tận. Chỉ cần chúng ta tuân theo trật tự và quy tắc này và đồng thời kết hợp các cụm từ có thể kết hợp lại với nhau thì có thể linh hoạt và tự do sáng tạo ra vô số các câu mới, hợp lệ và đúng ngữ pháp.

Từ lý thuyết cú pháp quy nạp, các nhà khoa học máy tính phát triển các thuật toán phân tích cú pháp từ trên xuống và từ dưới lên. Trong số các thuật toán phân tích cú pháp, thì thuật toán sớm và hoàn chỉnh nhất là thuật toán Transformations của Zelig Harris và dự án Discourse Analysis Project (TDAP).

Từ lý thuyết đến thuật toán Transformations của Zelig Harris

Zellig Harris, nhà ngôn ngữ học người Mỹ có nhiều đóng góp quan trọng trong lĩnh vực ngôn ngữ học và xử lý ngôn ngữ tự nhiên. Thuật toán Transformations được ông bắt đầu phát triển từ những năm 1950-1951, dựa trên các Lý thuyết cú pháp quy nạp (Generative Syntax Theory) cho rằng: chỉ cần dựa trên cấu trúc ngữ pháp và trật tự của cụm từ thì có thể tạo ra vô số các câu mới, từ ngữ pháp đơn giản có thể tạo ra ngữ pháp phức tạp hoặc ngược lại.

Thuật toán Transformations hoạt động theo trình tự như sau:

- Bắt đầu với một câu đơn giản, chẳng hạn như "John hit the ball."

- Áp dụng một quy tắc chuyển đổi để biến đổi câu thành một câu phức tạp hơn, chẳng hạn như "The ball was hit by John."

- Tiếp tục áp dụng các quy tắc chuyển đổi cho đến khi đạt được cấu trúc cú pháp mong muốn.

Thuật toán Transformations áp dụng 2 quy tắc chuyển đổi chính: Quy tắc chuyển đổi nội bộ và Quy tắc chuyển đổi ngoại bộ;

(1) Quy tắc chuyển đổi nội bộ dùng để biến đổi một thành phần của câu thành một thành phần khác của cùng một câu.

* Ví dụ, quy tắc chuyển đổi nội bộ "N + V" có thể được sử dụng để biến đổi câu "John hit the ball" thành câu "The ball was hit by John."

(2) Quy tắc chuyển đổi ngoại bộ biến đổi một câu thành một câu khác.

Ví dụ, quy tắc chuyển đổi ngoại bộ "NP + VP" có thể được sử dụng để biến đổi câu "John hit the ball" thành câu "The ball was hit by John."

Thuật toán Transformations được ứng dụng hết sức rộng rãi trong các công tác phân tích cú pháp, tạo câu, dịch máy, nhận dạng ngôn ngữ, trả lời câu hỏi, hoặc có thể được sử dụng để mô tả sự tương đồng giữa các câu. Tuy nhiên thuật toán Transformations tương đối khó học và khó sử dụng, và không thể áp dụng với tất cả các ngôn ngữ.

Đoạn mã triển khai thuật toán Transformations để phân tích một câu đơn giản

Dưới đây là một ví dụ bằng Java sử dụng thuật toán Transformations của Zelig Harris để phân tích cú pháp của một câu đơn giản:

import java.util.ArrayList;
import java.util.List;

public class TransformationsParser {

    private static List<Rule> rules = new ArrayList<>();

    static {
        rules.add(new Rule("S", "NP VP"));
        rules.add(new Rule("NP", "N"));
        rules.add(new Rule("NP", "Det N"));
        rules.add(new Rule("VP", "V"));
        rules.add(new Rule("VP", "V NP"));
    }

    public static List<Tree> parse(String sentence) {
        List<Tree> trees = new ArrayList<>();
        List<Word> words = sentence.split(" ");
        for (int i = 0; i < words.size(); i++) {
            Tree tree = new Tree(words.get(i));
            trees.add(tree);
        }

        int left = 0;
        int right = 0;
        while (left < trees.size()) {
            Tree tree = trees.get(left);
            List<Rule> applicableRules = getApplicableRules(tree);
            if (applicableRules.isEmpty()) {
                left++;
            } else {
                Rule rule = applicableRules.get(0);
                List<Tree> newTrees = applyRule(rule, trees.subList(left, right + 1));
                trees = newTrees;
                left = right + 1;
            }
        }

        return trees;
    }

    private static List<Rule> getApplicableRules(Tree tree) {
        List<Rule> applicableRules = new ArrayList<>();
        for (Rule rule : rules) {
            if (rule.left.equals(tree.label)) {
                applicableRules.add(rule);
            }
        }
        return applicableRules;
    }

    private static List<Tree> applyRule(Rule rule, List<Tree> trees) {
        List<Tree> newTrees = new ArrayList<>();
        for (Tree tree : trees) {
            if (tree.label.equals(rule.left)) {
                Tree newTree = new Tree(rule.right);
                newTree.children.addAll(tree.children);
                newTrees.add(newTree);
            }
        }
        return newTrees;
    }

    public static void main(String[] args) {
        String sentence = "John hit the ball";
        List<Tree> trees = parse(sentence);
        for (Tree tree : trees) {
            System.out.println(tree);
        }
    }
}

class Rule {

    String left;
    String right;

    public Rule(String left, String right) {
        this.left = left;
        this.right = right;
    }
}

class Tree {

    String label;
    List<Tree> children;

    public Tree(String label) {
        this.label = label;
        this.children = new ArrayList<>();
    }

    @Override
    public String toString() {
        return label + "(" + children.toString() + ")";
    }
}

í dụ này sử dụng một tập hợp quy tắc chuyển đổi đơn giản để phân tích cú pháp của câu "John hit the ball." Kết quả là một danh sách các cây cú pháp, mỗi cây đại diện cho một cấu trúc cú pháp khác nhau của câu.

Dưới đây là kết quả của ví dụ:

S(NP(N John) VP(V hit) NP(N the) VP(V ball))
S(NP(N John) VP(V hit) NP(N the) VP(V ball))
S(NP(N John) VP(V hit) NP(N the) VP(V ball))

Cây cú pháp đầu tiên là cây cú pháp đầy đủ của câu. Cây cú pháp thứ hai là cây cú pháp của mệnh đề chính. Cây cú pháp thứ ba là cây cú pháp của mệnh đề phụ. Cây cú pháp thứ tư là cây cú pháp của cụm danh từ "the ball."

Ví dụ này có thể được mở rộng để sử dụng một tập hợp quy tắc chuyển đổi phức tạp hơn.