رمزگشایی حریصانهٔ CTC با پایتون؛ blank، تکرار و مجموع احتمال مسیرها

در بازبینی خروجی یک روش گفتار به متن، گاهی برای هر قاب یک برچسب انتخاب می‌کنیم و تصور می‌کنیم محتمل‌ترین متن هم پیدا شده است. این دو پرسش یکسان نیستند. این درس با دو قاب و سه احتمالِ دست‌نویس، تفاوت را دقیق نشان می‌دهد. هیچ صوت، مدل آموزش‌دیده یا تماس واقعی نداریم؛ ورودی، جدول کوچکی است که همهٔ مسیرهای آن را می‌توان شمرد و جواب را با کسر کنترل کرد.

۱. مسیر قاب‌ها را از دنبالهٔ برچسب جدا کنیم

الفبای نمونه فقط دو برچسب a و b و یک نمادِ blank دارد. شماره‌های صفر، یک و دو را به همین ترتیب می‌دهیم. این دو حرف، آوانویسی فارسی، واژه یا فرمان نیستند. blank نیز فاصلهٔ نوشتاری، حرفِ ساکتِ مشخص یا تشخیصِ قطعی سکوت نیست؛ در نگاشتِ این درس، برچسبی به متن نهایی اضافه نمی‌کند.

مسیر، برای هر قاب دقیقاً یک انتخاب دارد؛ مثلاً دو انتخاب صفر و صفر، هنوز مسیری با طول دو هستند. دنبالهٔ خروجی می‌تواند کوتاه‌تر یا تهی باشد. مقالهٔ اصلی CTC، بخش‌های ۳٫۱ و ۳٫۲ نگاشتِ چندبه‌یک از مسیرها به دنباله‌ها و تفاوتِ رمزگشاییِ بهترین مسیر با انتخابِ بهترین دنباله را تعریف می‌کند. اعدادِ حاضر و محاسبهٔ شاهد، مثالِ تألیفیِ ما هستند.

در هر دو قاب، احتمالِ blank هشت‌بیستم، احتمالِ a هفت‌بیستم و احتمالِ b پنج‌بیستم است. هر سطر جمعِ یک دارد. برای دورماندن از ابهامِ اعشار، کد صورت‌های صحیحِ هشت، هفت و پنج را می‌گیرد و مخرج بیست را ثابت می‌داند. این‌ها شمارِ مشاهدهٔ آموزشی یا فراوانیِ اندازه‌گیری‌شده نیستند؛ فقط نمایشِ دقیقِ احتمال‌های انتخابی‌اند.

۲. تکرارِ همسایه را پیش از حذف blank جمع کنیم

نگاشت، نخست تکرارهای متوالیِ همان نماد را یکی می‌کند و سپس blank را کنار می‌گذارد. مسیر دو a مجاور، یک a می‌دهد. اما مسیر a، blank، a دو a می‌دهد، زیرا دو برچسبِ یکسان در مسیر اولیه همسایه نبوده‌اند. حذفِ blank پیش از ادغام، این فاصله را نابود می‌کند و به‌اشتباه خروجی را یک a می‌سازد.

تابع collapse آخرین نمادِ خام را نگه می‌دارد، حتی وقتی آن نماد blank است. برچسب فقط وقتی افزوده می‌شود که هم با نمادِ قبلی فرق داشته باشد و هم صفر نباشد. بنابراین blank حافظهٔ همسایگی را تغییر می‌دهد، هرچند خودش خروجی ندارد. مقایسه با آخرین حرفِ خروجی، جای نگهداریِ آخرین نمادِ مسیر را نمی‌گیرد.

مسیرِ تهی برای همین نگاشت خروجی تهی دارد؛ ولی جدولِ احتمالِ رمزگشا باید یک تا چهار قاب داشته باشد. این دو قرارداد عمداً جدا هستند. ورودیِ چندقابی با همهٔ انتخاب‌های blank نیز می‌تواند متن تهی بدهد؛ آن را خطای قالب نمی‌شماریم. از چنین خروجی‌ای هم علتِ سکوت یا خرابیِ میکروفون نتیجه نمی‌گیریم، چون اصلاً صوتی وارد نشده است.

