Luận văn thạc sĩ: Dự đoán chất lượng không khí bằng Graph Neural Network

Luận văn thạc sĩ nghiên cứu máy tính dự đoán chất lượng không khí dựa trên graph neural network, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh vực

• Tác giả: Phạm Linh Sơn
• Người hướng dẫn: PGS. Quản Thành Thơ
• Trường học: Đại học Quốc gia TP.HCM
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Dự Đoán Chất Lượng Không Khí Dựa Trên Graph Neural Network
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2023
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CÁM ƠN
• TÓM TẮT LUẬN VĂN
• ABSTRACT OF DISSERTATION
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Giới thiệu đề tài
• 1.2. Mô tả bài toán dự đoán chất lượng không khí dựa trên Graph Neural Network
• 1.3. Mục tiêu và nhiệm vụ của luận văn
• 1.4. Giới hạn đề tài
• 1.5. Đóng góp của luận văn
• 1.6. Tóm tắt nội dung
• 2. CHƯƠNG 2: CƠ SỞ KIẾN THỨC
• 3. CHƯƠNG 3: CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN
• 4. CHƯƠNG 4: CÁC MÔ HÌNH ĐỀ XUẤT
• 5. CHƯƠNG 5: KẾT LUẬN
• Tài liệu tham khảo

Tóm tắt

I. Giới thiệu đề tài

Nội dung luận văn "Dự đoán chất lượng không khí dựa trên Graph Neural Network" tập trung vào việc nghiên cứu và phát triển một hệ thống dự đoán chất lượng không khí thông qua việc ứng dụng Graph Neural Network (GNN). Đề tài này xuất phát từ nhu cầu cấp thiết trong việc theo dõi và cải thiện chất lượng không khí, một vấn đề ngày càng trở nên nghiêm trọng trong bối cảnh đô thị hóa và biến đổi khí hậu. Luận văn sẽ phân tích các phương pháp truyền thống như ARIMA, CNN và LSTM, từ đó chỉ ra những hạn chế của chúng trong việc khai thác mối liên kết không gian giữa các cảm biến. Phân tích dữ liệu không khí và dữ liệu môi trường sẽ được thực hiện để làm rõ hơn về mối quan hệ giữa các thông số không khí và sự phân bố không gian của các cảm biến. Mục tiêu cuối cùng là xây dựng một mô hình dự đoán có khả năng cải thiện độ chính xác dự báo thông qua việc kết hợp các yếu tố không gian và thời gian.

II. Cơ sở kiến thức

Chương này sẽ trình bày các khái niệm cơ bản về Graph Neural Network và lý thuyết phổ đồ thị. Mô hình học sâu đã trở thành một công cụ mạnh mẽ trong việc phân tích dữ liệu phức tạp. GNN cho phép khai thác mối quan hệ giữa các đỉnh trong đồ thị, giúp mô hình hóa dữ liệu không chỉ dựa trên các thuộc tính của từng đỉnh mà còn dựa trên mối liên hệ giữa chúng. Lý thuyết phổ đồ thị là một phần quan trọng trong việc hiểu cách thức hoạt động của GNN, giúp xác định các thuộc tính của đồ thị thông qua các giá trị riêng và vector riêng. Việc áp dụng lý thuyết này vào bài toán dự đoán chất lượng không khí sẽ giúp xác định rõ hơn các yếu tố ảnh hưởng đến chất lượng môi trường. Chương này cũng sẽ trình bày các phương pháp học sâu hiện có và cách thức chúng có thể được áp dụng trong bối cảnh dự đoán dữ liệu chuỗi thời gian.

III. Các công trình nghiên cứu liên quan

Trong chương này, các nghiên cứu trước đây liên quan đến dự đoán chất lượng không khí và ứng dụng của GNN sẽ được tổng hợp và phân tích. Nhiều nghiên cứu đã chỉ ra rằng việc áp dụng các mô hình học sâu, đặc biệt là GNN, có thể cải thiện đáng kể độ chính xác của các dự đoán về chất lượng không khí. Các công trình nghiên cứu này không chỉ cung cấp nền tảng lý thuyết mà còn đưa ra các phương pháp thực tiễn có thể áp dụng. Đặc biệt, việc sử dụng các mô hình như CNN-LSTM và mạng nơ-ron tích chập đồ thị sẽ được phân tích để làm nổi bật những ưu điểm và nhược điểm của từng phương pháp. Từ đó, luận văn sẽ chỉ ra hướng nghiên cứu mới nhằm cải thiện hiệu suất của mô hình dự đoán trong bối cảnh dữ liệu chuỗi thời gian.

