Zipf's law, slide 10

قانون Zipf، الشريحة 10

Start with a procedure, not a formula. Take a corpus. Count how often every word occurs. Sort the list from most frequent down to least frequent. Now number the rows: the most frequent word is rank R = 1, the next is R = 2, and so on. Slide 10 states that first bullet exactly this way: sort words by frequency, rank R = 1 is most frequent.

ابدأ بإجراء لا بمعادلة. خذ corpus. عدّ كم مرة تظهر كل كلمة. رتّب القائمة من الأكثر تكراراً إلى الأقل. ثم رقّم الصفوف: الكلمة الأكثر تكراراً رتبتها R = 1، والتالية R = 2، وهكذا. والشريحة 10 تذكر البند الأول بهذه الطريقة تماماً: رتّب الكلمات حسب التكرار، والرتبة R = 1 هي الأكثر تكراراً.

Zipf's observation is about the shape of that sorted list. The frequency does not trail off gently. It collapses, and it collapses in a very regular way:

ملاحظة Zipf تتعلق بشكل هذه القائمة المرتبة. التكرار لا يتناقص بلطف، بل ينهار، وينهار بطريقة منتظمة جداً:

تُقرأ المعادلة: تكرار الكلمة في الرتبة R يتناسب مع واحد مقسوماً على R مرفوعة للأس α.

The slide's wording: frequency decreases roughly as a power law. Read the formula as a sentence. The frequency of the word in position R is proportional to one over R raised to some exponent α. Halve nothing, just move down the ranked list, and the frequency falls off a cliff.

عبارة الشريحة: التكرار يتناقص تقريباً وفق قانون قوة (power law). اقرأ المعادلة كجملة: تكرار الكلمة في الموضع R يتناسب مع واحد على R مرفوعة لأس ما هو α. لا تفعل شيئاً سوى أن تنزل في القائمة المرتبة، فيسقط التكرار من حافة جرف.

Slide 10's third bullet is the intuition in eight words: few words are extremely common, most are rare. The symbol ∝ means "proportional to", so the formula fixes the shape of the curve but not its height. The height is set by the corpus size.

البند الثالث في الشريحة 10 هو الحدس في ثماني كلمات: كلمات قليلة شائعة جداً، ومعظم الكلمات نادرة. والرمز ∝ يعني "يتناسب مع"، فالمعادلة تحدد شكل المنحنى لا ارتفاعه. والارتفاع يحدده حجم الـ corpus.

What α does

ماذا يفعل α

If α = 1, the law reads: the second most common word occurs about half as often as the first, the tenth about a tenth as often, the hundredth about a hundredth as often. That is the version worth carrying in your head because the arithmetic is trivial.

إذا كان α = 1 فالقانون يقول: الكلمة الثانية في الشيوع تظهر بنحو نصف مرات الأولى، والعاشرة بنحو عُشرها، والمئة بنحو جزء من مئة. هذه هي النسخة التي تستحق أن تحملها في رأسك لأن حسابها بديهي.

Real corpora sit near α = 1 but not exactly on it. The figure on slide 11 fits two reference power laws and prints their exponents: α = 0.9290 for English Wikipedia and α = 0.9252 for Arabic Wikipedia. Nearly identical, both just under 1, in two unrelated languages with completely different morphology. That robustness is the reason the law is taken seriously.

الـ corpora الحقيقية قريبة من α = 1 لكنها ليست عليها تماماً. شكل الشريحة 11 يطابق قانونَي قوة مرجعيين ويطبع أسّيهما: α = 0.9290 لويكيبيديا الإنجليزية وα = 0.9252 لويكيبيديا العربية. متطابقان تقريباً، وكلاهما أقل من 1 بقليل، في لغتين لا علاقة بينهما وصرفهما مختلف تماماً. وهذه المتانة هي سبب أخذ القانون بجدية.

The Zipf curve, slide 11

منحنى Zipf، الشريحة 11

Slide 11 is a figure captioned "Rank vs. frequency (Zipf's law)". Both axes are logarithmic, which is the key to reading it. Taking logs of f(R) ∝ 1/R^α gives:

الشريحة 11 شكل عنوانه "Rank vs. frequency (Zipf's law)". المحوران لوغاريتميان، وهذا مفتاح قراءته. أخذ اللوغاريتم لـ f(R) ∝ 1/R^α يعطي:

أي أن log f(R) يساوي −α مضروباً في log R زائد ثابت، وهذه معادلة خط مستقيم.

A power law becomes a straight line with slope −α on log-log axes. So the way you test Zipf's law is: plot it log-log, and check whether you get a straight line. The slide's figure plots three real datasets (English Wikipedia, Arabic Wikipedia, and an undotted Arabic Wikipedia variant) against two dotted reference lines, and they all run close to straight across roughly six decades of rank.

قانون القوة يصبح خطاً مستقيماً ميله −α على محاور log-log. فطريقة اختبار Zipf's law هي: ارسمه log-log وتحقق هل تحصل على خط مستقيم. يرسم شكل الشريحة ثلاث مجموعات بيانات حقيقية (ويكيبيديا الإنجليزية، وويكيبيديا العربية، ونسخة من ويكيبيديا العربية بلا نقاط) مقابل خطين مرجعيين منقطين، وكلها تسير قريبة من الاستقامة عبر نحو ست مراتب عشرية من الرتب.

في الرسم محور أفقي للرتبة R ومحور رأسي للتكرار، وكلاهما بمقياس لوغاريتمي. تبدأ النقطة R = 1 (أكثر الكلمات تكراراً) في الأعلى يساراً، والخط المنقط هو قانون القوة الخالص بميل −α = −0.929. على محاور log-log يكون قانون القوة خطاً مستقيماً ميله −α. والمنحنى الحقيقي يتبع الخط المرجعي عبر عدة مراتب عشرية ثم يهبط في الذيل البعيد، حيث يصل التكرار إلى 1 ولا يمكنه النزول أكثر. وكل ما هو مسطّح على طول القاع هو كلمة ظهرت مرة واحدة بالضبط، وهذا هو الذيل الطويل (long tail) الذي تسكنه معظم الـ types.

f(R) = 10,000,000 / R^0.9290

R = 1       10^0.9290 = 1
            f = 10,000,000 / 1          = 10,000,000

R = 10      10^0.9290 = 8.4918
            f = 10,000,000 / 8.4918     =  1,177,606

R = 100     100^0.9290 = 10^1.858 = 72.11
            f = 10,000,000 / 72.11      =    138,676

R = 1000    1000^0.9290 = 10^2.787 = 612.3
            f = 10,000,000 / 612.3      =     16,331

R = 10000   10^3.716 = 5,200
            f = 10,000,000 / 5,200      =      1,923

R = 100000  10^4.645 = 44,157
            f = 10,000,000 / 44,157     =        226

Heaps' law, slide 12

قانون Heaps، الشريحة 12

Zipf described a corpus you already finished reading. Heaps describes what happens while you are still reading it.

Zipf وصف corpus انتهيت من قراءته. أما Heaps فيصف ما يحدث وأنت ما زلت تقرأ.

Slide 12's first bullet: as we see more tokens (N), we keep encountering new types (|V|). The question is at what rate, and the answer is called Heaps' law, or Herdan's law, and the slide gives both names:

البند الأول في الشريحة 12: كلما رأينا tokens أكثر (N) استمررنا في مصادفة types جديدة (|V|). والسؤال بأي معدل، والجواب يسمى Heaps' law أو Herdan's law، والشريحة تذكر الاسمين معاً:

تُقرأ المعادلة: |V| يساوي k مضروباً في N مرفوعة للأس β، بشرط 0 < β < 1.

Here N is the number of tokens read so far, |V| is the number of distinct types you have met, k is a constant that sets the scale, and β is the growth exponent. The parenthesis is part of the slide and it is the whole content of the law.

هنا N عدد الـ tokens المقروءة حتى الآن، و|V| عدد الـ types المميزة التي صادفتها، وk ثابت يحدد المقياس، وβ أس النمو. والشرط بين القوسين جزء من الشريحة، وهو مضمون القانون كله.

The slide's final bullet is the sentence to memorise: vocabulary growth is sublinear but unbounded. Both halves matter and they are easy to confuse.