۳. بهترین مسیر، لزوماً محتمل‌ترین دنباله نیست

در مدلِ احتمالیِ این مثال، جرمِ یک مسیر حاصل‌ضربِ احتمالِ انتخابِ هر قاب است. این همان تجزیهٔ شرطیِ مورد استفادهٔ CTC است؛ فرض نمی‌کنیم قاب‌های صوت واقعی مستقل‌اند. روشِ حریصانه در هر سطر بیشترین مقدار را می‌گیرد. برای دو سطرِ حاضر، مسیر blank، blank با احتمالِ شصت‌وچهار چهارصدم، یعنی چهاربیست‌وپنجم، به دست می‌آید و خروجی‌اش تهی است.

برای خروجیِ تک a، سه مسیر داریم: a سپس a، a سپس blank، و blank سپس a. صورتِ احتمال‌هایشان با مخرجِ چهارصد، به‌ترتیب چهل‌ونه، پنجاه‌وشش و پنجاه‌وشش است؛ جمع، صدوشصت‌ویک چهارصدم می‌شود. هر مسیر به‌تنهایی از مسیرِ حریصانه ضعیف‌تر است، ولی مجموعشان از احتمالِ خروجیِ تهی بیشتر است. این یک شاهدِ روشنِ تفاوتِ دو هدف است.

خروجیِ تک b جرمِ صد‌وپنج چهارصدم دارد. دنباله‌های ab و ba هرکدام سی‌وپنج چهارصدم دارند. این پنج خروجی، مجموعاً تمام احتمالِ نه مسیرِ دو‌قابی را پوشش می‌دهند و جمعشان یک است. بنابراین در همین جدول، محتمل‌ترین دنباله a است؛ نه خروجیِ تهیِ بهترین مسیر. نتیجه، حکمِ بدبودنِ همیشگیِ رمزگشایی حریصانه نیست.

مرجع CTCLoss در PyTorch 2.14 جمع احتمالِ هم‌ترازی‌های هدف را توضیح می‌دهد. تابعِ زیانِ آن، ورودیِ احتمالِ لگاریتمی و قراردادِ جداگانه‌ای دارد. برنامهٔ ما آن تابع، گرادیان یا آموزش شبکه را اجرا نمی‌کند؛ جدولِ کامل را فقط برای دامنه‌ای بسیار کوچک جمع می‌زند. جمعِ نماییِ مسیرها را راهکارِ مقیاس‌پذیرِ صوت بلند معرفی نمی‌کنیم.

۴. کد کامل و مرجع جمعِ همهٔ مسیرهای کوتاه

فایل ctc_greedy_collapse.py با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده است. جدول باید tuple واقعی و هر سطر tuple سه‌عضوی باشد؛ اعضا int دقیقِ صفر تا بیست و جمع سطر دقیقاً بیست‌اند. bool، شناور، رشته، بی‌نهایت، سطر نامتوازن و بیش از چهار قاب رد می‌شوند. هیچ نرمال‌سازیِ پنهان یا تبدیل خودکارِ احتمال نداریم.

"""Finite CTC greedy collapse and exact synthetic alignment-mass witness."""
from fractions import Fraction
from itertools import groupby, product
import json
import platform

DENOMINATOR = 20
MAX_FRAMES = 4
SYMBOLS = (0, 1, 2)  # blank, a, b; not an acoustic alphabet.


def checked_emissions(rows):
    if type(rows) is not tuple:
        raise TypeError("actual tuple of frame rows required")
    if not 1 <= len(rows) <= MAX_FRAMES:
        raise ValueError("one to four frames required")
    for row in rows:
        if type(row) is not tuple or len(row) != 3:
            raise ValueError("exactly three masses: blank, a, b")
        if any(type(value) is not int for value in row):
            raise TypeError("actual integer masses, no bool or coercion")
        if any(not 0 <= value <= DENOMINATOR for value in row):
            raise ValueError("mass outside zero to twenty")
        if sum(row) != DENOMINATOR:
            raise ValueError("each categorical row must sum to twenty")
    return rows


