সরাসরি পর্বে যান
পর্ব ৭৯ · ৮৫-এর মধ্যে · মডিউল ১৩

Formal language আর machine learning — neural network কী শিখতে পারে

Formal Languages and Machine Learning — Finite-Precision RNNs as Automata, Counters in LSTMs, Transformers on Parity and Dyck, Length Generalisation, Angluin's L*, Grammar-Constrained Decoding and Tokenizers

Taught in Bangla, this lesson separates what a network can express, what it learns and whether it generalises to longer inputs. It proves finite-precision RNNs recognise only regular languages, and a real desktop PyTorch CPU run shows a 6,465-parameter LSTM cell counting Dyck-1 depth while a small transformer fails parity beyond training length. In-page Python (Pyodide) runs Angluin's L* on a 7-state order DFA, grammar-constrained decoding and BPE as rewriting rules.

এই পর্বে যা শিখবেন

  • প্রকাশক্ষমতা, শেখা আর length generalisation-এর পার্থক্য, আর formal language কেন neural network পরীক্ষার পরিষ্কার মাপকাঠি
  • সসীম precision-এর RNN কেন শুধু regular language চেনে তার প্রমাণ, আর counter ও stack কোথায় দরকার
  • LSTM-এর counter আর transformer-এর parity-সমস্যা: গবেষণার ফল সাবধানে পড়া, আর নিজের সত্যিকারের training run
  • Angluin-এর L*: observation table, closed আর consistent, সঠিকতার যুক্তি, আর network থেকে automaton বের করা
  • Grammar-constrained decoding আর BPE tokenizer-কে automaton আর rewriting-এর চোখে দেখা

১ · Network কী “জানে”, তা মাপার একটি পরিষ্কার মাপকাঠি

বাজারঘরের support দল একটি ছোট language model-কে দিয়ে অর্ডারের তথ্য JSON-এ লেখায়। বেশিরভাগ দিন ঠিক চলে, কিন্তু মাঝে মাঝে একটি বন্ধনী বাদ পড়ে, আর parser ভেঙে যায়। প্রশ্নটি তখন এই কোর্সের ভাষায় দাঁড়ায়: “সুষম বন্ধনী” একটি context-free language (পর্ব ২৫), যার জন্য একটি stack বা অন্তত একটি counter লাগে। Network-এর ভেতরে কি এমন কিছু আছে? না থাকলে বাইরে থেকে কি নিয়ম চাপানো যায়?

রেলস্টেশনের টিকিট কাউন্টারের একজন কর্মীকে ভাবুন, যিনি শুধু মনে মনে গোনেন লাইনে কতজন ঢুকল আর কতজন বেরোল। দশ-বিশজন পর্যন্ত তিনি নির্ভুল। কিন্তু ঈদের আগে লাইনে পাঁচশো মানুষ এলে তাঁর মনে রাখার ক্ষমতা ফুরিয়ে যায়। কাগজ-কলমে দাগ টানলে (একটি counter) সমস্যা নেই। Neural network-এর প্রশ্নও একই: সে কি সত্যিই গুনছে, নাকি শুধু দেখা দৈর্ঘ্য পর্যন্ত মুখস্থ করেছে?

Formal language এখানে আদর্শ পরীক্ষাগার। ঠিক উত্তর নিখুঁতভাবে জানা, যেকোনো দৈর্ঘ্যের পরীক্ষা-ডেটা বানানো যায়, আর Chomsky hierarchy (পর্ব ০৬) বলে দেয় কোন language-এর জন্য কতটা স্মৃতি লাগে। এই পর্বে তিনটি language বারবার আসবে:

Languageউদাহরণন্যূনতম যন্ত্রকী মনে রাখতে হয়
PARITY: 1-এর সংখ্যা বিজোড়1011 ∈, 1001 ∉২-state DFAএকটি bit
Dyck-1: সুষম এক রকম বন্ধনী(()()) ∈, ()) ∉one-counter automatonবর্তমান গভীরতা, সীমাহীন
anbn (n ≥ 1)aaabbb ∈, aabbb ∉one-counter automatona-এর সংখ্যা, সীমাহীন

প্রথমটি regular language, বাকি দুটি নয় (anbn-এর প্রমাণ পর্ব ১৭-এ)। Dyck language context-free, আর এক রকম বন্ধনীর ক্ষেত্রে একটি counter automaton-ই যথেষ্ট; একাধিক রকম বন্ধনীতে সত্যিকারের stack লাগে (পর্ব ৩২)।

আর তিনটি প্রশ্ন সবসময় আলাদা রাখতে হবে। প্রকাশক্ষমতা (expressivity): এমন কোনো weight কি আছে, যাতে network-টি language-টি চেনে? শেখা (learnability): gradient descent কি সত্যিই সেই weight খুঁজে পায়? Length generalisation: ৪০ অক্ষর পর্যন্ত শিখে কি ১৬০ অক্ষরেও ঠিক থাকে? প্রথমটি গণিতের প্রশ্ন, তার উত্তর উপপাদ্যে। বাকি দুটি মূলত পরীক্ষার প্রশ্ন, তাই উত্তর শর্তসাপেক্ষ: model-এর আকার, training-এর ধরন, random seed, সবকিছুর ওপর নির্ভর করে।

২ · RNN আর finite automaton — সসীম precision-এর প্রমাণ

একটি recurrent neural network (RNN) প্রতিটি চিহ্ন পড়ে তার hidden state ht = f(ht−1, xt) হালনাগাদ করে, আর শেষে hn থেকে হ্যাঁ বা না বলে। কাঠামোটি হুবহু DFA-র δ̂-এর মতো (পর্ব ০৭): state, চিহ্ন, তারপর পরের state পাওয়া। পার্থক্য একটাই: DFA-র state সসীম set থেকে আসে, RNN-এর state একটি বাস্তব সংখ্যার vector. যোগসূত্রটি পুরোনো: Kleene-এর ১৯৫৬ সালের যে প্রবন্ধে regular expression-এর জন্ম, তার বিষয় ছিল McCulloch আর Pitts-এর ১৯৪৩ সালের “nerve net”, অর্থাৎ neural network আর finite automaton একই উৎস থেকে এসেছে।

বাস্তব কম্পিউটারে প্রতিটি সংখ্যা finite precision-এ রাখা হয়, যেমন 32-bit float. তাহলে d-টি unit-এর একটি hidden state বড়জোর 232d-টি আলাদা মান নিতে পারে: বিশাল, কিন্তু সসীম।

উপপাদ্য ২.১ (সসীম state ⇒ regular)

ধরুন একটি RNN-এর update function f আর output function g স্থির, আর শুরুর state h0 থেকে কোনো string পড়ে যত hidden state-এ পৌঁছানো যায়, তাদের set H সসীম। তাহলে RNN-টি যে language গ্রহণ করে, L = {w : g(f̂(h0, w)) = 1}, তা regular, আর তার minimal DFA-র state-সংখ্যা ≤ |H|.

প্রমাণ:

  1. একটি DFA M = (H, Σ, δ, h0, F) বানাই: δ(h, a) = f(h, a), আর F = {h ∈ H : g(h) = 1}. H সসীম আর f, H থেকে H-এ যায় (H-এর সংজ্ঞায় পৌঁছানো যায় এমন সব state আছে), তাই M বৈধ DFA. — নির্মাণ
  2. |w|-এর ওপর induction-এ δ̂(h0, w) = f̂(h0, w): ε-তে দুটিই h0, আর wa-তে দুই পাশে একই f প্রয়োগ। — আরোহ
  3. তাই w ∈ L(M) ⇔ g(f̂(h0, w)) = 1 ⇔ w ∈ L. L regular. — সংজ্ঞা
  4. একই hidden state-এ পৌঁছানো দুটি string x, y-এর জন্য প্রতিটি z-এ xz আর yz একই state-এ যায়, তাই x ≡L y. ফলে Nerode equivalence-এর class-সংখ্যা ≤ |H|, আর Myhill–Nerode theorem (পর্ব ১৮) অনুযায়ী এটিই minimal DFA-র state-সংখ্যা। ∎

