Tóm tắt Luận văn Tối ưu việc lựa chọn số đầu vào khi áp dụng mạng nơron nhân tạo trong bài toán dự đoán điểm đích của một chuyến taxi

ó thể áp dụng cho bài toán dự đoán số lượng đầu ra cố định (fixed-length output) từ số lượng đầu vào thay đổi (variable- length input). 1.3. Tổng quan luận văn Phần còn lại của luận văn được trình bày như sau. Chương 1 giới thiệu về hoàn cảnh, đặt vấn đề, mô tả phương pháp đề xuất, và cách nội dung trong luận văn được trình bày. Chương 2 trình bày về kiến thức nền tảng về mạng nơron nhân tạo truyền thẳng nhiều tầng. Chương 3 trình bày về bài toán dự đoán điểm đích của chuyến taxi và phương pháp đội MILA lab giải quyết vấn đề cũng như bài toán tìm số lượng đầu vào tối ưu cho mạng nơron nhân tạo nhiều tầng truyền thẳng để cải tiến mô hình của đội MILA lab.. Chương 4 trình bày mô hình đề xuất, xây dựng thử nghiệm và kết quả thực nghiệm của phương pháp. Phần kết luận đưa ra kết quả của luận văn và cũng như triển vọng và hướng nghiên cứu trong tương lai. 2 CHƯƠNG 2: MẠNG NƠRON NHÂN TẠO TRUYỀN THẲNG NHIỀU TẦNG 2.1. Mạng nơron nhân tạo Mạng nơron nhân tạo (artificial neural network) là một mô hình tính toán xử lý thông tin bằng cách mô phỏng theo cách thức hoạt động của hệ nơron sinh học trong bộ não con người [2]. Mạng gồm một nhóm các phần tử (nơron nhân tạo) kết nối với nhau thông qua các liên kết (liên kết được đánh trọng số). Nó làm việc như một thể thống nhất bằng cách truyền thông tin theo các kết nối và tính giá trị mới tại các nơron. Một mạng nơron nhân tạo sẽ được cấu hình để giải quyết một vấn đề cụ thể nào đó như nhận dạng mẫu, phân loại dữ liệu, dự đoán,... Nó hoạt động thông qua một quá trình học từ tập các mẫu huấn luyện. Việc học về bản chất chính là quá trình đưa dữ liệu vào mạng nơron và thực hiện hiệu chỉnh trọng số liên kết giữa các nơron thông qua kết quả có trước trong mẫu. Mô hình toán học tiêu biểu cho một nơron nhân tạo được minh họa như hình 2.1 sau: Hình 2.1 Mô hình toán học của một nơron Cấu trúc của một nơron k được mô tả toán học bằng cặp biểu thức sau: 𝑢𝑘 = ∑ 𝑤𝑘𝑗𝑥𝑗 𝑁 𝑗=1 và yk = f(uk – bk) Trong đó, cụ thể các thành phần của một nơron gồm: 1. Tập đầu vào: là các tín hiệu (dữ liệu) vào của nơron, thường được đưa dưới dạng một vector N chiều (x1, x2, xN). 2. Tập liên kết: là các liên kết từ tín hiệu đến nơron. Mỗi liên kết sẽ được đánh trọng số, ví dụ như nơron thứ k sẽ có trọng số wk1 ở liên kết 1. Do đó với mỗi nơron ta cũng có một vector trọng số liên kết N chiều (wk1,wk2, wkN). Các trọng số này thông thường sẽ được tạo ngẫu nhiên ở thời điểm tạo mạng, sau đó qua quá trình học sẽ được hiệu chỉnh dần. 3. Hàm tổng: là tổng của tích các đầu vào với trọng số liên kết của nó, kí hiệu cho hàm tổng của nơron thứ k là uk. 4. Ngưỡng: là một thành phần của hàm truyền, ký hiệu cho ngưỡng của nơron thứ k là bk. x1 Wk1 x2 Wk2 Ngưỡng bk Đầu vào Trọng số liên kết xN Hàm truyền WkN ∑ . . . Đầu ra Hàm tổng . f(.) yk 3 5. Hàm truyền: là một hàm dùng để tính đầu ra của nơron từ hàm tổng và ngưỡng, ký hiệu là f. 6. Đầu ra: là tín hiệu đầu ra của nơron. Mỗi nơron chỉ có một tín hiệu đầu ra. Với nơron thứ k đầu ra ký hiệu là yk. Khái quát lại, nơron nhân tạo cho một đầu ra từ tập tín hiệu đầu vào. Một số hàm truyền phổ biến là: * Hàm đồng nhất f(t) = αt * Hàm bước nhảy f(t) = { 1 𝑘ℎ𝑖 𝑡 ≥ 𝛼 0 𝑘ℎ𝑖 𝑡 < 𝛼 Có nhiều loại mạng nơron khác nhau trong đó mạng nơron truyền thẳng nhiều tầng là một trong những mạng nơron thông dụng nhất. 2.2. Mạng nơron truyền thẳng nhiều tầng Mạng nơron truyền thẳng nhiều tầng (multi layer perceptron - MLP) là mạng có n tầng (n >= 2). Trong đó tầng nhận tín hiệu vào của mạng gọi là tầng vào (input layer). Tín hiệu ra của mạng được đưa ra từ tầng ra (output layer). Các tầng ở giữa tầng vào và tầng ra gọi là các tầng ẩn (có n–1 tầng ẩn). Các nơron ở một tầng nhất định đều liên kết đến tất cả các nơron ở tầng tiếp theo. Với mạng nơron truyền thẳng (feedforward network) không có nút nào mà đầu ra của nó là đầu vào của một nút khác trên cùng tầng với nó hoặc tầng trước. Hình 2.1 Mạng nơron truyền thẳng nhiều tầng Kiến trúc của một mạng nơron truyền thẳng nhiều tầng tổng quát có thể mô tả như sau: + Đầu vào là một các tập vector (x1, x2, xp) p chiều, đầu ra là một tập các vector (y1, y2, yq) q chiều. + Mỗi nơron thuộc tầng sau sẽ liên kết với tất cả các nơron thuộc tầng ngay trước nó. Như vậy đầu ra của nơron tầng trước sẽ là đầu vào của nơron thuộc tầng liền sau. x2 . . xp x1 . . . . . . . y1 y2 yq Tầng ẩn n-1 . . Tầng ra . . . . . . . . . Tầng vào Tầng ẩn 1 4 Mạng nơron truyền thẳng nhiều tầng sẽ hoạt động như sau: tại tầng đầu vào các nơron nhận tín hiệu vào xử lý, thực hiện việc tính tổng trọng số rồi gửi tới hàm truyền, kết quả của hàm truyền sẽ được gửi tới các nơron thuộc tầng ẩn đầu tiên. Nơi đây các nơron tiếp nhận các kết quả này như là tín hiệu đầu vào và xử lý rồi gửi kết quả đến tầng ẩn thứ 2. Quá trình cứ tiếp tục như thế cho đến khi các nơron ở tầng ra cho ra kết quả. Về ứng dụng của mạng nơron truyền thẳng nhiều tầng, vài kết quả đã được chứng minh cụ thể như sau: + Mọi hàm toán học bất kỳ đều có thể được biểu diễn xấp xỉ bằng một mạng nơron truyền thẳng ba tầng trong đó các nơron ở tầng ra đều sử dụng hàm truyền tuyến tính và tất cả các nơron ở tầng ẩn đều dùng hàm truyền sigmoid. + Tất cả các hàm toán học liên tục đều có thể được biểu diễn xấp xỉ bởi một mạng nơron truyền thẳng hai tầng trong đó các nơron ở tầng ra đều sử dụng hàm truyền tuyến tính với sai số nhỏ tùy ý và tất cả các nơron ở tầng ẩn đều dùng hàm truyền sigmoid. 2.3. Các phương pháp học phổ biến Mạng nơron được học thông qua các luật học. Luật học là một thủ tục dùng để xác định việc cập nhật trọng số liên kết và ngưỡng của mạng nơron. Luật học còn được gọi là thuật toán huấn luyện mạng. Một mạng nơron được huấn luyện sao cho với một tập các vector đầu vào X, mạng sẽ cho ra tập các vector đầu ra Y mong muốn. Tập X dùng để làm đầu vào huấn luyện cho mạng nên được gọi là tập huấn luyện (training set). Các phần tử x thuộc X được gọi là các mẫu huấn luyện (training example). Như đã được đề cập ở phần đầu, việc học bản chất là việc cập nhật liên tục các trọng số liên kết trong mạng nơron. Trong quá trình này, các trọng số của mạng sẽ hội tụ dần tới các giá trị sao cho với mỗi đầu vào, mạng sẽ cho đầu ra như ý muốn. Với mỗi mạng nơron nhân tạo có hai vấn đề cần học đó là học tham số (parameter learning) và học cấu trúc (structure learning). Học tham số là việc điều chỉnh trọng số của các liên kết giữa các nơron trong mạng, còn học cấu trúc là việc thay đổi cấu trúc của mạng bao gồm thay đổi số lớp nơron, số nơron của mỗi lớp và cách liên kết giữa chúng. Luật học của mạng nơron có thể chia làm 3 loại: học có giám sát (supervised learning), học không có giám sát (unsupervised learning), học tăng cường (reinforcement learning). + Học có giám sát: là quá trình học giống việc ta dạy cho trẻ, luôn luôn có một người “thầy giáo”, muốn dạy cho trẻ chữ “a”, ta đưa chữ “a” ra và nói với trẻ rằng đây là chữ “a”. Cuối cùng để kiểm tra việc học, ta sẽ đưa ra một chữ cái bất kỳ và hỏi đây là chữ gì. + Học không giám sát: là quá trình học mà không có bất kỳ một người giám sát nào. Trong bài toán mà luật học không giám sát được áp dụng, với tập dữ liệu huấn luyện D thì nhiệm vụ của thuật toán học là phải phân chia tập dữ liệu D thành các nhóm con, mỗi nhóm chứa các giá trị đầu vào có đặc trưng giống nhau. Do đó với học không giám sát, số tầng phân loại chưa được biết và tùy theo yêu cầu về độ giống nhau giữa các mẫu mà ta có các tầng phân loại tương ứng. + Học tăng cường: còn được gọi là học thưởng phạt vì phương pháp này hoạt động như sau: với mỗi giá trị đầu vào, thực hiện đánh giá vector đầu ra mà mạng tính được với kết quả mong muốn, nếu được xem là “tốt” thì mạng sẽ được thưởng (chính là việc tăng các trọng số liên kết), ngược lại nếu “xấu” mạng sẽ bị phạt (tức là giảm các trọng số liên kết). Vì vậy học tăng cường là học theo nhà phê bình còn học giám sát là học theo thầy giáo. 5 CHƯƠNG 3: BÀI TOÁN TÌM SỐ ĐẦU VÀO TỐI ƯU KHI DỰ ĐOÁN ĐIỂM ĐÍCH CỦA CHUYẾN TAXI 3.1. Bài toán dự đoán điểm đích của taxi Bài toán tìm đích đến của một chuyến taxi đang gây được sự chú ý của cộng đồng nghiên cứu trong thời gian gần đây. Vì vậy vào năm 2015 tại hội nghị ECML/PKDD đã tổ chức một cuộc thi dự đoán đích đến của một chuyến taxi như là một cuộc thi của Kaggle [15]. Dữ liệu đầu vào của bài toán là những điểm bắt đầu trong hành trình của một chuyến taxi (thường gọi là prefixes) và những thông tin meta của chuyến taxi đó. Từ đó người tham gia cuộc thi phải tìm ra điểm đích của cuộc hành trình đó (gồm kinh độ và vĩ độ). Ý nghĩa của việc giải bài toán trên là sẽ giúp công ty taxi phân chia số lượng taxi tại mỗi điểm đón, khu vực đón một cách tối ưu nhất. Người tham gia cuộc thi sẽ phải xây dựng một mô hình dự đoán dựa trên tập dữ liệu gồm tất cả các chuyến đi của 442 taxi hoạt động tại thành phố Porto thủ đô của Bồ Đào Nha trong suốt một năm hoàn chỉnh (từ ngày 01/07/2013 đến ngày 30/06/2014) [15]. Tập dữ liệu huấn luyện trên có hơn 1.7 triệu chuyến đi hoàn chỉnh [1]. Mỗi chuyến đi sẽ bao gồm các thông tin sau: + Một chuỗi các vị trí (gồm kinh độ và vĩ độ) được đo bằng GPS mỗi 15 giây. + Thông tin meta tương ứng với mỗi chuyến đi gồm: 1. Nếu khách hàng gọi taxi bằng điện thoại thì chúng ta sẽ có ID của khách hàng. Nếu khách hàng bắt taxi tại điểm đón thì chúng ta sẽ có ID của điểm đón. Ngược lại chúng ta sẽ không có thông tin gì cả. 2. ID của taxi. 3. Thời gian bắt đầu của chuyến đi dưới định dạng của hệ điều hành unix. Tập dữ liệu đánh giá trong cuộc thi sẽ gồm 320 hành trình mà được lấy từ 5 snapshots của mạng lưới taxi tại 5 thời gian khác nhau. Tập dữ liệu đánh giá này thực ra được chia thành 2 tập nhỏ có kích thước bằng nhau: tập dữ liệu mở và tập dữ liệu kín. Tập dữ liệu mở sẽ được sử dụng trong suốt cuộc thi để so sánh các mô hình dự đoán của các đội thi, trong khi tập dữ liệu kín sẽ chỉ được sử dụng vào lúc kết thúc cuộc thi để đánh giá các đội lần cuối. 3.2. Phương pháp của MILA lab 3.2.1 Giới thiệu chung Do cuộc thi yêu cầu dự đoán điểm đích của một chuyến taxi dựa trên một số lượng điểm đầu (prefix) của cuộc hành trình, mà tập dữ liệu cho trước lại bao gồm tập đầy đủ các điểm của chuyến taxi, nên MILAB phải thực hiện tạo ra tập điểm đầu. Tập dữ liệu huấn luyện có trên 1.7 triệu hành trình hoàn thiện, các hành trình này cho ra 83.480.696 điểm có thể là điểm đầu. Do đó MILA lab sẽ cho tất cả các điểm trong tất cả các hành trình vào tập huấn luyện làm điểm đầu, như vậy phân phối (distribution) điểm đầu trong tập MILA lab sinh ra để huấn luyện sẽ giống với tập dữ liệu đánh giá [1]. Với mô hình chiến thắng cuộc thi, MILA lab đã sử dụng chỉ một tầng ẩn gồm 500 nơron ReLU [9]. 3.2.2. Tầng vào của mạng nơron Do số lượng điểm trong các chuyến taxi là khác nhau, điều này lại không phù hợp với mạng nơron nhân tạo truyền thẳng nhiều tầng, nơi mà tầng vào phải có kích thước cố định. Để giải quyết vấn đề này MILA lab quyết định chỉ lấy k điểm đầu tiên và k điểm cuối cùng của hành trình. Với mô hình chiến thắng, họ sử dụng k = 5. Khi số lượng điểm trong một hành trình ít hơn 2k điểm thì k điểm đầu 6 sẽ bị trùng một phần với k điểm sau. Còn khi số lượng điểm nhỏ hơn k thì ta sẽ thực hiện lặp lại điểm đầu hoặc điểm cuối [1]. Với thông tin meta là loại thông tin rời rạc gồm: ID của khách hàng, ID của taxi, thời gian, MILA lab thực hiện nhúng vào mô hình. Danh sách chi tiết các thông tin được nhúng được thể hiện ở bảng 3.1 sau [1]. Thông tin meta Số giá trị có thể Kích thước nhúng ID khách hàng 57106 10 ID taxi 448 10 ID điểm đón 64 10 Một phần tư giờ trong này 96 10 Ngày thứ mấy trong tuần 7 10 Tuần thứ mấy trong năm 52 10 Bảng 3.1. Thông tin meta chi tiết 3.2.3. Tầng ra của mạng nơron Cuộc thi chỉ yêu cầu tìm ra điểm đích của chuyến hành trình, tức chỉ gồm hai giá trị số kinh độ và vĩ độ, nhưng MILA lab thấy rằng việc huấn luyện một mô hình đơn giản như vậy, mà điểm đích lại không nằm trong bất kỳ một tập dữ liệu nào là rất khó. Vì vậy MILA lab quyết định tìm thêm thông tin về tập đích đến: thay vì dự đoán trực tiếp vị trí đích, họ sẽ sinh ra tập ci gồm vài nghìn tâm của các mạng lưới các điểm đích (gọi là một cụm, một cluster). Từ đó sẽ có một tầng ẩn thực hiện liên kết một giá trị vô hướng giống như xác suất pi với mỗi cụm. Do mạng nơron phải sinh ra một điểm đích y ̂ duy nhất nên ta sẽ thực hiện tính giá trị trung bình của tập tâm cụm đã sinh ra [1]: ŷ = ∑ 𝑝𝑖𝑐𝑖 𝐶 𝑖=1 Về bản chất việc tính giá trị trung bình này giống như một tầng ra tuyến tính mà ma trận trọng số sẽ được khởi tạo như là những tâm cụm và liên lục cập nhật trong suốt quá trình học. Đương nhiên tổng các giá trị ẩn pi phải bằng 1 để đảm bảo điểm y ̂ sẽ là tương ứng với xác suất của các tâm cụm, do đó MILA lab sử dụng tầng softmax để tính giá trị này: pi = exp(𝑒𝑖) ∑ exp(𝑒𝑗) 𝐶 𝑗=1 trong đó (ej)j là giá trị đầu ra của tầng trước. Các cụm ci được sinh ra bằng thuật toán mean-shift trên tất cả các hành trình có trong tập huấn luyện, và cuối cùng cho ra tập C chứa 3392 cụm. Tổng quát lại mô hình mạng nơron nhân tạo truyền thẳng nhiều tầng sử dụng trong cuộc thi của MILA lab được mô tả ở hình sau [1]: 7 dự đoán điểm đích 3.2.4. Thuật toán huấn luyện Để đo độ chính xác giữa các đội thi, công thức tính khoảng cách giữa hai điểm Haversine sẽ được áp dụng (với lox, lax lần lượi là kinh độ, vĩ độ của điểm x, R là bán kính của trái đất): dhaversine(x,y) = 2R arctan(√ 𝑎(𝑥,𝑦) 𝑎(𝑥,𝑦)−1 ) Trong đó: a(x,y) = sin2 ( 𝑙𝑎𝑦 − 𝑙𝑎𝑥 2 ) + cos(lax) cos(lay) sin2( 𝑙𝑜𝑦 − 𝑙𝑜𝑥 2 ) Nhưng mô hình của MILA lab lại không cho kết quả tốt khi huấn luyện trực tiếp với khoảng cách Haversine này, do đó họ đã sử dụng một công thức tính khoảng cách equirectanglular đơn giản hơn, mà hoàn toàn phù hợp với quy mô của thành phố Porto như sau [1]: deqrec(x,y) = R√(𝑙𝑜𝑦 − 𝑙𝑜𝑥) cos( 𝑙𝑎𝑦− 𝑙𝑎𝑥 2 ))2 + (𝑙𝑎𝑦 − 𝑙𝑎𝑥)2 3.2.5 Nhược điểm Mô hình này cho độ sai lệch 2.035km khi được đánh giá với tập dữ liệu kín của cuộc thi, trong khi độ lệch trung bình của các đội thi là 3.11km [1]. Bên cạnh đó, khi nghiên cứu kỹ phương pháp của MILA lab, chúng ta có thể thấy một số nhược điểm sau đây: Tầng ẩn (pi)i (ei)i Thông tin sẽ được nhúng Thời gian, id khách, Thông tin meta Chuỗi các điểm Hình 3.1 Kiến trúc của mạng nơron MILA lab centroid softmax y ̂ = ∑ 𝑝𝑖𝑐𝑖 𝐶 𝑖=1 Cụm (ci)1≤i≤c 8  Dữ liệu mà cuộc thi đưa ra đã không được tiền xử lý trước khi đưa vào mạng nơron nhân tạo. Các điểm dữ liệu GPS bị thiếu, thời gian bắt đầu chuyến taxi bị sai (một số chuyến taxi có thời gian chạy hơn 5 tiếng mà chỉ có vài điểm GPS), quỹ đạo chuyến đi không thực tế khi có một điểm ngược với hành trình đang đi [8]. Đồng thời điều này cũng cho thấy độ thích nghi tốt với dữ liệu thực tế của mô hình MILA lab sử dụng.  Khi chạy với dữ liệu cuộc thi, mô hình của MILA lab cho độ sai lệch là 2.035 km. Mặc dù đây là kết quả tốt nhất trong các đội thi nhưng ta có thể thấy độ sai lệch này còn cao. Chúng ta kỳ vọng một sự cải tiến với mô hình MILA lab để mang đến độ sai lệch dưới 2 km.  Trong mô hình mạng nơron nhân tạo của MILA lab, để thỏa mãn yêu cầu của mạng nơron nhân tạo nhiều tầng truyền thẳng là số đầu vào phải cố định, họ đã chọn chỉ sử dụng năm điểm đầu và năm điểm cuối để huấn luận mạng. Liệu một giá trị khác có giúp tăng độ chính xác khi dự đoán của mô hình mạng nơron nhân tạo này. 3.3. Bài toán tìm số lượng đầu vào tối ưu 3.3.1 Phát biểu bài toán Để giải quyết nhược điểm của mô hình mạng nơron nhân tạo của MILA lab khi lựa chọn chỉ 5 điểm đầu và 5 điểm cuối của chuyến taxi để đưa vào mạng nơron huấn luyện, để trả lời cho câu hỏi liệu con số 5 đã là tốt, tôi xin đề xuất bài toán tìm giá trị số lượng này tối ưu (ta gọi tham số này là k). Tôi tin tưởng rằng đây là một tham số quan trọng cần được tinh chỉnh để mang lại kết quả dự đoán tốt hơn. Kỳ vọng bài toán này sẽ tìm ra giá trị tối ưu nhất từ đó cho kết quả dự đoán chính xác hơn 10% so với kết quả hiện tại của MILA lab. Luận văn sẽ tập trung nghiên cứu bài toán tối ưu việc lựa chọn số đầu vào khi áp dụng mạng nơron nhân tạo trong bài toán dự đoán điểm đích của một chuyến taxi. Tổng quát hơn, đây chính là bài toán tìm số lượng đầu vào tối ưu cho mạng nơron truyền thẳng nhiều tầng. Bài toán này thuộc lớp bài toán tìm kiếm siêu tham số tối ưu, được cộng đồng nghiên cứu biết đến với tên gọi hyperparameter searching, hyperparameter optimization hay hyperparameter tuning. Mục tiêu của bài toán là lựa chọn một (hoặc nhiều) siêu tham số tối ưu từ tập (hoặc nhiều) siêu tham số để cho kết quả huấn luyện tốt nhất. Đầu vào của bài toán gồm: + mô hình mạng nơron nhân tạo truyền thẳng nhiều tầng của MILA lab + tập dữ liệu các chuyến taxi dùng để huấn luyện + tập dữ liệu các chuyến taxi dùng để đánh giá + khoảng giá trị tham số k, trong luận văn này k thuộc khoảng [2, 50] (chú ý k là số tự nhiên) Đầu ra của bài toán là giá trị k tối ưu trong khoảng giá trị [2, 50] đã chọn. Kết quả mong muốn của luận văn là tìm được giá trị k cho kết quả dự đoán chính xác nhất trong khoảng giá trị [2, 50]. 3.3.2 Bài toán số đầu vào cố định Nhu cầu của bài toán xuất phát từ yêu cầu mạng nơron nhân tạo truyền thẳng nhiều tầng cần vector đầu vào có kích thước cố định (fixed-length feature vector). Điều này khác với mạng nơron hồi quy (recurrent neutral network) khi cho phép số lượng đầu vào là có thể thay đổi. Trong thực tiễn, các bài toán phần lớn là có số lượng đầu vào không cố định: như bài toán chúng ta đang giải, số điểm trong chuyến hành trình taxi, mỗi chuyến taxi lại có số điểm khác nhau hay bài toán liên quan đến 9 đoạn văn, mỗi đoạn văn lại có số lượng và số loại từ khác nhau. Do đó các nhà nghiên cứu hiện đã đưa ra nhiều phương pháp để chuyển đổi số lượng đầu vào từ không cố định (variable-length input) sang số lượng đầu vào cố định. Một số phương pháp phổ biến như: túi từ (Bag of word), sử dụng vector từ (word vector), vector đoạn (paragraph vector), băm không gian đầu vào, sử dụng pool, lấy giá trị số lượng lớn nhất, trích xuất các đặc trưng. Như vậy cách giải quyết của MILA lab với bài toán dự đoán điểm đích của chuyến taxi là họ đã sử dụng phương pháp “trích xuất các đặc trưng”. MILA lab cho rằng chỉ những điểm đầu và những điểm cuối là có ảnh hưởng nhiều nhất đến việc dự đoán điểm đích của chuyến taxi nên họ chỉ sử dụng các điểm trong một chuyến taxi (bao gồm 5 điểm đầu tiên và 5 điểm kết thúc) để làm đầu vào cho mạng nơron của họ. 3.4. Các phương pháp giải quyết hiện nay 3.4.1. Tìm kiếm Grid Thuật toán đơn giản nhất có thể áp dụng để tìm siêu tham số tối ưu là tìm kiếm grid. Ý tưởng của thuật toán rất cụ thể, ta thực hiện huấn luyện mạng nơron cho tất cả các trường hợp có thể xảy ra. Với một siêu tham số, ta thực hiện huấn luyện cho tất cả các giá trị thuộc tập siêu tham số, với nhiều siêu tham số, ta thực hiện huấn huyện cho tất cả các tập siêu tham số có thể phối hợp với nhau. Sau đó, ta so sánh các kết quả để tìm kết quả tốt nhất, siêu tham số (hoặc tập các siêu tham số) cho kết quả tốt nhất chính là siêu tham số (hoặc tập các siêu tham số) tối ưu. Phương pháp tìm kiếm grid mang ý nghĩa lý thuyết nhiều hơn là thực tiễn, vì trong thực tế các bài toán cần giải quyết mà có sử dụng đến mạng nơron nhân tạo thì đều có thời gian huấn luyện mạng tính bằng ngày và số trường hợp siêu tham số có thể xảy ra là nhiều. 3.4.2. Tìm kiếm ngẫu nhiên Ý tưởng của phương pháp này giống với tìm kiếm grid, nhưng thay vì thử tất cả các trường hợp có thể, ta chỉ thực hiện trên một tập con ngẫu nhiên. Thay vì huấn luyện 1000 trường hợp, ta chỉ huấn luyện 10 trường hợp ngẫu nhiên thôi. Điều này sẽ rút ngắn thời gian thực thi xuống. Ta luôn luôn mong muốn các giá trị ngẫu nhiên mà ta sinh ra sẽ phủ đều không gian của siêu tham số, để từ đó kết quả huấn luyện sẽ mang tính chất đại diện hơn. Ta không hề mong muốn việc có hai giá trị ngẫu nhiên được sinh ra ở gần nhau. Vì vậy đã có nhiều kỹ thuật sinh ngẫu nhiên khác nhau nhằm đảm bảo việc này [13]. Phương pháp tìm kiếm ngẫu nhiên cũng mang ý nghĩa lý thuyết nhiều hơn là thực tiễn, vì trong thực tế khi giải quyết các bài toán, ta đều cần một phương pháp tin cậy để chắc chắn tìm ra siêu tham số tối ưu. 3.4.3. Dựa trên kinh nghiệm Dựa trên kinh nghiệm (heristic-based) là phương pháp dựa trên chủ nghĩa kinh nghiệm. Đầu tiên ta thực hiện huấn luyện với vài giá trị siêu tham số ngẫu nhiên. Sau đó, dựa vào các kết quả huấn luyện này, ta thực hiện việc lựa chọn siêu tham số tiếp theo sẽ huấn luyện. Siêu tham số tiếp theo này sau khi huấn luyện sẽ được đưa vào tập các siêu tham số đã huấn luyện để từ đó tìm ra siêu tham số tiếp theo. Ta tiếp tục thực hiện như vậy cho đến khi lặp lại siêu tham số đã nằm trong tập huấn luyện rồi hoặc đến khi đạt kết quả mong muốn thì dừng lại. Trong hướng này có hai phương pháp phổ biến là: tối ưu dựa trên gradient (gradient-based optimization) và tối ưu tiến hóa (evolutionary optimization). 10 Ta có thể thấy được kết quả tốt lên sau mỗi lần thay đổi siêu tham số, điều này hiển nhiên đạt được do ta đã sử dụng chủ nghĩa kinh nghiệm khi thực hiện lưu lại và phân tích kết quả phía trước, từ đó giúp ta lựa chọn các siêu tham số tiếp theo tốt hơn. Phương pháp lựa chọn siêu tham số bằng tay cũng dựa trên phương pháp này. 3.4.4. Dựa trên thống kê Dựa trên thống kê (statistic-based) là hướng nghiên cứu dựa trên xác suất và thống kê. Trong hướng đi này các nhà nghiên cứu cho rằng mối quan hệ giữa siêu tham số và kết quả huấn luyện là một hàm số mà thuộc một phân phối dữ liệu nào đó. Nhưng thực tế hàm số này là một hàm hộp đen, nó không thể được thể hiện bằng công thức. Do vậy, để có thể tìm ra giá trị siêu tham số tối ưu, các nhà nghiên cứu phải xây dựng các mô hình xấp xỉ (còn gọi là các surrogate model). Các mô hình này được xây dựng để đảm bảo mô phỏng giống nhất có thể, tính toán chính xác nhất có thể mà vẫn đảm bảm đơn giản nhất trong tính toán. Vì hàm số thể hiện mối quan hệ giữa siêu tham số và kết quả là chưa biết nên các mô hình xấp xỉ sẽ được xây dựng theo hướng hướng dữ liệu (data-driven) và từ dưới lên (bottom-up) theo hai bước chính: + Lựa chọn giá trị siêu tham số đưa vào huấn luyện dựa vào trạng thái hiện tại của mô hình xấp xỉ (như giá trị trung bình, phương sai, ). + Dựa vào cặp giá trị giữa siêu tham số và kết quả huấn luyện tương ứng, thực hiện cập nhật mô hình xấp xỉ. Hướng nghiên cứu dựa trên thống kê đang là hướng nghiên cứu gây được chú ý trong thời gian gần đây do những kết quả khả quan mà nó mang lại. Phương pháp phổ biến trong hướng này là tối ưu Bayes (Bayesian optimization) [3]. Tối ưu Bayes xây dựng một mô hình xác suất mà ánh xạ từ các siêu tham số với các kết quả cần đánh giá. Phương pháp này sẽ liên tục đánh giá các siêu tham số tiềm năng (được lấy từ mô hình hiện tại) và thực hiện cập nhật lại mô hình. Tối ưu Bayes hướng đến việc khoanh vùng được vùng các siêu tham số sẽ cho kết quả tốt [12]. 11 CHƯƠNG 4: MÔ HÌNH ĐỀ XUẤT VÀ THỰC NGHIỆM 4.1. Mô hình đề xuất Phương pháp dựa trên thống kê hiện nay được chú ý nhiều nhất do nó có thể mô tả bằng mô hình, thực hiện một cách tự động. Do đó trong luận văn này tôi xin đề xuất sử dụng một mô hình theo hướng dựa trên thống kê để giải quyết bài toán tìm số đầu vào tối ưu (gọi là tham số k) của mạng nơron nhân tạo khi sử dụng mạng nơron này trong bài toán dự đoán điểm đích của một chuyến taxi. Trong hướng dựa trên thống kê, phương pháp tối ưu Bayes nổi lên như một lựa chọn tốt và đang được sử dụng phổ biến và mô hình trình bày trong luận văn này cũng áp dụng phương pháp tối ưu Bayes. Phương pháp tối ưu Bayes sẽ gồm hai phần: mô hình xấp xỉ và hàm thu (acquisition function). Mô hình xấp xỉ có vai trò để lưu trữ và cập nhật, trích xuất các đặc trưng của mối quan hệ giữa siêu tham số và kết quả huấn luyện. Dựa trên đặc trưng mà mô hình xấp xỉ cung cấp, hàm thu thực hiện tính giá trị tối ưu tiếp theo [14]. Trong luận văn này, tôi đề xuất sử dụng Gaussion Process cho vai trò mô hình xấp xỉ và Expected Improvement cho vai trò hàm thu. Mô hình đề xuất được thể hiện bằng hình 4.1 sau: Hình 4.1 Mô hình sử dụng tối ưu Bayes đề xuất 4.1.1. Tối ưu Bayes Tối ưu Bayes là một thuật toán dựa trên mô hình để giải quyết các bài toán tối ưu hộp đen (black box optimization) mà hàm mục tiêu f(x) là hàm hộp đen. Mọi thông tin về biểu thức hay đạo hàm của hàm f(x) đều không được biết. Việc tìm hiểu về hàm số này chỉ thông qua giá trị của hàm tại một số điểm x. Tối ưu Bayes thường chỉ được áp dụng cho các bài toán mà việc tính toán hàm f là phức tạp, tốn thời gian, nguồn lực. Lúc này tối ưu Bayes sẽ giúp giảm số lần phải lấy mẫu từ đó giảm số lần thực hiện hàm f [5]. Thuật toán này được gọi là Bayes vì việc lựa chọn giá trị tiếp theo được thực hiện bằng việc tính toán toàn bộ phân phối hậu nghiệm (posterior distribution) của hàm f với tập đầu vào x thông qua:  giả thiết biết trước về hàm f  xác suất để toàn bộ các giá trị x đã lấy mẫu trước xảy ra (likelihood) 4.1.2. Gaussian process Huấn luyện Gaussion Process Hàm thu giá trị k tiếp theo kết quả huấn luyện của giá trị k đặc trưng của các cặp (k, kết quả) 12 Trong các mô hình của thuật toán tối ưu Bayes, Gaussian process là một mô hình phổ biến. Ý tưởng của mô hình Gaussian process là với mỗi đầu vào x ta có một đầu ra y = f(x) mà f là một hàm biến thiên ngẫu nhiên (stochastic function) [6]. Mô hình này coi rằng với mỗi đầu vào x sẽ có tương ứng một phân phối gaussian (phân phối chuẩn) được đặc trưng bằng giá trị trung bình µ và độ lệch chuẩn σ [10]. Do đó với mỗi đầu vào x, Gaussian process sẽ định nghĩa một phân phối xác suất cho giá trị có thể của f(x). Vì giá trị trung bình µ và độ lệch chuẩn σ có thể khác nhau cho mỗi giá trị x, nên ta định nghĩa phân phối xác suất như sau: P(f(x) | x) = N(µ(x), σ2(x)) Trong đó N là một phân phối chuẩn tắc (standard normal distribution). Để ước lượng giá trị của µ(x) và σ(x), cần phải điều chỉnh mô hình Gaussian process sao cho phù hợp với dữ liệu mẫu đang có. Vì mỗi giá trị f(x) được lấy mẫu từ phân phối chuẩn nên giả sử ta có t mẫu dữ liệu như sau: f(x1), f(x2), , f(xt) thì vector [f(x1), f(x2), , f(xt)] là một mẫu từ một phân phối chuẩn nhiều chiều [4]. Phân phối chuẩn nhiều chiều này sẽ được đặc trưng bởi một vector trung bình và một ma trận hiệp phương sai. Do đó một Gaussian process là sự tổng quát của một phân phối chuẩn cho n biến, với n là số mẫu đang có. Ma trận hiệp phương sai thể hiện sự tương quan giữa các mẫu. Với giả thiết ban đầu rằng hàm f mịn (smooth) dẫn tới các mẫu mà ở gần nhau sẽ có tương quan mạnh và các mẫu ở xa nhau thì độ tương quan sẽ thấp. Ma trận hiệp phương sai sẽ được định nghĩa thông qua một hàm hiệp phương sai k(xi, xj) (còn gọi là hàm nhân, hàm kernel). Cho trước tập f(x1:t) và một tham số lấy mẫu nhiễu σ2noise (tham số nhiễu này bằng không nếu tập dữ liệu huấn luyện không có nhiễu, còn không nó sẽ có giá trị lớn hơn 0) thì Gaussian process cho giá trị x sẽ được mô tả như sau: P(f(x) | f(x1:t), x) = N(µt(x), σt2(x)) với: µt(x) = k T K-1 f(x1:t) σt2(x) = k(x,x) - kT K-1 k K = [ 𝑘(𝑥1, 𝑥1) ⋯ 𝑘(𝑥1, 𝑥𝑡) ⋮ ⋱ ⋮ 𝑘(𝑥𝑡, 𝑥1) ⋯ 𝑘(𝑥𝑡, 𝑥𝑡) ] + σ2nhiễu I k = [k(x, x1), k(x, x2), ., k(x, xt)] I là ma trận định danh (identity matrix) có kích thước t x t Với Gaussian process có nhiều lựa chọn cho hàm nhân (hàm hiệp phương sai). Trong luận văn này ta chọn hàm Squared Exponential, hàm này được định nghĩa như sau [7]: k(xi, xj) = σf2 exp(- (𝑥𝑖− 𝑥𝑗) 2 2𝑙2 ) với σf2 và 𝑙 là hai tham số cần được cấu hình bằng tay. Tham số chiều dài 𝑙 đặc trưng cho độ mịn của hàm (thông thường tham số 𝑙 được cài đặt bằng 1 và bằng nhau cho toàn bộ giá trị x). Tham số σf2 đặc trưng cho độ biến thiên theo chiều dọc (thường được cài đặt bằng 1) 4.1.3. Hàm thu 13 Hàm thu định nghĩa tập siêu tham số cho lần huấn luyện tới của mạng nơron. Có rất nhiều hàm khác nhau có thể tính toán giá trị tốt nhất cho siêu tham số. Nhưng ở trong mô hình đề xuất này, tôi sử dụng hàm Expected Improvement. Hàm này có hai cách tính, nếu ta đang muốn tìm giá trị nhỏ nhất, ta sẽ sử dụng công thức sau: gmin(x) = max(0, ymin – ygiá trị mong muốn nhỏ nhất ) trong đó ymin là giá trị nhỏ nhất của y mà ta đã thấy và ygiá trị mong muốn nhỏ nhất là giá trị nhỏ nhất có thể. Nếu ta muốn tìm giá trị lớn nhất thì sử dụng công thức sau: gmax(x) = max(0, ygiá trị mong muốn lớn nhất - ymax) trong đó ymax là giá trị lớn nhất của y mà ta đã thấy và ygiá trị mong muốn lớn nhất là giá trị lớn nhất có thể. Trong bài toán hiện tại, chúng ta đang mong muốn sai số của việc dự đoán điểm đích là nhỏ nhất nên ta sẽ sử dụng công thức gmin(x) 4.2. Xây dựng thử nghiệm Cách thức triển khai thử nghiệm được biểu diễn ở hình 4.2 sau: 14 Sai số = 0? Hàm thu tính giá trị k mới Huấn luyện mô hình MILA Xác định giá trị k Cài đặt mô hình MILA với giá trị k Đẩy tệp dự đoán lên Kaggle website Kaggle tính sai số dự đoán Lấy sai số từ Kaggle về Sinh ra tập dữ liệu k-sai-số gồm các cặp (k, sai số) Tìm sai số nhỏ nhất trong tập k-sai-số, giá trị k tương ứng là tối ưu. k mới đã tồn tại trong tập k-sai- số? Lấy tập dữ liệu k-sai-số làm đầu vào cho Gausian process Lấy đẩu ra của Gausian process cho vào hàm thu Kết thúc Đúng Đúng Dự đoán điểm đích với tập đánh giá Bắt đầu Sai Sai Hình 4.2 Cách thức triển khai thử nghiệm Lưu kết quả dự đoán vào tệp csv 15 Trình tự triển khai mô hình như sau: + Cài đặt và chạy được mô hình của MILA lab [11] + Xác định vị trí cấu hình tham số k trong mã nguồn của MILA lab + Cài đặt thuật toán tối ưu Bayes mà cụ thể là cài đặt Gaussion Process cho vai trò mô hình xấp xỉ và Expected Improvement cho vai trò hàm thu. + Nếu giá trị k tiếp theo nằm trong tập các giá trị k đã huấn luyện thì mô hình đã hội tụ. Thực hiện dừng việc huấn luyện, tìm giá trị kết quả nhỏ nhất trong các kết quả đã huấn luyện. Giá trị tham số k tương ứng với giá trị này chính là tham số k tối ưu mà mô hình đã tìm ra. Kết thúc chương trình. + Nếu giá trị k tiếp theo không nằm trong tập các giá trị k đã huấn luyện, thực hiện huấn luyện mạng nơron với giá trị k này. + Sau khi huấn luyện xong, đưa dữ liệu đánh giá là tập các chuyến taxi vào mạng nơron nhân tạo để mạng dự đoán. Kết quả dự đoán sẽ được lưu vào tệp csv. + Thực hiện đẩy tệp kết quả csv này lên máy chủ Kaggle sẽ được trả lại giá trị sai lệch. + Kết quả sai lệch là một số thực, nếu sai lệch bằng 0, có nghĩa là đây chính là giá trị tối ưu nhất, do đó dừng chương trình, giá trị k tương ứng với kết quả này chính là giá trị tối ưu nhất. Nếu sai lệch khác 0 thì giá trị sai lệch này và giá trị k sẽ tạo thành cặp giá trị (k, sai số). + Cặp giá trị (k, sai số) mới cùng với những cặp giá trị (k, sai số) cũ tạo thành tập (k, sai số) mới. Tập này được đưa vào mô hình Gausian process để tính toán, cập nhật lại các đặc trưng. + Hàm thu sẽ sử dụng các đặc trưng lấy từ Gausian process cũng yêu cầu về độ tin cậy để tính toán giá trị k tiếp theo. + Thực hiện lặp lại quá trình trên đến khi nào kết thúc hoặc độ sai lệch đạt mức yêu cầu thì dừng lại. 4.2.1 Dữ liệu Toàn bộ dữ liệu sử dụng trong phần thực nghiệm đều được cung cấp bởi cuộc thi Kaggle và nó giống nhau cho mọi đội thi, do đó đảm bảo tính khách quan khi so sánh kết quả giữa mô hình luận văn đề xuất và MILA lab cũng như các đội thi khác. Các dữ liệu mà cuộc thi cung cấp gồm: - Tập dữ liệu tên và vị trí GPS các điểm chờ taxi nhưng ở bài toán này, ta hoàn toàn không cần sử dụng đến tập dữ liệu này, - Tập dữ liệu gồm hơn 1.7 triệu chuyến taxi hoàn chỉnh. Dữ liệu này sẽ được tách làm hai phần, một phần cho tập phê chuẩn (validation) và phần còn lại cho tập huấn luyện. Các thuộc tính trong tệp csv là: (trip_id, call_type, origin_call, origin_stand, taxi_id, timestamp, day_type, missing_data, polyline). - Tập dữ liệu đánh giá: đây là tập dữ liệu dùng để đánh giá các mô hình dự đoán. Tập dữ liệu này gồm năm tập con nhưng được cung cấp dưới một tệp định dạng CSV gồm tổng 320 chuyến taxi. 4.2.2. Công thức tính sai lệch dự đoán Mỗi đội thi cũng như mô hình luận văn thực hiện dự đoán điểm đích (dưới dạng kinh độ, vĩ độ) cho từng chuyến taxi và tổng hợp 320 điểm dự đoán này vào một tệp csv. Tệp này có 3 thuộc tính là (trip_id, latitude – vĩ độ, longitude – kinh độ). 16 Sau khi có được file csv dự đoán này, thực hiện đẩy lên website kaggle. Website này thực hiện việc tính sai số cho từng chuyến đi thông qua việc đo khoảng cách Haversine giữa điểm đích thật và kết quả dự đoán. Sau đó tính giá trị sai số trung bình cộng của tất cả các dự đoán và thông báo kết quả trung bình cộng. 4.2.3 Cài đặt thuật toán Với bài toán tìm giá trị tối ưu cho siêu tham số, ta cần xác định khoảng giá trị của siêu tham số mà ta sẽ thực hiện tìm kiếm. Do đó ta cần cài đặt khoảng giá trị của k. Hiển nhiên điểm cận dưới của k là giá trị một, nhưng do việc chỉ lấy một điểm đầu và điểm cuối để huấn luyện là không hợp lý, nên thực hiện cài giá trị nhỏ nhất của k là 2. Với cận trên của k, ta mong muốn lấy được quãng đường di chuyển được của taxi trong tối đa là 25 phút (đây là quãng thời gian hợp lý cho một chuyến taxi), nên với yêu cầu mỗi 15 giây lấy một điểm thì ta có giá trị tương ứng là 50. Do đó cận trên của k là 50. Vậy k nằm trong khoảng từ 2 đến 50. Do MILA lab sử dụng ngôn ngữ Python để cài đặt mô hình mạng nơron nhân tạo nên trong luận văn, python cũng được sử dụng để cài đặt Gaussian process và hàm thu. Để cài đặt Gaussian process, luận văn sử dụng thư viện sklearn trong đó đã có cài đặt Gaussian process: Mã nguồn 4.1 Gaussian process Với Gaussian process, ta cần đưa vào ít nhất 2 giá trị để hàm có thể hoạt động. Do đó ta có thể lấy ngẫu nhiên hai giá trị k bất kỳ để mô hình huấn luyện trước. Trong luận văn này, ta sử dụng giá trị bắt đầu của k là 5 (bằng với giá trị của MILA lab sử dụng) và giá trị thứ 2 là một giá trị ngẫu nhiên (khác 5). Lúc này tập k_train sẽ chứa 2 giá trị là 5 và một giá trị ngẫu nhiên, tập error_train sẽ chứa hai giá trị lỗi tương ứng cho 2 giá trị k này. Sau khi chạy Gaussian process thông qua hàm fit() ta sẽ có được giá trị trung bình và phương sai cho từng giá trị k trong khoảng [2, 50]. Nhưng đầu vào của hàm thu của ta nhận thông số là độ lệch chuẩn nên ta thực hiện thêm bước tính giá trị này từ phương sai. Ta định nghĩa hàm thu, cụ thể là hàm expected improvement như sau: Mã nguồn 4.2 Hàm thu from sklearn.gaussian_process import GaussianProcessRegressor noise = 0.1 rbf = ConstantKernel(1.0) * RBF(length_scale=1.0) gp = GaussianProcessRegressor(kernel=rbf, alpha=noise**2) gp.fit(k_train, error_train) error_mean, error_std = gp.predict(k_range, return_std=True) error_std = vector_2d(error_std) def expected_improvement(error_min, error_mean, error_std, k_range): # Calculate expected improvement from 95% confidence interval expected_improvement = error_min - (error_mean - 1.96 * error_std) expected_improvement[expected_improvement < 0] = 0 max_index = expected_improvement.argmax() # Select next k value next_k = k_range[max_index] return next_k 17 Hàm expected improvement xác định giá trị k tiếp theo dựa trên khoảng tin cậy 95%. Trong công thức ở mã nguồn 4.2, ta sử dụng hằng số 1.96 vì với phân phối chuẩn thì và khoảng tin cậy mong muốn là 95% thì giá trị tham số sẽ nằm phải trong khoảng (giá trị trung bình – 1.96*sai số chuẩn, giá trị trung bình + 1.96*sai số chuẩn). Toàn bộ mã nguồn của luận văn được đưa lên website github tại địa chỉ sau: https://github.com/nguyentuananh/OptimizeTaxiDestinationPredict 4.2.4 Môi trường thử nghiệm Mô hình được triển khai trên hệ thống phần cứng của dịch vụ google cloud platform, cụ thể sử dụng dịch vụ Google Computer Engine, ta thực hiện tạo máy ảo với cấu hình như sau: CPU: 2 vCPUs Broadwell 2300MHz, RAM: 5GB, GPU: 1 NVIDIA Tesla K80 12GB, SSD: 15GB Mô hình được triển khai trên hệ thống phần mềm như sau: Hệ điều hành: Ubuntu 16.04.5 LTS (GNU/Linux 4.15.0-1024-gcp x86_64), Cài đặt đầy đủ driver của NVIDIA, Sử dụng ngôn ngữ lập trình python 2.7.15, Firefox 57.0.3, Geckodriver 0.23.0, Selenium 3.14.1, Theano 1.0.3, Blocks 0.2.0, Fuel 0.2.0, H5py 2.8.0, Sklearn 0.20.0. 4.3. Kịch bản thực nghiệm Do k nằm trong khoảng [2,50], nên ta cần huấn luyện tối đa là 49 mô hình mạng nơron. Mỗi lần huấn luyện với cấu hình máy đã đưa ra ở phần 4.2 thì mất khoảng 21 giờ nên tổng thời gian cần thực hiện để huấn luyện hết các giá trị k là 43 ngày. Tổng thời gian này là có thể thực hiện được đối với luận văn này. Nếu có thể tạo nhiều máy ảo thì thời gian chờ có thể giảm xuống. Sau khi đã huấn luyện được 49 mô hình, ta có tương ứng 49 file dự đoán cho tập dữ liệu đánh giá và sau đó thực hiện lấy giá trị sai số thông qua Kaggle website cho từng trường hợp. Vì hai giá trị k mồi ban đầu cần khác nhau nên ta chỉ có 48 trường hợp tìm giá trị k tối ưu. Với mỗi cặp mồi, mô hình sẽ đi tìm giá trị k tối ưu đến khi nào sai lệch bằng 0 hoặc giá trị k đã được huấn luyện. Cuối cùng khi có 48 dãy giá trị k, ta đánh giá hiệu quả của mô hình luận văn đề xuất. 4.4. Kết quả thực nghiệm Bảng 4.1 sau thể hiện sai lệch dự đoán của mô hình mạng nơron với từng giá trị k trong khoảng [2, 50]. Giá trị k Sai số (km) Giá trị k Sai số (km) Giá trị k Sai số (km) 2 2.03574 19 2.05887 36 1.99248 3 1.96186 20 1.93285 37 2.00102 4 1.97275 21 1.9954 38 1.97844 5 2.00669 22 1.99724 39 2.19232 6 1.97495 23 1.89386 40 2.02894 7 1.93868 24 2.08459 41 2.01894 8 4.03735 25 2.07249 42 2.02387 9 270.15953 26 2.04924 43 2.08107 10 1.96785 27 1.95202 44 1.95307 18 11 1.92488 28 2.04802 45 2.04514 12 1.98391 29 1.94643 46 1.94423 13 2.06287 30 1.94861 47 2.14076 14 2.18516 31 2.07873 48 1.99676 15 6.40615 32 2.06058 49 1.99735 16 1.99129 33 2.0248 50 2.02899 17 2.05694 34 2.05073 18 3.91822 35 2.00601 Bảng 4.1 Sai lệch dự đoán của mô hình với từng giá trị k Trong cuộc thi, mô hình mạng nơron nhân tạo của MILA lab chưa được huấn luyện đủ hai triệu vòng lặp nên cho độ sai lệch là 2.03489 km. Còn trong bản kết quả của chúng ta, khi thực hiện huấn luyện mạng nơron này (vẫn với giá trị k là 5) cho đủ hai triệu vòng lặp thì độ sai lệch khi dự đoán là 2.00669 km. Kết quả này tốt hơn kết quả MILA lab công bố, điều đó cũng dễ hiểu khi mạng nơron đã được huấn luyện lâu hơn, vì vậy ta lấy con số 2.00669 km là kết quả của mô hình MILA lab với k bằng 5 để đánh giá độ tối ưu của mô hình luận văn đề xuất. Trong bảng 4.1 ta có thể thấy với k = 23, mạng nơron cho kết quả tốt nhất khi với sai lệch chỉ là 1.89386 km (bằng 94.38% so với kết quả 2.00669 của MILA lab). Giá trị tốt thứ 2 là k = 11 với sai lệch là 1.92488, bằng 95.92% so với kết quả của MILA lab). Giá trị tốt thứ 3 là k = 20 với sai lệch là 1.93285, bằng 96.32% so với kết quả của MILA lab). Trong khi đa phần các sai lệch chỉ dưới 2.2 km thì với k = 9, ta có kết quả sai lệch rất lớn lên tới 270.15953 km, điều này có thể là do dữ liệu đã không được tiền xử lý trước nên đã xảy ra ngoại lệ. Ngoài ra ta cũng có 3 giá trị của k là 8, 15 và 18 có độ sai lệch hơn 2.2 km. Trong tổng số 49 giá trị k, có 23 giá trị k cho kết quả dự đoán tốt hơn giá trị k = 5. Như vậy có thể nói giá trị k = 5 chỉ là giá trị trung bình. Giá trị này không thuộc nhóm đầu những giá trị k tối ưu. Bảng 4.2 sau thể hiện kết quả tìm kiếm các giá trị k tối ưu của mô hình luận văn đề xuất. Có 48 kết quả tương ứng với 48 cặp giá trị k ban đầu dùng để mồi. Mỗi một kết quả là một chuỗi các giá trị k mà mô hình tìm được. Hai giá trị k đầu tiên dùng để mồi sẽ nằm ở đầu dãy, do đó dãy luôn bắt đầu bằng số 5. Giá trị thứ 2 sẽ chạy lần lượt từ 2 đến 50 và bỏ qua giá trị 5 (vì trùng với giá trị đầu tiên). STT Dãy giá trị k tối ưu tìm được 1 5, 2, 50, 50, 2 5, 3, 50, 50, 3 5, 4, 50, 50 4 5, 6, 50, 50 5 5, 7, 50, 50 19 6 5, 8, 46, 27, 37, 19, 2, 50, 32, 42, 22, 4, 29, 48, 3, 21, 39, 45, 25, 3 7 5, 9, 21, 32, 43, 50, 26, 37, 16, 2, 47, 29, 40, 18, 23, 4, 35, 45, 49, 17, 30, 39, 24, 41, 22, 28, 36, 48, 31, 34, 22 8 5, 10, 50, 50 9 5, 11, 20, 29, 38, 47, 15, 24, 33, 42, 50, 2, 8, 36, 27, 44, 22, 4, 31, 40, 12, 21, 45, 49, 26, 35, 11 10 5, 12, 21, 30, 39, 48, 26, 2, 2 11 5, 13, 22, 31, 40, 49, 45, 2, 50, 2 12 5, 14, 23, 32, 41, 50, 27, 2, 2 13 5, 15, 24, 33, 42, 50, 10, 28, 38, 2, 46, 8, 20, 36, 30, 22, 12, 48, 4, 40, 11, 26, 44, 11 14 5, 16, 25, 34, 43, 50, 11, 20, 2, 2 15 5, 17, 26, 35, 44, 50, 11, 40, 2, 2 16 5, 18, 27, 36, 45, 11, 50, 31, 2, 41, 8, 23, 14, 38, 48, 25, 12, 33, 4, 43, 29, 22, 47, 39, 12 17 5, 19, 28, 37, 46, 12, 50, 2, 50 18 5, 20, 29, 38, 47, 13, 24, 2, 2 19 5, 21, 30, 39, 48, 13, 26, 2, 2 20 5, 22, 31, 40, 49, 13, 45, 2, 50, 2 21 5, 23, 14, 32, 41, 50, 27, 2, 2 22 5, 24, 14, 33, 42, 50, 19, 50 23 5, 25, 14, 34, 43, 50, 20, 9, 2, 30, 38, 47, 17, 27, 40, 22, 4, 32, 45, 15, 36, 49, 18, 28, 41, 21, 13, 3, 6, 7, 8, 10, 11, 12, 16, 19, 23, 24, 26, 29, 31, 33, 35, 37, 39, 42, 44, 46, 48, 23 24 5, 26, 14, 35, 44, 50, 20, 40, 2, 2 25 5, 27, 14, 36, 45, 21, 50, 31, 2, 2 26 5, 28, 14, 37, 46, 21, 50, 2, 2 27 5, 29, 14, 38, 47, 22, 33, 2, 2 28 5, 30, 14, 39, 48, 22, 34, 2, 2 20 29 5, 31, 14, 40, 49, 23, 19, 2, 2 30 5, 32, 14, 23, 41, 50, 27, 2, 2 31 5, 33, 14, 23, 42, 50, 28, 19, 2, 2 32 5, 34, 14, 23, 43, 50, 28, 19, 2, 2 33 5, 35, 14, 23, 44, 50, 29, 19, 2, 2 34 5, 36, 14, 23, 45, 29, 50, 19, 2, 2 35 5, 37, 14, 23, 46, 30, 19, 2, 2 36 5, 38, 14, 23, 47, 30, 19, 2, 2 37 5, 39, 14, 23, 48, 31, 19, 2, 2 38 5, 40, 14, 23, 49, 31, 19, 2, 2 39 5, 41, 14, 23, 32, 50, 27, 2, 2 40 5, 42, 14, 23, 32, 50, 37, 27, 2, 2 41 5, 43, 14, 23, 32, 50, 37, 27, 2, 2 42 5, 44, 14, 23, 32, 50, 38, 27, 2, 2 43 5, 45, 14, 23, 32, 39, 50, 2, 2 44 5, 46, 14, 23, 32, 39, 27, 2, 2 45 5, 47, 14, 23, 32, 39, 27, 2, 2 46 5, 48, 14, 23, 32, 40, 27, 2, 2 47 5, 49, 14, 23, 32, 40, 27, 2, 2 48 5, 50, 14, 23, 32, 41, 27, 2, 2 Bảng 4.2 Dãy giá trị k tối ưu tìm được Cần chú ý rằng các dãy ở bảng 4.2 có giá trị cuối là giá trị đã xuất hiện ở trong dãy. Giá trị cuối này thể hiện dãy số là hoàn thiện khi mô hình đề xuất đưa ra giá trị k đã xuất hiện ở trong dãy. Từ đó ta thấy rằng có 87.5% dãy có đội dài nhỏ hơn 10. Đây là một kết quả chấp nhận được khi mô hình cần 18.37% số giá trị k để có thể kết thúc tìm kiếm dãy tối ưu. Ta biết rằng với giá trị k bằng 23 thì kết quả dự đoán là tốt nhất. Mà trong 48 trường hợp trên, có tới 25 trường hợp giá trị k bằng 23 này được tìm thấy tương đương với tỷ lệ 52.08%. Đây là một kết quả rất tốt, cho thấy hiệu quả của mô hình luận văn đề xuất. Với tỷ lệ này, ta chỉ cần thử 2 trường 21 hợp là có thể có 1 trường hợp cho kết quả tối ưu nhất. Thậm chí có tới 21 trường hợp là giá trị k bằng 23 chỉ nằm ở vị trí thứ 4 hoặc nhỏ hơn của dãy. Điều này có nghĩa là nếu ta chỉ thực hiện tìm tối đa 4 giá trị tối ưu trong một dãy chứ không chạy đến khi dãy hoàn thiện thì tỷ lệ tìm thấy giá trị tối ưu nhất lên tới 43.75%. Đây là kết quả thực sự tốt. Sau giá trị k bằng 23 cho kết quả dự đoán tốt nhất thì giá trị k bằng 11 và 20 lần lượt giữ vị trí thứ hai và thứ ba. Nếu ta mong kết quả tìm thấy nằm trong top hai giá trị tối ưu nhất thì xác xuất tìm thấy là 60.42%. Còn nếu ta mong kết quả tìm thấy nằm trong top ba giá trị tối ưu nhất thì xác xuất lên tới 64.58%. Vậy kết quả thực nghiệm đã cho thấy mô hình luận văn đề xuất mang lại hiệu quả tốt trong việc nâng cao độ chính xác của mạng nơron nhân tạo mà MILA lab sử dụng khi dự đoán điểm đích của chuyến taxi. 22 KẾT LUẬN * Kết luận Với xu hướng ứng dụng thiết bị di động vào ngành taxi như hiện nay, cùng các hình thức vận chuyển hành khách mới theo mô hình nền kinh tế chia sẻ đang là những thách thức rất lớn cho các công ty taxi truyền thống. Họ cần nhanh chóng áp dụng xu hướng này vào vận hành trong công ty nếu không muốn bị đào thải. Không những vậy, trong kỷ nguyên công nghệ số này, công ty nào sở hữu hệ thống hiệu quả hơn sẽ chiếm ưu thế hơn trong cạnh tranh. Hệ thống điều phối taxi bằng phần mềm khi áp dụng công nghệ dự đoán điểm đích của chuyến taxi sẽ mang lại hiệu quả vượt trội so với hệ thống điều phối bằng radio truyền thống. Công ty vận tải có thể gửi yêu cầu chính xác tới từng chiếc taxi để đảm bảo giảm thời gian chờ xe của khách hàng xuống thấp nhất, đặc biệt trong khung giờ cao điểm. Từ đó giúp nâng cao trải nghiệm của khách hàng. Việc áp dụng công nghệ này không chỉ giúp phục vụ khách hàng tốt hơn mà còn giúp công ty giảm chi phí vận hành, tối ưu nguồn lực, đồng thời còn có tác động tới những vấn đề vĩ mô của xã hội như giảm ùn tắc giao thông, giảm ô nhiễm môi trường. Với nhu cầu thực tiễn trên, cùng kỳ vọng nâng cao độ chính xác khi dự đoán điểm đích của chuyến taxi, luận văn đã trình bày cụ thể một mô hình đề xuất để tối ưu việc lựa chọn số đầu vào khi áp dụng mạng nơron nhân tạo trong bài toán dự đoán điểm đích của một chuyến taxi. Kết quả thực nghiệm của mô hình đã cho thấy hiệu quả rõ rệt khi xác suất tìm ra giá trị số lượng đầu vào tối ưu nhất là hơn 50%. Điều này cho thấy việc sử dụng tối ưu Bayes, cụ thể là Gaussion Process và hàm thu (acquisition function), đã cho thấy sự đúng đắn. Mô hình luận văn đề xuất hoàn toàn có thể sử dụng trong thực tiễn. Khi áp dụng vào bài toán thực tế, các công ty vận tải sau một thời gian sử dụng hệ thống dự đoán điểm đích của chuyến taxi hoàn toàn có thể sử dụng mô hình luận văn đề xuất để cập nhật lại số lượng đầu vào của mạng nơron (tham số k). Từ đó đảm bảo sai số nhỏ nhất trong việc dự đoán vì theo thời gian lịch trình di chuyển của khách hàng cũng thay đổi theo nên có thể giá trị tối ưu nhất của tham số k cũng thay đổi. Mô hình của luận văn đề xuất mang đến sự chính xác và tự động khi tìm kiếm giá trị tham số k tối ưu trong khoảng giá trị mong muốn. Dù đã có những kết quả tốt trong thực nghiệm nhưng mô hình của luận văn đề xuất mới chỉ thử nghiệm trên một tập dữ liệu taxi, và tập dữ liệu này chỉ có kích thước trung bình. Do vậy kết quả thực nghiệm cũng chưa được khách quan. Mô hình luận văn đề xuất hoàn toàn có thể áp dụng rộng cho bài toán tổng quát hơn. Bất kỳ bài toán nào mà sử dụng mạng nơron nhân tạo truyền thẳng nhiều tầng và cần lựa chọn số lượng đầu vào cho mạng nơron này thì đều có thể sử dụng mô hình để tìm ra giá trị tối ưu nhất. * Hướng phát triển Kết quả của luận văn đạt được đã mở ra nhiều hướng nghiên cứu tiếp trong tương lai. Tác giả cần thử nghiệm các mô hình đề xuất với các tập dữ liệu taxi lớn hơn, đồng thời cải thiện tốc độ tính toán để có thể cho nhiều kết quả. Từ đó việc so sánh, đánh giá, nhận xét sẽ khách quan hơn. Tác giả cũng cần thử áp dụng mô hình đề xuất với các bài toán sử dụng mạng nơron nhân tạo truyền thẳng nhiều tầng mà cũng cần lựa chọn số đầu vào tối ưu cho mạng để đánh giá mức độ phù hợp của mô hình với các dạng bài toán khác nhau. Để đánh giá sự phù hợp của mô hình với thực tiễn, tác giả cần kết hợp với một công ty taxi để thực hiện triển khai thử nghiệm mô hình này trong một khoảng thời gian nhất định. Kết quả thử nghiệm đó chính là câu trả lời chính xác nhất cho việc mô hình luận văn đề xuất có mang lại hiệu quả thực tế, có tính ứng dụng trong thực tiễn hay không. 23 TÀI LIỆU THAM KHẢO [1] Alexandre de Brébisson, Étienne Simon, Alex Auvolat, Pascal Vincent, Yoshua Bengio (September 21, 2015), “Artificial Neural Networks Applied to Taxi Destination Prediction”, arXiv:1508.00021v2 [cs.LG] [2] Hopfield, John J (1988), "Artificial neural networks." IEEE Circuits and Devices Magazine 4.5, pp. 3-10. [3] Snoek, Jasper, Hugo Larochelle, and Ryan P. Adams (2012), "Practical Bayesian Optimization of machine learning algorithms.", Advances in neural information processing systems 25: 2960-2968 [4] Rasmussen, Carl Edward (2004), "Gaussian processes in machine learning.", Advanced lectures on machine learning. Springer, Berlin, Heidelberg, pp. 63-71 [5] Ryan P. Adams (2014), “A Tutorial on Bayesian Optimization for Machine Learning”, Harvard University [6] Carl Edward Rasmussen, Christopher K. I. Williams (2006), “Gaussian Processes for Machine Learning”, The MIT Press [7] Iain Murray (2008), “Introduction to Gaussian Processes” Dept. Computer Science, University of Toronto [8] Hoang Thanh Lam, Ernesto Diaz-Aviles, Alessandra Pascale, Yiannis Gkoufas, and Bei Chen (17 Sep 2015), “(Blue) Taxi Destination and Trip Time Prediction from Partial Trajectories”, arXiv:1509.05257v1 [stat.ML] [9] Alex Auvolat, Alexandre de Brébisson, Étienne Simon (July 2015), “Taxi Destination Prediction Challenge Winner Team's Report”, Github [10] Martin Krasser (March 19, 2018), “Gaussian processes”, [online], available: [11] adbreds’s Github repo, [online], available: https://github.com/adbrebs/taxi [12] resibots (2013), “Introduction to Bayesian Optimization (BO)”, [online], available: [13] neupy (December 17 2016), “Hyperparameter optimization for Neural Networks”, [online], available: [14] Martin Krasser (March 21, 2018), “Bayesian Optimization”, [online], available: https://krasserm.github.io/2018/03/21/bayesian-optimization/ [15] ECML/PKDD 15: Taxi Trajectory Prediction (I), [online], available: https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i