البند الأخير في الشريحة هو الجملة التي يجب حفظها: نمو المفردات دون خطي (sublinear) لكنه غير محدود (unbounded). والنصفان كلاهما مهم، ومن السهل الخلط بينهما.

الجدول: sublinear يعبّر عنه الشرط β < 1، وهو يستبعد أن ينمو |V| بالتناسب مع N، فمضاعفة النص لا تضاعف المفردات. وunbounded يعبّر عنه الشرط β > 0، وهو يستبعد أن يستقر |V| يوماً عند سقف، فلا يوجد حجم corpus تتوقف عنده عن مصادفة كلمات جديدة.

If β were 1 the growth would be linear. If β were 0 then |V| = k, a constant, and vocabulary would be fixed from the first sentence. The condition 0 < β < 1 is exactly the statement that reality sits strictly between those two.

لو كان β يساوي 1 لكان النمو خطياً. ولو كان 0 لكان |V| = k ثابتاً، ولكانت المفردات محددة منذ الجملة الأولى. والشرط 0 < β < 1 هو بالضبط القول بأن الواقع يقع بين هاتين الحالتين تماماً.

The Heaps curve, slide 13

منحنى Heaps، الشريحة 13

Slide 13 is a figure captioned "Vocabulary size |V| as a function of N (Heaps' law)". It plots three fitted curves and prints the fitted parameters in the legend:

الشريحة 13 شكل عنوانه "Vocabulary size |V| as a function of N (Heaps' law)". يرسم ثلاثة منحنيات مُطابَقة ويطبع المعاملات المطابقة في مفتاح الرسم:

قيم الجدول: english_wiki فيها k = 14.947 وβ = 0.583. وarabic_wiki فيها k = 73.321 وβ = 0.533. وundotted_arabic_wiki فيها k = 90.491 وβ = 0.506.

All three β values are strictly between 0 and 1, exactly as slide 12 requires. Notice also that Arabic has the much larger k. We will see what that buys in the worked example below.

قيم β الثلاث كلها بين 0 و1 تماماً كما تشترط الشريحة 12. ولاحظ أيضاً أن العربية لها k أكبر بكثير. وسنرى ما الذي يعنيه ذلك في المثال المحلول أدناه.

في الرسم محور أفقي هو النص المقروء N ومحور رأسي هو المفردات |V|. المنحنى الملوّن هو |V| = k · N^β مع β = 0.583: ينحني، وهذا معنى sublinear. ولا يصبح أفقياً أبداً، وهذا معنى unbounded، وتشير العلامة عند طرفه إلى أنه ما زال يرتفع، والخط الأفقي المنقط في الأعلى يذكّر بأنه لا يوجد سقف. أما الخط المستقيم المتقطع فهو ما سيبدو عليه النمو الخطي، ويخرج من أعلى الرسم فوراً تقريباً.

|V| = 14.947 x N^0.583

N = 100,000        N^0.583 = 10^(5 x 0.583) = 10^2.915 =     822.2
                   |V| = 14.947 x 822.2     =     12,290

N = 1,000,000      N^0.583 = 10^(6 x 0.583) = 10^3.498 =   3,147.7
                   |V| = 14.947 x 3,147.7   =     47,049

N = 10,000,000     N^0.583 = 10^(7 x 0.583) = 10^4.081 =  12,050.0
                   |V| = 14.947 x 12,050    =    180,117

N = 100,000,000    N^0.583 = 10^(8 x 0.583) = 10^4.664 =  46,131
                   |V| = 14.947 x 46,131    =    689,531

  47,049 /  12,290 = 3.828
 180,117 /  47,049 = 3.828
 689,531 / 180,117 = 3.828

and     10^0.583  = 3.828      the same number, every time

                       English fit              Arabic fit
                   k=14.947, B=0.583       k=73.321, B=0.533

N =     100,000            12,290                  33,902
N =   1,000,000            47,049                 115,672
N =  10,000,000           180,117                 394,665
N = 100,000,000           689,531               1,346,568

growth per 10x N      10^0.583 = 3.828       10^0.533 = 3.412

Zipf versus Heaps, the comparison that gets examined

Zipf مقابل Heaps، المقارنة التي يُختبر عليها

They are easy to blur because both are power laws about the same corpus. Here is the difference in one line: Zipf describes how frequency is distributed over the words you already have. Heaps describes how fast new words keep arriving.

من السهل الخلط بينهما لأن كليهما قانون قوة عن الـ corpus نفسه. وهذا هو الفرق في سطر واحد: Zipf يصف كيف يتوزع التكرار على الكلمات التي لديك أصلاً. وHeaps يصف بأي سرعة تستمر الكلمات الجديدة في الوصول.

الجدول يقارن القانونين. المعادلة: f(R) ∝ 1/R^α مقابل |V| = k · N^β. المتغير الداخل: R رتبة الكلمة في القائمة المرتبة بالتكرار، مقابل N كمية النص المقروء. الخارج: f تكرار تلك الكلمة، مقابل |V| حجم المفردات حتى الآن. السؤال: كم يتفاوت التكرار بين الكلمات، مقابل بأي سرعة ينمو القاموس. موضع الأس: في المقام، فـ α أكبر تعني انهياراً أشد، مقابل في البسط، فـ β أكبر تعني نمواً أسرع للمفردات. الاتجاه: متناقص في R، مقابل متزايد في N. القيم المطابقة في الشرائح: α = 0.9290 للإنجليزية و0.9252 للعربية، مقابل β = 0.583 للإنجليزية و0.533 للعربية. وهل يقول شيئاً عن |V|؟ Zipf لا، وHeaps نعم، فهذا موضوعه كله.

Why it matters, slide 14

لماذا يهم هذا، الشريحة 14

Slide 14 draws the engineering consequence in three bullets, and they form a chain:

ترسم الشريحة 14 النتيجة الهندسية في ثلاثة بنود، وهي تشكّل سلسلة:

1. Word-level vocabularies become huge, giving memory and sparsity problems. A neural model needs an embedding row and an output logit per type. At 689,531 types that is 689,531 rows. Sparsity is the deeper problem: most of those types occur a handful of times, so there is not enough evidence to estimate anything about them.

   المفردات على مستوى الكلمة تصبح ضخمة، فتنشأ مشكلات في الذاكرة والتناثر (sparsity). النموذج العصبي يحتاج صف embedding وlogit خرج لكل type. وعند 689,531 type يعني ذلك 689,531 صفاً. والتناثر هو المشكلة الأعمق: معظم هذه الـ types تظهر بضع مرات فقط، فلا توجد أدلة كافية لتقدير أي شيء عنها.

2. Many words are out-of-vocabulary (OOV) in training. This is Heaps' law restated as a threat. Because |V| never saturates, your test set is guaranteed to contain words your training set never showed you. You cannot fix that by collecting more training data, because the test data grows new words too.

   كلمات كثيرة تكون خارج المفردات (OOV) في التدريب. هذا هو Heaps' law معاداً صياغته كتهديد. لأن |V| لا يتشبع أبداً، فمجموعة الاختبار مضمون أن تحتوي كلمات لم تُرِك إياها مجموعة التدريب. ولا يمكنك إصلاح ذلك بجمع مزيد من بيانات التدريب، لأن بيانات الاختبار تنمو فيها كلمات جديدة أيضاً.

3. Motivates subword and byte tokenization. The escape. Stop making the token a word. If your units are pieces of words, or raw bytes, then the inventory is small and closed, and an unseen word is spelled out of pieces you already know rather than being an unknown. This is why byte-pair encoding exists, and it is the topic later in this same deck.

   هذا يدفع نحو subword وbyte tokenization. هذا هو المخرج. توقف عن جعل الـ token كلمة. إذا كانت وحداتك أجزاء كلمات أو بايتات خاماً، فالمخزون صغير ومغلق، والكلمة غير المرئية تُهجّأ من أجزاء تعرفها أصلاً بدلاً من أن تكون مجهولة. ولهذا وُجد byte-pair encoding، وهو موضوع لاحق في المحاضرة نفسها.

Notice the logic. Heaps' law is not a curiosity. It is the formal reason that the field abandoned word-level vocabularies.

لاحظ المنطق. Heaps' law ليس طرفة. إنه السبب الرسمي الذي جعل المجال يتخلى عن المفردات على مستوى الكلمة.

Rare words dominate, slide 15

الكلمات النادرة هي الغالبة، الشريحة 15

Slide 15's first bullet introduces the term you need: a hapax legomenon is a word that appears exactly once in a corpus. The plural is hapax legomena. The slide's claim is that a large fraction of types appear only once.

البند الأول في الشريحة 15 يقدّم المصطلح الذي تحتاجه: hapax legomenon هي كلمة تظهر مرة واحدة بالضبط في الـ corpus. وجمعها hapax legomena. ودعوى الشريحة أن نسبة كبيرة من الـ types تظهر مرة واحدة فقط.

That phrasing is deliberate and it is where students lose marks. Hapax legomena are a large share of the types. They are a small share of the tokens. Both statements are true at the same time, and they are not in tension once you see the arithmetic.

هذه الصياغة مقصودة، وهي الموضع الذي يخسر فيه الطلاب الدرجات. الـ hapax legomena حصة كبيرة من الـ types. وهي حصة صغيرة من الـ tokens. العبارتان صحيحتان في الوقت نفسه، ولا تعارض بينهما بمجرد أن ترى الحساب.

rank  word     count
  1   the        20
  2   of         12
  3   and         9
  4   a           7
  5   to          6
  6   in          5
  7   is          4
  8   it          3
  9   that        3
 10   was         3
                ---
      subtotal    72 tokens from 10 types

plus 28 further words, each occurring exactly once

      subtotal    28 tokens from 28 types

totals
      N   = 72 + 28 = 100 tokens
      |V| = 10 + 28 =  38 types

hapax as a share of TYPES   = 28 / 38  = 73.7 %     dominant
hapax as a share of TOKENS  = 28 / 100 = 28.0 %     a minority

meanwhile the single word "the"
  is 1 / 38 = 2.6 % of the types
  but      20 / 100 = 20 % of the tokens

Slide 15's remaining two bullets say what you do about it, and both are forward references to material you already have on other pages:

البندان الباقيان في الشريحة 15 يقولان ماذا تفعل حيال ذلك، وكلاهما إحالة إلى مادة موجودة في صفحات أخرى:

• Smoothing and backoff in n-gram models. Maximum likelihood gives probability zero to anything unseen, and with this many hapax that is a disaster. Smoothing moves probability mass towards the rare and unseen.

  Smoothing وbackoff في نماذج n-gram. الـ Maximum likelihood يعطي احتمال صفر لأي شيء لم يُرَ، ومع هذا العدد من الـ hapax تكون كارثة. والـ Smoothing ينقل كتلة احتمالية نحو النادر وغير المرئي.

• Subwords in neural models. The same escape slide 14 named, applied to the same problem from the other direction.

  الـ Subwords في النماذج العصبية. المخرج نفسه الذي سمّته الشريحة 14، مطبقاً على المشكلة نفسها من الاتجاه الآخر.

• Evaluation depends on how you treat unseen items. Two systems can be compared only if they handle unknown words the same way. Change the OOV policy and you change the score without changing the model.

  التقييم يعتمد على طريقة معاملة العناصر غير المرئية. لا يمكن مقارنة نظامين إلا إذا تعاملا مع الكلمات المجهولة بالطريقة نفسها. غيّر سياسة الـ OOV فتتغير النتيجة دون أن يتغير النموذج.

Thirty-second recap

خلاصة في ثلاثين ثانية

ملخص: Zipf هو f(R) ∝ 1 / R^α، وR = 1 هي الكلمة الأكثر تكراراً، ويظهر خطاً مستقيماً ميله −α على محاور log-log، ومطابقات الشريحة 11 هي α = 0.9290 للإنجليزية و0.9252 للعربية. وHeaps هو |V| = k · N^β مع 0 < β < 1، أي sublinear (β < 1) لكنه unbounded (β > 0)، ومطابقات الشريحة 13 هي k = 14.947 وβ = 0.583 للإنجليزية وk = 73.321 وβ = 0.533 للعربية. عشرة أضعاف الـ tokens تعطي 10^β = 3.83× من الـ types. و|V| الضخم يسبب مشكلات الذاكرة والتناثر والـ OOV. وhapax legomenon كلمة ظهرت مرة واحدة بالضبط، والـ hapax هي معظم الـ types وأقلية من الـ tokens.