Vector của chúng ta là gì, Victor?
Đề bài
Mô tả
Vector nhúng (embedding) là một công cụ phổ biến trong các hệ thống học máy. Các khái niệm phức tạp của thế giới thực (ví dụ các từ trong từ điển) được ánh xạ thành các vector số thực. Nếu phép nhúng được huấn luyện tốt, các khái niệm liên quan sẽ nằm gần nhau trong không gian vector, nên những câu hỏi như "hai từ này có đồng nghĩa không?" có thể quy về các phép kiểm tra toán học đơn giản.
Bạn được Tiệm Kem Ngày Xưa thuê xây dựng một mô hình nhúng cho các hương vị kem, để khi hết một vị, tiệm có thể gợi ý cho khách những vị liên quan. Sau bốn tháng huấn luyện phép nhúng trên sáu trung tâm dữ liệu đám mây, cuối cùng bạn đã có mô hình hương vị hoàn hảo! Bạn đã sẵn sàng cách mạng hóa ngành kem trên con phố của mình và, dám nói luôn, cả khu phố! Cho đến khi bạn vô tình làm rơi ít kem miễn phí lên bàn phím và xóa mất một nửa dữ liệu. Tiệm không đủ tiền chi tỷ rúp để huấn luyện lại mô hình, nên bạn đang gặp rắc rối.
May mắn là bạn vẫn còn nhiều kết quả huấn luyện nằm rải rác. Với một vector đã bị xóa, dữ liệu huấn luyện cho biết nó cách một số vector hương vị đã biết bao xa. Độ gần nhau của hai vector và chính là khoảng cách Euclid thông thường (tức là độ dài của vector ).
Hãy viết chương trình khôi phục một vector nhúng phù hợp với các kết quả huấn luyện.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và : là số chiều của các vector, là số kết quả huấn luyện của vector bị xóa mà bạn muốn khôi phục.
Mỗi dòng trong dòng tiếp theo mô tả một kết quả huấn luyện bằng số thực và : là tọa độ của một vector đã biết, còn là khoảng cách Euclid từ vector đó đến vector bị xóa.
Chương trình của bạn chỉ được chấm trên các ví dụ dưới đây và trên các input được sinh theo quy trình sau. Đầu tiên chọn và . Sau đó chọn ngẫu nhiên vector input và vector output, mỗi vector có chiều; tọa độ này độc lập và phân phối đều trong đoạn . Tiếp theo tính khoảng cách Euclid từ mỗi vector input đến vector output. Cuối cùng vector output bị bỏ đi. Mọi phép tính dùng số thực dấu phẩy động độ chính xác kép (double). Các số thu được theo quy trình này xuất hiện trong input với chữ số sau dấu thập phân.
Dữ liệu ra
In ra số thực, tọa độ của một vector bất kỳ có khoảng cách đến mỗi vector huấn luyện bằng khoảng cách đã cho, với sai số tuyệt đối hoặc tương đối không quá .
Ràng buộc
- , .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 0 0 2.5 3 0 2.5 1.5 0.5 2.5 |
1.5 -2 | Điểm cách , và đúng . |
| 2 2 0 0 2 4 -4 6 |
1.414213562373 1.414213562373 | Điểm cách đúng và cách đúng . Vector cũng là một đáp án đúng. |
| 4 3 0 1 2 3 2 1 2 -1 7 5 1 0.3 3.4 1.2 3.3 |
1 2 3 4 | Có vô số đáp án, in vector nào thỏa mãn cũng được. |
Bình luận