مسیرِ ویتربی در پایتون؛ احتمالِ دقیق، تساوی و شاهدِ شمارشِ کامل

۱. مسیرِ مشترک را از برچسبِ جداگانه جدا کنیم

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

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

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

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

۲. احتمال‌های کسری و مرزِ ورودی را دقیق تعریف کنیم

مدل سه بخش دارد: توزیعِ آغاز، ماتریسِ انتقال و ماتریسِ انتشار. خانهٔ سطرِ i و ستونِ j در انتقال، احتمالِ رفتن از حالتِ i به حالتِ j است. سطرِ j در انتشار، احتمالِ هر نماد در حالتِ j را نگه می‌دارد. جمعِ توزیعِ آغاز و جمعِ تک‌تکِ سطرها باید دقیقاً یک باشد. در این قرارداد، احتمال‌ها بی‌واحدند و توالی طولِ ازپیش‌معلوم دارد؛ احتمالِ پایان جداگانه‌ای ضرب نمی‌شود.

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

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

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

۳. کدِ کاملِ ویتربی با اشاره‌گرِ بازگشت

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

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

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

"""Bounded exact discrete HMM decoding; no audio, training, or network I/O."""
from fractions import Fraction as F
from itertools import product
from math import prod
import json
import platform


def validate(start, transitions, emissions, observations):
    """Exact tuples, reduced Fraction denominators <=1000, stochastic rows."""
    if type(start) is not tuple or not 1 <= len(start) <= 4:
        raise ValueError("start must be a tuple with 1..4 states")
    n = len(start)
    if type(transitions) is not tuple or len(transitions) != n:
        raise ValueError("transition row count")
    if type(emissions) is not tuple or len(emissions) != n:
        raise ValueError("emission row count")
    if type(emissions[0]) is not tuple or not 1 <= len(emissions[0]) <= 4:
        raise ValueError("1..4 emission symbols required")
    m = len(emissions[0])
    for row, size in [(start, n)] + [(r, n) for r in transitions] + [
        (r, m) for r in emissions
    ]:
        if type(row) is not tuple or len(row) != size:
            raise ValueError("rectangular tuple rows required")
        if any(type(p) is not F or not 0 <= p <= 1 or p.denominator > 1000
               for p in row):
            raise ValueError("exact bounded Fraction probabilities required")
        if sum(row, F(0)) != 1:
            raise ValueError("each probability row must sum exactly to one")
    if type(observations) is not tuple or not 1 <= len(observations) <= 8:
        raise ValueError("observations must be a tuple of length 1..8")
    if any(type(o) is not int or not 0 <= o < m for o in observations):
        raise ValueError("exact integer symbol indices required")


def viterbi(start, transitions, emissions, observations):
    """Return lexicographically first positive maximum-joint path, or None,0."""
    validate(start, transitions, emissions, observations)
    n = len(start)
    scores = [start[j] * emissions[j][observations[0]] for j in range(n)]
    ranks = {j: k for k, j in enumerate(j for j in range(n) if scores[j] > 0)}
    back = [[None] * n]
    if not ranks:
        return None, F(0)
    for symbol in observations[1:]:
        next_scores = [F(0)] * n
        parents = [None] * n
        for j in range(n):
            for i in ranks:
                candidate = scores[i] * transitions[i][j] * emissions[j][symbol]
                if candidate == 0:
                    continue
                previous = parents[j]
                if (candidate > next_scores[j] or
                    (candidate == next_scores[j] and
                     (previous is None or ranks[i] < ranks[previous]))):
                    next_scores[j], parents[j] = candidate, i
        alive = [j for j in range(n) if parents[j] is not None]
        if not alive:
            return None, F(0)
        # Equal-length survivor paths sort by their prefix rank, then final state.
        ordered = sorted(alive, key=lambda j: (ranks[parents[j]], j))
        ranks = {j: k for k, j in enumerate(ordered)}
        scores = next_scores
        back.append(parents)
    last = min(ranks, key=lambda j: (-scores[j], ranks[j]))
    probability = scores[last]
    path = [last]
    for t in range(len(observations) - 1, 0, -1):
        last = back[t][last]
        path.append(last)
    return tuple(reversed(path)), probability


def exhaustive_oracle(start, transitions, emissions, observations):
    """Independent whole-path product, no trellis, ranks, or production calls."""
    best_path, best_probability = None, F(0)
    total_probability = F(0)
    for path in product(range(len(start)), repeat=len(observations)):
        factors = [start[path[0]]]
        factors += [emissions[state][symbol]
                    for state, symbol in zip(path, observations)]
        factors += [transitions[left][right]
                    for left, right in zip(path, path[1:])]
        weight = prod(factors, start=F(1))
        total_probability += weight
        # product() visits paths lexicographically; never invent a zero path.
        if weight > best_probability:
            best_path, best_probability = path, weight
    return (best_path, best_probability), total_probability