def collapse(path):
    if type(path) is not tuple:
        raise TypeError("actual tuple path required")
    if len(path) > MAX_FRAMES:
        raise ValueError("path exceeds four frames")
    if any(type(label) is not int or label not in SYMBOLS for label in path):
        raise ValueError("only actual integer symbols zero, one, two")
    output = []
    previous = None
    for label in path:
        if label != previous and label != 0:
            output.append(label)
        previous = label  # A blank resets adjacency; do not skip this assignment.
    return tuple(output)


def greedy_path(rows):
    rows = checked_emissions(rows)
    # First maximum means smallest symbol ID on a tie, including blank.
    return tuple(max(SYMBOLS, key=lambda label: row[label]) for row in rows)


def greedy_decode(rows):
    return collapse(greedy_path(rows))


def enumerated_distribution(rows):
    rows = checked_emissions(rows)
    distribution = {}
    # Independent collapse: group adjacent raw symbols, then discard blank groups.
    for path in product(SYMBOLS, repeat=len(rows)):
        mass = Fraction(1)
        for t, label in enumerate(path):
            mass *= Fraction(rows[t][label], DENOMINATOR)
        if mass == 0:
            continue
        sequence = tuple(label for label, _ in groupby(path) if label != 0)
        distribution[sequence] = distribution.get(sequence, Fraction(0)) + mass
    return distribution


def integer_state_reference(rows):
    """Different summation route: integer prefix/last-symbol states, not paths."""
    rows = checked_emissions(rows)
    states = {((), None): 1}
    for row in rows:
        following = {}
        for (prefix, previous), weight in states.items():
            for label in SYMBOLS:
                if row[label] == 0:
                    continue
                extra = () if label == 0 or label == previous else (label,)
                key = (prefix + extra, label)
                following[key] = following.get(key, 0) + weight * row[label]
        states = following
    totals = {}
    for (prefix, _), weight in states.items():
        totals[prefix] = totals.get(prefix, 0) + weight
    return {prefix: Fraction(weight, DENOMINATOR ** len(rows))
            for prefix, weight in totals.items()}


def best_sequence(distribution):
    # Internal positive-mass distributions only; lexicographic tie is own policy.
    return min(distribution, key=lambda prefix: (-distribution[prefix], prefix))


def rejected(function, value):
    try:
        function(value)
    except (ValueError, TypeError):
        return True
    return False


