Những hạn chế về tính toán trong phân loại mạnh mẽ và kết quả đôi bên cùng có lợi

Tóm tắt

Chúng tôi tiếp tục nghiên cứu về sự đánh đổi thống kê/tính toán trong việc học các bộ phân loại mạnh mẽ, theo công trình gần đây của Bubeck, Lee, Price và Razenshteyn, những người đã đưa ra các ví dụ về nhiệm vụ phân loại trong đó tồn tại một bộ phân loại mạnh mẽ hiệu quả, trong chế độ nhiễu động nhỏ; một bộ phân loại không mạnh mẽ có thể được học một cách hiệu quả; nhưng rất khó để học một bộ phân loại mạnh mẽ về mặt tính toán, giả sử độ khó của việc phân tích thừa số các số lớn. Câu hỏi về việc liệu một bộ phân loại mạnh mẽ cho nhiệm vụ của họ có tồn tại trong chế độ nhiễu động lớn hay không có vẻ liên quan đến các câu hỏi mở quan trọng trong lý thuyết số tính toán. Trong công trình này, chúng tôi mở rộng công trình của họ theo ba hướng.

Đầu tiên, chúng tôi chứng minh các nhiệm vụ phân loại mà phân loại mạnh mẽ hiệu quả về mặt tính toán là không thể, ngay cả khi có các bộ phân loại mạnh mẽ không giới hạn về mặt tính toán. Đối với điều này, chúng tôi dựa vào sự tồn tại của các hàm cứng trường hợp trung bình.

Thứ hai, chúng tôi trình bày các tác vụ phân loại khó học mạnh mẽ trong chế độ nhiễu động lớn. Cụ thể, chúng tôi trình bày rằng mặc dù có một bộ phân loại hiệu quả mạnh mẽ đối với nhiễu động lớn, nhưng về mặt tính toán, rất khó để học bất kỳ bộ phân loại mạnh mẽ không tầm thường nào. Cấu trúc đầu tiên của chúng tôi dựa trên sự tồn tại của các hàm một chiều và thứ hai dựa trên độ khó của bài toán học tập tương đương với nhiễu. Trong bối cảnh sau, không chỉ có một bộ phân loại không mạnh mẽ mà còn có một thuật toán hiệu quả tạo ra các mẫu được gắn nhãn mới khi truy cập vào nhiều ví dụ đào tạo theo đa thức (được Kearns và cộng sự (1994) gọi là thế hệ).

Thứ ba, chúng tôi chỉ ra rằng bất kỳ phản ví dụ nào như vậy đều ngụ ý sự tồn tại của các nguyên hàm mật mã như các hàm một chiều. Điều này dẫn chúng ta đến một kịch bản đôi bên cùng có lợi: hoặc chúng ta có thể học một bộ phân loại mạnh mẽ hiệu quả, hoặc chúng ta có thể xây dựng các trường hợp mới của các nguyên hàm mật mã.

Xem thêm: mua tài khoản ChatGPT Plus và tài khoản ChatGPT 4 chính hãng giá rẻ với nhiều ưu đãi đặc biệt!