def rejected(arguments):
    try:
        viterbi(*arguments)
    except ValueError:
        return True
    return False


def self_check():
    start = (F(3, 5), F(2, 5))
    transitions = ((F(9, 10), F(1, 10)), (F(1, 5), F(4, 5)))
    emissions = ((F(3, 4), F(1, 4)), (F(1, 4), F(3, 4)))
    observations = (0, 1, 1)
    fixture = (start, transitions, emissions, observations)
    result = viterbi(*fixture)
    reference, likelihood = exhaustive_oracle(*fixture)
    checks = {}
    checks['hand_joint_path'] = result == ((1, 1, 1), F(9, 250))
    checks['joint_not_observation_likelihood'] = (
        result == reference and likelihood == F(297, 3200) and
        result[1] < likelihood
    )
    checks['one_observation'] = viterbi(start, transitions, emissions, (0,)) == (
        (0,), F(9, 20)
    )
    checks['single_state'] = viterbi(
        (F(1),), ((F(1),),), ((F(1, 3), F(2, 3)),), (1, 0, 1)
    ) == ((0, 0, 0), F(4, 27))
    checks['deterministic_zero_edges'] = viterbi(
        (F(1), F(0)), ((F(0), F(1)), (F(1), F(0))),
        ((F(1), F(0)), (F(0), F(1))), (0, 1, 0, 1)
    ) == ((0, 1, 0, 1), F(1))
    checks['unsupported_initial_observation'] = viterbi(
        (F(1),), ((F(1),),), ((F(1), F(0)),), (1,)
    ) == (None, F(0))
    checks['unsupported_later_observation'] = viterbi(
        (F(1),), ((F(1),),), ((F(1), F(0)),), (0, 1)
    ) == (None, F(0))
    checks['uniform_global_tie'] = viterbi(
        (F(1, 2), F(1, 2)), ((F(1, 2), F(1, 2)),) * 2,
        ((F(1),),) * 2, (0,) * 8
    ) == ((0,) * 8, F(1, 256))
    # First predecessor/final index would pick (1,0); global lex order is (0,1).
    final_tie = viterbi(
        (F(1, 2), F(1, 2)), ((F(0), F(1)), (F(1), F(0))),
        ((F(1),),) * 2, (0, 0)
    ) == ((0, 1), F(1, 2))
    predecessor_tie = viterbi(
        (F(1, 2), F(1, 2), F(0)),
        ((F(0), F(1, 2), F(1, 2)), (F(1), F(0), F(0)),
         (F(0), F(1), F(0))),
        ((F(1, 2), F(1, 2), F(0)), (F(1, 2), F(0), F(1, 2)),
         (F(0), F(1, 2), F(1, 2))), (0, 1, 2)
    ) == ((0, 2, 1), F(1, 32))
    checks['prefix_rank_not_last_index'] = final_tie and predecessor_tie
    bad_types = [
        ([F(1)], ((F(1),),), ((F(1),),), (0,)),
        ((True,), ((F(1),),), ((F(1),),), (0,)),
        ((1,), ((F(1),),), ((F(1),),), (0,)),
        (start, transitions, emissions, (True,)),
        (start, transitions, emissions, (0.0,)),
        (start, transitions, emissions, [0]),
    ]
    checks['strict_input_types'] = all(rejected(a) for a in bad_types)
    bad_shapes = [
        ((), (), (), (0,)),
        ((F(1),) * 5, (), (), (0,)),
        (start, transitions[:1], emissions, (0,)),
        (start, ((F(1),),) * 2, emissions, (0,)),
        (start, transitions, ((F(1),), (F(1, 2), F(1, 2))), (0,)),
        (start, transitions, emissions, ()),
        (start, transitions, emissions, (0,) * 9),
        (start, transitions, emissions, (-1,)),
        (start, transitions, emissions, (2,)),
    ]
    checks['dimension_and_observation_bounds'] = all(rejected(a) for a in bad_shapes)
    bad_probabilities = [
        ((F(1, 3), F(1, 3)), transitions, emissions, (0,)),
        ((F(-1), F(2)), transitions, emissions, (0,)),
        ((F(1, 1001), F(1000, 1001)), transitions, emissions, (0,)),
        (start, ((F(1, 2), F(1, 3)), transitions[1]), emissions, (0,)),
    ]
    checks['exact_stochastic_probability_contract'] = all(
        rejected(a) for a in bad_probabilities
    )
    # One broad oracle family: 81 models * 30 sequences, including zero support.
    fractions = (F(0), F(1, 2), F(1))
    oracle_cases = 0
    oracle_ok = True
    for p, a, b, e in product(fractions, repeat=4):
        model = ((p, 1-p), ((a, 1-a), (b, 1-b)),
                 ((e, 1-e), (1-e, e)))
        for length in range(1, 5):
            for obs in product(range(2), repeat=length):
                expected, _ = exhaustive_oracle(*model, obs)
                oracle_ok = oracle_ok and viterbi(*model, obs) == expected
                oracle_cases += 1
    checks['exhaustive_independent_model_family'] = oracle_ok and oracle_cases == 2430
    # Upper declared dimensions in one independent boundary family.
    uniform = ((F(1, 4),) * 4, ((F(1, 4),) * 4,) * 4,
               ((F(1, 4),) * 4,) * 4, (0, 1, 2, 3, 0, 1, 2, 3))
    expected, total = exhaustive_oracle(*uniform)
    checks['four_state_eight_step_boundary'] = (
        viterbi(*uniform) == expected == ((0,) * 8, F(1, 4**16)) and
        total == F(1, 4**8)
    )
    assert len(checks) == 14 and all(type(v) is bool for v in checks.values())
    assert all(checks.values()), checks
    return {
        'python': platform.python_version(), 'dependencies': 'standard library only',
        'fixture': {'observations': list(observations), 'path': list(result[0]),
                    'joint_probability': str(result[1]),
                    'observation_likelihood_oracle': str(likelihood)},
        'tie_fixture_path': [0, 1], 'unsupported_observation_path': None,
        'oracle_model_sequence_cases': oracle_cases,
        'boundary_paths_enumerated': 4**8,
        'unique_executed_checks': len(checks), 'checks': checks,
        'all_passed': all(checks.values()),
    }