def run_example():
    rows = ((8, 7, 5), (8, 7, 5))
    distribution = enumerated_distribution(rows)
    expected = {(): Fraction(64, 400), (1,): Fraction(161, 400),
                (2,): Fraction(105, 400), (1, 2): Fraction(35, 400),
                (2, 1): Fraction(35, 400)}
    checks = {}
    checks["literal_repeat_blank_and_empty_paths"] = (
        collapse(()) == () and collapse((1, 1)) == (1,)
        and collapse((0, 1, 1, 0)) == (1,) and collapse((0, 0)) == ()
        and collapse((1, 2, 1)) == (1, 2, 1)
    )
    checks["blank_separates_equal_labels_and_order_matters"] = (
        collapse((1, 0, 1)) == (1, 1)
        and collapse(tuple(x for x in (1, 0, 1) if x != 0)) == (1,)
    )
    collapse_cases = 0
    for length in range(5):
        for path in product(SYMBOLS, repeat=length):
            independent = tuple(label for label, _ in groupby(path) if label != 0)
            assert collapse(path) == independent
            collapse_cases += 1
    checks["all_121_bounded_paths_against_group_reference_one_group"] = collapse_cases == 121
    checks["literal_two_frame_probability_distribution"] = distribution == expected
    path = greedy_path(rows)
    path_mass = Fraction(rows[0][path[0]] * rows[1][path[1]], 400)
    checks["greedy_best_path_differs_from_most_probable_sequence"] = (
        path == (0, 0) and path_mass == Fraction(4, 25)
        and greedy_decode(rows) == () and best_sequence(distribution) == (1,)
        and distribution[(1,)] == Fraction(161, 400) > distribution[()]
    )
    checks["tie_policy_smallest_symbol_including_blank"] = (
        greedy_path(((10, 10, 0),)) == (0,)
        and greedy_path(((0, 10, 10),)) == (1,)
        and best_sequence({(2,): Fraction(1, 2), (1,): Fraction(1, 2)}) == (1,)
    )
    checks["deterministic_zero_mass_and_blank_separated_repeat"] = (
        enumerated_distribution(((0, 20, 0), (20, 0, 0), (0, 20, 0))) == {(1, 1): Fraction(1)}
        and enumerated_distribution(((20, 0, 0),) * 4) == {(): Fraction(1)}
        and enumerated_distribution(((0, 20, 0),) * 4) == {(1,): Fraction(1)}
    )
    checks["two_equal_output_labels_impossible_in_two_frames"] = (
        distribution.get((1, 1), Fraction(0)) == 0
        and enumerated_distribution(((0, 20, 0), (20, 0, 0), (0, 20, 0)))[(1, 1)] == 1
    )
    oracle_cases = 0
    profiles = ((8, 7, 5), (0, 10, 10), (20, 0, 0), (1, 18, 1))
    for length in range(1, 5):
        for profile_ids in product(range(len(profiles)), repeat=length):
            fixture = tuple(profiles[i] for i in profile_ids)
            enumerated = enumerated_distribution(fixture)
            assert enumerated == integer_state_reference(fixture)
            assert sum(enumerated.values(), Fraction(0)) == 1
            oracle_cases += 1
    checks["340_tables_integer_state_oracle_and_total_mass_one_group"] = oracle_cases == 340
    checks["time_reversal_reverses_sequence_masses"] = (
        enumerated_distribution(((1, 18, 1), (0, 10, 10), (8, 7, 5)))
        == {tuple(reversed(k)): value for k, value in
            enumerated_distribution(((8, 7, 5), (0, 10, 10), (1, 18, 1))).items()}
    )
    swapped = tuple((row[0], row[2], row[1]) for row in rows)
    checks["consistent_nonblank_symbol_permutation_preserves_mass"] = (
        enumerated_distribution(swapped)
        == {tuple(3 - label for label in key): value for key, value in distribution.items()}
    )
    checks["frame_count_and_row_shape_bounds"] = all(rejected(greedy_decode, bad) for bad in (
        (), rows * 3, list(rows), ((8, 12),), ((8, 7, 5, 0),), ([8, 7, 5],)))
    checks["exact_integer_types_and_mass_domain"] = all(rejected(greedy_decode, bad) for bad in (
        ((True, 14, 5),), ((8.0, 7, 5),), (("8", 7, 5),), ((float("nan"), 7, 5),),
        ((float("inf"), 7, 5),), ((-1, 16, 5),), ((21, 0, 0),), ((10 ** 500, 0, 0),),
        ((8, 7, 4),), ((0, 0, 0),)))
    checks["path_symbols_lengths_and_exact_types"] = all(rejected(collapse, bad) for bad in (
        [1, 0, 1], (True,), (1.0,), ("a",), (-1,), (3,), (1,) * 5))
    individual_masses = [Fraction(rows[0][i] * rows[1][j], 400)
                         for i, j in product(SYMBOLS, repeat=2)]
    checks["greedy_path_is_maximum_individual_mass_but_not_sequence_mass"] = (
        path_mass == max(individual_masses)
        and path_mass < distribution[(1,)]
        and rows == ((8, 7, 5), (8, 7, 5))
    )
    assert all(type(value) is bool and value for value in checks.values())
    serial_distribution = [{"sequence": list(key), "probability": str(value)}
                           for key, value in sorted(distribution.items())]
    return {"python": platform.python_version(), "dependencies": "standard library only",
            "alphabet": {"0": "blank", "1": "a", "2": "b"},
            "emission_row_denominator": DENOMINATOR, "maximum_frames": MAX_FRAMES,
            "fixture_integer_rows": rows, "greedy_path": path,
            "greedy_path_probability": str(path_mass), "greedy_sequence": greedy_decode(rows),
            "exact_sequence_distribution": serial_distribution,
            "most_probable_sequence": best_sequence(distribution),
            "most_probable_sequence_mass": str(distribution[best_sequence(distribution)]),
            "collapse_path_cases_inside_one_group": collapse_cases,
            "independent_table_cases_inside_one_group": oracle_cases,
            "checks": checks, "unique_check_groups": len(checks), "all_passed": True,
            "limits": ["Conditional factorized synthetic emissions, no independence claim about real audio frames",
                       "Exact finite path sum, not scalable beam decoding or trained acoustic model",
                       "No CTCLoss, PyTorch, ASR accuracy, language model or timing execution"]}