IV. Mô hình đề xuất

Chương này sẽ trình bày chi tiết về mô hình đề xuất cho bài toán dự đoán chất lượng không khí. Mô hình GNN sẽ được xây dựng dựa trên các thông số không khí và phân bố không gian của các cảm biến. Việc sử dụng lớp tích chập đồ thị (Graph Convolution Networks) sẽ giúp lọc ra thông tin quan trọng từ mạng lưới cảm biến. Đánh giá mô hình sẽ được thực hiện thông qua các chỉ số như MAE, RMSE và MAPE để xác định độ chính xác của các dự đoán. Các kết quả thực nghiệm cho thấy mô hình đề xuất có thể cải thiện đáng kể độ chính xác so với các phương pháp truyền thống. Chương này cũng sẽ thảo luận về các yếu tố ảnh hưởng đến hiệu suất của mô hình và các khuyến nghị cho các nghiên cứu trong tương lai.

V. Kết luận

Chương cuối cùng sẽ tóm tắt các đóng góp của luận văn trong việc ứng dụng Graph Neural Network vào dự đoán chất lượng không khí. Các kết quả thực nghiệm đã chỉ ra rằng mô hình đề xuất không chỉ cải thiện độ chính xác mà còn khai thác hiệu quả các mối liên kết không gian giữa các cảm biến. Luận văn cũng chỉ ra những thách thức còn tồn tại và đề xuất hướng nghiên cứu trong tương lai để tiếp tục cải thiện mô hình dự đoán. Việc áp dụng GNN trong lĩnh vực này mở ra nhiều cơ hội mới cho việc phát triển các ứng dụng trong công nghệ AI trong môi trường và giám sát ô nhiễm không khí.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của Internet vạn vật (IoT), việc thu thập và phân tích dữ liệu từ hệ thống cảm biến ngày càng trở nên quan trọng, đặc biệt trong lĩnh vực dự đoán chất lượng không khí. Theo ước tính, hệ thống cảm biến phân bố rộng khắp tạo ra lượng dữ liệu chuỗi thời gian đa biến lớn, đòi hỏi các phương pháp phân tích hiệu quả để dự báo chính xác các chỉ số không khí như PM2.5, PM10, NO2, CO, SO2, O3 và AQI. Vấn đề nghiên cứu tập trung vào việc khai thác mối liên kết không gian giữa các cảm biến để nâng cao độ chính xác dự đoán, điều mà các phương pháp truyền thống như ARIMA, CNN hay LSTM chưa thể hiện rõ. Mục tiêu cụ thể của luận văn là xây dựng và cải tiến mô hình dự đoán chất lượng không khí dựa trên Graph Neural Network (GNN), tận dụng cấu trúc đồ thị biểu diễn mối quan hệ giữa các cảm biến và dữ liệu chuỗi thời gian đa biến. Nghiên cứu được thực hiện trên dữ liệu thu thập từ 76 cảm biến với 2235 đồ thị, mỗi đồ thị chứa 100 điểm dữ liệu, trong khoảng thời gian phù hợp với hệ thống IoT tại một số địa phương. Ý nghĩa của nghiên cứu được thể hiện qua việc cải thiện các chỉ số đánh giá mô hình như MSE, RMSE, MAE và MAPE, góp phần nâng cao hiệu quả dự báo chất lượng không khí, hỗ trợ công tác quản lý môi trường và sức khỏe cộng đồng.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai lý thuyết chính: lý thuyết phổ đồ thị và mô hình học sâu Graph Neural Network (GNN). Lý thuyết phổ đồ thị sử dụng ma trận Laplacian để biểu diễn mối liên hệ giữa các đỉnh trong đồ thị, giúp mô hình hóa cấu trúc không gian của hệ thống cảm biến. Ma trận Laplacian được tính bằng công thức $L = D - A$, trong đó $D$ là ma trận bậc và $A$ là ma trận kề, phản ánh kết nối giữa các cảm biến dựa trên khoảng cách địa lý. GNN tận dụng các lớp tích chập đồ thị (Graph Convolutional Networks - GCN) để trích xuất đặc trưng không gian và thời gian từ dữ liệu chuỗi thời gian đa biến, đồng thời xử lý mối quan hệ phức tạp giữa các cảm biến. Ngoài ra, các mô hình học sâu truyền thống như mạng nơ-ron tích chập (CNN) và mạng ghi nhớ dài-ngắn hạn (LSTM) cũng được nghiên cứu để so sánh và kết hợp trong mô hình đề xuất. Các khái niệm chính bao gồm: ma trận Laplacian, vector đặc trưng đỉnh, lớp tích chập đồ thị, hàm kích hoạt ReLU và Tanh, cùng các chỉ số đánh giá mô hình như MSE, RMSE, MAE và MAPE.

