Home » TechNote » From Data Structure To Knowledge Representation – Từ “Cấu trúc dữ liệu” đến “Biểu diễn tri thức”

From Data Structure To Knowledge Representation – Từ “Cấu trúc dữ liệu” đến “Biểu diễn tri thức”

1. Dữ liệu là gì và tại sao phải tổ chức chúng:
Dữ liệu là một tập các giá trị dùng để mô tả các tính chất nhằm mục đích trình bày lại hay chia nhỏ thông tin. (Wiki: Data or is a set of value of qualitative or qualitative variable; restated, pieces of data are individual pieces of information). Chẳng hạn ta muốn mô tả các hình khối đơn giản như “Hình chữ nhật”:
– Chiều dài: giá trị độ dài của cạnh dài hơn của hình chữ nhật trên.
– Chiều rộng: giá trị độ dài của cạnh ngắn hơn của hình chữ nhật trên.
Với 2 giá trị như trên ta có thể phân biệt được các hình chữ nhật với nhau (Chỉ xét về khía cạnh kích thước, ví dụ không đề cập đến toạ độ, vị trí…).
Hay như trong đời sống bình thưởng, chúng ta có tên, có số CMND, mục đích của những thứ đó cũng là để phân biệt và xác định mỗi con người. Dĩ nhiên chúng cũng là những giá trị để mô tả con người trong xã hội (Không nằm trong một xã hội nào, thì bản thân chúng ta không cần tên hay CMND làm gì cả). Vì thế, đó cũng là dữ liệu. Dữ liệu ở khắp mọi nơi, chúng mô tả mọi thứ, từ trong từng tế bào (thông tin DNA của mỗi người) cho đến sổ sách, máy móc đều lưu trữ dữ liệu nào đó. Ngay cả như trí nhớ của chúng ta, cũng là dữ liệu, có điều nó mô tả những sự kiện, kiến thức, đối tương… ta đã học, gặp hay trải qua trong quá khứ. Nhắc đến trí nhớ, ta sẽ cảm thấy ngay một vấn đề, nếu đơn thuần là dữ liệu, chúng như nhau, vậy tại sao có người trí nhớ tốt, trí nhớ kém hay thậm chí…mất trí nhớ (ý là không nhớ được), vấn đề do đâu?
Câu hỏi này chắc hẳn ai cũng từng trả lời, câu trả lời có thể:
– Bẩm sinh, bản thân bộ não của người trí nhớ tốt đã hoạt động tốt hơn những người khác. (Really ?).
– Chăm chỉ, giống như việc ta học vẹt vậy, muốn nhớ cái gì cứ việc nhẩm đi nhẩm lại thứ đó cho tới khi nằm lòng thì thôi (Cơ chế tạo shortcut của não bộ).
– Khả năng tổ chức, cũng như việc ta sắp xếp đồ đạc sao cho dễ tìm vậy, chỉ việc tìm theo đúng quy trình, dũ đồ nhiều mấy cũng sẽ tìm ra. (Khả năng tổ chức, sắp xếp dữ liệu)

Hiện tại với vốn hiểu biết của bản thân cũng như tiếp xúc với các “nạn nhân”, tôi chỉ thấy họ đưa ra 3 ý kiến như trên (Có thể do giao thiệp không được rộng). Chúng ta sẽ mổ xẻ mấy điều trên một chút:
– Bẩm sinh: chuyện này thì hơi vượt quá hiểu biết của bản thân tôi hay những người bình thường khác, nhưng đại khái chắc là não bộ của những “siêu nhân“ này có khả năng hay cơ chế gì đó khác người giúp họ lấy ra được thông tin cần thiết một cách nhanh chóng.
– Chăm chỉ: vụ này thì tôi biết, cơ chế tạo “đường mòn” của não bộ giúp ta có những thứ như phản xạ có điều kiện, chủ yếu là do luyện tập, nhưng lâu không dùng đến, có khi những thông tin này vẫn bị mất đi.
– Khả năng tổ chức: điều này khiến mọi thứ có chút logic hơn, ví dụ như bạn muốn nhớ đường từ nhà tới phố A, phố B, phố C, cách 1, đi 1 lần là nhớ, cách 2, đi nhiều lần khắc nhớ, cách 3: … mang bản đồ. Bản đồ chính là 1 hình thức tổ chức các địa điểm nằm ở vị trí nào so với nhau, khoảng cách, hướng đi.. Vì thế nên vấn đề bây giờ chỉ còn là xem ta đang ở đâu.

