Lan truyền kích hoạt trên mạng ngữ nghĩa – spreading activation in semantic network.

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[i] 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[i] 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[i] = 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[i] chưa được kích hoạt trong đồ thị có một kích hoạt A[i] 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[i] với mục tiêu node[j] , điều chỉnh:

A [j] = A [j] + (A [i] * 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ị.

– Các nút nhận được giá trị kích hoạt mới có vượt quá ngưỡng kích hoạt F được đánh dấu để kích hoạt vào chu trình kích hoạt tiếp theo.

– Nếu kích hoạt bắt nguồn từ nhiều hơn một nút, một biến của thuật toán sẽ cho phép đánh dấu các kích hoạt đã đi qua để phân biệt với các con đường chưa được kích hoạt trên đồ thị.

– Thủ tục chấm dứt khi một trong hai không có thêm các nút để kích hoạt trong trường hợp các dấu hiệu chuyển từ nhiều nguồn gốc, khi có nhiều hơn một con đường xuất phát từ một nút. Các biến sử dụng trong thuật toán cho phép lặp đi, lặp lại hoặc sa thải nút hoặc dòng kích hoạt trong đồ thị, chấm dứt sau khi một trạng thái kích hoạt ổn định, đối với một số trường, được đạt tới, hoặc số lần lặp vượt quá mức tối đa.

3. Ví dụ:

clip_image001

Trong ví dụ này, nút gốc của kích hoạt lan truyền là node 1 với giá trị kích hoạt ban đầu là 1(100%). Mỗi liên kết có trọng số là 0.9. Các yếu tố suy biến là 0.85. Có 4 chu kỳ lan truyền kích hoạt xảy ra (thể hiện qua 4 màu của đồ thị trên). Màu sắc và độ bão hòa chỉ ra các giá trị kích hoạt khác nhau.

Tài liệu tham khảo.

Advertisements

About thanhcuong1990

Handsome and talent!! ^^
This entry was posted in Artificial Intelligence. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s