Phương pháp nghiên cứu

Nguồn dữ liệu sử dụng là tập dữ liệu chuỗi thời gian đa biến thu thập từ 76 cảm biến, với tổng số 2235 đồ thị, mỗi đồ thị chứa 100 điểm dữ liệu đặc trưng. Dữ liệu đầu vào được mô hình hóa dưới dạng cấu trúc đồ thị với vector đặc trưng gồm các chỉ số không khí và tọa độ địa lý (vĩ độ, kinh độ). Phương pháp phân tích chính là xây dựng và huấn luyện mô hình học sâu dựa trên Graph Neural Network kết hợp với các lớp 1D CNN để trích xuất đặc trưng thời gian. Mô hình được huấn luyện với batch size 20, số epoch 500, sử dụng thuật toán tối ưu Adam và hàm lỗi Huber nhằm tăng hiệu quả học và giảm thiểu hiện tượng quá khớp. Quá trình nghiên cứu diễn ra từ tháng 2/2022 đến tháng 6/2023, bao gồm các bước: khảo sát tài liệu, xây dựng mô hình tham khảo, đề xuất mô hình cải tiến, thực nghiệm trên hai hệ thống cảm biến phân bố dày và thưa, đánh giá kết quả dựa trên các chỉ số lỗi và so sánh với các mô hình truyền thống.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả mô hình đề xuất trên hệ thống cảm biến phân bố dày: Mô hình GNN đề xuất đạt MSE là 247.05, giảm 69.25 so với mô hình tham khảo GNN.base; RMSE giảm 2.07, MAE giảm 3.72 và MAPE giảm 0.03. Kết quả này cho thấy sự cải thiện đáng kể trong việc dự đoán chỉ số chất lượng không khí khi tận dụng tốt mối liên kết không gian giữa các cảm biến.

2. Hiệu quả trên hệ thống cảm biến phân bố thưa: Mô hình vẫn duy trì hiệu suất tốt với MSE là 281.05, cho thấy khả năng tổng quát hóa và ứng dụng rộng rãi của mô hình trong các điều kiện phân bố cảm biến khác nhau.

3. So sánh với các mô hình truyền thống: Mô hình kết hợp CNN-LSTM và LSTM đơn lẻ cho kết quả thấp hơn về độ chính xác so với mô hình GNN đề xuất, đặc biệt trong việc khai thác mối liên kết không gian giữa các cảm biến.

4. Tác động của việc tăng số lớp 1D CNN: Việc tăng số lượng lớp 1D CNN trong mô hình đề xuất giúp trích xuất đặc trưng thời gian hiệu quả hơn, góp phần nâng cao độ chính xác dự đoán.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện hiệu quả mô hình đề xuất là do việc kết hợp thông tin phân bố không gian của các cảm biến vào quá trình trích xuất đặc trưng chuỗi thời gian, giúp mô hình hiểu rõ hơn về mối quan hệ tương tác giữa các điểm dữ liệu. So với các nghiên cứu trước đây chỉ tập trung vào dữ liệu chuỗi thời gian đơn biến hoặc không khai thác đầy đủ mối liên kết không gian, mô hình này tận dụng lý thuyết phổ đồ thị và lớp tích chập đồ thị để biểu diễn và xử lý dữ liệu phức tạp hơn. Kết quả có thể được trình bày qua biểu đồ so sánh các chỉ số MSE, RMSE, MAE và MAPE giữa các mô hình trên hai hệ thống cảm biến, minh họa rõ ràng sự vượt trội của mô hình đề xuất. Ý nghĩa của nghiên cứu không chỉ nằm ở việc nâng cao độ chính xác dự đoán mà còn mở rộng khả năng ứng dụng của GNN trong các bài toán dự báo dữ liệu chuỗi thời gian đa biến có cấu trúc phức tạp.