if __name__ == "__main__":
    print(json.dumps(run_example(), ensure_ascii=False, indent=2))

مرجعِ شمارش، تمام مسیرهای سه‌نمادی را می‌سازد، احتمال را با Fraction ضرب می‌کند و گروه‌های نمادهای مجاور را مستقل از collapse پیدا می‌کند. سپس گروه‌های blank حذف می‌شوند. مسیرهای با جرم صفر در خروجیِ فرهنگِ احتمال نگه داشته نمی‌شوند؛ نبودِ یک کلید یعنی جرمِ صفر، نه ردشدنِ آن دنباله به علتِ قالبِ متن.

مسیرِ کنترلیِ دیگری، وزنِ صحیحِ حالت‌های پیشوند و آخرین نمادِ خام را قاب‌به‌قاب جمع می‌کند و فقط در پایان بر بیست به توانِ تعداد قاب تقسیم می‌کند. این مسیر، نه همهٔ مسیرها را فهرست می‌کند و نه تابعِ نگاشتِ اصلی را صدا می‌زند. الگوریتمِ آموزشیِ ماست و جایگزینِ پیاده‌سازیِ کاملِ پیشروـپسرو، جست‌وجوی پرتو یا کتابخانهٔ CTC نامیده نمی‌شود.

{
  "python": "3.14.5",
  "dependencies": "standard library only",
  "alphabet": {
    "0": "blank",
    "1": "a",
    "2": "b"
  },
  "emission_row_denominator": 20,
  "maximum_frames": 4,
  "fixture_integer_rows": [
    [
      8,
      7,
      5
    ],
    [
      8,
      7,
      5
    ]
  ],
  "greedy_path": [
    0,
    0
  ],
  "greedy_path_probability": "4/25",
  "greedy_sequence": [],
  "exact_sequence_distribution": [
    {
      "sequence": [],
      "probability": "4/25"
    },
    {
      "sequence": [
        1
      ],
      "probability": "161/400"
    },
    {
      "sequence": [
        1,
        2
      ],
      "probability": "7/80"
    },
    {
      "sequence": [
        2
      ],
      "probability": "21/80"
    },
    {
      "sequence": [
        2,
        1
      ],
      "probability": "7/80"
    }
  ],
  "most_probable_sequence": [
    1
  ],
  "most_probable_sequence_mass": "161/400",
  "collapse_path_cases_inside_one_group": 121,
  "independent_table_cases_inside_one_group": 340,
  "checks": {
    "literal_repeat_blank_and_empty_paths": true,
    "blank_separates_equal_labels_and_order_matters": true,
    "all_121_bounded_paths_against_group_reference_one_group": true,
    "literal_two_frame_probability_distribution": true,
    "greedy_best_path_differs_from_most_probable_sequence": true,
    "tie_policy_smallest_symbol_including_blank": true,
    "deterministic_zero_mass_and_blank_separated_repeat": true,
    "two_equal_output_labels_impossible_in_two_frames": true,
    "340_tables_integer_state_oracle_and_total_mass_one_group": true,
    "time_reversal_reverses_sequence_masses": true,
    "consistent_nonblank_symbol_permutation_preserves_mass": true,
    "frame_count_and_row_shape_bounds": true,
    "exact_integer_types_and_mass_domain": true,
    "path_symbols_lengths_and_exact_types": true,
    "greedy_path_is_maximum_individual_mass_but_not_sequence_mass": true
  },
  "unique_check_groups": 15,
  "all_passed": true,
  "limits": [
    "Conditional factorized synthetic emissions, no independence claim about real audio frames",
    "Exact finite path sum, not scalable beam decoding or trained acoustic model",
    "No CTCLoss, PyTorch, ASR accuracy, language model or timing execution"
  ]
}

