CS 5293 Assignment-1¶
Welcome to CS 5293 (Natural Language Processing)!
For this assignment 1, the main goal is to help you setup your python environment, and do some warmup coding for the following two parts:
- Part 1. Analyze the vocabulary of large language model Llama-3.1 (35')
- Part 2. Build your own N-gram model (60')
- Statement of AI Usage (5')
Part 1. Analyze Llama-3.1 Vocabulary (35')¶
In the lecture 2, we learned the Heap's law. As the corpus size grow, we don't hope the vocabulary continuously go larger, but we still hope the vocabulary cover all the words to avoid the out-of-vocabulary error(OOV). Hence, we learned the subword tokenization, typically the Byte Pair Encoding(BPE).
From BERT, RoBERTa, T5, Llama-1, to Llama-2, majority of these language models vocabulary size is often around 30K. However, Llama-3 replaced the original tokenizer Sentence Piece [1] with the TikToken [2] used in OpenAI models, which has 128K vocabulary size.
On the other side, larger vocabulary size also means more token efficient (i.e., fewer tokens are necessary to encode the same piece of text by Llama-3 relative to Llama-2), which makes inference more efficient. However, the optimal size of vocabulary is still unknown.
Here, we have a list of the "tokens" that are in the "Llama-3.1-8B" vocabulary file (../data/Llama-3.1-8b/vocab.txt), with one "token" per line. This goal of this assignment is to write a program to identify what are the 128K tokens in the Llama-3.1-8B vocabulary, and choose an open research question you are curious about LLM tokenizations, and write program to analyze that.
Grading Criteria¶
- (15') Part 1.1, Be able to set up the envrionment, read and run through all the code via VSCode or your own jupternote, and understand how to use regex pattern to analyze the text. Hence, to get this score, you only need to read through and make sure you could run each cell of the Part 1.1 to get an output to indicate that your setup is ready.
- (20') Part 1.2, Investigate your own research question.
Recommended open questions (not limited to this list, and not limited to English)¶
- How many English roots are covered in the vocabulary? (../data/english.roots.list.build.json)
- How many whole English words are there in the vocabulary? (../check_word.ipynb)
- How emojis are tokenized in the tokenizer? What are the related tokens in the vocabulary?
- How combining characters are tokenized in the tokenizer? What are the related tokens in the vocabulary?
- ...
Other Unhelpful Reading for This Assignment:¶
- Sentence Piece. https://github.com/google/sentencepiece
- Tiktoken. Think of the simple version of BPE algorithm we learned in lecture 2. The educational.py in Tiktoken algorithm offers an implementation of that. https://github.com/openai/tiktoken/blob/63527649963def8c759b0f91f2eb69a40934e468/tiktoken/_educational.py#L119
- Llama3.1 use a different
pat_strto split the sentence, a bunch of special tokens, and larger vocabulary size: https://github.com/meta-llama/llama3/blob/main/llama/tokenizer.py#L21, please consider the special tokens as the shape of "<|.*|>" - Here is an OpenAI tutorial to compare different vocabulary of their models from GPT2 to recent GPT-o1. https://github.com/openai/openai-cookbook/blob/main/examples/How_to_count_tokens_with_tiktoken.ipynb
- Research on scaling laws of vocabulary also has been studied this. https://arxiv.org/abs/2407.13623. At the same time, researcher also studied the unfaireness of the tokenizer for different languages. https://arxiv.org/pdf/2305.15425
Part 1.1 Setup (15')¶
Python Environment and VSCode¶
import the environment.yml under our root assignment folder, and create and activate your environment via the setup_tutorial.ipynb.
# Depends on your current path in the terminal, please change the path to the file.
mamba env create -n cs5293-1 -f ../environment.yml
mamba activate cs5293-1
If you failed to run the above command your in terminal. This is because the exported environmental.yml file by mamba is not cross-platform. It may fail in your OS envrionment. So you need to create your own "cs5293-1" from scratch.
Setup from Scratch¶
A simple rule to use mamba(a faster versin of conda) and uv(a faster version of pip): only use mamba/conda for system-related packages, such as cuda, python or others. But for python libraries xxx, e.g. transformers, torch, priotize to use pip install xxx or uv pip install xxx first, then mamba install xxx.
┌───────────────────────────┐
│ Your Python code │
├───────────────────────────┤
│ Python packages │ ← pip/uv lives here
│ (pip / wheels) │
├───────────────────────────┤
│ Native libraries │ ← mamba/conda lives here
│ (CUDA, MKL, libstdc++) │
├───────────────────────────┤
│ OS │
└───────────────────────────┘
Please simply use the following commands to setup:
mamba env create -n cs5293-1 python=3.10
mamba deactive && mamba activate cs5293-1
pip install transformers torch
## The following uv usage is for your own curiousity
# uv venv uv-cs5293-1
# source uv-cs5293-1/bin/activate
# uv pip install transformers torch
Hopefully all the above steps are sucessful, Good luck!
If you’re eager to try the latest tooling in the Python ecosystem, give uv a shot as a drop-in replacement for pip: https://docs.astral.sh/uv/getting-started/installation/#next-steps
Then you need to go the top-right corner of the VSCode, click the Select Kernel, (and Select Another Kernel if needed) to select the above cs5293-1 envrionment.
If your VSCode didn't find the cs5293-1 environment, please try to fully quit your VSCode and reopen the project folder, try the Select Kernel again.
Launch VSCode, and Open the whole assignment-1 folder in your VSCode. Then open this jupyter notebook Assignment-1.ipynb in VSCode by click the Explorer in the left side bar. For AI usage in VSCode, you are encouraged to explore claude or codex plugins in vscode, but you are free to decide to not use any AI tools.
About OSCER¶
OSCER setup will take a whole week or more. For this assignment, we don't need OSCER machines, but feel free to set up when it ready. As mentioned in this webpage(https://www.ou.edu/oscer/support/VS_Code), starting from VS Code version 1.86.0, Microsoft now drop support for older operating system with glibc<2.28, which include ALL OSCER compute nodes. Until we upgrade our entire supercomputer to a newer operating system, your ONLY choice is to use VS Code Desktop AND CLI version 1.85.2 via the links the above webpage.
Attention! You need to run all the code on you own environment not just look. Running it code means the output cell should show your own path instead of anyone else's path.
from transformers import AutoTokenizer
import os
import sys
sys.path.append("../src")
print(sys.path)
#Disabling the parallelism of the tokenizers to avoid issues with the multiprocessing
os.environ["TOKENIZERS_PARALLELISM"] = "false"
#Importing the necessary modules for this assignment
import vocab_utils
['/Users/jcao/mamba/envs/cs5293-1/lib/python310.zip', '/Users/jcao/mamba/envs/cs5293-1/lib/python3.10', '/Users/jcao/mamba/envs/cs5293-1/lib/python3.10/lib-dynload', '', '/Users/jcao/mamba/envs/cs5293-1/lib/python3.10/site-packages', '/var/folders/nf/gj_5trts2qj8gq13_52ybrr80000gp/T/tmp6fm9a9u8', '../src']
# If you understand the vocab_utils.py file,
# you can freely change the following variables to test other models, such as the recent release of GPT-oss or Grok2.
# https://huggingface.co/openai/gpt-oss-20b and https://huggingface.co/tiiuae/grok-2-20b
# Otherwise, please DON'T change these variables.
llama3_model_name = "meta-llama/Llama-3.1-8b"
llama3_local_model = "../data/Llama-3.1-8b"
vocab3_file = os.path.join(llama3_local_model,"vocab.txt")
vocab3_file
'../data/Llama-3.1-8b/vocab.txt'
We load the tokenizer from the remote huggingface repo via the name of the model.
# Please ignore this cell, because it requires a license to do that.
# The purpose of this is to load the tokenizer remotely and save it in your local folder.
# You need to obtain a license for your own access to the model.
# https://huggingface.co/meta-llama/Meta-Llama-3-8B
# via the steps here. https://huggingface.co/meta-llama/Meta-Llama-3-8B/discussions/172
# Feel free to do that because if you will need this in Assignment 4 or your project.
# But you don't need that for this assignment.
# We have saved the tokenizer for you locally and store them in the data folder.
#tokenizer = vocab_utils.save_tokenizer_to_local(llama3_model_name, llama3_local_model)
#vocab_utils.save_vocab(tokenizer, vocab3_file)
Load Llama3 Tokenizer Locally¶
For this assignment, we will load the Llama3 tokenizer locally
tokenizer = vocab_utils.load_local_tokenizer(llama3_local_model)
tokenizer loaded from ../data/Llama-3.1-8b
Test the Llama3 Tokenizer¶
Test on English¶
Please investigate the whitespace, line wrap and soon on.
non_white_space_sequence = "BuyableInstoreAndOnline\n"
tokenized_sentences = tokenizer.tokenize(non_white_space_sequence)
print(f"tokenized_sentences for \n{non_white_space_sequence}\n{tokenized_sentences}")
tokenized_sentences for BuyableInstoreAndOnline ['Buy', 'able', 'In', 'store', 'And', 'Online', 'Ċ']
white_space_sequence = "Buyable In store And Online\n"
tokenized_sentences = tokenizer.tokenize(white_space_sequence)
# please pay attention to the special whitespace and \n in the sequence.
# they are just stored as unicode characters, not some newly added characters.
# (0x20 is space, and they add 0x100 to every symbol they have to encode)
# (0x0a is newline, and they add 0x100 to every symbol they have to encode)
for token in tokenized_sentences:
print(f"for token = {token}")
for ch in token:
print(f"{ch}, U+{ord(ch):04x}")
print(f"tokenized_sentences for \n{white_space_sequence}\n{tokenized_sentences}")
for token = Buy B, U+0042 u, U+0075 y, U+0079 for token = able a, U+0061 b, U+0062 l, U+006c e, U+0065 for token = ĠIn Ġ, U+0120 I, U+0049 n, U+006e for token = Ġstore Ġ, U+0120 s, U+0073 t, U+0074 o, U+006f r, U+0072 e, U+0065 for token = ĠAnd Ġ, U+0120 A, U+0041 n, U+006e d, U+0064 for token = ĠOnline Ġ, U+0120 O, U+004f n, U+006e l, U+006c i, U+0069 n, U+006e e, U+0065 for token = Ċ Ċ, U+010a tokenized_sentences for Buyable In store And Online ['Buy', 'able', 'ĠIn', 'Ġstore', 'ĠAnd', 'ĠOnline', 'Ċ']
Test Emojis¶
# testing emojis, https://en.wikipedia.org/wiki/Emoticons_(Unicode_block)
sequence = "😀🙅🏻" # The second emoji is so called emoji with a modifer.
# The string is naturally in unicode in Python.
# You could print the unicode for each character in the string.
for ch in sequence:
print(f"{ch}, U+{ord(ch):04x}")
tokenized_sentences = tokenizer.tokenize(sequence)
print(f"tokenized_sentences for \n{sequence}\n{tokenized_sentences}")
😀, U+1f600 🙅, U+1f645 🏻, U+1f3fb tokenized_sentences for 😀🙅🏻 ['ðŁĺ', 'Ģ', 'ðŁ', 'Ļ', 'ħ', 'ðŁ', 'ı', '»']
Test on Combining Characer¶
# The combination characters for 'Tokenization is fun!'
# You could generate more here https://lingojam.com/ZalgoText
sequence = "T̵o̵k̴e̵n̷i̸z̵a̵t̴i̴o̴n̵ ̴i̶s̵ ̷f̸u̴n̶!̵"
# The string is naturally in unicode in Python.
# You could print the unicode for each character in the string.
for ch in sequence:
print(ch, ord(ch))
tokenized_sentences = tokenizer.tokenize(sequence)
print(f"tokenized_sentences for \n{sequence}\n{tokenized_sentences}")
T 84 ̵ 821 o 111 ̵ 821 k 107 ̴ 820 e 101 ̵ 821 n 110 ̷ 823 i 105 ̸ 824 z 122 ̵ 821 a 97 ̵ 821 t 116 ̴ 820 i 105 ̴ 820 o 111 ̴ 820 n 110 ̵ 821 32 ̴ 820 i 105 ̶ 822 s 115 ̵ 821 32 ̷ 823 f 102 ̸ 824 u 117 ̴ 820 n 110 ̶ 822 ! 33 ̵ 821 tokenized_sentences for T̵o̵k̴e̵n̷i̸z̵a̵t̴i̴o̴n̵ ̴i̶s̵ ̷f̸u̴n̶!̵ ['T', 'Ì', 'µ', 'o', 'Ì', 'µ', 'k', 'Ì', '´', 'e', 'Ì', 'µ', 'n', 'Ì', '·', 'i', 'Ì', '¸', 'z', 'Ì', 'µ', 'a', 'Ì', 'µ', 't', 'Ì', '´', 'i', 'Ì', '´', 'o', 'Ì', '´', 'n', 'Ì', 'µ', 'Ġ', 'Ì', '´', 'i', 'Ì', '¶', 's', 'Ì', 'µ', 'Ġ', 'Ì', '·', 'f', 'Ì', '¸', 'u', 'Ì', '´', 'n', 'Ì', '¶', '!', 'Ì', 'µ']
Initial Exploration for Llama3's Vocabulary via Linux Commands¶
As an exmaple, in the following, we show a list of linux commands for an initial analysis on the vacabulary. Please to find the corresponding python code to get the same function, which is not hard. These are just an optional practice for verification of your python code.
The following command will count in total how many lines in the vocab.txt
!wc -l ../data/Llama-3.1-8b/vocab.txt
128256 ../data/Llama-3.1-8b/vocab.txt
So we're in the right ballpark with 128256 lines (tokens).
# Python code for count lines in the file ../data/Llama-3.1-8b/vocab.txt
line_count = 0
with open(vocab3_file) as f:
line_count = sum(1 for _ in f)
print(f"line_count = {line_count}")
line_count = 128256
So the above python code will read the vocabulary file, and count each lines(one token per line).
Let's see what's in there.
Because the list is too long. You could use the command head to print the first 10 lines.
!head ../data/Llama-3.1-8b/vocab.txt
! " # $ % & ' ( ) *
Ok, those look like the initial set of characters we mentioned in our lectures. Remember we said that subword tokenization algorithms start with an initial vocabulary of characters. In the lecture 2, we only consider the letters and numbers. That's really not quite right, if you're using arbitrary web docs and things like Wikipedia then you're going to run into a lot of odd characters, such as the combination characters used in Fentayln example. Better to just use all the unicode characters that occur in the training text. Let's see what we get we look at all the single character entries in the list.
!grep '^.$' ../data/Llama-3.1-8b/vocab.txt | head
! " # $ % & ' ( ) *
%%bash
single_char_num=$(grep '^.$' ../data/Llama-3.1-8b/vocab.txt | wc -l)
echo "With grep command, there are ${single_char_num} single characters, which are all the 2^8 bytes"
With grep command, there are 256 single characters, which are all the 2^8 bytes
import re
# please learn to use python regex. https://www.w3schools.com/python/python_regex.asp
single_char_num = 0
with open(vocab3_file) as f:
for token in f:
if re.match(r'^.$', token):
single_char_num += 1
print(f"With python regex, there are {single_char_num} single characters, which are all the 2^8 bytes")
With python regex, there are 256 single characters, which are all the 2^8 bytes
Next, let us take a look at the special tokens as the shape of "<|.*|>". https://github.com/meta-llama/llama3/blob/main/llama/tokenizer.py#L21 Please try to write a python program to replicate this result for detecting the special tokens.
!ggrep -E -o '^<\|.*\|>$' ../data/Llama-3.1-8b/vocab.txt| head -50
<|begin_of_text|> <|end_of_text|> <|reserved_special_token_0|> <|reserved_special_token_1|> <|finetune_right_pad_id|> <|reserved_special_token_2|> <|start_header_id|> <|end_header_id|> <|eom_id|> <|eot_id|> <|python_tag|> <|reserved_special_token_3|> <|reserved_special_token_4|> <|reserved_special_token_5|> <|reserved_special_token_6|> <|reserved_special_token_7|> <|reserved_special_token_8|> <|reserved_special_token_9|> <|reserved_special_token_10|> <|reserved_special_token_11|> <|reserved_special_token_12|> <|reserved_special_token_13|> <|reserved_special_token_14|> <|reserved_special_token_15|> <|reserved_special_token_16|> <|reserved_special_token_17|> <|reserved_special_token_18|> <|reserved_special_token_19|> <|reserved_special_token_20|> <|reserved_special_token_21|> <|reserved_special_token_22|> <|reserved_special_token_23|> <|reserved_special_token_24|> <|reserved_special_token_25|> <|reserved_special_token_26|> <|reserved_special_token_27|> <|reserved_special_token_28|> <|reserved_special_token_29|> <|reserved_special_token_30|> <|reserved_special_token_31|> <|reserved_special_token_32|> <|reserved_special_token_33|> <|reserved_special_token_34|> <|reserved_special_token_35|> <|reserved_special_token_36|> <|reserved_special_token_37|> <|reserved_special_token_38|> <|reserved_special_token_39|> <|reserved_special_token_40|> <|reserved_special_token_41|>
!ggrep -E -o '^<\|.*\|>$' ../data/Llama-3.1-8b/vocab.txt|wc -l
256
So there are 256 used or reserved special tokens in Llama-3.1-8b vocabulary. Next we found the special Ġ is used for the leading whitespace of the token.
!grep '^Ġ'< ../data/Llama-3.1-8b/vocab.txt | wc -l
57875
!ggrep -E -o '[[:digit:]]+' < ../data/Llama-3.1-8b/vocab.txt| head -200
0 1 2 3 4 5 6 7 8 9 00 20 10 201 12 19 11 32 16 15 25 000 30 18 14 13 100 200 17 50 24 64 40 22 60 23 99 80 27 28 26 33 29 21 01 35 45 37 36 90 34 38 70 75 44 55 39 31 48 66 05 08 202 04 65 88 02 49 78 09 199 07 68 47 500 06 95 46 77 03 59 58 42 69 67 300 41 255 57 98 43 400 56 97 198 150 51 87 52 001 256 96 86 102 53 120 54 128 197 123 89 79 101 800 76 111 600 110 250 196 180 85 72 63 999 62 61 74 84 130 91 192 81 73 71 83 92 82 003 195 94 160 93 194 125 105 108 002 127 360 104 140 103 700 190 112 193 115 106 900 404 191 107 109 010 204 121 114 116 113 170 122 240 512 005 117 220 350 004 333 210 124 135 118 144 168 119 131 141 188 189 126 132 133 134 320 145 203 187 151
Let's see how many tokens are started with white space character in the unicode 'Ġ'
!grep '^Ġ' ../data/Llama-3.1-8b/vocab.txt | wc -l
57875
!grep -v '\[' ../data/Llama-3.1-8b/vocab.txt | grep -v '^.$' | grep -v '^Ġ' | head -200
in
er
on
re
at
st
en
or
ĊĊ
le
it
an
ar
al
;Ċ
ou
is
ing
es
ion
ed
ic
et
ĉĉ
ro
as
el
ct
nd
ent
id
am
--
om
);Ċ
im
čĊ
il
//
ur
se
ex
ad
ch
ut
if
**
em
ol
th
)Ċ
ig
iv
,Ċ
ce
od
ate
ag
ay
ot
us
un
ul
ue
ow
ew
ation
()
ab
ort
um
ame
pe
tr
ck
âĢ
ist
----
.ĊĊ
he
lo
ers
ap
ub
ass
int
>Ċ
ly
urn
;ĊĊ
av
port
ir
->
nt
ction
end
00
ith
out
turn
our
lic
res
pt
==
ver
age
ht
ext
="
****
ess
os
and
ect
ke
rom
con
("
qu
lass
iz
de
op
up
get
ile
ata
ore
ri
;čĊ
ĉĉĉĉ
ter
ain
art
ack
import
ublic
est
ment
able
ine
ill
ind
ere
::
ity
elf
ight
('
orm
ult
str
..
",
ype
pl
20
ld
oc
:Ċ
--------
.s
{Ċ
',
ant
ase
.c
</
ave
ang
âĢĻ
_t
ert
ial
act
}Ċ
ive
ode
ost
og
ord
alue
all
ff
();Ċ
ont
ime
are
ies
ize
ure
ire
.p
ice
ast
ption
tring
ok
grep: write error: Broken pipe
grep: write error: Broken pipe
grep: write error: Broken pipe
Although its not stated, this is obviously a frequency ordered list. "in" is at the top. Some of these are recognizable as English suffixes (-ed, -ing, -ly, etc).
Let's just sort it alphanumerically to see what's in there.
!grep -v '\[' < ../data/Llama-3.1-8b/vocab.txt | grep -v '^.$' | grep -v '^Ġ' | sort | head -200
»¿
·¸
¬¸
·»
£¼
³»
¨¡
µ¬
¡°
ר
¦¬
¥¿
ש
·¨
×¢
¡´
¬´
¬¬
¯¸
¯¼
£¨
£½
¥¤
¾¸
®¤
¯¿
¢°
__
___
____
_____
________
____________
________________
________________________________
________________________________________________________________
_________________ĊĊ
___ĊĊ
__,
__,__
__,Ċ
__;
__;Ċ
__:
__.
__.__
__.'/
__',
__':Ċ
__':čĊ
__":Ċ
__(
__('
__("
__((
__()
__()Ċ
__()ĊĊ
__(*
__(/*!
__(Ċ
__)
__),
__);
__);Ċ
__);ĊĊ
__).
__))
__));Ċ
__))Ċ
__)Ċ
__)ĊĊ
__)ĊĊĊ
__*/
__/
__$
__Ċ
__čĊ
__ĊĊ
_-
_-_
_->
_,
_,,
_,Ċ
_;
_;Ċ
_;čĊ
_;ĊĊ
_:
_:*
_.
_'
_',
_'.$
_'+
_"
_",
_".$
_"+
_(
_('
_("
_();Ċ
_()Ċ
_)
_),
_);Ċ
_);čĊ
_);ĊĊ
_));Ċ
_)Ċ
_)čĊ
_]
_{
_*
_/
_\
_#{
_##
_%
_^
_^(
_<
_<?
_=
_='
_>
_|
_$
_$_
_${
_a
_A
_aa
_AA
_ab
_AB
_ABC
_ABI
_ability
_abort
_ABORT
_about
_above
_abs
_ABS
_absolute
_abstract
_Abstract
_ac
_AC
_acc
_ACC
_accel
_accept
_ACCEPT
_accepted
_access
_ACCESS
_accessible
_accessor
_account
_Account
_ACCOUNT
_accounts
_accum
_accuracy
_ack
_ACK
_acl
_ACL
_acquire
_act
_Act
_ACT
_action
_Action
_ACTION
_actions
_ACTIONS
_activ
_ACTIV
_activate
_activation
_active
_ACTIVE
_activities
_activity
_ACTIVITY
_actor
_actual
_ad
_Ad
_AD
_adapter
_ADAPTER
_adc
_ADC
_add
sort: Broken pipe
Hmm. A lot of puntuations, and many with line wrap.
!grep -v '\[' < ../data/Llama-3.1-8b/vocab.txt | grep -v '^.$' | grep -v '^Ġ' | grep -v '^Ċ' | wc -l
69647
Let's just get the numbers that constitute the whole line.
!ggrep -E -o '[[:digit:]]+' ../data/Llama-3.1-8b/vocab.txt | wc -l
1358
Part 1.2 Study Your Own Research Question (20')¶
Step 1: Please add a paragraph here to explain what is your research question?
# Describe your research question here.
Step 2: Your explorative code to study your research question
# Then please add more cells to study your questions as the above
# You could write all your code in the cells below.
# Or your code could be written in a python file in the src folder, then call it in the cells bellow.
# Take the vocab_utils.py and the hello_world.py as an example, they are written in the src folder as single files.
# But they are imported in the juptyer notebook and run in the cells.
Your Final Submission for Part 1¶
- (1) A PDF(simply exported from jypernotebook with all the output). You need to make sure this jupyter note book having ran through all the cells with the outputs.(include the above cells and the new cells you will add below), and export a pdf file with all the output as your main submission. The grading will start with your exported PDF from jupter note book. We will only rerun your jupternotebook when necessary.
- (2) You should submit the whole Assignment-1 folder as a zip file. Your code and instruction should use this jupyter notebook or put some seperate python file in the src folder. Any external resource should be placed in the data folder. We will use this to rerun your code.
- (3) Feel free to add an extra PDF file to report your findings in Part 1.2 if the jupternote is not good enough to demostrate your findings. (optional)
Part 2. N-Gram Language Model (60')¶
Your task for this Part 2 is to build an N-gram language model from scratch. Your language modeling program should accept three input files: (1) a training corpus file, (2) a test sentences file, and (3) a seeds file, which will contain a list of words to begin the language generation process. In Part-1, you have learned to use jupyter notebooks. In this Part 2, you will learn the way of using command-line to run your program out of the jupter notebook, which is a more common way for AI model development. Your program should accept three files as command-line arguments in the following order:
```python ngram.py <training file> <test file> <seeds_file>```Grading Criteria¶
We will run your program on the files that we give you as well as new files(private test set) to evaluate the generality and correctness of your code. So please test your program thoroughly! Even if your program works perfectly on the examples that we give you, that does not guarantee that it will work perfectly on different test cases.
- (30') Part 2.1 N-gram LM Task 1: Computing Sentence Probability
- (30') Part 2.2 N-gram LM Task 2: Language Generator
Input Files¶
All the input files located in the data folder.
Training File¶
The training file will consist of sentences, one sentence per line. For example, a training file might look like this:
I love natural language processing .
This assignment looks like fun !
You should divide each sentence into unigrams based solely on white space, which means no need to use special tokenizer "spacy" or "NLTK" mentioned in class. Note that this can produce isolated punctuation marks (when white space separates a punctuation mark from adjacent words) as well as words with punctuation symbols that are still attached (when white space does NOT separate a punctuation mark from an adjacent word). For example, consider the following sentence:
“This is a funny-looking sentence” , she said !
This sentence should be divided into exactly nine unigrams: (1) “This (2) is (3) a (4) funny-looking (5) sentence” (6) , (7) she (8) said (9) !
Test File¶
The test file will have exactly the same format as the training file and it should be divided into unigrams exactly the same way. So please feel comfortable the punctuations, again, just use the white space to tokenize each raw sentence, not any processing. People may ask what about the validatio or develop set. Since the N-gram training is almost deterministic, so in this assignment, we will not use a develop set to select the model hyperparameters or a held-out set for further testing the generalization.
Seeds File¶
The seeds file will have one word per line, and each word should be used to start the language generation process.
Building the N-gram Language Models¶
To create the N-gram language models, you will need to generate tables of frequency counts from the training corpus for unigrams (1-grams) and bigrams (2-grams). An N-gram should not cross sentence boundaries. All of your N-gram tables should be case-insensitive (i.e., “the”, “The”, and “THE” should be treated as the same word).
You should create three different types of language models:
- (a) A unigram language model with no smoothing.
- (b) A bigram language model with no smoothing.
- (c) A bigram language model with add-one smoothing.
You can assume that the set of unigrams found in the training corpus is the entire universe of unigrams. We will not give you test sentences that contain unseen unigrams. So the vocabulary $V$ for this assignment is the set of unique unigrams that occur in the training corpus, and they are not subwords in the Part 1.
However, we will give you test sentences that contain bigrams that did not appear in the training corpus. The n-grams will consist entirely of unigrams that appeared in the training corpus, but there may be new (previously unseen) combinations of the unigrams. The first two language models (a and b) do not use smoothing, so unseen bigrams should be assigned a probability of zero. For the last language model (c), you should use add-one smoothing to compute the probabilities for all of the bigrams.
For bigrams, you will need to have a special pseudo-word “<s>” as a beginning-of-sentence symbol. Bigrams of the form "<s>$w_i$" mean that word $w_i$ occurs at the beginning of the sentence. Do NOT include "<s>" as a word in your vocabulary for the unigram language model or include "<s>" in the sentence probability for the unigram model. For simplicity, just use the unigram frequency count of $w_{k−1}$ to compute the conditional probability $P (w_k | w_{k−1})$. (This means you won’t have to worry about cases where w_{k−1} occurs at the end of the sentence and isn’t followed by anything.) For example, just compute $P (w_k | w_{k−1}) = count (w_{k−1}w_k) /count (w_{k−1})$. You should NOT use an end-of-sentence symbol. The last bigram for a sentence of length should represent the last 2 words of the sentence: $w_{n−1}w_n$.
Part 2.1 N-gram LM Task 1: Computing Sentence Probability (30')¶
For each of the language models, you should create a function that computes the probability of a sentence $P(w_1 ... w_n)$ using that language model. Since the probabilities will get very small, you must do the probability computations in log space (as discussed in class, also see the lecture slides). Please do these calculations using log base 2.
Output Specifications for Task 1¶
Your program should print the following information for each test sentence. When printing the logprob numbers, please only print 4 digits after the decimal point. For example, print -8.9753864210 as -8.9754. The programming language will have a mechanism for controlling the number of digits that are printed. If $P(S) = 0$, then the logarithm is not defined, so print logprob(S) = undefined.
Please print the following information, a sentence line, an empty line, and three probabilities formatted like this:
S = <sentence>
Unigrams: logprob(S) = #
Bigrams: logprob(S) = #
Smoothed Bigrams: logprob(S) = #
For example, your output might look like this (the examples below are not real, they are just for illustration!):
S = Trump has given his second inaugural speech .
Unigrams: logprob(S) = -6.5712
Bigrams: logprob(S) = -9.2253
Smoothed Bigrams: logprob(S) = -10.4291
Part 2.2 N-gram LM Task 2: Language Generator (30')¶
Your language generator should use the unsmoothed bigram language model to produce new sentences, probabilistically! Given a seed word, the language generation algorithm is:
- Find all bigrams that begin with the seed word - let’s call this set $B_{seed}$. Probabilistically select one of the bigrams in $B_{seed}$ with a likelihood proportional to its probability. For example, suppose “crazy” is the seed and exactly two bigrams begin with “crazy”: “crazy people” (frequency=10) and “crazy horse” (frequency=15).
Consequently, $P (people | crazy) = \frac{10}{25} = .40$ and $P (horse | crazy) = \frac{15}{25} = .60$ There should be a 40% chance that your program selects “crazy people” and a 60% chance that it selects “crazy horse”. An easy way to do this is to generate a random number x between [0,1]. Then establish ranges based on the bigram probabilities. For example, if 0 ≤ x ≤.40 then your pro- gram selects “crazy people”, but if.40 < x ≤ 1 then your program selects “crazy horse”.
Let’s call the selected bigram $B^\prime=w_0w_1$ (where $w_0$ is the seed). Generate $w_1$ as the next word in your new sentence.
Return to Step 1 using $w_1$ as the new seed word to generate the next $w_2$ and continue.
Your program should stop generating words when one of the following conditions exists:
- your program generates one of three words: [. ? !]
- your program generates 40 words (NOT including the original seed word)
- $B_{seed}$ is empty (i.e., there are no bigrams that begin with the seed word).
IMPORTANT: For each seed word, your language generator should randomly generate 10 sentences that begin with that word. Since each sentence is generated probabilistically, the sentences will (usually) be different from each other.
Output Specifications for Generation Task¶
Your program should print each seed word followed by a blank line and then the 10 sentences generated from that seed word. You should format your output like this:
Seed = <seed>
Sentence 1: <sentence>
Sentence 2: <sentence>
Sentence 3: <sentence>
Sentence 4: <sentence>
Sentence 5: <sentence>
Sentence 6: <sentence>
Sentence 7: <sentence>
Sentence 8: <sentence>
Sentence 9: <sentence>
Sentence 10: <sentence>
Seed = <seed>
Sentence 1: <sentence>
Sentence 2: <sentence>
Sentence 3: <sentence>
Sentence 4: <sentence>
Sentence 5: <sentence>
Sentence 6: <sentence>
Sentence 7: <sentence>
Sentence 8: <sentence>
Sentence 9: <sentence>
Sentence 10: <sentence>
Your Final Submission for Part 2¶
The Part 2 does not depend on any the previous cells in this jupyter note book. Instead, you need to create your own python environment, and write your ngram.py from scratch. You need to output the log probabilities for the test file, and generate 10 sentences for each seed in the seeds file. Hence, please submit three things, and put all of them in the "ASSIGNMENT-1" folder, so that they could be compressed into a single file to submit:
- The source code for your program. Be sure to include all files that are needed to run your program, include a conda/mamba environmental file(
mamba env export > environment.yml)! - A README file(an empty README already there) located in the root folder of assignment-1 that includes the following information:
- how to run your code (suggest to use 3.10 python)
- any known bugs, problems, or limitations of your program
Submit two trace files: (1) ngram-prob.trace for the logprob outputs (2) ngram-gen.trace for the generated sentence for each seed.
Please don't submit any .cache or libraries, the size of submission should be less than 10M.
Statement of AI Usage (5')¶
For this assignment and all future assignment, a modatory pdf about your AI usage is always required.
- If you never use any AI in this assingment, Good luck. A comment with your submission "I never specifically use any AI in this assignment" and you will get 5 points for this single sentence.
- If you use any AI, please note down your usage, including the version/model of AI, related prompts, ideas, plans, questions, answers, what helps, what doesn't. You could easily find those chat log in your AI.