Đề xuất và khuyến nghị

1. Tăng cường tích hợp dữ liệu không gian-thời gian: Khuyến nghị các nhà nghiên cứu và phát triển hệ thống IoT nên áp dụng mô hình Graph Neural Network kết hợp với các lớp CNN để khai thác tối đa mối liên kết không gian giữa các cảm biến, nhằm cải thiện độ chính xác dự báo chất lượng không khí trong vòng 6-12 tháng tới.

2. Mở rộng hệ thống cảm biến và dữ liệu đầu vào: Đề xuất tăng số lượng cảm biến và đa dạng hóa các chỉ số môi trường thu thập để mô hình có thêm dữ liệu phong phú, giúp nâng cao khả năng dự đoán và giảm thiểu ảnh hưởng của nhiễu, thực hiện trong giai đoạn 1-2 năm.

3. Áp dụng thuật toán tối ưu và hàm lỗi phù hợp: Khuyến khích sử dụng thuật toán Adam kết hợp hàm lỗi Huber để tăng hiệu quả huấn luyện và giảm hiện tượng quá khớp, áp dụng ngay trong các dự án phát triển mô hình mới.

4. Phát triển giao diện trực quan và hệ thống cảnh báo: Đề xuất xây dựng hệ thống trực quan hóa kết quả dự báo và cảnh báo sớm chất lượng không khí dựa trên mô hình GNN, giúp các cơ quan quản lý và người dân dễ dàng tiếp cận thông tin, triển khai trong vòng 12 tháng.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành Khoa học Máy tính, Học máy: Luận văn cung cấp kiến thức sâu về ứng dụng Graph Neural Network trong dự đoán dữ liệu chuỗi thời gian đa biến, hỗ trợ phát triển các nghiên cứu tiếp theo về học sâu trên đồ thị.

2. Chuyên gia môi trường và quản lý chất lượng không khí: Các kết quả và mô hình đề xuất giúp cải thiện công tác dự báo chất lượng không khí, hỗ trợ ra quyết định chính sách và quản lý môi trường hiệu quả hơn.

3. Nhà phát triển hệ thống IoT và công nghệ cảm biến: Tham khảo để thiết kế hệ thống thu thập và xử lý dữ liệu cảm biến tối ưu, tận dụng mối liên kết không gian giữa các thiết bị nhằm nâng cao hiệu quả phân tích dữ liệu.

4. Các tổ chức y tế và cộng đồng dân cư: Sử dụng kết quả dự báo chất lượng không khí để cảnh báo sớm, giảm thiểu tác động tiêu cực đến sức khỏe cộng đồng, đặc biệt trong các khu vực đô thị và công nghiệp.

Câu hỏi thường gặp

1. Tại sao cần sử dụng Graph Neural Network thay vì các mô hình truyền thống?
   GNN tận dụng được mối liên kết không gian giữa các cảm biến, điều mà các mô hình truyền thống như ARIMA, CNN hay LSTM không khai thác hiệu quả, từ đó cải thiện độ chính xác dự báo.

2. Mô hình đề xuất có thể áp dụng cho các loại dữ liệu chuỗi thời gian khác không?
   Có, mô hình có thể mở rộng cho các bài toán chuỗi thời gian đa biến có cấu trúc đồ thị tương tự, ví dụ như dự báo giao thông, thời tiết hoặc dữ liệu y tế.

3. Các chỉ số đánh giá mô hình nào được sử dụng trong nghiên cứu?
   Luận văn sử dụng MSE, RMSE, MAE và MAPE để đánh giá hiệu quả dự báo, giúp đo lường sai số và độ chính xác của mô hình.

