Đồ Án Đề Tài: Giải bài toán tam giác tổng quát sử dụng mạng ngữ nghĩa – Solution for triangle using semant

1. Đôi điều cần biết về về giải thuật lan truyền kích hoạt(spreading activation)
Lan truyền kích hoạt (spreading activation) là một phương pháp để tìm kiếm các mạng lưới liên kết, các mạng thần kinh(neural networks), hoặc mạng ngữ nghĩa (semantic networks). Quá trình tìm kiếm được bắt đầu bằng cách ghi nhãn một tập hợp các nút nguồn (ví dụ các khái niệm trong mạng ngữ nghĩa) với kích hoạt hay “activation” và sau đó lặp đi lặp lại các lan truyền hay “spreading” tiếp tục kích hoạt các nút tiếp theo liên quan đến nút nguồn. Trong kích hoạt lan truyền, các nút đã được kích hoạt, và các nút chưa kích hoạt được lưu lại để phục vụ cho việc tìm nút lan truyền tiếp theo hợp lý hơn.
Lan truyền kích hoạt được ứng dụng trong truy suất thông tin, bằng việc sử dụng ngữ nghĩa của một mạng lưới đại diện cho các nút tài liệu và các từ ngữ có trong văn bản đó.
2. Thuật toán:
Cho một đồ thị có hướng được thể hiện bởi mảng Nodes[1 . N], mỗi kích hoạt liên quan đến giá trị A là một số thực nằm trong khoảng [0.0 . 1.0]. Link[i, j] sẽ kết nỗi với nguồn node với mục tiêu là node[j]. Mỗi liên kết có một trọng số là W[i, j] thường là một số thực nằm trong dãy [0.0 . 1.0].
Các tham số:
- Ngưỡng kích hoạt F là một số thực nằm trong khoảng [0.0 . 1.0].
- Yếu tố suy biến D (Decay factor) là một số thực nằm trong khoảng [0.0, , 1.0].
Các bước thực hiện thuật toán:
- Khởi tạo đồ thị, cài đặt tất cả các kích hoạt giá trị A = 0, thiết lập một hoặc thêm các nút gốc để kích hoạt một giá trị ban đầu lớn hơn ngưỡng F. Giá trị khởi tạo thông thường là 1.
- Đối với mỗi node chưa được kích hoạt trong đồ thị có một kích hoạt A lớn hơn giá trị node ngưỡng kích hoạt F.
- Đối với mỗi Link[i, j] kết nối node với mục tiêu node[j] , điều chỉnh:
A [j] = A [j] + (A * W [i, j] * D) trong đó D là yếu tố suy biến.
- Nếu một nút nhận được một mục tiêu điều chỉnh giá trị kích hoạt của nó sẽ vượt quá 1.0, sau đó đặt giá trị kích hoạt mới của nó là 1.0. Tương tự như vậy, duy trì 0.0 như một giá trị ràng buộc kích hoạt thấp hơn, các nút mục tiêu của nó sẽ nhận được giá trị điều chỉnh xuống dưới 0.0.
- Khi một nút đã kích hoạt nó có thể kích hoạt lại một lần nữa, mặc dù các biến thể của thuật toán cơ bản cho phép bỏ qua việc lặp đi lặp lại và vòng qua đồ thị.