Như ví dụ ở trên ta thấy, nếu không có thiên phú, ta sẽ phải chọn hoặc là nhớ “vẹt” từng đoạn đường từ nhà tới phố A, phố B, phố C hoặc là sử dụng bản đồ (bản đồ ta cũng hoàn toàn có thể…tự vẽ).  Vấn đề ở đây là trí nhớ thực tế chỉ là cách ta lấy thông tin từ trong não bộ ra như việc tìm đồ đạc, dễ tìm hay không là do ta sắp xếp chúng (Các bạn thử tượng tượng tìm kim khâu trong 1 toà biệt thự bừa bộn hay ngăn nắp). Mọi thứ vẫn ở đó, nhưng thời gian và sức lực bỏ ra rất khác nhau, hoặc nhanh hoặc chậm hoặc thậm chí không bao giờ. Vậy nên tổ chức dữ liệu vô cùng quan trọng, không chỉ ở CNTT mà ở mọi lĩnh vực.

2. Ý nghĩa của biểu diễn tri thức và cấu trúc dữ liệu đối với máy tính:
Như phần trên chúng ta đã thấy được phần nào giá trị của việc tổ chức dữ liệu trong cuộc sống (một cách trực quan). Khác với con người – chúng ta có thể hiểu mọi thứ thông qua những gì ta cảm nhận được qua các giác quan, đối với máy tính mọi thứ trong tiến trình của chúng chỉ được biểu diễn thông qua những biến số hay phương thức mà chúng áp dụng với những biến số đó. Việc tổ chức dữ liệu hay biểu diễn tri thức sẽ rất quan trọng, nó tạo ra sự khác biệt giữa giải thuật hiểu quả, có thể giải quyết được vấn đề và giải thuật vô nghĩa. Điều này đặc biệt đúng với mọi vấn đề của AI (Artificial Intelligent) vì chúng giải quyết những vấn đề mang đặc tính con người hơn mà thông tin con người tiếp nhận một cách thông thường thì máy tính lại không hiểu. Chẳng hạn như trong ví dụ sau:
Trên sân bóng có rất nhiều những camera đặt quanh sân giúp bình luận viên có thể chuyển cảnh tới đối tượng mà mình đang bình luận.
– Cách con người: dùng mắt tìm kiếm đối tượng đang bình luận và tìm kiếm xung quanh đối tượng đó những camera phù hợp.
– Cách máy tính: chia nhỏ sân bóng thành dạng lưới, đủ nhỏ để xác định chính xác vị trí các đối tượng và đủ lớn để phù hợp với kích cỡ bộ nhớ. Câu hỏi con người đưa vào thay vì là “Tìm vị trí của camera thích hợp” sẽ là “x = ?, y = ?” với x và y là toạ độ của mắt lưới chứa đối tượng cần tìm.

3. Một số cách biểu diễn:
Nếu ai từng học qua về cấu trúc dữ liệu và giải thuật cũng như khá quen với lập trình thông dụng, những cách cấu trúc như Stack, Queue, Graph, Tree sẽ không quá xa lạ. Một số cách tôi đề cập ở đây sẽ gần gũi với ngôn ngữ con người hơn mặc dù khi implement chúng, có thể sẽ chẳng giống với những cách vừa nói hơn.
a. Semantic Net (Mạng ngữ nghĩa):
Đây là một dạng đồ thị định hướng, có khả năng kế thừa. Thông tin được biểu diễn trên các node và liên kết với nhau bởi các edge (có hướng). Mạng ngữ nghĩa cũng là một cách biểu diễn phổ biến trong AI.

Screen Shot 2016-03-21 at 1.14.37 PM
Định hướng: Fido —is a—> Dog (Fido is a Dog ngược lại Dog is a Fido không đúng)
Kế thừa: nếu ta di chuyển edge Fido—chases—> Fang sang Dog—chases—>Cat thì chỉ cần Fido is a Dog && Fang is a Cat sẽ dẫn đến Fido chases Fang mà không cần liên kết trực tiếp.
Nhược điểm: mạng ngữ nghĩa chỉ có thể biểu diễn tri thức dưới dạng liên kết 1-1 nên không thể suy diễn ra những thông tin 1-n một cách trực tiếp.