4. Làm thế nào để xử lý dữ liệu nhiễu trong chuỗi thời gian?
   Mô hình đề xuất sử dụng lớp tích chập đồ thị giúp lọc và trích xuất đặc trưng quan trọng, giảm ảnh hưởng của nhiễu thông qua việc khai thác mối liên kết giữa các cảm biến.

5. Thời gian huấn luyện mô hình mất bao lâu và có thể tối ưu không?
   Với batch size 20 và 500 epoch, thời gian huấn luyện phụ thuộc vào cấu hình phần cứng; việc sử dụng thuật toán Adam và hàm lỗi Huber giúp tối ưu quá trình huấn luyện, có thể rút ngắn thời gian bằng cách điều chỉnh tham số.

Kết luận

• Luận văn đã xây dựng thành công mô hình dự đoán chất lượng không khí dựa trên Graph Neural Network, kết hợp lý thuyết phổ đồ thị và học sâu.
• Mô hình đề xuất cải thiện đáng kể các chỉ số MSE, RMSE, MAE và MAPE so với các mô hình truyền thống và mô hình tham khảo.
• Nghiên cứu khai thác hiệu quả mối liên kết không gian giữa các cảm biến, đồng thời xử lý dữ liệu chuỗi thời gian đa biến với độ chính xác cao.
• Các kết quả thực nghiệm trên hệ thống cảm biến phân bố dày và thưa cho thấy tính khả thi và ứng dụng rộng rãi của mô hình.
• Đề xuất các hướng nghiên cứu tiếp theo bao gồm mở rộng dữ liệu, tối ưu thuật toán và phát triển hệ thống cảnh báo trực quan, góp phần nâng cao quản lý chất lượng không khí và bảo vệ sức khỏe cộng đồng.

Hành động tiếp theo là triển khai mô hình trong các hệ thống IoT thực tế và mở rộng nghiên cứu ứng dụng cho các lĩnh vực khác liên quan đến dữ liệu chuỗi thời gian đa biến.

Trích đoạn nội dung tài liệu

Chương 1 GIỚI THIỆU ĐỀ TÀI: giới thiệu về nhu cầu dự đoán trong dữ liệu chuỗi thời gian, mô tả bài toán dự đoán chất lượng không khí dựa trên mạng nơ-ron tích chập đồ thị, tập dữ liệu dạng chuỗi thời gian được sử dụng cũng như phương pháp đánh giá. − Chương 2 CƠ SỞ KIẾN THỨC: bàn về cơ sở kiến thức cơ bản trong học sâu, từ mạng nơ-ron tích chập tới mạng nơ-ron tích chập đồ thị, Hồi quy dịch chuyển trung bình, Mạng ghi nhớ dài-ngắn hạn. − Chương 3 CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN: nói về các công trình nghiên cứu liên quan, bắt đầu từ công trình nghiên cứu mạng học sâu trên đồ thị của Stefan Bloemheuvel, Jurgen van den Hoogen, Dario Jozinovi´c, Alberto Michelini & Martin Atzmueller, 2022, mở ra hàng loạt công trình tiếp theo cho hướng nghiên cứu cho bài toán dự đoán trong dữ liệu chuỗi thời gian, và đó cũng là cơ sở quan trọng cho nghiên cứu của học viên trong luận văn. − Chương 4 CÁC MÔ HÌNH ĐỀ XUẤT: Chương 4 nói cụ thể về các mô hình đề xuất của học viên cho bài toàn dự đoán chất lượng không khí và các kết quả thực nhiệm.

5 − Chương 5 KẾT LUẬN: Tổng kết các đóng góp của luận văn, các vấn đề còn tồn tại của bài toán dự đoán dữ liệu chuỗi thời gian đồng thời nói về nghiên cứu trong tương lai. 6 Chương 2 CƠ SỞ KIẾN THỨC Trong luận văn, tác giả lựa chọn trình bày theo hướng sử dụng mô hình Graph Neural Networks cho bài toán dự đoán chất lượng không khí. Trong nhiều nghiên cứu trước đây chủ yếu sử dụng các công cụ toán học hoặc sử dụng học máy xoay quanh mô hình mạng nơ-ron tích chập. Tuy nhiên, các mô hình đó vẫn tồn tại nhược điểm là chưa biểu diễn được mối liên kết tự nhiên giữa tính không gian và thời gian của dữ liệu.