پانزده گروهِ نام‌دار گذشتند. تمام ۱۲۱ مسیر از طول صفر تا چهار در یک گروه، و ۳۴۰ جدولِ ساخته‌شده از چهار سطرِ مشخص در یک گروهِ دیگر بررسی شدند. زیرحالت‌ها و اجرای دوباره، بررسیِ مستقلِ تازه نمی‌سازند. جوابِ دستیِ پنج احتمال، ترتیبِ حذف، تساوی، مرزِ طول، نوع‌ها، تغییرِ نامِ برچسب‌ها و وارونگیِ ترتیب قاب‌ها نیز شاهدهای جدا دارند.

۵. چهار پرسش و مرزِ نتیجه برای گفتار واقعی

پرسش اول: مسیر a، blank، a چه می‌دهد؟ پاسخ: دو a؛ blank ابتدا مانعِ همسایگی است و بعد حذف می‌شود. اگر آن را پیش‌تر پاک کنیم، دو a مجاور و سپس یکی می‌شوند؛ این ترتیبِ نادرست را کد عمداً به‌عنوان شاهد مقایسه می‌کند.

پرسش دوم: چرا خروجی a از مسیرِ حریصانه محتمل‌تر است؟ پاسخ: سه مسیرِ متفاوت به آن می‌رسند و مجموعِ صدوشصت‌ویک چهارصدم از شصت‌وچهار چهارصدم بیشتر است. انتخابِ بیشترین احتمالِ یک مسیر، جمعِ جرمِ مسیرهای هم‌خروجی را محاسبه نمی‌کند.

پرسش سوم: آیا دو قاب برای خروجی aa کافی است؟ پاسخ: در همین الفبا و نگاشت، خیر؛ مسیر aa به a جمع می‌شود. سه قابِ a، blank، a کافی است. پس کوتاه‌ترنبودنِ ورودی نسبت به هدف، به‌تنهایی وجودِ هم‌ترازی برای برچسب‌های تکراری را تضمین نمی‌کند.

پرسش چهارم: در تساوی احتمال چه می‌کنیم؟ پاسخ: انتخابِ قاب، شناسهٔ کوچک‌تر را می‌گیرد؛ پس تساویِ blank و a به blank می‌رسد. برای تساویِ جرمِ دنباله‌ها، ترتیبِ واژگانیِ تاپل را انتخاب کرده‌ایم. هر دو سیاستِ صریحِ همین مثال‌اند، نه راهی برای ترجیحِ معناییِ متن یا قاعدهٔ اجباریِ همهٔ رمزگشاها.

پس از تولید متن، هم‌ترازی واژه‌ها و WER پرسشِ دیگری دربارهٔ اختلاف با مرجع دارد؛ ارزیابیِ عدد و واحدهای بحرانیِ گفتار هم اهمیتِ فیلدهای مشخص را جدا می‌سنجد. این درس هیچ‌کدام را روی صوت یا مدل واقعی اجرا نکرده است. منابع در ۲۶ مهر ۱۴۰۵ خوانده شدند؛ مقالهٔ اصلی مربوط به ICML 2006 و نسخهٔ مستندات PyTorch برابر 2.14 است. تاریخِ روزِ انتشارِ مقاله و تاریخِ اولیهٔ صفحهٔ مستندات را معلوم فرض نمی‌کنیم؛ آموزش خبر تازه نیست.

منابع و مطالعهٔ بیشتر

• Graves و همکاران؛ مقالهٔ اصلی CTC در ICML 2006
• PyTorch 2.14؛ جمع احتمال هم‌ترازی‌ها و قرارداد CTCLoss

بررسی منابع: ۲۶ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.