فهرست مقاله
۱. ترتیبِ قاب‌ها را از ساعتِ واقعی جدا کنیم
دو دنبالهٔ ویژگی ممکن است ترتیبِ مشابهی داشته باشند، اما تعدادِ قاب‌هایشان برابر نباشد. پیش از مقایسهٔ خانه‌به‌خانه، باید تعریف کنیم کدام قاب‌ها اجازه دارند مقابلِ هم قرار بگیرند. این درس، هم‌ترازیِ پویا یا DTW را با چند عددِ ساختگی بررسی می‌کند. هر عدد فقط یک ویژگیِ اسکالر و بی‌واحد است؛ صوت، میکروفن، گفتار، مدلِ آموزش‌دیده و اندازه‌گیریِ واقعی در ورودی وجود ندارد.
واژهٔ قاب در اینجا به یک جایگاهِ مرتب اشاره دارد. نه نرخِ نمونه‌برداری تعیین کرده‌ایم و نه فاصلهٔ زمانیِ قاب‌ها را می‌دانیم؛ بنابراین شمارهٔ قاب را به ثانیه تبدیل نمی‌کنیم. تکرارِ یک شماره در مسیر یعنی همان ویژگی با چند ویژگیِ طرفِ دیگر مقایسه شده است. این کار اطلاعاتِ اندازه‌گیری‌شدهٔ تازه تولید نمی‌کند و به‌تنهایی دستورِ بازسازی یا کشیدنِ فایلِ صوتی نیست.
در درسِ مسیرِ دقیقِ ویتربی، احتمالِ مشترکِ حالت‌های پنهان و مشاهده بیشینه می‌شد. اینجا نه حالتِ پنهان داریم و نه احتمال. همچنین محاسبهٔ WER و هم‌ترازیِ واژه‌ها عملیاتِ درج، حذف و جایگزینی را می‌شمارد. اشتراکِ این روش‌ها در برنامه‌ریزیِ پویا، به معنی یکسان‌بودنِ قراردادِ مسیر یا معنای امتیاز نیست.
هدفِ مشخصِ ما، کمینه‌کردنِ مجموعِ اختلاف‌های مربعی روی یک مسیرِ سراسری است. توالیِ کوتاه‌تر می‌تواند بعضی جایگاه‌هایش را در تطبیق تکرار کند، اما ترتیبِ هر دو ورودی حفظ می‌شود. دربارهٔ تشخیصِ واژه، کیفیتِ ادراکی یا مناسب‌بودنِ ویژگی برای یک کارِ واقعی نتیجه نمی‌گیریم. این جداسازی، امکان می‌دهد خودِ محاسبه را مستقل از کاربردِ احتمالیِ آینده وارسی کنیم.
۲. هزینهٔ محلی و مسیرِ مجاز را دقیق بنویسیم
ورودی‌های x و y تاپل‌هایی با طولِ یک تا پنج‌اند. هر عضو باید دقیقاً int یا Fraction باشد؛ بولی، زیرکلاس، اعشار و رشته پذیرفته نمی‌شود. قدرِ مطلقِ مقدار حداکثر چهار است و مخرجِ ساده‌شدهٔ Fraction نباید از هشت بیشتر باشد. ورودیِ خالی را رد می‌کنیم. این حدود انتخابِ آموزشی‌اند و تعریفِ عمومیِ DTW را محدود نمی‌کنند؛ هیچ تبدیلِ بی‌صدای اعشاری یا نرمال‌سازی انجام نمی‌دهیم.
هزینهٔ محلیِ خانهٔ i و j برابر مربعِ اختلافِ x[i] و y[j] است. مسیر از خانهٔ صفر، صفر شروع می‌شود و در خانهٔ آخر، آخر پایان می‌یابد. در هر گام فقط یکی از تغییرهای یک، صفر؛ صفر، یک؛ یا یک، یک مجاز است. در نتیجه هیچ جایگاهِ ورودی جا نمی‌افتد، حرکتِ رو به عقب نداریم و یک جفتِ شاخص دوباره بازدید نمی‌شود؛ هرچند یکی از شاخص‌ها می‌تواند تکرار شود.
این تعریفِ مسیر و جمعِ هزینهٔ محلی در درسِ اصلیِ DTW از مولر و زالکو توضیح داده شده است. نمونهٔ عددیِ آن صفحه از قدرِ مطلقِ اختلاف استفاده می‌کند؛ انتخابِ مربع، شاهدها، مرزِ ورودی و کدِ کسریِ این مقاله مستقل‌اند. اینجا پنجرهٔ محدودکننده، جریمهٔ اضافیِ گام، تطبیقِ زیرتوالی یا وزنِ جداگانه برای جهت‌ها نداریم.
نامِ امتیاز باید همراهِ فرمول بیاید. در مستنداتِ رسمیِ tslearn نسخهٔ ۰٫۹٫۰، خروجیِ dtw ریشهٔ مجموعِ مربع‌هاست. برنامهٔ ما خودِ مجموع را برمی‌گرداند و ریشه نمی‌گیرد؛ پس عددِ آن را خروجیِ آن API معرفی نمی‌کنیم. ویژگی‌های این مثال بی‌واحدند؛ اگر ویژگیِ دیگری واحدِ U داشته باشد، مجموعِ مربعی واحدِ U² خواهد داشت، نه ثانیه یا درصدِ دقت.
۳. جدولِ کمینه و قاعدهٔ تساویِ مسیر
خانهٔ نخستِ جدول همان هزینهٔ محلیِ نخست است. در سطرِ نخست تنها از چپ و در ستونِ نخست تنها از بالا می‌رسیم؛ بنابراین هزینه‌ها جمع می‌شوند. برای خانهٔ داخلی، هزینهٔ همان خانه را به کوچک‌ترین مجموعِ سه پیشین اضافه می‌کنیم. هر مسیرِ رسیدن به خانه باید از یکی از همین سه پیشین بیاید؛ جایگزینیِ پیشوندِ آن با پیشوندِ ارزان‌تر، ادامهٔ مشترک را گران‌تر نمی‌کند.
به‌همراهِ مجموع، یک پیشین ذخیره می‌شود تا از انتها مسیر را برگردانیم. در تساوی، ترتیبِ ترجیحِ برنامه قطر، سپس بالا و سپس چپ است. این قاعدهٔ محلی فقط خروجی را قطعی می‌کند؛ ادعای کوچک‌ترین مسیرِ کامل در ترتیبِ واژه‌نامه‌ای نداریم. برای دو توالیِ دوخانه‌ایِ سراسر صفر، سه مسیرِ مجاز همگی هزینهٔ صفر دارند و کد مسیرِ دوخانه‌ایِ قطری را انتخاب می‌کند.
برای شاهدِ دستی، x برابر صفر، یک، دو و y برابر صفر، صفر، سه‌دوم، دو است. مسیرِ گزارش‌شده جفت‌های صفر، صفر؛ صفر، یک؛ یک، دو؛ و دو، سه را دارد. تنها اختلافِ ناصفر نیم است؛ پس هزینه یک‌چهارم می‌شود. از سوی دیگر، ویژگیِ سه‌دوم باید با یکی از صفر، یک یا دو تطبیق یابد و حداقل هزینهٔ آن یک‌چهارم است؛ این کران و همان مسیر، بهینگی را مستقل توضیح می‌دهند.
۴. کدِ کامل و مرجعِ شمارشِ مستقل
فایلِ زیر با پایتونِ ۳٫۱۴٫۵ و کتابخانهٔ استاندارد اجرا شده است. Fraction جمع و مقایسهٔ هزینه‌ها را دقیق نگه می‌دارد. تابعِ اصلی جدولِ کمینه می‌سازد؛ مرجعِ مستقل، همهٔ واژه‌های ممکنِ گام را تولید می‌کند، تنها مسیرهای منتهی به گوشهٔ آخر را نگه می‌دارد و هزینهٔ هر مسیرِ کامل را مستقیم جمع می‌کند. مرجع نه جدولِ اصلی را می‌خواند و نه تابعِ اصلی را فراخوانی می‌کند.
"""Exact bounded scalar-feature DTW; no audio or third-party dependencies."""
from fractions import Fraction as F
from itertools import product
import json
import platform
def sequence(value, name):
"""An exact tuple with 1..5 exact int/Fraction values in [-4,4]."""
if type(value) is not tuple or not 1 <= len(value) <= 5:
raise ValueError(name + '_sequence')
if any(type(v) not in (int, F) or abs(v) > 4 or
(type(v) is F and v.denominator > 8) for v in value):
raise ValueError(name + '_values')
return tuple(F(v) for v in value)
def dtw_squared(x, y):
"""Minimum SUM of squared local costs; path indexes start at zero.
Equal predecessor totals choose diagonal, then vertical, then horizontal.
This local rule is not a lexicographic rule for entire forward paths.
"""
x, y = sequence(x, 'x'), sequence(y, 'y')
n, m = len(x), len(y)
totals = [[None] * m for _ in range(n)]
parents = [[None] * m for _ in range(n)]
for i in range(n):
for j in range(m):
local = (x[i] - y[j]) ** 2
if i == 0 and j == 0:
totals[i][j] = local
continue
candidates = []
if i and j:
candidates.append((i - 1, j - 1))
if i:
candidates.append((i - 1, j))
if j:
candidates.append((i, j - 1))
# min preserves the first candidate on equal keys.
parent = min(candidates, key=lambda p: totals[p[0]][p[1]])
parents[i][j] = parent
totals[i][j] = local + totals[parent[0]][parent[1]]
cell = (n - 1, m - 1)
reverse_path = []
while cell is not None:
reverse_path.append(cell)
cell = parents[cell[0]][cell[1]]
return totals[-1][-1], tuple(reversed(reverse_path))
def exhaustive_paths(n, m):
"""Every monotone path, by complete step-word enumeration, not a DP."""
steps = ((1, 0), (0, 1), (1, 1))
for length in range(max(n, m) - 1, n + m - 1):
for word in product(steps, repeat=length):
i, j = 0, 0
path = [(i, j)]
for di, dj in word:
i, j = i + di, j + dj
if i >= n or j >= m:
break
path.append((i, j))
else:
if (i, j) == (n - 1, m - 1):
yield tuple(path)
def path_cost(x, y, path):
"""Direct complete-path sum; no accumulated totals or production calls."""
return sum(((F(x[i]) - F(y[j])) ** 2 for i, j in path), F(0))
def exhaustive_oracle(x, y):
"""Return exact minimum and all minimizing paths; valid inputs only."""
scored = [(path_cost(x, y, p), p) for p in exhaustive_paths(len(x), len(y))]
minimum = min(score for score, _ in scored)
return minimum, tuple(p for score, p in scored if score == minimum), len(scored)
def valid_path(path, n, m):
return (path[0] == (0, 0) and path[-1] == (n - 1, m - 1) and
all(0 <= i < n and 0 <= j < m for i, j in path) and
all((b[0] - a[0], b[1] - a[1]) in ((1, 0), (0, 1), (1, 1))
for a, b in zip(path, path[1:])) and
{i for i, _ in path} == set(range(n)) and
{j for _, j in path} == set(range(m)))
def rejected(x, y):
try:
dtw_squared(x, y)
except ValueError:
return True
return False
def self_check():
x, y = (0, 1, 2), (0, 0, F(3, 2), 2)
score, path = dtw_squared(x, y)
reference, optimal_paths, path_count = exhaustive_oracle(x, y)
checks = {}
checks['hand_fixture_quarter_cost_and_explicit_witness_path'] = (
score == F(1, 4) and path == ((0, 0), (0, 1), (1, 2), (2, 3)))
checks['single_cell_includes_both_endpoints_once'] = (
dtw_squared((-1,), (F(1, 2),)) == (F(9, 4), ((0, 0),)))
checks['one_row_and_one_column_include_every_local_cost'] = (
dtw_squared((1,), (0, 1, 2)) ==
(F(2), ((0, 0), (0, 1), (0, 2))) and
dtw_squared((0, 1, 2), (1,)) ==
(F(2), ((0, 0), (1, 0), (2, 0))))
checks['distinct_sequences_can_have_zero_cost_after_repetition'] = (
dtw_squared((0, 1), (0, 0, 1))[0] == 0)
tie_score, tie_path = dtw_squared((0, 0), (0, 0))
tie_reference, tied, tie_count = exhaustive_oracle((0, 0), (0, 0))
checks['three_zero_cost_paths_and_deterministic_diagonal_predecessor_tie'] = (
tie_score == tie_reference == 0 and len(tied) == tie_count == 3 and
tie_path == ((0, 0), (1, 1)) and
dtw_squared((0, 0), (0, 0)) == (tie_score, tie_path))
checks['summed_squared_score_fails_triangle_inequality_even_for_singletons'] = (
dtw_squared((0,), (2,))[0] == 4 and
dtw_squared((0,), (1,))[0] + dtw_squared((1,), (2,))[0] == 2)
family = [v for length in range(1, 4) for v in product((-1, 0, 1), repeat=length)]
oracle_ok, paths_ok, symmetric, cases = True, True, True, 0
for a in family:
for b in family:
actual_cost, actual_path = dtw_squared(a, b)
expected_cost, choices, _ = exhaustive_oracle(a, b)
oracle_ok &= actual_cost == expected_cost and actual_path in choices
paths_ok &= (valid_path(actual_path, len(a), len(b)) and
path_cost(a, b, actual_path) == actual_cost)
symmetric &= actual_cost == dtw_squared(b, a)[0]
cases += 1
checks['1521_pairs_match_all_path_oracle_in_one_family'] = bool(
oracle_ok and cases == 1521)
checks['same_family_paths_cover_inputs_and_direct_sums_equal_scores'] = bool(paths_ok)
checks['same_family_costs_are_symmetric_without_path_symmetry_promise'] = bool(symmetric)
boundary_x = (-4, F(-1, 8), 0, F(1, 8), 4)
boundary_y = (-4, -1, 0, 1, 4)
boundary_score, boundary_path = dtw_squared(boundary_x, boundary_y)
boundary_minimum, boundary_optima, boundary_count = exhaustive_oracle(boundary_x, boundary_y)
checks['five_by_five_boundary_uses_all_321_monotone_paths'] = (
boundary_count == 321 and boundary_score == boundary_minimum and
boundary_path in boundary_optima)
translated = tuple(F(v) + 1 for v in x), tuple(F(v) + 1 for v in y)
negated = tuple(-v for v in x), tuple(-v for v in y)
checks['common_translation_and_joint_sign_change_preserve_cost_and_ties'] = (
dtw_squared(*translated) == (score, path) and
dtw_squared(*negated) == (score, path))
scales = (F(-2), F(-1), F(0), F(1, 2), F(2))
checks['common_scaling_multiplies_cost_by_square'] = all(
dtw_squared(tuple(s * v for v in x), tuple(s * v for v in y))[0]
== s * s * score for s in scales)
bad_sequences = ([], (), (0,) * 6, '0', None, iter((0,)))
checks['both_sides_reject_non_tuple_empty_and_overlength_sequences'] = all(
rejected(a, (0,)) and rejected((0,), a) for a in bad_sequences)
class IntSubclass(int):
pass
class FractionSubclass(F):
pass
bad_values = (True, False, 0.0, float('nan'), float('inf'), '0', None,
F(1, 9), -5, 5, IntSubclass(1), FractionSubclass(1, 2))
checks['exact_scalar_types_value_bounds_and_reduced_denominator_bounds'] = all(
rejected((v,), (0,)) and rejected((0,), (v,)) for v in bad_values)
assert len(checks) == 14 and all(type(v) is bool for v in checks.values())
assert all(checks.values()), checks
return dict(python=platform.python_version(), dependencies='standard library only',
contract='minimum sum of squared scalar-feature differences; no final square root',
units='all synthetic feature values and summed squared costs dimensionless',
predecessor_tie_policy='diagonal, vertical, horizontal; not full-path lexicographic',
fixture=dict(x=[str(v) for v in x], y=[str(v) for v in y],
summed_squared_cost=str(score), path=path,
oracle_cost=str(reference), all_monotone_paths=path_count,
optimal_path_count=len(optimal_paths)),
zero_tie=dict(path=tie_path, all_paths=tie_count),
oracle_pair_cases=cases, boundary_paths=boundary_count,
actual_audio_or_asr_used=False, third_party_libraries_executed=False,
unique_executed_checks=len(checks), checks=checks, all_passed=all(checks.values()))
if __name__ == '__main__':
print(json.dumps(self_check(), ensure_ascii=False, indent=2))
{
"python": "3.14.5",
"dependencies": "standard library only",
"contract": "minimum sum of squared scalar-feature differences; no final square root",
"units": "all synthetic feature values and summed squared costs dimensionless",
"predecessor_tie_policy": "diagonal, vertical, horizontal; not full-path lexicographic",
"fixture": {
"x": [
"0",
"1",
"2"
],
"y": [
"0",
"0",
"3/2",
"2"
],
"summed_squared_cost": "1/4",
"path": [
[
0,
0
],
[
0,
1
],
[
1,
2
],
[
2,
3
]
],
"oracle_cost": "1/4",
"all_monotone_paths": 25,
"optimal_path_count": 1
},
"zero_tie": {
"path": [
[
0,
0
],
[
1,
1
]
],
"all_paths": 3
},
"oracle_pair_cases": 1521,
"boundary_paths": 321,
"actual_audio_or_asr_used": false,
"third_party_libraries_executed": false,
"unique_executed_checks": 14,
"checks": {
"hand_fixture_quarter_cost_and_explicit_witness_path": true,
"single_cell_includes_both_endpoints_once": true,
"one_row_and_one_column_include_every_local_cost": true,
"distinct_sequences_can_have_zero_cost_after_repetition": true,
"three_zero_cost_paths_and_deterministic_diagonal_predecessor_tie": true,
"summed_squared_score_fails_triangle_inequality_even_for_singletons": true,
"1521_pairs_match_all_path_oracle_in_one_family": true,
"same_family_paths_cover_inputs_and_direct_sums_equal_scores": true,
"same_family_costs_are_symmetric_without_path_symmetry_promise": true,
"five_by_five_boundary_uses_all_321_monotone_paths": true,
"common_translation_and_joint_sign_change_preserve_cost_and_ties": true,
"common_scaling_multiplies_cost_by_square": true,
"both_sides_reject_non_tuple_empty_and_overlength_sequences": true,
"exact_scalar_types_value_bounds_and_reduced_denominator_bounds": true
},
"all_passed": true
}خروجی شامل هزینه، مسیر، تعدادِ مسیرهای مرجع و چهارده گروهِ بررسی است. خانوادهٔ اصلی، همهٔ سی‌ونه توالیِ طولِ یک تا سه روی اعدادِ منفی‌یک، صفر و یک را با هم مقایسه می‌کند: هزاروپانصدوبیست‌ویک جفت، یک گروهِ توافق با مرجع است. گروه‌های دیگر، معتبرماندنِ مسیر، جمعِ مستقیم، تقارنِ هزینه، ورودیِ نامعتبر و قراردادهای مرزی را جدا بررسی می‌کنند؛ هر جفت یا تکرارِ حلقه آزمونِ مستقلِ تازه شمرده نمی‌شود.
شاهدِ پنج‌درپنج، هر سیصدوبیست‌ویک مسیرِ مجاز را می‌سنجد. تعدادِ خانه‌های جدول متناسب با حاصل‌ضربِ طول‌هاست، اما هزینهٔ حسابِ کسری را ثابت فرض نمی‌کنیم. مرجعِ شمارش با رشدِ طول پرهزینه می‌شود؛ سقفِ پنج برای بازبینیِ کوچک انتخاب شده است. این اجرا شاهدِ سرعت، مصرفِ حافظهٔ دستگاه، بلادرنگ‌بودن یا سازگاریِ بیتی با MATLAB، tslearn یا کتابخانهٔ دیگری نیست.
۵. چهار پرسش دربارهٔ امتیاز و محدودیت‌ها
پرسش اول: آیا هزینهٔ صفر یعنی دو توالی برابرند؟ پاسخ: خیر؛ صفر، یک و صفر، صفر، یک با تکرارِ تطبیقِ صفر، هزینهٔ صفر دارند، ولی طول و خودِ توالی‌ها متفاوت است. همچنین امتیازِ مربعیِ ما متریکِ ریاضی نیست: برای تک‌عضوی‌های صفر، یک و دو، هزینهٔ صفر تا دو چهار است، درحالی‌که جمعِ دو هزینهٔ میانی دو می‌شود؛ نابرابریِ مثلث برقرار نیست.
پرسش دوم: آیا عوض‌کردنِ دو ورودی، همان مسیر را با شاخص‌های جابه‌جا می‌دهد؟ پاسخ: کمترین هزینه متقارن است؛ مربعِ اختلاف و مجموعهٔ گام‌های مجاز با جابه‌جاییِ دو محور حفظ می‌شوند. دربارهٔ مسیر چنین تضمینی نداده‌ایم؛ در تساوی، تقدمِ بالا بر چپ با تعویضِ محورها عوض می‌شود. برای مقایسهٔ نتیجه، ابتدا هزینه و مجازبودنِ مسیر را بسنجید، سپس سیاستِ تساوی را بررسی کنید.
پرسش سوم: با تغییرِ مقیاس چه رخ می‌دهد؟ پاسخ: افزودنِ ثابتِ مشترک به هر دو ورودی، اختلاف‌ها را عوض نمی‌کند. ضربِ هر دو در s، هر هزینهٔ محلی و کمترین مجموع را در s² ضرب می‌کند؛ البته ورودی‌های جدید هم باید حدودِ قرارداد را رعایت کنند. برای s غیرصفر ترتیبِ هزینه‌ها و تساوی‌ها حفظ می‌شود؛ در صفر همهٔ هزینه‌ها صفرند و مسیرِ منتخب ممکن است عوض شود.
پرسش چهارم: آیا کم‌شدنِ این امتیاز، بهترشدنِ تبدیلِ گفتار به متن است؟ پاسخ: خیر؛ هنوز ویژگیِ صوتی، متنِ مرجع، مدل و سنجهٔ خطای واژه نداریم. امتیاز به مقیاس، طول‌ها، ویژگی و قراردادِ مسیر وابسته است؛ تقسیمِ دلخواه بر طولِ مسیر نیز مسئلهٔ بهینه‌سازیِ دیگری می‌سازد. نتیجهٔ قابل‌دفاعِ این درس فقط توافقِ محاسبهٔ کوچکِ تعریف‌شده با شمارشِ مستقلِ مسیرهاست، با منابعِ بررسی‌شده در ۲۷ مهرِ ۱۴۰۵.
منابع و مطالعهٔ بیشتر
- مولر و زالکو؛ درسِ اصلیِ مسیر و الگوریتمِ DTW
- tslearn0.9.0؛ تعریفِ امتیازِ ریشهٔ مجموعِ مربعات در dtw
بررسی منابع: ۲۷ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.