Để giải quyết vấn đề đó, mô hình mạng nơ-ron tích chập đồ thị dựa trên lý thuyết phổ đồ thị được chọn là hướng nghiên cứu chính của luận văn. Đồ thị Một phần của học sâu với đồ thị là tập trung vào cấu trúc dữ liệu dạng đồ thị. Đồ thị thể hiện mối quan hệ giữa tập các đỉnh (vertices) được kết nối bởi các cạnh (edges) với nhau. Đồ thị được định nghĩa 𝐺 = (𝑉, 𝐸) trong đó V là tập đỉnh và E là tập cạnh.

Mỗi cạnh 𝑒𝑖𝑗 = (𝑥𝑖 , 𝑥𝑗 ) kết nối đỉnh 𝑥𝑖 và 𝑥𝑗. Một cách phổ biến để biểu diễn đồ thị là sử dụng ma trận kề (Adjacency matrix) 𝐴 ∈ ℝ𝑁×𝑁 với 𝑁 = |𝑉|, ma trận kề là ma trận vuông có giá trị của đường chéo chính bằng một 𝐴𝑖𝑗 = 1 nếu tồn tại cạnh nối đỉnh 𝑥𝑖 đến 𝑥𝑗 , ngược lại 𝐴𝑖𝑗 = 0. Số lượng đỉnh lân cận thuộc đỉnh 𝑥 được xác định bởi bậc của đỉnh 𝑥 và biểu diễn như sau 𝐷𝑖𝑖 = ∑𝑗 𝐴𝑖𝑗 , trong đó D là ma trận bậc. Cạnh có thể có hướng 7 hoặc vô hướng.

Cạnh có hướng là cạnh chỉ hướng từ đỉnh nguồn đến đỉnh đích. Cạnh vô hướng là cạnh không có khái niệm liên quan đến đỉnh nguồn và đích. Các đỉnh, cạnh và toàn bộ biểu đồ có thể có các các đặc trưng (features) của dữ liệu, ví dụ: vector 𝑥 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) là một vector đặc trưng của đỉnh 𝑎.1: Vector đặc trưng của mỗi đỉnh thuộc đồ thị 2. Lý thuyết phổ đồ thị Lý thuyết phổ đồ thị (Spectral Graph Theory) [5] là hướng nghiên cứu về tính chất của đồ thị trong qua công cụ đại số với mối quan hệ của giá trị riêng (eigenvalues) và vector riêng (eigenvectors), điển hình như ma trận kề, ma trận Laplacian.

