Thuật toán có dự đoán là một cách tiếp cận mới tận dụng những hiểu biết sâu sắc về dữ liệu mà công nghệ máy học có thể cung cấp cho dữ liệu mà các phương pháp thông thường có thể không xử lý được. Thuật toán là công cụ cơ bản của điện toán hiện đại.
Thuật toán là bộ máy bên trong đồng hồ, thực hiện các hoạt động được xác định trước trong các chương trình phức tạp hơn. Sự phổ biến khắp nơi của chúng đã giúp chúng được tinh chỉnh một cách tỉ mỉ theo thời gian. Khi nhà phát triển cần sắp xếp danh sách, họ thường sẽ sử dụng thuật toán “sắp xếp” điển hình đã được sử dụng trong nhiều thập kỷ.
Các thuật toán được hỗ trợ bởi ML với các dự đoán sẽ cải thiện các phương pháp truyền thống
Các nhà nghiên cứu đang đánh giá lại các thuật toán cơ bản theo hướng này, sử dụng học máy như một nhánh của trí tuệ nhân tạo được gọi là học máy. Kỹ thuật của họ, được gọi là thuật toán dự đoán, tận dụng những hiểu biết sâu sắc về dữ liệu mà công nghệ máy học có thể cung cấp cho dữ liệu mà các phương pháp truyền thống xử lý. Theo nghĩa thực sự, những công nghệ này đã hồi sinh hoạt động nghiên cứu thuật toán cơ bản. Ngoài ra, bạn có biết rằng các cửa hậu không thể phát hiện được có thể được triển khai trong bất kỳ thuật toán ML nào không?
“Học máy và các thuật toán truyền thống là hai cách tính toán khác nhau đáng kể và các thuật toán có khả năng dự đoán là cách kết nối hai cách này. Đó là một cách để kết hợp hai chủ đề khá khác nhau này,” giải thích Piotr Indykmột nhà khoa học máy tính tại MIT.
Sự quan tâm tăng vọt gần đây đối với phương pháp này bắt đầu bằng một giấy của Tim Kraska, một nhà khoa học máy tính tại MIT và một nhóm các nhà nghiên cứu của Google vào năm 2018. Các tác giả tuyên bố rằng học máy có thể được sử dụng để cải thiện một thuật toán nổi tiếng được gọi là bộ lọc Bloom, giúp giải quyết một vấn đề đơn giản nhưng khó khăn.
Hãy xem xét tình huống này: bạn điều hành bộ phận CNTT tại công ty của mình và bạn muốn đảm bảo rằng nhân viên của bạn đang truy cập các trang web an toàn. Bạn có thể tin rằng bạn sẽ cần phải kiểm tra mọi trang web họ truy cập dựa trên danh sách đen các trang web khét tiếng. Nếu danh sách này rộng rãi (có thể là các trang web xấu trên internet), việc xử lý nó sẽ trở nên khó khăn—bạn sẽ không thể kiểm tra từng trang web dựa trên một danh sách khổng lồ kịp thời để nó tải trước khi trang web xuất hiện.
Bộ lọc Bloom là một công cụ hữu ích để xác định nhanh chóng và chính xác xem địa chỉ hoặc URL của một trang web nhất định có nằm trong danh sách đen hay không. Nó thực hiện điều này bằng cách giảm danh sách lớn thành một danh sách nhỏ hơn với những đảm bảo nhất định.
Bộ lọc Bloom không bao giờ tạo ra kết quả âm tính giả, có nghĩa là chúng sẽ không chẩn đoán sai một trang web là nguy hiểm. Tuy nhiên, chúng có thể tạo ra kết quả dương tính giả trong một số trường hợp nhất định, vì vậy nhóm của bạn có thể không truy cập được một số trang web mà lẽ ra họ nên truy cập. Bộ lọc Bloom sử dụng tính năng nén “mất mát” để tiết kiệm dung lượng trong khi hy sinh độ chính xác. Càng nhiều bộ lọc Bloom nén dữ liệu gốc thì độ chính xác của chúng càng kém nhưng chúng càng tiết kiệm được nhiều dung lượng hơn.
Mọi trang web đều đáng báo động như nhau đối với bộ lọc Bloom cơ bản cho đến khi nó được xác minh là nằm ngoài danh sách. Tuy nhiên, không phải tất cả các trang web đều được tạo ra như nhau: do những yếu tố cụ thể như tên miền hoặc cụm từ cụ thể trong URL, một số trang web có nhiều khả năng nằm trong danh sách đen hơn những trang web khác. Mọi người hiểu điều này bằng trực giác nên bạn có thể đọc URL trước khi nhấp vào chúng để đảm bảo chúng an toàn.
Nhóm của Kraska đã tạo ra một phương pháp học máy có thể áp dụng kiểu lập luận này. Họ gọi nó là “bộ lọc Bloom đã học”, được tạo thành từ bộ lọc Bloom nhỏ cộng với mạng thần kinh tái phát (RNN). Kỹ thuật học máy này thu thập các URL có hại trông như thế nào sau khi xem hàng trăm nghìn trang web an toàn và nguy hiểm theo thời gian.
Khi RNN kiểm tra một trang web, nó sẽ hành động trước tiên và sử dụng thông tin đào tạo của mình để xác định xem trang web đó có nằm trong danh sách đen hay không. Bộ lọc Bloom đã học sẽ từ chối nó nếu RNN xác định nó có trong danh sách. Nếu RNN kết luận rằng nó không có trong danh sách, bộ lọc Bloom nhỏ bé sẽ có cơ hội tìm kiếm các trang web nén của nó một cách chính xác mà không cần suy nghĩ.
Các nhà nghiên cứu đã tiến thêm một bước nữa bằng cách đặt bộ lọc Bloom ở cuối quá trình và cho phép nó đưa ra quyết định cuối cùng. Họ đảm bảo rằng các bộ lọc Bloom đã học có thể đảm bảo không có kết quả âm tính giả bằng cách đặt chúng ở vị trí cuối cùng. Mặt khác, bộ lọc Bloom nhỏ đóng vai trò chủ yếu như một bản sao lưu, giữ cho kết quả dương tính giả ở mức tối thiểu trong khi vẫn chặn các kết quả dương tính thực sự được lọc trước bởi RNN.
Một trang web vô hại mà bộ lọc Bloom lớn hơn có thể đã phát hiện được giờ đây có thể được bộ lọc Bloom đã học chính xác hơn vượt qua. Trên thực tế, Kraska và các đồng nghiệp của ông đã phát hiện ra một phương pháp sử dụng hai cách tiếp cận nổi tiếng nhưng riêng biệt để đạt được kết quả có thể so sánh được một cách nhanh chóng và chính xác hơn.
Nhóm nghiên cứu Kraska đã chứng minh rằng phương pháp mới có hiệu quả nhưng họ không giải thích lý do tại sao. Michael Mitzenmacher, chuyên gia về bộ lọc Bloom tại Đại học Harvard, nhận thấy nghiên cứu của Kraska “sáng tạo và thú vị”.
“Họ chạy thử nghiệm và nói rằng thuật toán của họ hoạt động tốt hơn. Nhưng chính xác điều đó có nghĩa là gì? Làm sao chúng tôi biết được,” ông nói thêm.
Năm 2019, Mitzenmacher đề xuất một định nghĩa chính xác về bộ lọc Bloom và nghiên cứu các tính chất toán học của nó, đưa ra lý thuyết giải thích cách thức hoạt động của nó. Và trong khi nhóm của Kraska chứng minh rằng nó có thể hoạt động trong một tình huống thì Mitzenmacher đã chứng minh rằng nó luôn có thể làm như vậy.
Mitzenmacher cũng cải tiến bộ lọc Bloom đã được phát triển trước đó. Ông đã chứng minh rằng việc kết hợp bộ lọc Bloom tiêu chuẩn thứ hai vào quy trình, lần này là trước RNN, có thể lọc trước các trường hợp không mong muốn và đơn giản hóa việc phân loại. Sau đó, ông cho thấy nó có hiệu quả bằng cách sử dụng phương pháp lý thuyết của mình.
Lộ trình của các thuật toán với các dự đoán trong những ngày đầu cũng tương tự như vậy — những ý tưởng đột phá, chẳng hạn như bộ lọc Bloom, đã khơi dậy sự hiểu biết và nghiên cứu toán học nghiêm ngặt, dẫn đến nhiều khám phá hơn nữa. Các nhà nghiên cứu đã chỉ ra cách tích hợp các thuật toán với các dự đoán vào thuật toán lập kế hoạch, thiết kế chipVà trình tự DNA tìm kiếm trong vài năm qua.
Bên cạnh những lợi thế về hiệu suất, lĩnh vực này còn giúp phát triển một phương pháp khoa học máy tính ngày càng phổ biến: tạo ra các thuật toán hiệu quả hơn bằng cách tối ưu hóa chúng cho các ứng dụng phổ biến.
Hiện tại, các nhà khoa học máy tính thường xây dựng thuật toán của họ để tồn tại trong trường hợp khó khăn nhất có thể, được tạo ra bởi kẻ tấn công muốn phá hoại chúng. Giả sử bạn đang cố kiểm tra tính bảo mật của một trang web về virus máy tính. Trang web có thể an toàn nhưng có từ “vi-rút máy tính” trong URL và tiêu đề trang. Ngay cả những thuật toán phức tạp cũng có thể bị nhầm lẫn bởi sự mơ hồ như vậy.
Theo Indyk, đây là một cách tiếp cận hoang tưởng. Ông nói: “Trong đời thực, thông tin đầu vào thường không do đối thủ tạo ra.
Các trang web dành riêng cho nhân viên khó phân loại hơn nhiều so với trang web tập trung vào bệnh tật của chúng tôi, vì vậy thuật toán sẽ phát hiện chúng đơn giản hơn. Các nhà nghiên cứu có thể xây dựng các thuật toán phù hợp hơn với các tình huống mà họ sẽ gặp phải bằng cách bỏ qua các khả năng xảy ra trong trường hợp xấu nhất. Cơ sở dữ liệu hiện có thể xử lý tất cả dữ liệu như nhau, nhưng các thuật toán có dự đoán có thể dẫn đến cơ sở dữ liệu sắp xếp việc lưu trữ dữ liệu tùy thuộc vào nội dung và cách sử dụng dữ liệu đó.
Đây mới chỉ là bước khởi đầu, vì các thuật toán tăng cường học máy với các dự đoán thường được sử dụng theo cách khá hạn chế. Bởi vì các bộ lọc Bloom và các cấu trúc tương tự đã được thiết lập nên hầu hết các dạng mới đều bao gồm một thành phần học máy. Kraska hình dung ra một hệ thống bao gồm nhiều thành phần khác nhau, mỗi thành phần dựa trên các thuật toán tạo ra dự đoán và các tương tác của chúng được điều chỉnh bởi các thành phần tăng cường dự đoán.
Kraska cho biết: “Việc tận dụng lợi thế đó sẽ tác động đến rất nhiều lĩnh vực khác nhau.
Nếu bạn thấy thú vị khi đọc về các thuật toán có dự đoán thì cũng có những nghiên cứu đề cập đến nhu cầu năng lượng ngày càng tăng của ML, nếu bạn quan tâm đến sự phát triển của trí tuệ nhân tạo.
