MỞ ĐẦU Sự phát triển mạnh mẽ của công nghệ thông tin trong thời gian qua đang nhanh chóng đƣa hệ thống thông tin kỹ thuật số thay thế hệ thống thông tin văn bản cổ truyền. Khi xử lý thông tin số, đặc biệt là khi giải quyết các bài toán kỹ thuật, ta thƣờng gặp bài toán nội suy và xấp xỉ hàm. Mặc dù bài toán này đã đƣợc nghiên cứu kỹ và giải quyết khá trọn vẹn từ lâu cho các hàm một biến, đến nay đối với hàm nhiều biến vẫn còn nhiều vấn đề mở thu hút nhiều nhà nghiên cứu. Hiện nay, các phƣơng pháp địa phƣơng và mạng nơron là hai cách tiếp cận thông dụng để nội suy và xấp xỉ hàm nhiều biến tuy rằng việc ƣớc lƣợng sai số còn chƣa đƣợc giải quyết trọn vẹn.
Trong cách tiếp cận địa phƣơng, các phƣơng pháp k- láng giềng gần nhất và hồi quy địa phƣơng có thời gian tính giá trị hàm tại mỗi biến nhanh nhƣng chúng không dùng hết thông tin và với các điểm khác nhau thì thông tin đã biết ở những điểm khác khó đƣợc sử dụng lại nên khi cần phải tính giá trị hàm tại nhiều điểm thì rất tốn thời gian và không tiện dùng. Mạng MLP (Multilayer Perceptron) là một công cụ mạnh nhƣng thời gian huấn luyện lâu nên không thích hợp cho các hệ thống thời gian thực. Một hệ thống thời gian thực có thể đƣợc hiểu nhƣ là một mô hình xử lý mà tính đúng đắn của hệ thống không chỉ phụ thuộc vào kết quả tính toán mà còn phụ thuộc vào thời gian đƣa ra kết quả. Bài toán thời gian thực này hầu nhƣ xuất hiện trong mọi lĩnh vực.
Trong kinh doanh, các doanh nghiệp luôn cần có những thông tin “thời gian thực” từ thị trƣờng, từ đối tác và bạn hàng, qua đó có thể đƣa ra những chính sách hợp lý. Trong kiểm soát giao thông, việc xác định “thời gian thực” mật độ và lƣu lƣợng giao thông giúp cho các đơn vị sử dụng điều khiển, phân luồng giao thông một cách hợp lý. Trong truyền thông, việc duy trì kết nối “thời gian thực” giúp cho việc tƣơng tác giữa các hệ thống khác nhau đƣợc vận hành đồng bộ và thực hiện đúng mục đích. Trong điều khiển tự động, việc có đƣợc thông tin “thời gian thực” hoạt động của các thiết bị cho phép theo dõi và vận hành các thiết bị này một cách hợp lý và hiệu quả.
Có thể kể ra rất nhiều yêu cầu thực tế khác nhau đòi hỏi các hệ thống phải đảm bảo yếu tố “thời gian thực”. So với mạng MLP, mạng RBF có thời gian huấn luyện nhanh hơn, đặc biệt là thuật toán huấn luyện lặp đƣợc đề xuất trong [2, 3] nên thích hợp với nhiều bài LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Trang - 6 - toán đòi hỏi thời gian xấp xỉ hàm ngắn nói chung và bài toán “thời gian thực” nói riêng. Luận văn này trình bày các nội dung sau: Khảo cứu về mạng nơron RBF để nội suy, xấp xỉ hàm số mà chủ yếu tập trung vào mạng nội suy và thuật toán huấn luyện. Xây dựng phần mềm huấn luyện lặp mạng RBF làm công cụ học tập và nghiên cứu.
Xây dựng phần mềm tính giá trị gần đúng của hàm nội suy trên lƣới đều dựa trên tập giá trị quan trắc cho trƣớc dùng trong bài toán khí tƣợng. Phần trọng tâm của đề tài chính là xây dựng phần mềm cho phép thực nghiệm nội suy bằng mạng nơron RBF và bƣớc đầu thực nghiệm nó vào bài toán khí tƣợng Ngoài phần kết luận, các chƣơng của đề tài đƣợc trình bày nhƣ sau: CHƢƠNG 1: BÀI TOÁN NỘI SUY VÀ XẤP XỈ HÀM Trình bày tóm tắt các điểm cơ bản về bài toán nội suy bao gồm nội suy hàm một biến và nội suy hàm nhiều biến. CHƢƠNG 2: GIỚI THIỆU MẠNG NƠRON Giới thiệu ngắn gọn về mạng nơron bao gồm kiến trúc và luật học của Perceptron đơn, mạng ADALINE và mạng MLP. CHƢƠNG 3: MẠNG NƠRON NỘI SUY RBF Trình bày khảo cứu về mạng RBF và một số ứng dụng.
Nội dung chính của Phương pháp Lặp huấn luyện mạng RBF. CHƢƠNG 4: GIỚI THIỆU CHƢƠNG TRÌNH MÁY TÍNH Giới thiệu chương trình máy tính thực nghiệm bài toán nội suy bằng mạng RBF được huấn luyện bằng phương pháp lặp được trình bày tại chương 3. CHƢƠNG 5: BÀI TOÁN XẤP XỈ HÀM TRONG KHÍ TƢỢNG THỦY VĂN Giới thiệu bài toán thực tế trong khí tượng thuỷ văn đòi hỏi áp dụng xấp xỉ hàm nhiều biến. Bài toán này được đặt ra dựa trên công tác nghiên LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Trang - 7 - cứu, hoạt động của Khoa Khí tượng Thủy văn và Hải dương học – Đại học KHTN – Đại học Quốc gia Hà Nội.
Đồng thời giới thiệu ứng dụng chương trình máy tính được xây dựng để nội suy giá trị theo các mốc quan trắc. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Trang - 8 - CHƢƠNG 1: BÀI TOÁN NỘI SUY VÀ XẤP XỈ HÀM 1. Giới thiệu chung Nội suy và xấp xỉ hàm số là những bài toán đã đƣợc các nhà khoa học nghiên cứu từ rất sớm. Lý thuyết về nội suy hàm số có thể ứng dụng ở rất nhiều lĩnh vực khoa học cũng nhƣ các lĩnh vực trong cuộc sống.
Bài toán nội suy là một trong những vấn đề chính thúc đẩy các nhà khoa học trong ngành Khoa học máy tính phát triển các mạng nơron để giải quyết bài toán này. Chƣơng này trình bày những vấn đề cơ bản liên quan đến bài toán nội suy và xấp xỉ hàm. Bài toán xấp xỉ hàm sẽ đƣợc trình bày rõ hơn trong Chƣơng 5 (Bài toán xấp xỉ hàm trong Khí tƣợng thủy văn). Chƣơng này cũng giới thiệu phƣơng pháp nội suy k-lân cận gần nhất, đây là phƣơng pháp nội suy đơn giản và hiện nay đƣợc nhiều ngƣời ƣa dùng.
Mặc dù các lý thuyết và phƣơng pháp về nội suy hàm một biến đƣợc nghiên cứu khá đầy đủ nhƣng điều này vẫn còn rất hạn chế để áp dụng trong thực tế vì các hàm hay gặp trong thực tế thƣờng là hàm nhiều biến. Bài toán nội suy và xấp xỉ hàm nhiều biến Giả sử D là một miền giới nội trong Rn và f là một hàm liên tục xác định trên D. Ngƣời ta chỉ mới xác định đƣợc tại N điểm x1,x2….xN trong D: f(xi) = yi với mọi i=1,2…,N và cần tính giá trị của f(x) tại các điểm x khác trong D. Bài toán nội suy hàm nhiều biến Để tính f(x), ta cần một hàm (x) xác định trên D có dạng đơn giản dễ tính giá trị sao cho (xi)=yi tại mọi điểm xi đã biết và xấp xỉ f(x) bởi (x).
Khi đó các điểm xi đƣợc gọi là các mốc nội suy và hàm đƣợc gọi là hàm nội suy và đƣợc chọn dƣới dạng đơn giản, dễ tính giá trị trong miền D. Phƣơng pháp k-lân_cận_gần_nhất Đây là phƣơng pháp nội suy đơn giản và hiện nay đƣợc nhiều ngƣời ƣa dùng. Chọn trƣớc số tự nhiên k, với mỗi x D , ta xác định giá trị (x) qua giá trị của f tại k mốc nội suy gần nó nhất. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Trang - 9 - Ký hiệu z1,…,zk là k mốc nội suy gần x nhất và d(u,v) là khoảng cách của hai điểm u,v bất kỳ trong D, khi đó (x) xác định nhƣ sau: k ( x) j f ( z j ) j 1 Trong đó i đƣợc xác định bởi: d ( x, z i ) 1 d ( x, z ) i k 1 j j 1 Dễ thấy rằng khi x dần tới các mốc nội suy thì (x) xác định nhƣ trên dần tới giá trị của f tại mốc nội suy tƣơng ứng.
Tuy sai số của phƣơng pháp không đánh giá chặt chẽ đƣợc nhƣng vẫn đƣợc ƣa dùng trong thực nghiệm. Ta có thể nhận xét rằng phƣơng pháp k-lân_cận_gần_nhất có ƣu điểm là cách tính toán đơn giản và dễ thực hiện, tuy nhiên trên thực tế việc xác định giá trị k phù hợp là một vấn đề khó (phụ thuộc rất nhiều vào kinh nghiệm đánh giá bài toán thực tế), đồng thời mỗi khi cần xác định giá trị của một điểm, phƣơng pháp này lại tìm trong tất cả các giá trị đã biết để tìm đƣợc các mốc gần nhất, điều này đòi hỏi chi phí tính toán nhiều. Ta có thể xem xét một ví dụ: Bài toán phân loại văn bản: Cho mô ̣t số lớp văn bản đã đƣợc xác định trƣớc chủ đề, nhiê ̣m vu ̣ của phân loa ̣i văn bản là : gán các văn bản vào mô ̣t (hay mô ̣t số ) lớp văn bản thić h hơ ̣p dựa vào nội dung của văn bản. Cách thực hiện: Khi cần phân loại một văn bản mới, phƣơng pháp này sẽ tìm trong tập các văn bản đã xác định đƣợc chủ đề để tìm ra k văn bản gần nhất với văn bản cần phân loại (k chính là chỉ số của thuật toán k-lân_cận_gần_nhất và văn bản đƣợc đánh giá là gần nhất dựa trên tiêu chí nào đó, ví dụ mức độ tƣơng tự về nội dung).
Dùng khoảng cách giữa k điểm thu đƣợc để đánh trọng số cho chính chủ đề của văn bản đó. Nhƣ vậy, trọng số của một chủ đề chính là tổng tất cả các khoảng cách văn bản trong k-lân_cận_gần_nhất thu đƣợc ở trên và dễ thấy chủ đề nào không xuất hiện trong k-lân_cận_gần_nhất sẽ có tổng trọng số bằng 0. Sau đó, LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Trang - 10 - các chủ đề sẽ đƣợc sắp theo mức độ trọng số giảm dần và các chủ đề có trọng số cao sẽ đƣợc chọn là chủ đề của văn bản cần phân loại. Cũng theo nhận xét ở phần trên, ta thấy trong ví dụ này, việc xác định chỉ số k một cách hợp lý chỉ có thể dựa theo kinh nghiệm và rất khó để chứng minh k đƣợc chọn là tối ƣu, hơn nữa nếu văn bản có “nhiễu” thì sẽ ảnh hƣởng lớn đến kết quả phân loại.
Bài toán xấp xỉ hàm nhiều biến Bài toán xấp xỉ hàm nhiều biến đƣợc xem là bài toán chung, tổng quát mà trong đó cách tiếp cận nội suy là một trƣờng hợp đặc biệt. Trong bài toán nội suy hàm nội suy phải có giá trị trùng với các giá trị tính đƣợc tại các mốc nội suy đã biết. Khi số mốc nội suy lớn việc xác định hàm nội suy trở thành bài toán khó, khi đó ta chấp nhận các giá trị gần đúng tại các mốc nội suy đã biết và chọn hàm có dạng đơn giản sao cho sai số là tốt nhất.