Ma trận Laplacian: Cho đồ thị 𝐺 = (𝑉, 𝐸), với |𝑉| = 𝑛, ma trận Laplacian là ma trận thể hiện mối liên hệ của đồ thị G, có kích thước 𝑛 × 𝑛.1) 8 Trong đó, D là ma trận bậc (degree matrix) với 𝐷(𝑖, 𝑖) là bậc của đỉnh 𝑖𝑡ℎ, A là ma trận kề với 𝐴(𝑖, 𝑗) = 1 nếu và chỉ nếu (𝑖, 𝑗) ∈ 𝐸. Vì vậy, ta có thể biểu diễn ma trận Laplacian như sau: deg(𝑖) 𝑛ế𝑢 𝑖 = 𝑗 𝐿(𝑖, 𝑗) = {−1 𝑛ế𝑢 (𝑖, 𝑗) ∈ 𝐸 (2.2: Tính ma trận Laplacian từ ma trận bậc và ma trận kề. Trong đồ thị G, phép nhân một vector với ma trận Laplacian thể hiện sự sai biệt của một đỉnh đối với các đỉnh lân cận.3) 9 Phần tử thứ 𝑖𝑡ℎ của phép nhân 𝐿𝑥 bằng tổng của các hiệu từ phần tử thứ 𝑖𝑡ℎ đến các phần tử còn lại: 𝑤(𝑖) = deg(𝑖) 𝑥(𝑖) − ∑𝑗:(𝑖,𝑗)∈𝐸 𝑥𝑗 = ∑𝑗:(𝑖,𝑗)∈𝐸 (𝑥(𝑖) − 𝑥(𝑗)) (2.4) Nếu một đỉnh của đồ thị G có vector đặc trưng là 𝑣 thì dạng toàn phương (quadratic form) 𝑣 𝑡 𝐿𝑣 thể hiện chính xác mối liên hệ của đỉnh này đến các đỉnh lân cận. 𝑣 𝑡 𝐿𝑣 được tính chính xác bằng tổng bình phương của các hiệu với những giá trị của đỉnh lân cận.

Graph Neural Network Graph Neural Network - GNNs là mô hình học sâu dựa trên cơ sở của đồ thị. Trước đây có 2 phương pháp sử dụng GNNs là: Phương pháp phổ (Spectral method) và phương pháp không gian (Spatrial methods). Phương pháp phổ sử dụng vector riêng (eigenvectors) và trị riêng (eigenvalues) của ma trận và thực hiện tích chập với phép biến đổi Fourier đồ thị ( Graph Fourier Transformation) và nghịch đảo biến đổi Fourier đồ thị (inverse Graph Fourier transform). Phép biến đổi của đầu vào 𝑥 được định nghĩa là 𝐹(𝑥) = 𝑈 𝑇 𝑥 và 𝐹 −1 (𝑥) = 𝑈𝑥.

Trong đó, U đại diện cho ma trận vector riêng của ma trận chuẩn hóa Laplacian: 𝐿 = 𝐼 − 𝐷 −1/2 𝐴𝐷−1/2 (2.6) 10 Trong đó, D là ma trận bậc của ma trận kề A và I là ma trận đơn vị. Phương pháp không gian sử dụng kỹ thuật message passing để xác định các đỉnh lân cận và thực hiện tính toán giới hạn đến lân cận thứ k. Mỗi đỉnh sẽ được cập nhập giá trị mới bởi hàm 𝑓, một phép cập nhập được biểu diễn bởi hàm 𝑍 = 𝑓(𝐺)𝑋. Trong đó, 𝐺 là ma trận chuẩn hóa Laplacian và 𝑋 là đặc trưng của đỉnh (node features).

Tuy nhiên, vấn đề gặp phải với phương pháp không gian là định nghĩa lớp tích chập kết hợp với k đỉnh lân cận.3: Đồ thị được áp dụng bộ lọc F vào mỗi đỉnh. 𝐹 được xác định bởi một hàm số 𝑔𝜃 = 𝑑𝑖𝑎𝑔(𝜃) trong đó 𝜃 là bộ tham số cần học. Khi áp dụng hàm số 𝑔𝜃 tại mỗi đỉnh, đồng nghĩa thực hiện phép toán 𝑔𝜃 × 𝑥 = 𝑈𝑔𝜃 (Λ)𝑈 𝑇 , trong đó 𝑥 là vector đặc trưng, Λ là ma trận giá trị riêng, 𝑈 là mà trận vector riêng của ma trận chuẩn hóa đồ thị Laplacian. Vì vậy, ta có thể hiểu 𝑔𝜃 (Λ) là hàm số xác định ma trận giá trị riêng của L.

11 Tối ưu bằng cách áp dụng đa thức Chebyshev (Hammond, Vandergheynst & Gribonval, 2011) và phương pháp chuẩn hóa, vì thế có thể tăng tốc độ học và tránh hiện tượng không học được gì (vanishing gradients). Phương pháp không gian tập trung vào sự kết nối của đồ thị trong khi phương pháp phổ dựa vào giá trị riêng và vector riêng của đồ thị. Phương thức lan truyền được biểu diễn như sau: ̃ −1/2 𝐴̃𝐷 𝐻(𝑙+1) = 𝜎(𝐷 ̃ −1/2 𝐻(𝑙) 𝑊 (𝑙) ) (2.4: Phương thức lan truyền của mô hình. Trong đó, 𝐻 (𝑙) là ma trận của lớp kích hoạt thứ 𝑙𝑡ℎ, 𝜎 biểu thị hàm kích ̃ = ∑𝑗 𝐴̃𝑖𝑗 là ma trận bậc; 𝐴̃ = 𝐴 + 𝐼𝑁 là ma trận kề của đồ thị vô hướng hoạt, 𝐷 G được kết hợp với ma trận đơn vị để thể hiện kết nối của một đỉnh với chính nó, 𝑊 (𝑙) là ma trận trọng số huấn luyện.

Mô hình Artificial Neural Network Mô hình Mạng nơ-ron nhân tạo (Hopfield, 1988) là mô hình tính toán được xây dựng dựa trên ý tưởng lấy từ cấu trúc và cách hoạt động của mạng nơ-ron 12 thần kinh trong não người nhằm thực hiện một tác vụ nào đó với tập dữ liệu đầu vào. Một mạng nơ-ron thần kinh được tạo nên từ nhiều nơ-ron sinh học kết nối và hoạt động cùng nhau. Mỗi nơ-ron sinh học đó được cấu tạo bởi các thành phần cơ bản được mô tả trong Hình 3.1 bao gồm đuôi gai, thân nơ-ron và sợi trục. Các đuôi gai (Dendrites) Sợi trục Thân nơ-ron (Axon) (Cell body) Hình 2.5: Các thành phần cơ bản của một nơ-ron sinh học.

Nơ-ron thần kinh hoạt động bằng cách tiếp nhận các thông tin đưa vào từ các đuôi gai (dendrites), tính toán và tổng hợp tại thân nơ-ron (cell body), sau đó lan truyền kết quả đến các nơ-ron khác thông qua sợi trục (axon). Có thể dễ dàng rút ra nhận xét rằng mạng nơ-ron thần kinh nhận nhiều thông tin đầu vào nhưng chỉ đưa ra một kết quả duy nhất. Tương tự như cách thức hoạt động của mạng nơ-ron thần kinh nêu trên, ANN cũng được cấu thành từ nhiều nơ-ron được gọi là perceptron có cấu trúc như Hình 3. Trong đó: 13 - 𝑥1 , 𝑥2 , 𝑥3 , … 𝑥𝑛 là các thông tin dữ liệu đầu vào.

- Phép cộng và hàm kích hoạt chính là các phép tính toán và tổng hợp các thông tin dữ liệu đầu vào. - 𝑤0 , 𝑤1 , 𝑤2 , 𝑤3 , … 𝑤𝑛 là các trọng số cần phải học, đóng vai trò tham gia quá trình tính toán và chuyển đổi các thông tin đầu vào thành thông tin đầu ra. - 𝑦 là dữ liệu đầu ra. 𝑥1 𝑤0 hàm kích hoạt 𝑤1 𝑥2 𝑤2 𝑥3 𝑤3 Σ 𝑦 …….

𝑤𝑛 𝑥𝑛 phép cộng Hình 2.6: Cấu trúc của một perceptron. Cụ thể hơn, phương thức tính toán và tổng hợp dữ liệu của một perceptron được mô tả theo từng bước sau: 1. Sau khi tiếp nhận tập các dữ liệu đầu vào {𝑥1 , 𝑥2 , … , 𝑥𝑛 }, perceptron thực hiện phép cộng bằng cách tính tổng giá trị tất cả các tích số của từng cặp dữ liệu đầu vào và giá trị trọng số tương ứng. Kết quả 𝑎 của phép cộng được đưa vào hàm kích hoạt là hàm không tuyến tính như sigmoid, tanh, ReLU, LeakyReLU.7: Một số hàm kích hoạt được sử dụng trong perceptron.

Sau đó, perceptron thực hiện phép so sánh giá trị nhận được từ hàm kích hoạt 𝑓(𝑎) với một giá trị ngưỡng (threshold) là t cho trước nhằm xác định giá trị đầu ra 𝑦̂ được hiểu là tín hiệu kích hoạt của perceptron. Giả sử tín hiệu kích hoạt là 1 và tín hiệu không kích hoạt là 0, ta có: 15 𝑦 = [01 𝑖𝑓 𝑖𝑓 𝑓(𝑎)≥𝑡 𝑓(𝑎)<𝑡 (2.9) Tầng dữ Các tầng ẩn Tầng kết kiện quả Dữ liệu 1 Đầu ra 1 …. Dữ liệu Đầu ra m 3 Hình 2.8: Cấu trúc mô hình Artificial Neural Network.