if __name__ == '__main__':
    print(json.dumps(self_check(), indent=2, ensure_ascii=True))

{
  "python": "3.14.5",
  "dependencies": "standard library only",
  "fixture": {
    "observations": [
      0,
      1,
      1
    ],
    "path": [
      1,
      1,
      1
    ],
    "joint_probability": "9/250",
    "observation_likelihood_oracle": "297/3200"
  },
  "tie_fixture_path": [
    0,
    1
  ],
  "unsupported_observation_path": null,
  "oracle_model_sequence_cases": 2430,
  "boundary_paths_enumerated": 65536,
  "unique_executed_checks": 14,
  "checks": {
    "hand_joint_path": true,
    "joint_not_observation_likelihood": true,
    "one_observation": true,
    "single_state": true,
    "deterministic_zero_edges": true,
    "unsupported_initial_observation": true,
    "unsupported_later_observation": true,
    "uniform_global_tie": true,
    "prefix_rank_not_last_index": true,
    "strict_input_types": true,
    "dimension_and_observation_bounds": true,
    "exact_stochastic_probability_contract": true,
    "exhaustive_independent_model_family": true,
    "four_state_eight_step_boundary": true
  },
  "all_passed": true
}

۴. شاهدِ شمارشِ کامل و تساویِ مسیرها را بسنجیم

در شاهدِ اصلی، آغاز برابر سه‌پنجم و دوپنجم است. سطرهای انتقال به‌ترتیب نه‌دهم و یک‌دهم، سپس یک‌پنجم و چهارپنجم‌اند. انتشارِ نمادِ صفر در دو حالت، سه‌چهارم و یک‌چهارم است و برای نمادِ یک برعکس می‌شود. مشاهدهٔ صفر، یک، یک به مسیرِ یک، یک، یک می‌رسد. احتمالِ مشترکِ آن از ضربِ دوپنجم، یک‌چهارم و دو بارِ حاصلِ چهارپنجم در سه‌چهارم، برابر 9/250 می‌شود.

این مسیر از حالتِ یک شروع می‌شود، با اینکه در نخستین مشاهده، امتیازِ حالتِ صفر بیشتر است. شاهد نشان می‌دهد بستنِ تصمیمِ نخست با یک انتخابِ محلی می‌تواند پاسخ را تغییر دهد. مجموعِ احتمالِ هر هشت مسیر برای همین مشاهده، برابر 297/3200 است؛ این عدد با احتمالِ بهترین مسیر فرق دارد. مرجع این مجموع را فقط برای روشن‌کردنِ تفاوتِ دو کمیت گزارش می‌کند.

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

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

۵. چهار پرسش دربارهٔ صفر، مقیاس و معنای نتیجه

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

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

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

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

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

• یورافسکی و مارتین؛ مدل مارکوف پنهان و ویتربی، پیوست A
• hmmlearn0.3.3؛ تفاوت Viterbi و MAP در decode

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