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

trị k cho kết quả dự đoán chính xác nhất trong khoảng giá trị [2, 50]. 19 Chúng ta cần phân biệt giữa tham số mô hình (model parameter) và siêu tham số (hyperparameter). Tham số mô hình là các giá trị của mô hình được sinh ra từ dữ liệu huấn luyện giúp thể hiện mối liên hệ giữa các đại lượng trong dữ liệu. Tham số mô hình sẽ được cập nhật trong quá trình học. Còn siêu tham số là các tham số được cấu hình khi bắt đầu thực hiện việc huấn luyện. Nó hoàn toàn nằm ngoài mô hình và không phụ thuộc và tập dữ liệu huấn luyện. Siêu tham số được sử dụng trong quá trình huấn luyện để giúp mô hình tìm ra được các tham số mô hình hợp lý nhất. Thông thường nó được lựa chọn thủ công bởi người thực hiện huấn luyện mô hình và nó có thể được định nghĩa dựa trên một vài chiến lược. Siêu tham số có thể là số lượng đầu vào của mạng nơron, chỉ số tốc độ học khi huấn luyện, số lượng tầng ẩn, 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 đ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): các từ trong đoạn văn sẽ được tách riêng biệt và đếm số lần xuất hiện, lúc này thứ tự sắp xếp các từ đã không còn, các cặp từ và số lần xuất hiện của nó trở nên vô hướng, do đó ngữ nghĩa sẽ không còn được giữ nguyên. + Sử dụng vector từ (word vector), vector đoạn (paragraph vector): đây cũng là hai phương pháp được sử dụng trong lĩnh vực xử lý ngôn ngữ tự nhiên. Với vector từ thì mỗi từ sẽ được biểu diễn bằng một vector có kích thước cố định (fixed size vector). Vector này ban đầu có thể được sinh ra ngẫu nhiên. Sau đó các vector tiếp theo sẽ được sinh ra bằng giá trị trung bình của các vector xung quanh. Điều này sẽ giúp giữ được mối liên hệ giữa các từ. Cuối cùng các 20 từ giống nhau sẽ được biểu diễn bởi các vector gần giống nhau. Phương pháp vector đoạn cũng tương tự như vậy nhưng lúc này mỗi đoạn văn sẽ có thêm một vector biểu diễn cho một đoạn văn. Khi thực hiện các tác vụ như học hay dự đoán từ bên cạnh, vector đoạn đều tham gia vào để tăng độ chính xác của thuật toán. + Băm không gian đầu vào: toàn bộ không gian đầu vào sẽ được băm để đưa về tập giá trị hữu hạn và tập này sẽ là đầu vào của mạng nơron. + Sử dụng pool: với mô hình pool, ta sẽ chia dữ liệu đầu vào ra thành nhiều tập con có kích thước giống nhau và đưa vào pool, sau đó thực hiện lấy dữ liệu lần lượt từ pool ra để đưa vào mô hình. + Lấy giá trị số lượng lớn nhất: với phương pháp này, ta thực hiện tìm giá trị số lượng lớn nhất có thể của đầu vào và cài đặt mạng nơron theo số lượng đầu vào lớn nhất này. Với trường hợp các dữ liệu mà có số đầu vào nhỏ hơn giá trị lớn nhất thì ta có thể bổ sung các giá trị còn lại bằng giá trị 0 hoặc bằng giá trị trung bình hoặc bằng giá trị cuối của dữ liệu. + Trích xuất các đặc trưng: trong tập dữ liệu đầu vào, ta thực hiện tìm các đặc trưng quan trọng ảnh hưởng tới kết quả đầu ra. Sau đó lựa chọn số lượng các đặc trưng cần trích xuất và thực hiện trích xuất tập các đặc trưng này cho tất cả các mẫu đầu vào, như vậy ta sẽ có số lượng đầu vào của mạng nơron là cố định. 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 21 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. Ưu điểm: + huấn luyện được tất cả các trường hợp có thể có của các siêu tham số, do đó đảm bảo kết quả tìm ra sẽ là kết quả tối ưu nhất. + thực hiện đơn giản. + phù hợp với bài toán có số lượng siêu tham số nhỏ hoặc mạng nơron có thể huấn luyện trong thời gian ngắn. Nhược điểm: + nếu tập siêu tham số có số lượng lớn thì thời gian chạy lâu, đôi khi là không thể thực hiện. Giả sử ta cần tối ưu 3 siêu tham số, mỗi siêu tham số ta có 10 trường hợp, như vậy có tới 1000 trường hợp. Giả sử một mạng huấn luyện mất 100 phút thì cần tới gần 3 tháng để chạy hết các trường hợp. Như vậy phương pháp này không phù hợp với các bài toán có số lượng siêu tham số lớn. + đa phần các mạng nơron cần nhiều thời gian hơn rất nhiều để huấn luyện nên phương pháp này cần được cân nhắc kỹ. + không phù hợp với các mạng nơron có thời gian huấn luyện lâu và có số lượng siêu tham số nhiề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 22 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]. Ưu điểm: + có thể sử dụng cho các bài toán mà tập siêu tham số có nhiều phần tử. + cung cấp cái nhìn tổng quan về kết quả mà tập siêu tham số mang lại. Nhược điểm: + để đạt được độ phủ mong muốn thì số lượng giá trị ngẫu nhiên sử dụng cũng cần tỷ lệ với số lượng siêu tham số có thể, do đó phương pháp này không thể sử dụng cho các bài toán mà tập siêu tham số có quá nhiều phần tử. + không đảm bảo tìm được giá trị tối ưu nhất. + cần sử dụng thêm các kỹ thuật sinh để đảm bảo độ phủ 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). 23 Tối ưu dựa trên gradient là phương pháp dựa trên độ sai lệch của các kết quả đã thử trước đó để tìm ra siêu tham số tiếp theo đưa vào huấn luyện. Đến khi nào đạt được độ hội tụ mong muốn thì dừng lại. Giả sử để lựa chọn số tầng ẩn tối ưu cho một mạng nơron, ban đầu ta chọn số tầng là 10 và cho độ chính xác là 65%. Kết quả này khá thấp nên ta quyết định tăng số tầng lên, giả sử tăng lên 110 tầng (việc tăng lên bao nhiêu là do người huấn luyện quyết định) và đạt được độ chính xác là 85%. Vậy ta có nhận xét khi số tầng tăng lên thì kết quả cũng tốt hơn, do đó ta tiếp tục tăng số tầng lên 210 và độ chính xác thu được là 88%. Lúc này dù ta đã tăng số tầng lên gần gấp đôi nhưng độ chính xác chỉ tăng 3%. Mức độ tăng này là không nhiều so với số tầng ta tăng nên mặc dù nếu tiếp tục tăng số tầng ẩn thì độ chính xác còn được nâng cao hơn, ta vẫn quyết định dừng lại ở số tầng 210. 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. Phương pháp tối ưu tiến hóa cũng hoạt động tương tự phương pháp tối ưu dựa trên gradient nhưng thay vì chỉ đánh giá một tập các siêu tham số một lần, phương pháp này thực hiện đánh giá nhiều tập các siêu tham số (các tập này ban đầu cũng được sinh ngẫu nhiên). Sau đó những tập siêu tham số cho kết quả kém nhất sẽ bị loại bỏ và thay bằng các tập mới. Các tập mới này không phải được sinh ngẫu nhiên mà được sinh ra thông qua thuật toán xuyên chéo (crossover) và biến đổi (mutation), có thể hiểu đơn giản là các tập siêu tham số mới được sinh ra dựa trên các tập siêu tham số cho kết quả tốt nhất. Ưu điểm: + không cần huấn luyện nhiều siêu tham số mà vẫn tìm ra được giá trị siêu tham số tối ưu trong mức cho phép. + phù hợp cho mọi loại bài toán Nhược điểm: 24 + giá trị tối ưu tìm thấy thường là giá trị tối ưu cục bộ, chứ không đảm bảo tìm được giá trị tối ưu nhất. + việc cài đặt thuật toán phức tạp hơn. Phương pháp dựa trên kinh nghiệm đã cho thấy sự vượt trội so với phương pháp tìm kiếm grid và tìm kiếm ngẫu nhiên. Phương pháp hoàn toàn có tính ứng dụng trong các bài toán thực tiễn. Tuy nhiên để tránh chỉ tìm được giá trị tối ưu cục bộ đôi khi ta cần phải thực hiện bước nhảy giá trị cho siêu tham số. 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ỉ. Ưu điểm: + không cần huấn luyện nhiều siêu tham số mà vẫn tìm ra được giá trị siêu tham số tối ưu trong mức cho phép. + phù hợp cho mọi loại bài toán. Nhược điểm: 25 + độ tối ưu khi tìm giá trị siêu tham số còn phụ thuộc vào việc lựa chọn mô hình xấp xỉ cùng việc tính toán giá trị siêu tham số tiếp theo sẽ đưa vào huấn luyện. + việc cài đặt thuật toán phức tạp hơn. 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]. 26 CHƯƠNG 4: MÔ HÌNH ĐỀ XUẤT VÀ THỰC NGHIỆM 4.1. Mô hình đề xuất Với bài toán tìm giá trị siêu tham số tối ưu, hiện nay có bốn hướng giải pháp chính là tìm kiếm grid, tìm kiếm ngẫu nhiên (có hoặc không có các giải pháp đảm bảo các giá trị ngẫu nhiên phủ đều không gian giá trị), dựa theo kinh nghiệm và dựa trên thống kê. Trong đó phương pháp tìm kiếm grid và tìm kiếm ngẫu nhiên không mang nhiều giá trị thực tiễn nhưng là cơ sở nền tảng quan trọng. Phương pháp dựa theo kinh nghiệm được sử dụng phổ biến do nó là nền tảng cho việc lựa chọn (tuning) giá trị siêu tham số tối ưu bằng tay. Còn 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: 27 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) Từ đó việc lựa chọn giá trị tiếp theo tùy thuộc vào việc ta muốn chọn giá trị lớn nhất hay nhỏ nhất. 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ả) 28 4.1.2. Gaussian process 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: 29 P(f(x) | f(x1:t), x) = N(µt(x), σt2(x)) với: µt(x) = kT 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 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ể. 30 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 Nhắc lại bài toán: Trong bài toán dự đoán điểm đích của một chuyến taxi, MILA lab sử dụng mạng nơron nhân tạo nhiều tầng truyền thẳng để giải quyết vấn đề. Để thực hiện training mạng nơron này, MILA lab chỉ sử dụng k điểm đầu tiên và k điểm cuối cùng của chuyến taxi làm dữ liệu đầu vào. MILA lab cài đặt k có giá trị là 5 mà không có giải thích nào, trong khi đó tham số k ảnh hưởng trực tiếp đến việc bao nhiêu dữ liệu mà mạng nơron có thể học được nên tham số này là một siêu tham số quan trọng ảnh hưởng đến độ chính xác khi dự đoán điểm đích. Do đó mô hình mà luận văn xây dựng nhằm mục đích xác định được giá trị k tối ưu đảm bảo cho sai số dự đoán là nhỏ nhất. Việc huấn luyện mạng nơron của MILA lab là cần nhiều thời gian. Với một giá trị k và cài đặt số vòng lặp là 2 triệu, thực hiện huấn luyện trên một máy tính cơ bản sẽ mất gần một ngày, nên để tối ưu thời gian chạy thì mọi bước khi thực hiện mô hình luận văn đề xuất cần phải được thực hiện liên tục, hoàn toàn tự động để đảm bảo thời gian chạy là ít nhất và cũng giảm thiểu sức lao động. Bản thân phương pháp của MILA lab cũng là phương pháp duy nhất trong các đội thi mà chạy hoàn toàn tự động, không cần thực hiện bất cứ thao tác bằng tay nào. Cách thức triển khai thử nghiệm được biểu diễn ở hình 4.2 sau: 31 Sai số = 0? Hàm thu tính giá trị k mới Xác định giá trị k Cài đặt mô hình MILA với giá trị k Huấn luyện mô hình MILA Đẩ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 32 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. + Chú ý để mô hình Gaussion Process có thể hoạt động ta cần ít nhất 2 cặp giá trị tham số k và kết quả huấn luyện tương ứng để mồi, vì mô hình hoạt động dựa trên thống kê cùng các đặc trưng như giá trị trung bình, phương sai. Kết quả huấn luyện là giá trị trung bình của tất cả các sai lệch khi dự đoán điểm đích của toàn bộ chuyến taxi. Sau khi đã có 2 cặp giá trị mồi, thực hiện tính toán giá trị k tối ưu tiếp theo. + 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 (vì kết quả là sai số nên giá trị càng nhỏ càng tốt). 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 chạy. + 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, máy chủ Kaggle sẽ trả lại giá trị sai lệch. Ta sử dụng trực tiếp tập dữ liệu đánh giá của Kaggle để đảm bảo giống với các đội thi từ đó có được so sánh khách quan. Đồng thời dữ liệu đánh giá của Kaggle là ở thời điểm một năm sau dữ liệu huấn luyện nên kết quả đánh giá sẽ mang lại ý nghĩa thực tiễn hơn so với việc tách một phần tập dữ liệu huấn luyện ra làm tập dữ liệu đánh giá. + 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ả 33 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, thu thập liên tục trong suốt một năm hoàn chỉnh (từ ngày 01/07/2013 đến ngày 30/06/2014) của 442 taxi hoạt động tại thành phố Porto thủ đô của Bồ Đào Nha. Dữ liệu này được cung cấp cho mỗi đội tham gia cuộc thi Kaggle và lưu ở định dạng file CSV. Dữ liệu này được MILA lab sử dụng trong quá trình huấn luyện mạng nơron. Do đó trong phần chạy thử nghiệm của mô hình luận văn đề xuất, dữ liệu này cũng được sử dụng để huấn luyện mạng nơron. 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). Một trường mẫu trong file CSV như sau: trip_id: T1 call_type: B origin_call: NA 34 origin_stand: 15 taxi_id: 20000542 timestamp: 1408039037 day_type: A missing_data: FALSE polyline: [ [-8.585676,41.148522], [-8.585712,41.148639], [-8.585685,41.148855], [-8.58573,41.148927], [-8.585982,41.148963],[-8.586396,41.148954], [-8.586072,41.14872],[-8.586324,41.147847], [-8.586999,41.14746],[-8.586576,41.147154], [-8.584884,41.146623] ] Một trường dữ liệu này mô tả đầy đủ thông tin cho một hành trình hoàn thiện của chuyến taxi, trong đó: + trip_id: được biểu diễn dưới dạng xâu, là một định danh duy nhất cho mỗi chuyến taxi + call_type: được biểu diễn dưới dạng ký tự, dùng để xác định kiểu gọi xe của hành khách cho chuyến taxi này. Trường này là một trong ba giá trị sau: - ‘A’: nếu chuyến taxi được điều đi từ trung tâm vận hành - ‘B’: nếu chuyến taxi được gọi trực tiếp từ điểm đón taxi - ‘C’: trong các trường hợp khác (như khách đón taxi ngay trên đường) + origin_call: được biểu diễn dưới dạng số tự nhiên, thể hiện một định danh độc nhất cho mỗi số điện thoại khách hàng đã từng phục vụ. Khi call_type là ‘A’ thì trường này sẽ có giá trị, ngược lại nó có giá trị NULL. + origin_stand: được biểu diễn dưới dạng số tự nhiên, thể hiện một định danh độc nhất cho điểm chờ taxi. Trường này sẽ là vị trí bắt đầu của chuyến đi, nếu call_type là ‘B’, ngược lại nó có giá trị NULL. 35 + taxi_id: được biểu diễn dưới dạng số tự nhiên, thể hiện một định danh độc nhất cho tài xế đang thực hiện chuyến đi + timestamp: được biểu diễn dưới dạng số tự nhiên dưới định dạng thời gian của hệ điều hành Unix, thể hiện thời gian bắt đầu của chuyến đi. + day_type: được biểu diễn dưới dạng ký tự, thể hiện loại của ngày mà chuyến taxi này đang chạy. Trường này là một trong ba giá trị sau: - ‘B’: nếu chuyến taxi chạy trong ngày lễ hoặc một ngày đặc biệt nào đó (ngày nghỉ lễ bù) - ‘C’: nếu chuyến taxi chạy trước ngày kiểu ‘B’ - ‘A’ trong những trường hợp còn lại (ngày thường, ngày cuối tuần,...) + missing_data: được biểu diễn dưới dạng boolean, mang giá trị sai (false) nếu luồng dữ liệu GPS là hoàn thiện, mang giá trị đúng (true) nếu một hoặc nhiều vị trí GPS bị mất. + polyline: được biểu diễn dưới dạng xâu, thể hiện một chuỗi các điểm GPS (dưới định dạng WGS84) mà được ánh xạ sang dạng xâu ký tự. Ký tự bắt đầu xâu là ‘[’, ký tự kết thúc xâu là ‘]’. Mỗi một cặp tọa độ cũng được thể hiện bằng một cặp ngoặc vuông như sau ‘[kinh độ, vĩ độ]’. Với mỗi 15 giây của chuyến taxi sẽ có một cặp tọa độ tương ứng. Cặp tọa độ đầu tiên là vị trí xuất phát, cặp tọa độ cuối cùng là vị trí kết thúc. - 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. Mỗi tập dữ liệu con này tương ứng với những chuyến hành trình diễn ra trong thời gian từ 01/07/2014 đến ngày 31/12/2014. Mỗi tập con sẽ cung cấp thông tin tương ứng một snapshot của mạng lưới taxi tại một thời điểm cố định. Thông tin các taxi đang chạy, những điểm đã chạy qua đều được cung cấp. Năm thời điểm tương ứng với năm tập con được lấy từ năm thời gian sau: 1. 14/08/2014 18:00:00 36 2. 30/09/2014 08:30:00 3. 06/10/2014 17:45:00 4. 01/11/2014 04:00:00 5. 21/12/2014 14:30:00 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 độ). Một ví dụ của file dự đoán này như sau: TRIP_ID LATITUDE LONGITUDE T1 41.146504 -8.611317 T2 41.146504 -8.611317 T320 41.146504 -8.611317 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. Do sau khi cuộc thi kết thúc, Kaggle cũng không công bố điểm đích của các chuyến taxi trong tập đánh giá, nên để biết được sai số dự đoán, ta vẫn cần đẩy các dự đoán lên Kaggle website. Kết quả cuối cùng này sẽ được dùng để so sánh, đánh giá xem mô hình của luận văn có giúp cải thiện độ chính xác của thuật toán do MILA lab đề xuất khô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 37 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. Để đạt được kết quả đứng đầu các đội thi, MILA lab cần thực hiện huấn luyện mạng nơron nhân tạo của mình với gần 2 triệu vòng lặp. Mặc dù đây số vòng lặp này chưa đảm bảo độ hội tụ nhưng kết quả này hiện là đủ tốt để ta thực hiện so sánh mà vẫn đảm bảo thời gian chạy hợp lý. Vậy trong mô hình đề xuất của luận văn, số vòng lặp khi thực hiện huấn luyện được cài đặt là 2 triệu. 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 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) 38 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 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 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 39 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 Do hệ thống chạy trên máy ảo nên để đảm bảo khi thoát khỏi cửa sổ terminal thì chương trình huấn luyện mạng nơron vẫn tiếp tục, ta cần sử dụng thêm phần mềm screen. 40 4.3. Kịch bản thực nghiệm Trong phần thực nghiệm, mô hình đề xuất của luận văn cần sử dụng hai giá trị mồi ban đầu. Giá trị đầu tiên ta chọn bằng 5 (bằng với giá trị MILA lab) còn giá trị thứ hai ta lựa chọn ngẫu nhiên. Nhưng việc lựa chọn ngẫu nhiên như vậy không đảm bảo tính khách quan của mô hình. Đồng thời nếu chỉ thực nghiệm trên một cặp giá trị duy nhất thì không thể đánh giá hiệu quả của mô hình chính xác được. Chúng ta cần nhiều giá trị k tối ưu mà mô hình luận văn đề xuất tìm ra, càng nhiều giá trị k tối ưu tìm thấy thì việc đánh giá hiệu quả của mô hình càng tối ưu. 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. 41 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 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 42 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). 43 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 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 44 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 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 45 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 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%. 46 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. 47 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. 48 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. 49 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: 50 [13] neupy (December 17 2016), “Hyperparameter optimization for Neural Networks”, [online], available: s.html [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 51 PHỤ LỤC Hướng dẫn cài đặt và chạy mô hình đề xuất 1. Chuẩn bị máy tính có card màn hình NVIDIA, được cài sẵn hệ điều hành Ubuntu và đầy đủ driver của NVIDIA. Sử dụng lệnh “nvidia-smi” để kiểm tra driver của NVIDIA đã được cài đặt đầy đủ. 2. Lấy dữ liệu từ Kaggle website từ link sau: https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i/data Ta sẽ có tập dữ liệu huấn luyện trong file “train.csv” và tập dữ liệu test trong file “test.csv” 3. Lấy mã nguồn của chương trình luận văn từ link sau: https://github.com/nguyentuananh/OptimizeTaxiDestinationPredict 4. Cài đặt các thư viện của python thông qua pip như sau: pip install h5py pip install fuel pip install cython pip install sklearn 5. Lấy file cài đặt miniconda từ link sau: https://repo.continuum.io/miniconda/Miniconda2-latest-Linux-x86_64.sh Chạy file “sh” này để cài miniconda. 6. Cài đặt các thư viện của python qua miniconda như sau: conda install numpy scipy mkl conda install theano pygpu 52 conda install cudnn 7. Cài đặt thư viện block, lấy file requirement từ link sau: https://raw.githubusercontent.com/mila-udem/blocks/stable/requirements.txt Cài đặt block bằng lệnh sau: pip install git+git://github.com/mila-udem/blocks.git@stable -r requirements.txt 8. Chạy file “prepare.sh” có trong mã nguồn để chuẩn bị dữ liệu cho mô hình của MILA lab. Trước khi chạy file này ta cần đặt biến môi trường TAXI_PATH bằng đường dẫn đến nơi lưu trữ dữ liệu đã lấy ở bước 2 bằng lệch export. 9. Thêm tài khoản và mật khẩu ở website Kaggle vào file “getResultKaggle.py” để thực hiện việc đẩy kết quả tự động lên Kaggle website, cụ thể ở hai dòng mã nguồn: username.send_keys("") password.send_keys("") 10. Chạy file “start.sh” thì chương trình sẽ bắt đầu chạy mô hình đề xuất. 11. Kết quả sẽ được thông báo trên màn hình console và giá trị k tối ưu sẽ được lưu ở file “koptimal”. 12. Nếu muốn khi thoát khỏi console mà chương trình vẫn huấn luyện thì ta cài đặt thư viện “screen” và dùng nó theo hướng dẫn sau: - lệnh “screen” để tạo một screen mới, sau khi tạo thì màn hình đang làm việc là ở screen mới. - detach khỏi screen dùng phím tắt “ctrl + a + d” - attach vào screen dùng lệnh “screen –r” Sau khi tạo screen thì sẽ chạy các lệnh trong này, khi muốn thoát chỉ cần detach khỏi screen mà không cần lo chương trình ngừng chạy.