b. Frames:
Frames là cách biểu diễn dựa trên mạng ngữ nghĩa và cho phép chúng ta thể hiện được tính kế thừa một cách rõ ràng hơn. Ý tưởng của cách biểu diễn này cũng tương tự như của OOP (lập trình hướng đối tượng), nói cách khác Frames là một cách biểu diễn hướng đối tượng và có thể được sử dụng trong xây dựng Expert Systems (Hệ Chuyên Gia – một nhánh của AI).
Frames khắc phục được vấn đề của mạng ngữ nghĩa là chỉ biểu diễn tri thức dưới dạng liên kết 1-1. Frames có thể có nhiều hơn 1 slot, mỗi slot có thể chứa thông tin hay một liên kết tới một Frame khác.

Screen Shot 2016-03-21 at 1.44.46 PM
Với mạng ngữ nghĩa, ta phải cần 3 edge để mô tả thông tin của Bob trong khi chỉ cần 1 Frame với 3 slot. Bên cạnh đó tính kế thừa cũng được thể hiện rõ ràng hơn, chẳng hạn trong 1 slot của Frame “Fido” có thuộc tính Dog -> Fido kế thừa mọi thuộc tính của Dog.

c. Search Spaces: (Không gian tìm kiếm):
Không gian tìm kiếm chứa tập tất cả những trạng thái có thể của đối tượng. Để tìm được đến đích, ta cần xác định được trạng thái ban đầu, trạng thái đích, và những trạng thái trung gian. Một trong số những cách thực hiện là biểu diễn không gian trạng thái của đối tượng, thực hiện duyệt cũng với các phép đánh giá. Đây là cách biểu diễn thường được sử dụng cho AI trong game.
Ví dụ: với game cờ caro
Screen Shot 2016-03-21 at 3.21.00 PM
Mô tả: Game dành cho 2 người, chơi trên bàn cờ 3×3, bắt đầu với bàn cờ trống, mỗi người chơi lần lượt tick “X” hoặc “O” vào các ô còn trống. Ai đạt 3 kí tự cùng loại là thắng. Nếu hết 9 ô trên bàn cờ không có ai thắng thì kết quả là hoà.
Biểu diễn: mỗi trạng thái của ván cờ là 1 tập gồm 9 giá trị đại diện các quân cờ trên bàn cờ. Như hình trên ta có:
(“x”, “x”, “O”, “O”, “”, “”, “”, “”, “”) tương ứng (a00, a01, a02, a10, a11, a12, a20, a21, a22). Vậy nên trong bài toán này ta biểu diễn tập các trạng thái là tập các bộ gồm 9 giá trị như trên. Với trường hợp này, không gian trạng thái không quá lớn, nên có thể không cần sử dụng hàm đánh giá để giảm số lượng trạng thái mà máy tính vẫn có thể tìm ra trạng thái đích.

d. Biểu diễn dạng luật (Rule):
Đây là cách biểu diễn tri thức được sử dụng nhiều trong các Hệ Chuyên Gia (y khoa) phục vụ mục đích chẩn đoán và đưa ra phương pháp điều trị. Cách biểu diễn này khá thân thuộc với con người, chúng tựa như những câu điều kiện trong tiếng Anh: IF A THEN B. Nghĩa là nếu có A thì B sẽ xảy ra.
Biểu diễn: Mọi tri thức sẽ được chuyển thành các luật, mỗi luật bao gồm 2 phần, Fact: nguyên nhân (tương đương với A) và Conclusion: Hệ quả (tương đương với B).
Ví dụ:
Screen Shot 2016-03-21 at 3.42.30 PM
Trong 3 Rule trên chỉ có 1 Fact duy nhất là “it is cold” và 3 con conclusions cho từng luật là “wear a coat” ; “stay at home” ; “turn on the heat”. Trong quá trình suy diễn nếu gặp Fact “it is cold” máy sẽ suy ra 3 kết luận trên.

4. Kết luận:
Tóm lại qua lịch sử nhiều thập kỉ phát triển, từ dữ liệu phổ thông tới những cách biểu diễn tri thức phức tạp đã mang lại nhiều cách tiếp cận cho con người giúp máy tính trở nên thông minh hơn. Bài viết này mới chỉ dừng lại ở mức đề cập, giới thiệu đôi nét về những cách mà con người tạo ra để giúp máy tính “hiểu” vấn để và giải quyết nó. Những bài viết sau tôi sẽ đi sâu hơn với bài toán cụ thể hơn cũng như cách ứng dụng chúng như thế nào.

Tagged width:, ,