ai-086Đọc toàn bộ đề miễn phí
Khoảng Cách Biến Dạng Thời Gian Động (Dynamic Time Warping - DTW)
D[i, j] = |xi - yj| + min(D[i-1, j], D[i, j-1], D[i-1, j-1])
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: linear-layer-and-mlp-foundations.
Nội dung đề bài
Mục tiêu kiến thức
- Khi so sánh 2 chuỗi âm thanh hoặc chuỗi thời gian có tốc độ phát âm khác nhau (ví dụ một người nói từ "hello" nhanh trong 0.5s và người khác nói chậm kéo dài 1.2s), khoảng cách Euclidean thông thường thất bại hoàn toàn vì hai chuỗi lệch pha nhau.
- Thuật toán DTW (Dynamic Time Warping):
- Cho hai chuỗi X = (x1, …, xN) và Y = (y1, …, yM).
- Ma trận chi phí tích lũy D ∈ R(N+1) × (M+1) khởi tạo bằng +∞, D[0, 0] = 0:
D[i, j] = |xi - yj| + min(D[i-1, j], D[i, j-1], D[i-1, j-1])
- Khoảng cách DTW chính là D[N, M].
- Cho phép "kéo giãn" hoặc "co ngắn" trục thời gian phi tuyến tính để tìm sự tương đồng tối đa.
Yêu cầu
Viết hàm:
def compute_dtw(s1: np.ndarray, s2: np.ndarray) -> tuple[float, list[tuple[int, int]]]:
passs1: Mảng 1D độ dài N.s2: Mảng 1D độ dài M.- Trả về tuple
(dtw_distance, warping_path): dtw_distance: Chi phí tối ưu D[N, M] (float).warping_path: Danh sách các cặp chỉ số(i, j)(0-indexed) từ(0, 0)đến(N-1, M-1)dọc theo đường đi tối ưu.
Input
- Hàm
compute_dtw(s1,s2): Các tham số đầu vào chứa dữ liệu Tensor/mảng NumPy hoặc giá trị siêu tham số tương ứng.
Output
- Hàm
compute_dtw: Trả về kết quả kiểutuple[float, list[tuple[int, int]]]theo đúng đặc tả kỹ thuật và kích thước quy định.
Ràng buộc
- Thời gian chạy tối đa: 2000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào hợp lệ theo đúng kiểu dữ liệu và miền giá trị được mô tả.
Ví dụ 1
Input
s1 = np.array([1.0, 2.0, 3.0, 4.0])
dist_same, path_same = compute_dtw(s1, s1)
s2 = np.array([1.0, 1.0, 2.0, 2.0, 3.0, 4.0])
dist_warp, _ = compute_dtw(s1, s2)Output
(0, [(0, 0), (0, 1), (1, 2), (1, 3), (2, 4), (3, 5)])Giải thích
Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.
Ví dụ 2
Input
s1 = np.array([0.0, 0.0])
s2 = np.array([2.0, 2.0])
dist, path = compute_dtw(s1, s2)Output
(4, [(0, 0), (1, 1)])Giải thích
Hàm/lớp được gọi với các tham số mẫu trên và trả về kết quả số học / kích thước tensor tương ứng theo đúng thiết kế.
3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.
Phân tích lời giảiGiải thích hướng tư duy và thuật toán.
Code tham khảoDùng để đối chiếu sau khi tự làm.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.