উপসিদ্ধান্ত সরাসরি: সসীম precision-এর কোনো RNN “সব দৈর্ঘ্যে” Dyck-1 বা anbn চিনতে পারে না, কারণ এদের Nerode class অসীম: (i আর (j (i ≠ j) suffix )i দিয়ে আলাদা হয়। কিন্তু একটি বাস্তব RNN বড় একটি সীমা পর্যন্ত নির্ভুল থাকতে পারে, ঠিক কাউন্টারের কর্মীর মতো। নিচের JavaScript ব্লক এটাই দেখায়: গভীরতা K-তে আটকে থাকা (K + 2)-state-এর একটি যন্ত্র কোন string-এ প্রথম ভুল করে, তা shortlex order-এ খোঁজা।

// Dyck-1: an unbounded counter vs. a finite automaton that can count only up to K
const dyck = s => { let d = 0;
  for (const c of s) { d += c === "(" ? 1 : -1; if (d < 0) return false; }
  return d === 0; };
const bounded = (s, K) => { let d = 0;      // states 0..K plus a dead state
  for (const c of s) {
    if (c === "(") d = Math.min(d + 1, K);  // no room above K: the depth is clipped
    else if (--d < 0) return false;
  }
  return d === 0; };
const depths = s => { let d = 0; return [...s].map(c => (d += c === "(" ? 1 : -1)); };
console.log("depth trace of (()(())): " + depths("(()(()))").join(" "));
const all = n => n === 0 ? [""] : all(n - 1).flatMap(w => [w + "(", w + ")"]);
for (let K = 1; K <= 4; K++) {
  let found = null;
  for (let n = 1; n <= 12 && !found; n++)          // shortlex search for a disagreement
    found = all(n).find(w => dyck(w) !== bounded(w, K));
  console.log(`K=${K} (${K + 2} states): first error on ${found}, ` +
    `true answer ${dyck(found)}, automaton says ${bounded(found, K)}`);
}

আসল আউটপুট (ব্রাউজারের JavaScript):

depth trace of (()(())): 1 2 1 2 3 2 1 0
K=1 (3 states): first error on ((), true answer false, automaton says true
K=2 (4 states): first error on ((()), true answer false, automaton says true
K=3 (5 states): first error on (((())), true answer false, automaton says true
K=4 (6 states): first error on ((((()))), true answer false, automaton says true

প্রথম ভুল সবসময় দৈর্ঘ্য 2K + 1-এ: K + 1টি খোলা বন্ধনী, তারপর K-টি বন্ধ। গভীরতা K-তে আটকে যাওয়ায় যন্ত্রটি একটি খোলা বন্ধনী “হারায়” আর অসমান string গ্রহণ করে। State বাড়ালে ভুল আরও দূরে সরে, কিন্তু কখনো মোছে না: এটাই উপপাদ্য ২.১-এর ব্যবহারিক রূপ।

এখানে একটি সতর্কতা জরুরি। Hava Siegelmann আর Eduardo Sontag ১৯৯০-এর দশকের প্রথমার্ধে দেখান, মূলদ সংখ্যার weight আর অসীম precision ধরলে একটি RNN যেকোনো Turing machine-কে অনুকরণ করতে পারে: সংখ্যার দশমিকের পরের অঙ্কে একটি পুরো stack লুকিয়ে রাখা যায়। দুটি ফলই সত্য, শুধু অনুমান আলাদা। পরে গবেষকেরা একটি মাঝামাঝি আদর্শ নেন: saturated RNN, যেখানে প্রতিটি activation সীমায় (0/1 বা ±1) পৌঁছে যায়। এই মডেলে সাধারণ tanh-RNN আর GRU finite automaton-এর মতো আচরণ করে, কিন্তু LSTM-এর cell state সীমাহীনভাবে বাড়তে পারে বলে তা counter রাখতে পারে বলে দেখানো হয়েছে (Gail Weiss, Yoav Goldberg আর Eran Yahav ২০১৮; William Merrill আর সহকর্মীদের ২০১৯–২০২০ সালের কাজ)।

৩ · LSTM-এর ভেতরের counter

একটি LSTM-এর cell state হালনাগাদ হয় ct = ft ⊙ ct−1 + it ⊙ gt নিয়মে (বিস্তারিত ডিপ লার্নিং, NLP আর Generative AI কোর্সের পর্ব ২৯-এ)। Forget gate ft ≈ 1, input gate it ≈ 1 আর gt ≈ ±1 হলে ct ≈ ct−1 ± 1: একটি counter. Felix Gers আর Jürgen Schmidhuber ২০০১ সালে দেখান যে LSTM anbn আর anbncn শিখে training-এর চেয়ে অনেক বড় n-এও ঠিক থাকতে পারে। প্রশ্ন হলো, আমাদের নিজের ছোট LSTM কি সত্যিই এমন করে?

অংশ ৫-এর সত্যিকারের run-এ Dyck-1-এ শেখানো একটি LSTM (৩২টি cell) নিয়ে আমরা string ((()(()))(((()))))-এর প্রতিটি অক্ষরের পরে ৩২টি cell-এর মান তুলেছি, আর দেখেছি কোন cell-এর মান গভীরতার সঙ্গে সবচেয়ে বেশি মেলে। Cell 0-এর |correlation| ০.৯৯৯. নিচের stepper সেই আসল সংখ্যাগুলোর কয়েকটি ধাপ দেখায়।

1(2((3(((4((()((5((()(()))((((6…((((()))))
এই ধাপে
পড়া অক্ষর
আসল গভীরতা
cell 0-এর মান
  1. প্রথম খোলা বন্ধনী। গভীরতা ১, cell 0-এর মান −0.13. ছোট একটি শুরু; এরপর থেকে প্রতিটি অক্ষরে মোটামুটি একই মাপে নড়াচড়া।
  2. আরেকটি খোলা। গভীরতা ২, মান −1.07: প্রায় ০.৯৪ কমেছে। একটি “(” মানে counter-এ প্রায় এক ধাপ।
  3. তৃতীয় খোলা। গভীরতা ৩, মান −2.03. পার্থক্য আবার প্রায় এক ধাপ, অর্থাৎ মানটি মোটামুটি ১ − গভীরতা-র কাছাকাছি।
  4. ওঠানামা। “((()((” পড়ার পর গভীরতা ৪ আর মান −3.01. মাঝের “)” মানকে এক ধাপ বাড়িয়েছিল, তারপর দুটি “(” আবার নামিয়েছে। Network কোনো নিয়ম লেখা ছাড়াই যোগ-বিয়োগ শিখেছে।
  5. Training-এর বাইরের গভীরতার কাছে। ১৩ অক্ষরে গভীরতা ৫, মান −4.05. লক্ষ করুন, গভীরতা ১-এ মান প্রথমে −0.13, পরে −0.16 আর −0.25 হয়েছে: একটু একটু সরে যাওয়া, যা লম্বা string-এ জমতে পারে।
  6. শূন্যে ফেরা। শেষ “)”-এ গভীরতা ০ আর মান 0.72, একমাত্র ধনাত্মক মান। Output স্তর এই চিহ্ন থেকেই “গভীরতা > 0 নয়” বলতে পারে। Cell-টি একটি one-counter automaton-এর counter-এর মতো কাজ করছে।

এটি সুন্দর, কিন্তু প্রমাণ নয়। Correlation বলে মানটি গভীরতার সঙ্গে চলে; network ঠিক এই cell দিয়েই সিদ্ধান্ত নেয় কি না, তা আলাদা পরীক্ষা চায়। আর ধাপ ৫-এর ধীর সরে যাওয়া দেখায় কেন লম্বা string-এ নির্ভুলতা কমতে পারে: সসীম precision-এ একটি counter-ও শেষ পর্যন্ত একটি বড় DFA, যেমন উপপাদ্য ২.১ বলে।

৪ · Transformer আর formal language — parity কেন কঠিন

একটি transformer চিহ্নগুলো একটি একটি করে বয়ে নেয় না; প্রতিটি স্তরে self-attention দিয়ে প্রতিটি অবস্থান বাকি সব অবস্থানের একটি ওজনসহ গড় নেয় (ডিপ লার্নিং কোর্সের পর্ব ৩৩ আর পর্ব ৩৫)। Attention নিজে ক্রম দেখে না, তাই ক্রমের তথ্য আসে positional encoding থেকে। দুটি বৈশিষ্ট্য formal language-এর জন্য জরুরি: স্তরের সংখ্যা স্থির (input লম্বা হলে ধাপ বাড়ে না), আর গড় নেওয়া একটি স্বাভাবিক “গোনার” যন্ত্র।

গড় দিয়ে গোনা কেমন? সব অবস্থানে সমান ওজন দিলে একটি head দেয় “এ পর্যন্ত ‘(’-এর ভাগ” f. গভীরতা = (২f − ১) × দৈর্ঘ্য, তাই “গভীরতা > 0” ⇔ f > ½: এই শর্ত দৈর্ঘ্যের ওপর নির্ভর করে না। কিন্তু PARITY function সম্পূর্ণ আলাদা স্বাদের।

1২-state DFA, input 10112RNN: h ← −h যখন 13attention: 1-এর ভাগ k/n4k আর k+1-এর ফারাক 1/n5প্রতিটি bit-ই গুরুত্বপূর্ণ6সত্যিকারের run
এই ধাপে
কে হিসাব করছে
মান
  1. DFA-র কাছে এক bit-এর কাজ। 1011 পড়তে state জোড় → বিজোড় → বিজোড় → জোড় → বিজোড়। শেষ state বিজোড়, তাই উত্তর 1. শুধু দুটি state.
  2. RNN হুবহু অনুকরণ করে। একটি saturated unit প্রতিটি 1-এ চিহ্ন বদলায়: +1, −1, −1, +1, −1. এটি উপপাদ্য ২.১-এর DFA, দুটি hidden state-এ।
  3. Attention-এর স্বাভাবিক হিসাব। সমান ওজনের একটি head দেয় 1-এর ভাগ k/n; 1011-এ 3/4 = 0.75. এখান থেকে k = 3 বের করা যায়, কিন্তু parity-র জন্য k জোড় না বিজোড় সেটাই দরকার।
  4. বিন্দুগুলো ঘন হয়ে আসে। k আর k + 1-এর ভাগের ফারাক 1/n: n = 100-এ 0.01, n = 1000-এ 0.001. পরের স্তরকে এই ঘন বিন্দুগুলোকে পালাক্রমে 0, 1, 0, 1-এ পাঠাতে হবে, অর্থাৎ একটি function যা n বার ওঠানামা করে। স্থির আকারের স্তর আর সসীম precision-এ সব n-এর জন্য তা সম্ভব নয়: এটি একটি অন্তর্দৃষ্টি, পূর্ণ প্রমাণ নয়।
  5. প্রতিটি bit-ই গুরুত্বপূর্ণ। PARITY-তে যেকোনো একটি bit উল্টালে উত্তর উল্টায়: এর sensitivity সর্বোচ্চ, n. Michael Hahn ২০২০ সালে কিছু নির্দিষ্ট transformer মডেলের জন্য দেখান যে লম্বা input-এ একটি bit-এর প্রভাব কমে যায়, তাই এমন মডেল লম্বা input-এ parity নির্ভরযোগ্যভাবে করতে পারে না।
  6. আমাদের run একই দিকে। অংশ ৫-এ ১৭,১৮৫-parameter-এর transformer training-এর দৈর্ঘ্যেই (১–৪০) মাত্র ৯.৫% থেকে ২৭.৫% string পুরো ঠিক করেছে, আর লম্বা দৈর্ঘ্যে ০%; একই কাজে LSTM সব দৈর্ঘ্যে ১০০%. তবে এটি একটি ছোট setup; অন্য setup-এ ভিন্ন ফল সম্ভব।

এই ছবির পাশে আরও কয়েকটি প্রকাশিত ফল রাখা দরকার, প্রতিটি নিজের অনুমানসহ। David Chiang আর Peter Cholak ২০২২ সালে এমন একটি transformer নির্মাণ দেখান যা parity চেনে, কিন্তু দৈর্ঘ্য বাড়লে তার আত্মবিশ্বাস (দুই উত্তরের score-এর ফারাক) কমতে থাকে; অর্থাৎ প্রকাশ সম্ভব, কিন্তু ভঙ্গুর। Satwik Bhattamishra আর সহকর্মীরা ২০২০ সালের পরীক্ষায় দেখান, transformer Dyck-1-এর মতো counter language মোটামুটি ভালো শেখে, কিন্তু parity-র মতো কিছু সরল regular language-এ সমস্যায় পড়ে। আর সসীম precision-এর transformer threshold circuit-এর শ্রেণি TC0-এর মতো সীমার মধ্যে পড়ে বলে দেখানো হয়েছে (পর্ব ৭০)। অন্যদিকে ধাপে ধাপে মধ্যবর্তী token লিখতে দিলে (chain of thought) প্রকাশক্ষমতা বাড়ে বলেও গবেষণা আছে। তাই “transformer X পারে না” কথাটি সবসময় precision, attention-এর ধরন আর output-এর নিয়মসহ বলতে হয়।

৫ · সত্যিকারের run — ছোট LSTM বনাম ছোট transformer

তত্ত্বের পাশে নিজের পরীক্ষা। uv দিয়ে বানানো একটি ছোট প্রকল্পে PyTorch 2.15.0 (শুধু CPU-র wheel; মূল licence BSD-3-Clause ধাঁচের, সঙ্গের অংশগুলোর Apache-2.0, MIT ইত্যাদি) আর NumPy 2.5.5 (BSD-3-Clause), Python 3.12.13. PyTorch-এর কোনো নথিভুক্ত usage-reporting নেই; installed source-এর usage-hook (torch/_utils_internal.py) শুধু স্থানীয় log লেখে, network-এ কিছু পাঠায় না। সব run শুধু CPU-তে, OMP_NUM_THREADS=3 আর torch.set_num_threads(3), প্রতিটি run ৭–১৯ সেকেন্ড।

কাজটি প্রতিটি অবস্থানে একটি হ্যাঁ/না লেবেল দেওয়া: Dyck-1-এ “এখন গভীরতা > 0?”, anbn-এ “এখানে কি akbk শেষ হলো?”, parity-তে “এ পর্যন্ত 1-এর সংখ্যা বিজোড়?”। একটি string ঠিক ধরা হয় শুধু তখন, যখন তার প্রতিটি অবস্থান ঠিক। তিনটি model: LSTM, sinusoidal positional encoding-সহ transformer, আর কোনো positional encoding ছাড়া transformer (“nope”), প্রতিটি তিনটি seed-এ।

def dyck1(rng, n):          # a prefix of a Dyck-1 word; label: depth > 0 after each symbol
    s, d, y = [], 0, []
    for _ in range(n):
        c = "(" if d == 0 or rng.random() < 0.5 else ")"
        d += 1 if c == "(" else -1
        s.append(c); y.append(int(d > 0))
    return "".join(s), y
# anbn: label 1 only at the very end of a^k b^k;  parity: label = odd number of 1s so far

class LSTMTagger(nn.Module):            # 6,465 parameters
    def __init__(s, h=32):
        super().__init__(); s.emb = nn.Embedding(2, 16)
        s.rnn = nn.LSTM(16, h, batch_first=True); s.out = nn.Linear(h, 1)
    def forward(s, x): return s.out(s.rnn(s.emb(x))[0]).squeeze(-1)

class TinyTransformer(nn.Module):       # 17,185 parameters: causal, 2 layers, 4 heads, d = 32
    ...   # embedding (+ sinusoidal positions, or none for "nope") -> TransformerEncoder with a causal mask

# training: Adam, 2000 steps x 64 random strings of length 1..40 (a^n b^n: n = 1..20), seeds 0, 1, 2
# test: a string counts as correct only if EVERY position is right

সত্যিকারের run (ডেস্কটপ CPU, torch 2.15.0+cpu, Python 3.12.13; acc-এর তিন কলাম: Dyck-1 আর parity-তে দৈর্ঘ্য ১–৪০, ৪১–৮০, ৮১–১৬০, প্রতিটিতে ২০০টি string; anbn-এ n = ১–২০, ২১–৪০, ৪১–৮০, প্রতিটিতে ২০টি নমুনা):

~/bazarghar-toc$ python train_formal.py dyck1,parity lstm,transformer,nope
torch 2.15.0+cpu | threads 3 | CPU only
dyck1  lstm        seed 0  loss 0.0001  acc 100.0%   99.5%   88.0%  (7s)
dyck1  lstm        seed 1  loss 0.0001  acc 100.0%  100.0%   92.5%  (7s)
dyck1  lstm        seed 2  loss 0.0001  acc 100.0%   99.5%   91.5%  (7s)
dyck1  transformer seed 0  loss 0.0003  acc 100.0%   50.0%    5.5%  (17s)
dyck1  transformer seed 1  loss 0.0002  acc 100.0%   67.5%   35.5%  (17s)
dyck1  transformer seed 2  loss 0.0011  acc 100.0%   69.5%   42.0%  (18s)
dyck1  nope        seed 0  loss 0.0020  acc 100.0%   93.0%   54.5%  (17s)
dyck1  nope        seed 1  loss 0.0001  acc 100.0%   79.5%   44.0%  (18s)
dyck1  nope        seed 2  loss 0.0001  acc 100.0%  100.0%   98.0%  (18s)
parity lstm        seed 0  loss 0.0000  acc 100.0%  100.0%  100.0%  (8s)
parity lstm        seed 1  loss 0.0000  acc 100.0%  100.0%  100.0%  (8s)
parity lstm        seed 2  loss 0.0001  acc 100.0%  100.0%  100.0%  (8s)
parity transformer seed 0  loss 0.3845  acc  24.5%    0.0%    0.0%  (19s)
parity transformer seed 1  loss 0.3050  acc  27.5%    0.0%    0.0%  (18s)
parity transformer seed 2  loss 0.7077  acc   9.5%    0.0%    0.0%  (19s)
parity nope        seed 0  loss 0.6151  acc   6.0%    0.0%    0.0%  (19s)
parity nope        seed 1  loss 0.5268  acc  11.0%    0.0%    0.0%  (19s)
parity nope        seed 2  loss 0.5585  acc   8.5%    0.0%    0.0%  (19s)
~/bazarghar-toc$ python train_formal.py anbn lstm,transformer,nope
torch 2.15.0+cpu | threads 3 | CPU only
anbn   lstm        seed 0  loss 0.0001  acc 100.0%  100.0%   40.0%  (8s)
anbn   lstm        seed 1  loss 0.0001  acc 100.0%  100.0%   15.0%  (8s)
anbn   lstm        seed 2  loss 0.0001  acc 100.0%   85.0%    0.0%  (8s)
anbn   transformer seed 0  loss 0.0000  acc 100.0%    0.0%    0.0%  (18s)
anbn   transformer seed 1  loss 0.0000  acc 100.0%   15.0%    5.0%  (18s)
anbn   transformer seed 2  loss 0.0001  acc 100.0%    0.0%    0.0%  (18s)
anbn   nope        seed 0  loss 0.0000  acc 100.0%  100.0%  100.0%  (18s)
anbn   nope        seed 1  loss 0.0000  acc 100.0%  100.0%   20.0%  (18s)
anbn   nope        seed 2  loss 0.0000  acc 100.0%  100.0%  100.0%  (18s)

সংখ্যাগুলো সতর্কভাবে পড়া যাক, পাঁচটি পর্যবেক্ষণে:

  1. Training-এর দৈর্ঘ্যে প্রায় সবাই নিখুঁত, একমাত্র ব্যতিক্রম parity-তে দুই transformer (৬–২৭.৫%). অর্থাৎ এখানে transformer-এর সমস্যা শুধু সাধারণীকরণ নয়, শেখাও।
  2. LSTM parity-তে চার গুণ দৈর্ঘ্যেও ১০০%: একটি ২-state DFA শেখা সহজ, আর সেই নিয়ম দৈর্ঘ্যের ওপর নির্ভর করে না। Dyck-1-এ চার গুণে ৮৮–৯২.৫%: counter আছে, কিন্তু নিখুঁত নয়। আলাদা একটি পরীক্ষায় ১,০০০টি লম্বা string-কে সর্বোচ্চ গভীরতা অনুযায়ী ভাগ করে দেখা গেছে, ভুল গভীর string-এ বেশি হয়নি; অংশ ৩-এর সরে যাওয়া counter একটি সম্ভাব্য ব্যাখ্যা, প্রমাণিত নয়।
  3. Sinusoidal transformer সব কাজে লম্বা input-এ ভেঙে পড়েছে (Dyck-1-এ ৫.৫–৪২%, anbn-এ প্রায় ০%). সম্ভাব্য কারণ: ৪০-এর পরের অবস্থানের positional vector training-এ কখনো আসেনি।
  4. Positional encoding ছাড়া transformer গোনার কাজে ভালো, কিন্তু seed-নির্ভর: anbn-এ দুটি seed-এ ১০০%, একটিতে ২০%. অংশ ৪-এর যুক্তিতে “a-এর ভাগ ঠিক ½” একটি দৈর্ঘ্য-নিরপেক্ষ শর্ত, তাই এটি প্রত্যাশিত দিক; তবে ½ আর ½ + 1/(২n)-এর ফারাক n বাড়লে কমে।
  5. Seed গুরুত্বপূর্ণ: একই model আর ডেটায় ২০% বনাম ১০০%. একটি seed-এর ফল দিয়ে “X পারে” বা “পারে না” বলা ঝুঁকিপূর্ণ।

সামগ্রিক দিকটি প্রকাশিত বড় পরীক্ষার সঙ্গে মেলে। Grégoire Delétang আর সহকর্মীরা (২০২৩ সালে প্রকাশিত) Chomsky hierarchy-র বিভিন্ন স্তরের কাজে হাজার হাজার model চালিয়ে length generalisation মেপেছিলেন; সেখানে LSTM সাধারণত regular আর counter-ধাঁচের কাজে ভালো, transformer অনেক কাজে training দৈর্ঘ্যের বাইরে দুর্বল, আর stack বা tape যোগ করা network ওপরের স্তরে উঠতে পেরেছে। তবু আমাদের সংখ্যা একটি ছোট setup-এর, ৩টি seed-এর; এগুলো উদাহরণ, সাধারণ সূত্র নয়।

৬ · Network থেকে automaton বের করা — Angluin-এর L*

একটি প্রশিক্ষিত network একটি কালো বাক্স। তাকে যেকোনো string দিয়ে প্রশ্ন করা যায়, কিন্তু তার নিয়ম পড়া যায় না। যদি সে আসলে একটি regular language চেনে, সেই language-এর minimal DFA বের করা যায় কি? Dana Angluin ১৯৮৭ সালে এর একটি সুন্দর উত্তর দেন: L* algorithm. শিক্ষার্থী দুই রকম প্রশ্ন করে:

  • Membership query: “w কি L-এ আছে?” উত্তর হ্যাঁ বা না।
  • Equivalence query: “এই DFA H কি ঠিক L চেনে?” না হলে উত্তরদাতা একটি counterexample দেয়, যেখানে H আর L আলাদা।

শিক্ষার্থী একটি observation table (S, E, T) রাখে: S হলো prefix-এর set (সম্ভাব্য state-এর প্রতিনিধি), E হলো suffix-এর set (পরীক্ষা), আর T(u, e) = [ue ∈ L]. প্রতিটি u-এর সারি row(u) = (T(u, e))e ∈ E. এটি Myhill–Nerode-এর সসীম ছায়া: x ≡L y হলে প্রতিটি suffix-এ উত্তর মেলে, তাই row(x) = row(y); উল্টোটি E যথেষ্ট বড় না হলে সত্য না-ও হতে পারে।

সংজ্ঞা ৬.১ (closed আর consistent)

টেবিলটি closed, যদি প্রতিটি s ∈ S আর a ∈ Σ-এর জন্য এমন s′ ∈ S থাকে যে row(sa) = row(s′). টেবিলটি consistent, যদি s1, s2 ∈ S আর row(s1) = row(s2) হলে প্রতিটি a ∈ Σ-এ row(s1a) = row(s2a). দুটিই হলে hypothesis DFA: state = S-এর আলাদা সারি, শুরু row(ε), δ(row(s), a) = row(sa), আর row(s) গ্রহণকারী ⇔ T(s, ε) = 1.

Closed না হলে row(sa)-কে S-এ তোলা হয়; consistent না হলে যে suffix ae দুটি সমান সারিকে আলাদা করে, তা E-তে যোগ হয়। Counterexample এলে Angluin-এর মূল নিয়মে তার সব prefix S-এ যোগ হয়। নিচে L = “a-এর সংখ্যা জোড় আর b-এর সংখ্যাও জোড়”, Σ = {a, b}-এর ওপর পুরো দৌড়; counterexample-এ shortlex-এ সবচেয়ে ছোট string দেওয়া হয়েছে, আর সারির প্রতিটি অঙ্ক E-এর একটি suffix-এর উত্তর।

1শুরু: S = {ε}, E = {ε}2closed করা: a যোগ3counterexample ba4consistent করা: suffix a5suffix b, ৪টি state
এই ধাপে
E
S-এর সারি
S·Σ-এর সারি
  1. শুরু। S = E = {ε}. row(ε) = 1, কারণ ε-তে a আর b দুটিই ০টি। কিন্তু row(a) = 0 আর S-এ 0-সারি নেই: টেবিল closed নয়, তাই a যোগ হলো।
  2. প্রথম অনুমান-যন্ত্র। S = {ε, a}; বর্ধিত সারি b:0, aa:1, ab:0, সবই S-এ আছে। Closed আর consistent, তাই ২-state DFA: “a-এর সংখ্যা জোড়?”-এর মতো কিছু। Equivalence query-র উত্তর counterexample ba: hypothesis একে গ্রহণ করে, অথচ ba-তে একটি a আর একটি b.
  3. Counterexample-এর prefix যোগ। b আর ba S-এ এল। এখন row(a) = row(b) = 0, কিন্তু a-এর পরে a দিলে aa:1, আর b-এর পরে a দিলে ba:0. টেবিল consistent নয়: suffix “a” তাদের আলাদা করে।
  4. Suffix a যোগ। সারিগুলো দুই অঙ্কের: ε:10, a:01, b:00, ba:00. এবার b আর ba সমান, কিন্তু bb:10 আর bab:01. Suffix “b” যোগ করতে হবে।
  5. চারটি Nerode class পাওয়া গেল। E = {ε, a, b}-এ চারটি আলাদা সারি: 100, 010, 001, 000, অর্থাৎ (জোড়, জোড়), (বিজোড়, জোড়), (জোড়, বিজোড়), (বিজোড়, বিজোড়). টেবিল closed আর consistent, আর equivalence query “হ্যাঁ” বলে। ঠিক minimal DFA, ৪টি state.
উপপাদ্য ৬.২ (Angluin ১৯৮৭)

L regular আর তার minimal DFA-র state n হলে, L* বড়জোর n-টি equivalence query-র পরে L-এর একটি minimal DFA ফেরত দেয়, আর মোট membership query n, |Σ| আর সবচেয়ে লম্বা counterexample-এর দৈর্ঘ্য m-এর একটি polynomial-এ সীমিত।

প্রমাণের রূপরেখা:

  1. S-এর দুটি আলাদা সারি মানে দুটি prefix কোনো suffix e ∈ E দিয়ে আলাদা, অর্থাৎ ভিন্ন Nerode class-এ। তাই আলাদা সারির সংখ্যা সবসময় ≤ n. — Myhill–Nerode, পর্ব ১৮
  2. Closed না হলে নতুন সারি যোগ হয়, consistent না হলে নতুন suffix কোনো পুরোনো সারিকে ভাগ করে; দুই ক্ষেত্রেই আলাদা সারির সংখ্যা ১ বাড়ে। তাই এই দুই কাজ মিলে বড়জোর n − 1 বার ঘটে। — ধাপ ১-এর সীমা
  3. Closed আর consistent টেবিলের hypothesis টেবিলের প্রতিটি ঘরের সঙ্গে মেলে, আর এমন DFA-র মধ্যে এটিই সবচেয়ে কম state-এর। ফলে একটি counterexample পেলে, তার prefix যোগ করে টেবিল আবার closed আর consistent করলে নতুন hypothesis-এ state অন্তত একটি বাড়ে। — Angluin-এর মূল lemma; বিস্তারিত তাঁর প্রবন্ধে
  4. State n-এর বেশি হতে পারে না, তাই বড়জোর n-টি equivalence query; সারি আর কলামের সংখ্যা n, m আর |Σ|-এর polynomial, তাই membership query-ও polynomial. শেষ hypothesis-এ n-টি state আর তা L-এর সমান, তাই minimal. ∎

এবার বাজারঘরের অর্ডার-অবস্থা। ঘটনা p (টাকা দেওয়া), s (পাঠানো), c (বাতিল), d (পৌঁছানো), r (ফেরত টাকা)। একটি ঘটনা-ক্রম গ্রহণযোগ্য, যদি অর্ডার বন্ধ হয়: পৌঁছেছে, টাকা দেওয়ার আগে বাতিল, বা ফেরত টাকা পেয়েছে। লক্ষ্য-যন্ত্রটি ইচ্ছা করে ৮টি state-এ লেখা, যার দুটি (cancel আর refund) আসলে সমতুল্য। L* কি তা নিজে খুঁজে পায়?

# Angluin's L*: learn the order-status DFA from membership and equivalence queries
from collections import deque
SIG = "pscdr"            # paid, shipped, cancelled, delivered, refunded
T = {("new", "p"): "paid", ("new", "c"): "cancel", ("paid", "s"): "ship", ("paid", "c"): "wait",
     ("ship", "d"): "done", ("done", "r"): "refund", ("wait", "r"): "refund"}  # rest: "dead"
ACC = {"done", "cancel", "refund"}               # a closed order
step = lambda q, a: T.get((q, a), "dead"); mq = {}
def member(w):                                   # membership query (answers cached)
    if w not in mq:
        q = "new"
        for a in w: q = step(q, a)
        mq[w] = q in ACC
    return mq[w]
row = lambda s: tuple(member(s + e) for e in E)
def equivalence(S):          # exact oracle: BFS over (hypothesis state, target state)
    start = (row(""), "new"); seen = {start: ""}; todo = deque([start])
    while todo:
        h, t = todo.popleft(); w = seen[h, t]
        if h[0] != (t in ACC): return w          # shortest string they disagree on
        for a in SIG:
            nxt = (row(next(s for s in S if row(s) == h) + a), step(t, a))
            if nxt not in seen: seen[nxt] = w + a; todo.append(nxt)
S, E, n_eq = [""], [""], 0
while True:
    rows = {row(s) for s in S}
    if new := next((s + a for s in S for a in SIG if row(s + a) not in rows), None):
        S.append(new); continue                  # table not closed
    if e := next((a + e for s1 in S for s2 in S for a in SIG for e in E if s1 < s2
                  and row(s1) == row(s2) and member(s1 + a + e) != member(s2 + a + e)), None):
        E.append(e); continue                    # table not consistent
    n_eq += 1; cex = equivalence(S)
    print(f"EQ {n_eq}: |S|={len(S)} |E|={len(E)} states={len(rows)} counterexample={cex!r}")
    if cex is None: break
    S += [cex[:i] for i in range(1, len(cex) + 1) if cex[:i] not in S]
print("membership queries:", len(mq), "| E =", E)

আসল আউটপুট (ব্রাউজারের Python):

EQ 1: |S|=2 |E|=1 states=2 counterexample='pc'
EQ 2: |S|=4 |E|=3 states=4 counterexample='psd'
EQ 3: |S|=6 |E|=4 states=6 counterexample='sd'
EQ 4: |S|=8 |E|=5 states=7 counterexample=None
membership queries: 173 | E = ['', 'c', 'r', 'cr', 'd']

চারটি equivalence query, প্রতিবার state বেড়েছে (২ → ৪ → ৬ → ৭), ঠিক উপপাদ্য ৬.২-এর মতো। প্রথম hypothesis “c পড়লেই বন্ধ” ভেবেছিল, তাই counterexample pc: টাকা দেওয়ার পর বাতিলে ফেরত টাকা বাকি। শেষে ৭টি state, ৮টি নয়: cancel আর refund-এর পরে কোনো ঘটনাই বৈধ নয় আর দুটিই গ্রহণকারী, তাই একই Nerode class (পর্ব ১৯-এর minimisation এখানে বিনা চেষ্টায় এল)। E-এর suffix-গুলো একেকটি “পরীক্ষা”: যেমন cr আলাদা করে paid-কে, কারণ শুধু paid থেকে c তারপর r দিলে অর্ডার বন্ধ হয়।

L* যে minimal DFA শিখল

দ্বৈত বৃত্ত = বন্ধ অর্ডার (গ্রহণ)। দেখানো হয়নি এমন প্রতিটি তীর একটি dead state-এ যায়, যা এখানে আঁকা হয়নি।

Minimal DFA for the order-status language learned by L* newpaidship donewaitclosed psd crr c বন্ধ = বাতিলবা ফেরত
ছবি ৭৯.১ — L*-এর শেখা ৭-state DFA, dead state বাদে ৬টি আঁকা। লক্ষ্য-যন্ত্রের cancel আর refund এখানে একটি state “closed”, কারণ কোনো suffix এদের আলাদা করে না।

সত্যিকারের run: প্রশিক্ষিত LSTM থেকে DFA বের করা। এবার membership-এর উত্তরদাতা আর কোনো জানা DFA নয়, অংশ ৫-এর parity-তে শেখানো LSTM (seed 0) নিজে: “w-এর শেষ অবস্থানে network কী বলে?” Equivalence query-র সঠিক উত্তর এখানে কেউ জানে না, তাই তা অনুমানে করা হলো: ১–৬০ দৈর্ঘ্যের ২,০০০টি এলোমেলো string-এ hypothesis আর network মেলানো (এটি নিশ্চয়তা দেয় না, শুধু আস্থা)। এই কৌশলের নাম automata extraction; Weiss, Goldberg আর Yahav ২০১৮ সালে L*-কে এভাবে RNN-এর ওপর ব্যবহার করেন। একই প্রকল্পে, একই PyTorch আর Python:

~/bazarghar-toc$ python extract.py
EQ 1: states=2 counterexample=None
membership queries to the LSTM: 1878, random equivalence tests: 2000
extracted DFA vs true parity, all 8190 strings of length 1..12: 8190 agree
cell unit 0: |correlation with depth| = 0.999
string: ((()(()))(((()))))
depth :     1     2     3     2     3     4     3     2     1     2     3     4     5     4     3     2     1     0
cell  : -0.13 -1.07 -2.03 -1.07 -2.04 -3.01 -2.07 -1.11 -0.16 -1.11 -2.09 -3.07 -4.05 -3.10 -2.15 -1.20 -0.25  0.72

প্রথম hypothesis-ই ২,০০০টি পরীক্ষা পার করেছে: ২-state DFA, আর ১–১২ দৈর্ঘ্যের সব ৮,১৯০টি string-এ আসল parity-র সঙ্গে হুবহু মেলে। ১,৮৭৮টি আলাদা string-এর প্রশ্নের প্রায় সবই এসেছে random পরীক্ষা থেকে; L*-এর নিজের টেবিলে লেগেছে হাতে গোনা কয়েকটি। শেষ তিন লাইন অংশ ৩-এর stepper-এর উৎস। Dyck-1-এর LSTM থেকে এভাবে DFA বের করতে চাইলে প্রতিবার আরও গভীর counterexample আসত আর hypothesis বড় হতে থাকত, কারণ লক্ষ্যটি regular নয়; তখন L* একটি নির্দিষ্ট গভীরতা পর্যন্ত সঠিক regular আসন্ন-রূপই দিতে পারে।

৭ · Grammar-constrained decoding — automaton দিয়ে output বাঁধা

Network-এর ভেতরে counter না থাকলেও বাইরে থেকে একটি automaton বসিয়ে output-এর format নিশ্চিত করা যায়। একটি language model প্রতিটি ধাপে সব token-এর logits দেয়, তারপর softmax থেকে একটি token বাছা হয়। Grammar-constrained decoding-এ পাশে একটি DFA (regex-এর জন্য) বা PDA (grammar-এর জন্য) চলে। বর্তমান state q-তে যে token-এর অক্ষরগুলো পড়লে DFA dead state-এ যায়, তার logit −∞ করে দেওয়া হয়; শেষ-চিহ্ন (<eos>) অনুমোদিত শুধু গ্রহণকারী state-এ।

একটি সূক্ষ্মতা আছে: model-এর token আর DFA-র অক্ষর এক নয়। একটি tokenizer-এর token “G-0” একসঙ্গে তিনটি অক্ষর, তাই DFA-কে তিন ধাপ চালিয়ে দেখতে হয়। নিচের stepper-এ বাজারঘরের অর্ডার কোড BG- আর চারটি অঙ্ক তৈরি হচ্ছে, ১৪টি token-এর একটি খেলনা ভান্ডার থেকে। DFA-র state q = এ পর্যন্ত মেলা অক্ষরের সংখ্যা (০–৭)।

1B2BG-03BG-024BG-02425BG-0242 + শেষ
এই ধাপে
DFA-র state
অনুমোদিত token
বাছা হলো
  1. শুরুর state 0. প্রথম অক্ষর B হতেই হবে। ১৪টি token-এর মধ্যে শুধু B, BG আর BG- B দিয়ে শুরু হয়ে DFA-কে বাঁচিয়ে রাখে। Model এলোমেলোভাবে B বাছল; state 1.
  2. State 1-এ। এখন G লাগবে। G আর G-0 দুটিই চলে; BG চলে না, কারণ তার প্রথম অক্ষর B. “G-0” বাছা হলো: G, -, 0 তিনটি অক্ষর একসঙ্গে, state 1 থেকে 4.
  3. State 4-এ। বাকি তিনটি অঙ্ক। এক বা দুই অঙ্কের সব token (0, 4, 2, 00, 42, 7) অনুমোদিত, কারণ দুই অঙ্কের পরেও সীমা 7 পেরোয় না। 2 বাছা হলো; state 5.
  4. State 5-এ। আরও দুটি অঙ্ক বাকি, তাই এখনো ৬টি token চলে। (State 6-এ দুই অঙ্কের token বাদ পড়ত।) 42 বাছা হলো, state 5 থেকে 7.
  5. State 7, গ্রহণকারী। আর কোনো অক্ষর চলে না, তাই শুধু <eos> বাকি। লেখা BG-0242, যা regex BG-\d{4} মানে। শুরু থেকেই অবৈধ পথ বন্ধ ছিল বলে এটি নিশ্চিত, ভাগ্যের ব্যাপার নয়।
# Constrained generation: a toy "model" may only pick tokens that keep the DFA alive
import random, re
VOCAB = ["B", "G", "BG", "BG-", "-", "0", "4", "2", "00", "42", "7", "x", "G-0", "<eos>"]
def delta(q, ch):            # DFA for "BG-" + 4 digits; state q = characters matched so far
    if q < 3: return q + 1 if ch == "BG-"[q] else None       # None = dead state
    return q + 1 if q < 7 and ch.isdigit() else None
def run(q, tok):             # feed every character of a token to the DFA
    for ch in tok:
        if q is None: break
        q = delta(q, ch)
    return q
def allowed(q):              # the mask: <eos> only in the accept state 7
    return [t for t in VOCAB if (q == 7 if t == "<eos>" else run(q, t) is not None)]
def generate(rng, constrained, show=False):
    q, text = 0, ""
    for _ in range(10):
        options = allowed(q) if constrained else VOCAB
        tok = rng.choice(options)          # uniform "logits" over the unmasked tokens
        if show: print(f"  state {q}: {len(options):2} of {len(VOCAB)} allowed -> {tok}")
        if tok == "<eos>": break
        text += tok; q = run(q, tok) if constrained else q
    return text
rng = random.Random(79)
print("one constrained run:"); print("  result:", generate(rng, True, show=True))
for c in (False, True):
    outs = [generate(rng, c) for _ in range(1000)]
    ok = sum(bool(re.fullmatch(r"BG-\d{4}", s)) for s in outs)
    print(f"{'constrained' if c else 'free':11}: {ok:4} of 1000 valid, e.g. {outs[:3]}")

আসল আউটপুট (ব্রাউজারের Python):

one constrained run:
  state 0:  3 of 14 allowed -> B
  state 1:  2 of 14 allowed -> G-0
  state 4:  6 of 14 allowed -> 2
  state 5:  6 of 14 allowed -> 42
  state 7:  1 of 14 allowed -> <eos>
  result: BG-0242
free       :    0 of 1000 valid, e.g. ['BG-BG-xx2BGG0BBG-', 'Gx2x-BG42', 'x042']
constrained: 1000 of 1000 valid, e.g. ['BG-0027', 'BG-0072', 'BG-0242']

প্রথম অংশ stepper-এর সঙ্গে হুবহু মেলে। বাঁধনহীন খেলনা model ১,০০০ বারে একবারও বৈধ কোড দেয়নি; বাঁধা অবস্থায় ১,০০০-এ ১,০০০. Model একই, পার্থক্য শুধু DFA-র mask-এ।

বাস্তবে তিনটি কথা মনে রাখুন। প্রথম, প্রতিটি DFA state-এর জন্য অনুমোদিত token-এর তালিকা আগেই একবার হিসাব করে রাখা যায়, কারণ DFA সসীম; regex থেকে এভাবে mask বানানোর কাজ Outlines-এর মতো library-তে আর llama.cpp-এর GBNF grammar-এ দেখা যায় বলে পরিচিত (বিস্তারিত তাদের নথিতে মিলিয়ে নিন)। দ্বিতীয়, JSON-এর মতো nested format-এ DFA যথেষ্ট নয়; একটি PDA-র stack লাগে (পর্ব ৩২), আর তখন mask stack-এর অবস্থার ওপরও নির্ভর করে। তৃতীয়, mask format নিশ্চিত করে, অর্থ নয়: BG-0242 সঠিক আকারের, কিন্তু সত্যিকারের অর্ডার কি না, তা কোনো automaton বলতে পারে না। আর প্রতিটি ধাপে আলাদা করে mask করলে model-এর মূল সম্ভাব্যতা বণ্টন একটু বিকৃত হয়; “বৈধ string-এর ওপর শর্তসাপেক্ষ বণ্টন” থেকে নমুনা নেওয়া আলাদা, কঠিনতর সমস্যা।

৮ · Tokenizer — BPE একটি rewriting system

Language model লেখা দেখে না, দেখে token. আধুনিক tokenizer-এর বড় অংশ BPE (byte pair encoding)-এর ওপর দাঁড়ানো: মূলত Philip Gage-এর ১৯৯৪ সালের data compression-এর পদ্ধতি, যা Rico Sennrich আর সহকর্মীরা ২০১৬ সালের দিকে machine translation-এ subword বানাতে ব্যবহার করেন (বিস্তারিত ডিপ লার্নিং কোর্সের পর্ব ৪০-এ)। Training-এ সবচেয়ে ঘন ঘন পাশাপাশি আসা জোড়াকে একটি নতুন চিহ্নে জোড়া হয়, আর প্রতিটি জোড়া একটি নিয়ম হয়ে থাকে। নতুন লেখা tokenize করা মানে নিয়মগুলো শেখার ক্রমে, বাঁ থেকে ডানে প্রয়োগ করা: এটি একটি নির্ধারিত string-rewriting system.

# BPE as rewriting: learn merge rules, then tokenize new text by applying them in order
from collections import Counter
def apply(seq, a, b, new):                 # rewrite every non-overlapping "a b" (left to right)
    out, i = [], 0
    while i < len(seq):
        if i + 1 < len(seq) and seq[i] == a and seq[i + 1] == b:
            out.append(new); i += 2
        else:
            out.append(seq[i]); i += 1
    return out
seq, rules = list("aaabdaaabac"), []
for new in "ZYX":                          # learn at most three merges
    (a, b), n = Counter(zip(seq, seq[1:])).most_common(1)[0]
    if n < 2: break
    rules.append((a, b, new)); seq = apply(seq, a, b, new)
    print(f"learn rule {a}{b} -> {new}: {' '.join(seq)}")
def tokenize(text):
    seq = list(text)
    for a, b, new in rules: seq = apply(seq, a, b, new)
    return seq
def expand(tok):                           # undo the rules: tokens back to text
    for a, b, new in reversed(rules): tok = tok.replace(new, a + b)
    return tok
for w in ["aaab", "aaaab", "baaab", "dab"]:
    toks = tokenize(w)
    print(f"{w:6} -> {toks}  back: {''.join(map(expand, toks))}")

আসল আউটপুট (ব্রাউজারের Python):

learn rule aa -> Z: Z a b d Z a b a c
learn rule Za -> Y: Y b d Y b a c
learn rule Yb -> X: X d X a c
aaab   -> ['X']  back: aaab
aaaab  -> ['Z', 'Z', 'b']  back: aaaab
baaab  -> ['b', 'X']  back: baaab
dab    -> ['d', 'a', 'b']  back: dab

তিনটি নিয়ম শেখা হলো: aa → Z, Za → Y, Yb → X. (সমান গণনায় কোন জোড়া আগে আসবে তা নিয়মের ওপর নির্ভর করে; এখানে প্রথমে দেখা জোড়া।) লক্ষ করুন aaaab: ভেতরে “aaab” থাকলেও tokenization [X] দিয়ে শুরু হয় না, হয় [Z, Z, b], কারণ বাঁ থেকে aa আগে জোড়া লেগে যায়। একই অক্ষর-ক্রম প্রসঙ্গভেদে ভিন্ন token পায়। আর “back” কলাম দেখায় নিয়ম উল্টে দিলে লেখা হুবহু ফেরে: কিছু হারায় না।

এটি formal language-এর চোখে গুরুত্বপূর্ণ দুটি কারণে। প্রথম, কয়েকটি সাম্প্রতিক গবেষণায় দেখানো হয়েছে যে একটি নির্দিষ্ট merge-তালিকার BPE tokenizer-কে একটি finite-state transducer হিসেবে লেখা যায় (পর্ব ১২); তখন “এই regex মানা লেখার সব tokenization” নিজেই একটি regular language, যা constrained decoding-এ token আর অক্ষরের অমিল মেটাতে কাজে লাগে। এর সঠিক শর্ত আর আকার মূল প্রবন্ধে মিলিয়ে নিন। দ্বিতীয়, অংশ ১–৫-এর পরীক্ষাগুলো অক্ষর-স্তরে, কিন্তু বাস্তবের model token-স্তরে দেখে: “strawberry-তে কয়টি r” ধরনের গোনার কাজে model-কে token-এর ভেতরের অক্ষর আলাদা করে জানতে হয়, যা সে সরাসরি দেখে না। তাই কোনো model-এর formal language-ক্ষমতা মাপতে tokenization-ও পরীক্ষার অংশ।

আরও গভীরে: উদাহরণ থেকে automaton শেখা query ছাড়া অনেক কঠিন। E. Mark Gold ১৯৬৭ সালে দেখান, শুধু ইতিবাচক উদাহরণ দেখে regular language-এর পুরো শ্রেণিকে “সীমায়” চেনা যায় না, আর ১৯৭৮ সালে দেখান, দেওয়া উদাহরণের সঙ্গে মেলে এমন সবচেয়ে ছোট DFA খোঁজা NP-hard. Michael Kearns আর Leslie Valiant (১৯৮৯ সালের দিকে) দেখান, শুধু এলোমেলো উদাহরণ থেকে DFA শেখা (PAC অর্থে) cryptography-র কিছু অনুমান সত্য হলে কঠিন (পর্ব ৭৬-এর one-way function-এর আত্মীয়)। L* এই দেয়াল পেরোয় শুধু কারণ সে নিজে প্রশ্ন বাছতে পারে।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন আসে:

  • সসীম precision-এর RNN কোন শ্রেণির language চেনে? শুধু regular; পৌঁছানো hidden state সসীম, তাই একটি DFA, আর Myhill–Nerode-এ class ≤ state.
  • L*-এর দুই রকম query কী? Membership (w ∈ L?) আর equivalence (H = L? না হলে counterexample); বড়জোর n-টি equivalence query.
  • Observation table closed আর consistent মানে কী? Closed: প্রতিটি row(sa) S-এর কোনো সারির সমান; consistent: সমান সারির এক-চিহ্নের বর্ধিত সারিও সমান।
  • Constrained decoding-এ একটি token কখন অনুমোদিত? বর্তমান DFA state থেকে token-এর সব অক্ষর পড়ে dead state-এ না গেলে; <eos> শুধু গ্রহণকারী state-এ।
  • Dyck-1-এর জন্য ন্যূনতম কোন যন্ত্র? একটি one-counter automaton; একাধিক রকম বন্ধনীতে stack-সহ PDA.

৯ · AI-এর যুগে formal language আর neural network

এই বিষয়ে AI assistant-এর ভুলগুলো চেনা। গবেষণার ফলকে শর্ত ছাড়া বলা (“transformer parity পারে না”, অথচ ফলটি নির্দিষ্ট precision আর মডেলে; বা “RNN Turing-complete”, অথচ তা অসীম precision ধরে), প্রবন্ধের নাম বা সাল বানিয়ে দেওয়া, training-এর দৈর্ঘ্যে ১০০% দেখে “language শিখে ফেলেছে” বলা, একটি seed-এর ফল দিয়ে সিদ্ধান্ত, L*-এ consistency check বাদ দেওয়া বা counterexample-এর prefix যোগ করতে ভুলে যাওয়া, আর constrained decoding-এ token-কে একটি অক্ষর ধরে mask বানানো। এর সঙ্গে এই কোর্সের পুরোনো ভুলগুলোও আসে: ভুল language চেনা DFA, ε বা খালি string ভুলে যাওয়া, dead state বাদ দেওয়া, আর খোলা প্রশ্নকে মীমাংসিত বলা।

ভালো ব্যবহার: AI-কে পরীক্ষার নকশা আর কোড লিখতে দিন, কিন্তু প্রতিটি গবেষণা-দাবির অনুমান আর উৎস চান, আর ফলাফল নিজে বহু seed আর লম্বা দৈর্ঘ্যে চালিয়ে দেখুন।

আমি গণনার তত্ত্ব শিখছি। একটি ছোট LSTM আর একটি ছোট transformer-কে Dyck-1 আর parity-তে শেখাতে চাই, শুধু CPU-তে। ১. PyTorch-এ কোড লেখো: প্রতিটি অবস্থানে লেবেল, training দৈর্ঘ্য ১–৪০, পরীক্ষা ৪১–৮০ আর ৮১–১৬০, তিনটি seed. একটি string ঠিক ধরবে শুধু তখন, যখন সব অবস্থান ঠিক। ২. প্রতিটি লেবেল একটি আলাদা সরল Python function দিয়েও হিসাব করো, আর দুটি মিলিয়ে দেখার কোড দাও। ৩. Angluin-এর L* লেখো (closed আর consistent দুটি check-ই), আর ছোট একটি DFA-তে brute force দিয়ে শেখা DFA মেলাও। ৪. প্রতিটি গবেষণা-দাবির পাশে লেখক, সাল আর অনুমান (precision, model-এর ধরন) লেখো। নিশ্চিত না হলে বলো, কোনো প্রবন্ধ বানিয়ো না। ৫. কোনটি প্রমাণিত উপপাদ্য আর কোনটি শুধু পরীক্ষার পর্যবেক্ষণ, আলাদা করে লেখো।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১একই RNN সম্পর্কে একটি ফল বলে “Turing machine-এর সমান”, আরেকটি বলে “শুধু finite automaton”. দুটি কীভাবে একসঙ্গে সত্য, আর কোনটি বাস্তবের জন্য প্রাসঙ্গিক?

দুটি ফলের পার্থক্য একটিমাত্র অনুমানে: একটি সংখ্যায় কত তথ্য রাখা যায়। Siegelmann আর Sontag-এর নির্মাণে একটি unit-এর মান একটি মূলদ সংখ্যা, যার দশমিকের পরের অঙ্কগুলো একটি পুরো stack. “push 1” মানে সংখ্যাটিকে একটি ভিত্তি দিয়ে ভাগ করে একটি অঙ্ক যোগ করা, “pop” মানে গুণ করে প্রথম অঙ্ক ছেঁটে ফেলা। দুটি এমন stack দিয়ে একটি Turing machine অনুকরণ করা যায়, যেমন পর্ব ৪৫-এর রূপভেদের যুক্তিতে দুই-stack যন্ত্র Turing machine-এর সমান। কিন্তু এর জন্য precision-কে input-এর দৈর্ঘ্যের সঙ্গে সীমাহীনভাবে বাড়তে হয়, আর গণনার প্রতিটি ধাপ নিখুঁত হতে হয়।

উপপাদ্য ২.১-এর অনুমান উল্টো: hidden state-এর সম্ভাব্য মান সসীম। 32-bit float-এ এটি আক্ষরিকভাবে সত্য, তাই কঠোর অর্থে প্রতিটি বাস্তব RNN একটি DFA. কিন্তু সেই DFA-র state-সংখ্যা জ্যোতির্বৈজ্ঞানিক, তাই “শুধু DFA” কথাটি ব্যবহারিক সীমা খুব ভালো ধরে না। এজন্য গবেষকেরা মাঝামাঝি মডেল আনেন: saturated network, যেখানে activation সীমায় পৌঁছে যায়; অথবা log n bit-এর precision, যা দৈর্ঘ্যের সঙ্গে ধীরে বাড়ে। Saturated মডেলে tanh-RNN আর GRU-র ক্ষমতা সসীম automaton-এর, কিন্তু LSTM-এর cell state যোগের পথে বাড়ে বলে counter রাখতে পারে; এই পার্থক্যটি পরীক্ষাতেও দেখা গেছে বলে Weiss, Goldberg আর Yahav ২০১৮ সালে জানান।

বাস্তবের জন্য প্রশ্নটি তাই “কত দূর পর্যন্ত নির্ভুল”: অংশ ৫-এর LSTM ৪০ দৈর্ঘ্যে শিখে ১৬০-এ প্রায় ৯০% Dyck-1 ঠিক রেখেছে, কিন্তু cell-এর মান ধীরে সরে যাচ্ছিল। একই সঙ্গে মনে রাখুন, প্রকাশক্ষমতার উপপাদ্য বলে কোন weight আছে; gradient descent তা খুঁজে পাবে কি না, তা আলাদা প্রশ্ন, আর Turing-complete নির্মাণের weight training-এ স্বাভাবিকভাবে আসে না।

মূল উপলব্ধি: RNN-এর শক্তি precision-এর অনুমানের ওপর নির্ভর করে: অসীম precision-এ Turing-সমান, সসীম precision-এ একটি (বিশাল) DFA, আর বাস্তবে প্রাসঙ্গিক প্রশ্ন হলো শেখা নিয়ম কত দৈর্ঘ্য পর্যন্ত টেকে।

প্র ০২একটি model training-এর দৈর্ঘ্যে ১০০% পেল। “এটি language-টি শিখেছে” বলার আগে কী কী দেখা দরকার, আর এমন পরীক্ষার ফল লিখতে কী কী জানাতে হবে?

Training দৈর্ঘ্যের ১০০% একটি সসীম language-এর সাফল্য: ১–৪০ দৈর্ঘ্যের string-এর set সসীম, তাই একটি যথেষ্ট বড় lookup table-ও তা পারে। অংশ ৫-এ sinusoidal transformer Dyck-1-এ ঠিক এমন করেছে: ১–৪০-এ ১০০%, ৮১–১৬০-এ ৫.৫–৪২%. সত্যিকারের প্রশ্ন হলো, model এমন একটি নিয়ম শিখেছে কি না যা সব দৈর্ঘ্যে খাটে, আর তার একমাত্র পরীক্ষা হলো training-এর বাইরের দৈর্ঘ্য, বিশেষত গভীরতার মতো কঠিনতা-মাপকাঠি যা training-এ আসেনি।

দ্বিতীয়, seed. একই setup-এ anbn-এ positional encoding-হীন transformer দুটি seed-এ ১০০% আর একটিতে ২০% দিয়েছে। শুধু সেরা seed দেখালে ছবি বিকৃত হয়। Delétang আর সহকর্মীদের বড় পরীক্ষার মতো কাজে তাই অনেক seed আর hyperparameter চালিয়ে সেরা আর গড় দুটিই দেখানো হয়, আর প্রশ্নটি স্পষ্ট করা হয়: “কোনো একটি run কি সাধারণীকরণ করে?” আর “সাধারণত করে কি?” আলাদা প্রশ্ন।

তৃতীয়, লেবেল আর মূল্যায়নের নিয়ম। অবস্থান-ভিত্তিক নির্ভুলতা সহজেই ৯৯% দেখায়, কারণ বেশিরভাগ অবস্থান সহজ; আমরা তাই পুরো string-এর নির্ভুলতা ধরেছি। লেবেল-function নিজে brute force দিয়ে মেলানো দরকার, কারণ ভুল লেবেলে শেখা model “ভুল language”-টাই নিখুঁতভাবে শিখবে। Tokenization-ও উল্লেখ করা দরকার, কারণ অক্ষর-স্তর আর token-স্তরের পরীক্ষা আলাদা কাজ।

তাই একটি ভালো প্রতিবেদনে থাকে: model-এর আকার আর ধরন, positional encoding, training-এর দৈর্ঘ্য আর ডেটার পরিমাণ, পরীক্ষার দৈর্ঘ্য, মূল্যায়নের মাপ, seed-এর সংখ্যা আর প্রতিটির ফল, আর software-এর version. এ পর্বের run ঠিক এগুলো জানিয়েছে, আর তবু নিজেকে “একটি ছোট setup” বলেছে।

মূল উপলব্ধি: Training দৈর্ঘ্যে নিখুঁত হওয়া একটি সসীম language শেখার প্রমাণ মাত্র; language শেখার দাবি লম্বা দৈর্ঘ্যে, একাধিক seed-এ আর যাচাই করা লেবেলে পরীক্ষা চায়, আর প্রতিটি অনুমান লিখে রাখতে হয়।

প্র ০৩L* polynomial সংখ্যক query-তে DFA শেখে, অথচ উদাহরণ থেকে সবচেয়ে ছোট DFA খোঁজা NP-hard. এই দুটি কীভাবে মেলে, আর প্রশিক্ষিত network-এর ক্ষেত্রে equivalence query-র কী হয়?

পার্থক্য তথ্যের উৎসে। Gold-এর ১৯৭৮ সালের ফলে শিক্ষার্থী একটি স্থির উদাহরণ-set পায়, যা অন্য কেউ বেছেছে; সেখান থেকে সবচেয়ে ছোট সংগত DFA খোঁজা একটি combinatorial খোঁজ, যা NP-hard. Kearns আর Valiant-এর ফল আরও শক্ত: এলোমেলো উদাহরণ থেকে DFA শেখা কিছু cryptographic অনুমানে কঠিন, কারণ একটি সহজে শেখা যায় এমন DFA-শ্রেণি দিয়ে গোপন চাবির function অনুকরণ করা যেত। L*-এ শিক্ষার্থী নিজে প্রশ্ন বাছে: ঠিক যে suffix দুটি prefix-কে আলাদা করবে, তা জিজ্ঞেস করে। এই “minimally adequate teacher” মডেলে Myhill–Nerode-এর class একটি একটি করে উন্মোচিত হয়, আর কাজ polynomial হয়।

দাম লুকিয়ে আছে equivalence query-তে। একটি জানা DFA-র সঙ্গে তুলনা সহজ (পর্ব ২০-এর product আর BFS, যা আমাদের Pyodide ব্লক করেছে)। কিন্তু প্রশিক্ষিত network-এর “language” আগে থেকে জানা নেই। তখন দুটি পথ: এলোমেলো নমুনায় পরীক্ষা (Angluin নিজেই দেখান, যথেষ্ট নমুনায় এটি PAC অর্থে প্রায়-সঠিক DFA দেয়), অথবা network-এর hidden state ভাগ করে hypothesis-এর সঙ্গে তুলনা, যেমন Weiss, Goldberg আর Yahav ২০১৮ সালে করেন। আমাদের extraction প্রথম পথে ২,০০০টি নমুনা নিয়েছে; ফল শক্তিশালী আস্থা, কিন্তু প্রমাণ নয়। Network যদি ৬১ দৈর্ঘ্যের কোনো বিরল string-এ ভুল করে, পরীক্ষা তা ধরবে না।

আরেকটি সূক্ষ্মতা: network-এর language regular না হলে L* থামে না, বা প্রতি counterexample-এ বড় হতে থাকে। তখন extraction একটি আসন্ন-রূপ দেয়, যা “এই দৈর্ঘ্য পর্যন্ত এই DFA network-এর মতো আচরণ করে” বলে। এর ব্যবহার আছে: network-এর লুকোনো ভুল খুঁজে পাওয়া, যেমন একটি counterexample যা দেখায় network কোথায় ভুল নিয়ম শিখেছে, আর এই একই ধারণা network protocol-এর আচরণ থেকে model শেখাতেও ব্যবহৃত হয়েছে।

মূল উপলব্ধি: নিজে প্রশ্ন বাছার ক্ষমতাই L*-কে উদাহরণ-ভিত্তিক শেখার NP-hard আর cryptographic দেয়াল পার করায়; network-এর ক্ষেত্রে equivalence query অনুমানে হয়, তাই extraction-এর ফল আস্থা দেয়, নিশ্চয়তা নয়।

প্র ০৪Grammar-constrained decoding output-এর format নিশ্চিত করে। তাহলে বাজারঘরের সব JSON কি এখন নির্ভুল? এই পদ্ধতির তাত্ত্বিক আর ব্যবহারিক সীমা কোথায়?

Format-এর নিশ্চয়তা সত্যিকারের: প্রতিটি ধাপে শুধু এমন token চলে, যার পরে গ্রহণকারী state-এ পৌঁছানোর পথ খোলা থাকে, তাই শেষ লেখা automaton-এর language-এ পড়বেই। কিন্তু এর জন্য একটি শর্ত লাগে, যা অনেকে ভুলে যান: প্রতিটি অ-dead state থেকে কোনো গ্রহণকারী state-এ পৌঁছানো যেতে হবে, আর model-এর token-ভান্ডারে সেই পথের token থাকতে হবে। নইলে decoding একটি কানাগলিতে আটকে যেতে পারে। Grammar-এর ক্ষেত্রে (PDA) একই শর্ত stack-সহ configuration-এর ওপর খাটে, আর তা প্রতিটি ধাপে হিসাব করতে parser-এর মতো কাঠামো (Earley বা LR-ধাঁচের) লাগে।

সীমা তিন স্তরে। প্রথম, অর্থ: “amount একটি সংখ্যা” automaton বলতে পারে, কিন্তু “amount অর্ডারের আসল দামের সমান” পারে না; সেটি একটি ডেটাবেস প্রশ্ন। আর “এই কোড সবসময় থামে” ধরনের শর্ত কোনো automaton দিয়েই চাপানো যায় না, কারণ তা undecidable (পর্ব ৫৩)। দ্বিতীয়, গুণমান: mask model-কে অবৈধ পথে যেতে দেয় না, কিন্তু model যদি ভুল পথে অনেক দূর এগিয়ে গিয়ে থাকে, তবে বৈধ-কিন্তু-অর্থহীন লেখায় আটকে যেতে পারে। প্রতিটি ধাপে আলাদা করে mask করা “বৈধ লেখার ওপর শর্তসাপেক্ষ বণ্টন” থেকে নমুনা নেওয়ার সমান নয়, আর এই বিকৃতি কমাতে গবেষণা চলছে। তৃতীয়, প্রকৌশল: বড় grammar আর বড় token-ভান্ডারে প্রতিটি ধাপে mask হিসাবের খরচ, আর token ও অক্ষরের অমিল (অংশ ৭-এর “G-0”) সামলানো।

তাই বাজারঘরের জন্য সঠিক নকশা স্তরে স্তরে: constrained decoding দিয়ে format নিশ্চিত, তারপর একটি সাধারণ validator দিয়ে আবার parse (দুই স্বাধীন যাচাই), তারপর ব্যবসার নিয়ম কোডে পরীক্ষা, আর সন্দেহজনক ক্ষেত্রে মানুষ।

মূল উপলব্ধি: Automaton দিয়ে বাঁধা decoding format-কে একটি regular বা context-free language-এ নিশ্চিত করে, কিন্তু অর্থ, ব্যবসার নিয়ম আর undecidable ধর্ম এর বাইরে, আর ধাপে ধাপে mask model-এর বণ্টন কিছুটা বদলায়।

প্র ০৫Tokenizer কেন formal language-এর প্রশ্ন? BPE-কে rewriting system বা transducer হিসেবে দেখলে কী লাভ, আর বাংলা লেখার মতো জটিল লিপিতে কী কী সতর্কতা দরকার?

Tokenizer হলো model আর লেখার মাঝের একটি function: Σ∗ থেকে token-ক্রমে। অংশ ৮-এর BPE এই function-কে ক্রমিক rewriting নিয়মে সংজ্ঞায়িত করে, আর দুটি ধর্ম সঙ্গে সঙ্গে দেখা যায়। এটি ক্ষতিহীন (নিয়ম উল্টালে লেখা ফেরে), কিন্তু compositional নয়: aaab একা [X], অথচ aaaab-এর ভেতরে থাকলে [Z, Z, b]. অর্থাৎ একটি শব্দের tokenization তার প্রতিবেশী অক্ষরের ওপর নির্ভর করে। Model-কে তাই একই অর্থের জিনিস ভিন্ন ভিন্ন token-ক্রমে চিনতে শিখতে হয়।

Transducer হিসেবে দেখার লাভ হলো, automaton-এর সব যন্ত্রপাতি পাওয়া যায়। Regular language-এর ওপর একটি finite-state transducer-এর প্রতিচ্ছবি আবার regular, তাই “BG-dddd মানে এমন সব লেখার সব সম্ভাব্য token-ক্রম”-কে একটি DFA হিসেবে গঠন করা যায়, আর constrained decoding সরাসরি token-এর ওপর চালানো যায়। একই যুক্তিতে দুটি tokenizer একই লেখাকে কোথায় আলাদা ভাঙে, তা পর্ব ২০-এর মতো decision-পদ্ধতিতে খোঁজা যায়। কয়েকটি সাম্প্রতিক গবেষণা এই দৃষ্টিভঙ্গি নিয়ে কাজ করেছে; সঠিক নির্মাণ আর আকার তাদের প্রবন্ধে দেখে নেওয়া উচিত।

বাংলা লিপিতে বাড়তি স্তর আছে। একটি দৃশ্যমান অক্ষর (যেমন যুক্তাক্ষর “ক্ষ” বা কার-চিহ্নসহ ব্যঞ্জন) কয়েকটি Unicode code point দিয়ে গড়া, আর byte-স্তরের BPE সেগুলো মাঝখান থেকে ভাঙতে পারে। তখন একটি token একটি অর্ধেক অক্ষর হতে পারে, আর অক্ষর-গোনা বা বানান-সংক্রান্ত কাজ model-এর জন্য আরও কঠিন হয়। Constrained decoding-এ এর অর্থ: mask-কে byte বা code point স্তরে automaton চালাতে হবে, দৃশ্যমান অক্ষরে নয়। এ বিষয়ে কোনো নির্দিষ্ট model-এর আচরণ নিয়ে সংখ্যা দাবি করার আগে নিজে মেপে দেখা উচিত।

মূল উপলব্ধি: BPE tokenizer ক্রমিক rewriting নিয়মের একটি ক্ষতিহীন কিন্তু অ-compositional function, যাকে transducer হিসেবে দেখলে automaton-এর যন্ত্রপাতি কাজে লাগে; বাংলার মতো লিপিতে token দৃশ্যমান অক্ষরের মাঝখানে পড়তে পারে, তাই যাচাই সবসময় byte-স্তর মাথায় রেখে।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। ওপরের Python ব্লকগুলোতে নিজের language বা নিয়ম বসিয়ে উত্তর যাচাইও করতে পারেন।

  1. নকশা: সসীম precision-এর একটি RNN বড়জোর একটি সীমাবদ্ধ গভীরতা পর্যন্ত Dyck-1 ঠিক রাখতে পারে। L2 = Σ = {(, )}-এর ওপর সুষম string, যাদের গভীরতা কখনো ২ ছাড়ায় না (ε সহ)। L2-এর একটি complete DFA নকশা করুন, আর Myhill–Nerode দিয়ে দেখান এটি minimal. তারপর পুরো Dyck-1-এর জন্য একটি one-counter automaton-এর নিয়ম লিখুন।

    DFA: state q0 (গভীরতা ০, গ্রহণ ও শুরু), q1, q2, আর dead qd. δ(q0, ( ) = q1, δ(q0, ) ) = qd; δ(q1, ( ) = q2, δ(q1, ) ) = q0; δ(q2, ( ) = qd, δ(q2, ) ) = q1; qd দুই চিহ্নেই qd. মোট ৪টি state.

    Minimal: চারটি string ε, (, ((, ) জোড়ায় জোড়ায় আলাদা। ε বনাম ( বা ((: suffix ε (শুধু ε গ্রহণ)। ( বনাম ((: suffix “)” দিলে “()” ∈ L2, “(()” ∉. যেকোনো একটি বনাম ): “)” থেকে কোনো suffix-এ গ্রহণ নেই, অন্যদের আছে (যেমন ( -এর জন্য “)”)। তাই অন্তত ৪টি Nerode class, আর DFA-তে ৪টি state: minimal. (Scratch-এ ৬ পর্যন্ত দৈর্ঘ্যের prefix আর suffix দিয়ে brute force-এ ঠিক ৪টি class পাওয়া গেছে।)

    One-counter automaton: counter c = 0 দিয়ে শুরু; “(” পড়লে c ← c + 1; “)” পড়লে c = 0 হলে বাতিল, নইলে c ← c − 1; শেষে c = 0 হলে গ্রহণ। L2-এর DFA এরই সেই রূপ, যেখানে c ২-এর বেশি হলেই বাতিল।

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “PyTorch-এর LSTM-এর hidden state ৩২টি float32, তাই সম্ভাব্য state সসীম, তাই উপপাদ্য ২.১ অনুযায়ী এটি একটি DFA, আর Dyck-1 regular নয়। কাজেই এই LSTM ১৬০ দৈর্ঘ্যের Dyck-1 string-এ ৫০%-এর বেশি ঠিক করতে পারে না। অংশ ৫-এর ৮৮–৯২.৫% তাই নিশ্চয়ই কোনো ভুল।” কোথায় ভুল?

    উপপাদ্য ২.১ ঠিক বলে: LSTM-এর language regular, তাই তা Dyck-1-এর সমান হতে পারে না; অর্থাৎ কোথাও না কোথাও অন্তত একটি string-এ ভুল আছে। কিন্তু “কোথাও একটি ভুল” থেকে “নির্দিষ্ট দৈর্ঘ্যে ৫০%-এর বেশি ভুল” আসে না। একটি DFA বড় একটি সীমা পর্যন্ত Dyck-1-এর সঙ্গে হুবহু মিলতে পারে: অংশ ২-এর JS ব্লকে K-তে আটকানো (K + 2)-state যন্ত্র 2K + 1 দৈর্ঘ্যের আগে কোনো ভুল করে না। আর 232·32-এর মতো সম্ভাব্য state-এর যন্ত্রে সেই সীমা বিশাল হতে পারে।

    ভুলটি তাই একটি অসমর্থিত লাফ: অসীম আচরণের উপপাদ্য থেকে একটি সসীম দৈর্ঘ্যের পরিসংখ্যান অনুমান। সঠিক উপসংহার: যথেষ্ট লম্বা (বা গভীর) string-এ এই LSTM অবশ্যই ভুল করবে, কিন্তু কোথা থেকে, তা শুধু পরীক্ষা বা network-এর বিশ্লেষণ বলতে পারে।

  3. Trace (আউটপুট অনুমান): L = Σ = {a, b}-এর ওপর “ab দিয়ে শেষ” string. L* চালান: S = E = {ε} দিয়ে শুরু, closed না হলে row(sa) যোগ, consistent না হলে suffix যোগ, আর equivalence query shortlex-এ সবচেয়ে ছোট counterexample দেয়, যার সব prefix S-এ যায়। প্রতিটি hypothesis-এর state কয়টি, counterexample কী, আর শেষে E কী? মোট কয়টি আলাদা string-এর membership query লাগে?

    শুরুতে row(ε) = row(a) = row(b) = 0: টেবিল closed আর consistent, hypothesis ১-state, সব বাতিল। Counterexample ab (সবচেয়ে ছোট গ্রহণযোগ্য string). S = {ε, a, ab}: সারি ε:0, a:0, ab:1. এখন ε আর a সমান, কিন্তু ε·b = b:0 আর a·b = ab:1, তাই consistent নয়: suffix “b” যোগ, E = {ε, b}.

    নতুন সারি ε:00, a:01, ab:10; বর্ধিত সারি b:00, aa:01, aba:01, abb:00, সবই S-এ আছে। Closed আর consistent, hypothesis ৩-state, আর equivalence query “হ্যাঁ”। এটি “ab দিয়ে শেষ”-এর minimal DFA (তিনটি state-এর অর্থ: শেষে কিছু মেলেনি, শেষে a, শেষে ab). Scratch-এ চালানো একই L*-এ মোট ১১টি আলাদা string: ε, a, b, aa, ab, bb, aab, aba, abb, abab, abbb.

  4. হিসাব: অংশ ৮-এর শেখা BPE নিয়ম ক্রমানুসারে aa → Z, Za → Y, Yb → X. (ক) “aaabaaab” আর “abaaa”-র tokenization কী? (খ) অংশ ৭-এর order-code DFA-র state 6-এ ১৪টি token-এর ভান্ডার থেকে কোন কোন token অনুমোদিত?

    (ক) aaabaaab: প্রথম নিয়মে বাঁ থেকে aa জোড়া লাগে: Z a b Z a b; দ্বিতীয়তে Y b Y b; তৃতীয়তে X X. ফল [X, X]. abaaa: a b a a a-তে aa একবার (অবস্থান ৩–৪), তারপর a: a b Z a; Za থেকে Y: a b Y; Yb নেই। ফল [a, b, Y]. দুটিই bpe_rules.py-র tokenize দিয়ে scratch-এ মেলানো।

    (খ) State 6-এ ঠিক একটি অঙ্ক বাকি। একক অঙ্কের token 0, 4, 2, 7 চলে (৪টি); 00 আর 42 বাদ, কারণ দ্বিতীয় অঙ্কে state 7 থেকে dead; অক্ষর-token আর <eos>-ও বাদ, কারণ 6 গ্রহণকারী নয়। মোট ১৪-র ৪টি।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমAngluin-এর L* algorithm-এর একটি চক্রের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. S = E = {ε} নিয়ে membership query দিয়ে টেবিল ভরা
  2. Closed না হলে অনুপস্থিত সারির string S-এ যোগ করা
  3. Consistent না হলে দুটি সমান সারিকে আলাদা করা suffix E-তে যোগ করা
  4. সারি থেকে hypothesis DFA বানিয়ে equivalence query করা
  5. Counterexample পেলে তার সব prefix S-এ যোগ করে আবার শুরু; না পেলে থামা

একটি RNN-এর hidden state-এ ৬৪টি unit, প্রতিটি 32-bit float. Weight স্থির রেখে যেকোনো দৈর্ঘ্যের input-এ এটি কোন শ্রেণির language চিনতে পারে?

  • শুধু regular language
  • সব context-free language
  • সব decidable language, কারণ RNN Turing-complete
  • কোনো অসীম language-ই নয়

L*-এর একটি observation table-এ Σ = {a, b}, E = {ε, a}, S = {ε, a}; সারি row(ε) = 10, row(a) = 01, আর বর্ধিত সারি row(b) = 00, row(aa) = 10, row(ab) = 00. পরের ধাপ কী?

  • টেবিল তৈরি, hypothesis DFA বানিয়ে equivalence query করা
  • টেবিল consistent নয়, একটি নতুন suffix যোগ করা
  • টেবিল closed নয়, b-কে S-এ যোগ করা
  • একটি counterexample-এর সব prefix S-এ যোগ করা

নিচের কোন language-এর জন্য একটি ২-state DFA যথেষ্ট, অথচ গবেষণা আর ছোট পরীক্ষায় transformer-এর জন্য এটি কঠিন বলে পরিচিত?

  • Dyck-1 (সুষম বন্ধনী)
  • PARITY: 1-এর সংখ্যা বিজোড়
  • anbn
  • {ww : w ∈ {0, 1}∗}

Grammar-constrained decoding-এ “BG-” আর চারটি অঙ্কের DFA চলছে, বর্তমান state = এ পর্যন্ত মেলা অক্ষর ৫টি। Token “42” কেন অনুমোদিত, আর “427” কেন নয়?

  • শুধু প্রথম অক্ষর দেখা হয়, আর “427” তিন অক্ষর বলে নিষিদ্ধ
  • দুই অক্ষরের বেশি token কখনো অনুমোদিত নয়
  • Model “427”-কে কম সম্ভাব্যতা দেয় বলে
  • “42” DFA-কে state 7-এ নেয়, “427”-এর শেষ অঙ্কে DFA dead state-এ যায়

একটি model anbn-এ n ≤ ২০-তে ১০০%, n = ৪১–৮০-তে ৪০% পেল (একটি seed). কোন সিদ্ধান্তটি সবচেয়ে যুক্তিসঙ্গত?

  • Model anbn শিখে ফেলেছে
  • এই architecture কখনো anbn সাধারণীকরণ করতে পারে না, প্রমাণিত
  • নিয়মটি লম্বা দৈর্ঘ্যে আংশিকভাবে খাটে; আরও seed আর দৈর্ঘ্যে পরীক্ষা ছাড়া সাধারণ দাবি করা যায় না
  • ফল প্রমাণ করে anbn regular

BPE নিয়ম ক্রমানুসারে aa → Z, Za → Y, Yb → X. “aaab” হয় [X], কিন্তু “aaaab” হয় [Z, Z, b]. এ থেকে tokenizer সম্পর্কে কী বোঝা যায়?

  • Tokenization compositional নয়: একটি অংশের token তার প্রতিবেশী অক্ষরের ওপর নির্ভর করে
  • Tokenizer তথ্য হারায়, তাই লেখা ফেরানো যায় না
  • BPE এলোমেলো, তাই একই লেখার ফল প্রতিবার বদলায়
  • “aaaab”-এ একটি অচেনা চিহ্ন আছে

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. প্রকাশক্ষমতা, শেখা আর length generalisation তিনটি আলাদা প্রশ্ন; প্রথমটির উত্তর উপপাদ্যে, বাকি দুটির উত্তর শর্তসাপেক্ষ পরীক্ষায়।
  2. পৌঁছানো hidden state সসীম হলে RNN একটি DFA, তাই শুধু regular language; Turing-সমান ফল অসীম precision ধরে। LSTM-এর cell state counter রাখতে পারে, আর আমাদের run-এ একটি cell Dyck-1-এর গভীরতা প্রায় হুবহু গুনেছে।
  3. Parity-র DFA দুই state-এর, কিন্তু প্রতিটি bit উত্তর উল্টায়; গড়-নেওয়া attention-এর জন্য এটি কঠিন বলে পরিচিত, আর ছোট transformer training দৈর্ঘ্যেই আটকে গেছে। প্রতিটি দাবি precision আর মডেলের অনুমানসহ পড়ুন।
  4. L* membership আর equivalence query দিয়ে observation table-কে closed আর consistent করে minimal DFA শেখে, বড়জোর n-টি equivalence query-তে; network-এর ক্ষেত্রে equivalence অনুমানে হয়।
  5. Constrained decoding প্রতিটি ধাপে DFA বা PDA-র state দেখে token বাদ দিয়ে format নিশ্চিত করে, অর্থ নয়; BPE tokenizer ক্রমিক rewriting নিয়ম, ক্ষতিহীন কিন্তু অ-compositional.

পরের পর্বে: পুরো কোর্স এক প্রকল্পে: বাজারঘরের অর্ডার কোড আর কুপনের minimised validator, order-query ভাষার lexer, grammar আর evaluator, model-checked অর্ডার-অবস্থার যন্ত্র, কোথায় undecidability বাধা দেয়, আর SAT solver দিয়ে delivery-র সময়সূচি (পর্ব ৮০ · ক্যাপস্টোন — বাজারঘরের জন্য formal language toolkit).

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান