diff options
| author | Jonas Knobloch <jonas.knobloch@t-online.de> | 2026-09-11 18:39:02 +0200 |
|---|---|---|
| committer | Jonas Knobloch <jonas.knobloch@t-online.de> | 2026-09-11 18:39:02 +0200 |
| commit | 9e1b8c4bde9b0263a4c4d2278e3c283ca0eb07f1 (patch) | |
| tree | bf6b604a150a196490b92f89ca40a335aca83d31 /research/knobloch | |
| parent | 75e581b3bc19a73d0c1f48b32f2e58121c9741c1 (diff) | |
Diffstat (limited to 'research/knobloch')
| -rw-r--r-- | research/knobloch/cmd/dev/main.go | 20 | ||||
| -rw-r--r-- | research/knobloch/cmd/morphbands/main.go | 183 | ||||
| -rw-r--r-- | research/knobloch/cmd/plot/main.go | 58 | ||||
| -rw-r--r-- | research/knobloch/cmd/rankshift/main.go | 486 | ||||
| -rw-r--r-- | research/knobloch/cmd/tablea/main.go | 144 | ||||
| -rw-r--r-- | research/knobloch/cmd/tableb/main.go | 350 | ||||
| -rw-r--r-- | research/knobloch/cmd/tables/main.go | 220 | ||||
| -rw-r--r-- | research/knobloch/cmd/window/main.go | 254 | ||||
| -rw-r--r-- | research/knobloch/cmd/windowoverlap/main.go | 190 | ||||
| -rw-r--r-- | research/knobloch/lesci.go | 260 | ||||
| -rw-r--r-- | research/knobloch/share.go | 223 | ||||
| -rw-r--r-- | research/knobloch/shared.go | 152 | ||||
| -rw-r--r-- | research/knobloch/stats.go | 244 | ||||
| -rw-r--r-- | research/knobloch/tables.go | 483 |
14 files changed, 3267 insertions, 0 deletions
diff --git a/research/knobloch/cmd/dev/main.go b/research/knobloch/cmd/dev/main.go new file mode 100644 index 0000000..c1fbe4e --- /dev/null +++ b/research/knobloch/cmd/dev/main.go @@ -0,0 +1,20 @@ +package main + +import ( + "fmt" + + "github.com/jonasknobloch/mbpe" +) + +func main() { + splits := []string{"air", "sick"} + + c := mbpe.NewChunk("airsick", 1, splits, 0.3) + + weights := make(map[mbpe.Pair]float64) + + epsilon := c.PairWeights(weights) + + fmt.Printf("weights: %v\n", weights) + fmt.Printf("epsilon: %v\n", epsilon) +} diff --git a/research/knobloch/cmd/morphbands/main.go b/research/knobloch/cmd/morphbands/main.go new file mode 100644 index 0000000..620b563 --- /dev/null +++ b/research/knobloch/cmd/morphbands/main.go @@ -0,0 +1,183 @@ +// Command morphbands reports morpheme content per band of vocabulary-id space, +// counted two ways: by type and weighted by corpus frequency. +// +// The two disagree sharply. Morpheme types concentrate early -- around two +// thirds of the first 2,048 sub-words -- and thin out into the tail, but the +// tail is where most of the vocabulary is, so a type count says little about how +// much text is actually covered by morphemic sub-words. Weighting each sub-word +// by how often the tokenizer emits it over the corpus answers that instead. +// +// Frequencies come from encoding the dictionary, the same way the frequency +// plots do, so this takes a few minutes per tokenizer and is the slow part. +package main + +import ( + "encoding/csv" + "flag" + "fmt" + "log" + "os" + "strconv" + "strings" + + "github.com/jonasknobloch/mbpe" + "go.jknobloc.com/x/research/knobloch" + "go.jknobloc.com/x/shelf" + "go.jknobloc.com/x/tokenizer/bpe" +) + +// frequencies counts how often each vocabulary id is emitted over the +// dictionary, each word weighted by its corpus count. +func frequencies(t *bpe.Tokenizer, dictPath string) ([]int, error) { + dict := mbpe.NewDict() + + if err := dict.Load(dictPath); err != nil { + return nil, err + } + + // the dictionary is already pre-tokenized, so re-splitting would corrupt it + m := bpe.MBPE(t) + m.SetPreTokenizer(&knobloch.NoPreTok{}) + + r := make([]int, len(bpe.Vocab(t))) + + for _, v := range dict.Items() { + n := v.N() + + for _, id := range t.Encode(v.Src()) { + r[id] += n + } + } + + return r, nil +} + +func parseBands(s string, size int) []int { + var edges []int + + for _, f := range strings.Split(s, ",") { + v, err := strconv.Atoi(strings.TrimSpace(f)) + + if err != nil { + log.Fatalf("bad band edge %q: %v", f, err) + } + + edges = append(edges, v) + } + + if edges[0] != 0 { + edges = append([]int{0}, edges...) + } + + if last := edges[len(edges)-1]; last < size { + edges = append(edges, size) + } + + return edges +} + +func share(part, whole int) string { + if whole == 0 { + return "" + } + + return fmt.Sprintf("%.2f", 100*float64(part)/float64(whole)) +} + +func main() { + dirs := flag.String("dirs", "results/knobloch/minipile_19_ctrl/%s_minipile", + "tokenizer directory, %s is the alignment name") + dict := flag.String("dict", "results/knobloch/minipile_19_ctrl/dict.txt", + "pre-tokenized corpus dictionary") + list := flag.String("alignments", "m000,m050,m100,mi050,mi100", + "comma-separated alignments to report") + bands := flag.String("bands", "2048,8192,32768,100512,131072,262144", + "comma-separated upper edges of the id bands") + out := flag.String("out", "morpheme_bands.csv", "output CSV") + + flag.Parse() + + morph, err := knobloch.Morphemes(shelf.Abs(knobloch.SegmentsPath)) + + if err != nil { + log.Fatal(err) + } + + log.Printf("%d known morphemes", len(morph)) + + f, err := os.Create(*out) + + if err != nil { + log.Fatal(err) + } + + defer f.Close() + + w := csv.NewWriter(f) + defer w.Flush() + + if err := w.Write([]string{"tokenizer", "band_lo", "band_hi", "size", + "morpheme_types", "type_share", "occurrences", "morpheme_occurrences", + "token_share"}); err != nil { + log.Fatal(err) + } + + for _, n := range strings.Split(*list, ",") { + n = strings.TrimSpace(n) + dir := shelf.Item(fmt.Sprintf(*dirs, n)) + + tok, err := bpe.NewTokenizerFromFiles( + shelf.Abs(dir+"/vocab.json"), shelf.Abs(dir+"/merges.txt"), + bpe.Config{Recover: false}) + + if err != nil { + log.Fatal(err) + } + + vocab := bpe.Vocab(tok) + + log.Printf("%s: encoding dictionary over %d sub-words", n, len(vocab)) + + r, err := frequencies(tok, shelf.Abs(shelf.Item(*dict))) + + if err != nil { + log.Fatal(err) + } + + edges := parseBands(*bands, len(vocab)) + + log.Printf("%-6s %10s %9s %9s %11s %9s", n, "band", "types%", "tokens%", "occurrences", "morphs") + + for i := 0; i+1 < len(edges); i++ { + lo, hi := edges[i], edges[i+1] + + var types, morphTypes, occ, morphOcc int + + for id := lo; id < hi && id < len(vocab); id++ { + types++ + occ += r[id] + + if _, ok := morph[vocab[id]]; ok { + morphTypes++ + morphOcc += r[id] + } + } + + row := []string{n, strconv.Itoa(lo), strconv.Itoa(hi), strconv.Itoa(types), + strconv.Itoa(morphTypes), share(morphTypes, types), + strconv.Itoa(occ), strconv.Itoa(morphOcc), share(morphOcc, occ)} + + if err := w.Write(row); err != nil { + log.Fatal(err) + } + + log.Printf("%-6s %10s %8s%% %8s%% %11d %9d", "", + fmt.Sprintf("%d-%d", lo, hi), share(morphTypes, types), + share(morphOcc, occ), occ, morphTypes) + } + + w.Flush() + } + + log.Printf("wrote %s", *out) +} diff --git a/research/knobloch/cmd/plot/main.go b/research/knobloch/cmd/plot/main.go new file mode 100644 index 0000000..e754f6f --- /dev/null +++ b/research/knobloch/cmd/plot/main.go @@ -0,0 +1,58 @@ +package main + +import ( + "fmt" + "log" + + "go.jknobloc.com/x/research/knobloch" + "go.jknobloc.com/x/shelf" + "go.jknobloc.com/x/tokenizer/bpe" +) + +const modelDir = "models/mbpe/minipile" + +// the two families are swept separately, so a model is only ever compared +// against its own kind and the shared/unshared split never mixes m with mi +var families = []string{"m", "mi"} + +func models(family string) []string { + var r []string + + for alpha := 0; alpha <= 100; alpha += 10 { + r = append(r, fmt.Sprintf("gpt2_50256_%s%03d_minipile", family, alpha)) + } + + return r +} + +func main() { + dict := shelf.Abs("results/knobloch/minipile/dict.txt") + + cfg := bpe.Config{ + Recover: false, + } + + for _, family := range families { + names := models(family) + + knobloch.SharedVocabs = nil + + for _, model := range names { + knobloch.SharedVocabs = append(knobloch.SharedVocabs, shelf.Item(modelDir+"/"+model+"/vocab.json")) + } + + for _, model := range names { + dir := shelf.Item(modelDir + "/" + model) + + t, err := bpe.NewTokenizerFromFiles(shelf.Abs(dir+"/vocab.json"), shelf.Abs(dir+"/merges.txt"), cfg) + + if err != nil { + log.Fatal(err) + } + + if err := knobloch.TokenFrequencies(t, dict, model); err != nil { + log.Fatal(err) + } + } + } +} diff --git a/research/knobloch/cmd/rankshift/main.go b/research/knobloch/cmd/rankshift/main.go new file mode 100644 index 0000000..b81e7ea --- /dev/null +++ b/research/knobloch/cmd/rankshift/main.go @@ -0,0 +1,486 @@ +// Command rankshift reports how far the alignment objective moves sub-words in +// the merge order, split by whether the sub-word is a known morpheme. +// +// A variant's vocabulary can only be compared to the baseline's on the sub-words +// they have in common: an unshared sub-word has no baseline position, so there is +// nothing to displace. Over the shared set, each string holds a position in both +// vocabularies, and Spearman's rho between those two position vectors says how +// much the objective has reordered them. +// +// Rho alone is symmetric and says nothing about direction, so the signed +// displacement is reported alongside it. Position is merge order, so a lower id +// is an earlier, more important merge: a negative displacement means the sub-word +// gained rank. The expectation is that morphemes gain and non-morphemes lose, +// with the inverted objective reversing it. +// +// -intersect all (the default) compares every tokenizer on the sub-words the +// whole sweep has in common, matching what the *_shared plots do, so rows are +// comparable to each other. -intersect baseline uses each variant's own +// intersection with the baseline, which keeps far more data per row but makes +// the rows incomparable, since the set shrinks with alpha and does so by +// exactly the displacement being measured. +// +// Reordering only describes sub-words that survive. The added and dropped rows +// cover the rest: how many sub-words the variant swaps out of the baseline's +// vocabulary, and what share of each side is morphemic. +// +// Reads vocabularies only, so it runs in seconds and never touches the corpus. +package main + +import ( + "encoding/csv" + "flag" + "fmt" + "log" + "os" + "slices" + "strconv" + + "gonum.org/v1/gonum/stat" + + "go.jknobloc.com/x/research/knobloch" + "go.jknobloc.com/x/shelf" + "go.jknobloc.com/x/tokenizer/bpe" +) + +var alphas = []int{0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100} + +func name(alpha int, inverted bool) string { + if inverted { + return fmt.Sprintf("mi%03d", alpha) + } + + return fmt.Sprintf("m%03d", alpha) +} + +// names lists every tokenizer in the sweep, baseline first. +func names(baseline string) []string { + var all []string + + for _, inv := range []bool{false, true} { + for _, a := range alphas { + if n := name(a, inv); n != baseline { + all = append(all, n) + } + } + } + + return append([]string{baseline}, all...) +} + +// positions maps each sub-word string to its index in the merge order. +func positions(dir string) (map[string]int, error) { + tok, err := bpe.NewTokenizerFromFiles( + shelf.Abs(shelf.Item(dir)+"/vocab.json"), + shelf.Abs(shelf.Item(dir)+"/merges.txt"), + bpe.Config{Recover: false}) + + if err != nil { + return nil, err + } + + vocab := bpe.Vocab(tok) + p := make(map[string]int, len(vocab)) + + for id, token := range vocab { + p[token] = id + } + + return p, nil +} + +// spearman is the rank correlation between two position vectors. Positions are +// distinct within a vocabulary, so ranking them is just sorting -- no tie +// handling is needed, unlike the frequency ranks in stats.go. +func spearman(a, b []int) float64 { + if len(a) < 2 { + return 0 + } + + return stat.Correlation(ranks(a), ranks(b), nil) +} + +func ranks(v []int) []float64 { + order := make([]int, len(v)) + + for i := range order { + order[i] = i + } + + slices.SortFunc(order, func(x, y int) int { return v[x] - v[y] }) + + r := make([]float64, len(v)) + + for rank, i := range order { + r[i] = float64(rank + 1) + } + + return r +} + +func median(v []int) float64 { + if len(v) == 0 { + return 0 + } + + s := slices.Clone(v) + slices.Sort(s) + + if n := len(s); n%2 == 1 { + return float64(s[n/2]) + } else { + return float64(s[n/2-1]+s[n/2]) / 2 + } +} + +func mean(v []int) float64 { + if len(v) == 0 { + return 0 + } + + sum := 0 + + for _, x := range v { + sum += x + } + + return float64(sum) / float64(len(v)) +} + +func percent(n, total int) string { + if total == 0 { + return "" + } + + return fmt.Sprintf("%.1f", 100*float64(n)/float64(total)) +} + +// group holds the compared sub-words of one class and their positions either +// side, plus how many of them are morphemes. +type group struct { + base, variant []int + shift []int + morphemes int +} + +func (g *group) add(basePos, variantPos int, isMorph bool) { + g.base = append(g.base, basePos) + g.variant = append(g.variant, variantPos) + g.shift = append(g.shift, variantPos-basePos) + + if isMorph { + g.morphemes++ + } +} + +func (g *group) row() []string { + // gained counts sub-words that moved to an earlier merge, i.e. a lower id + gained := 0 + + for _, s := range g.shift { + if s < 0 { + gained++ + } + } + + return []string{ + strconv.Itoa(len(g.shift)), + percent(g.morphemes, len(g.shift)), + fmt.Sprintf("%.4f", spearman(g.base, g.variant)), + fmt.Sprintf("%.1f", median(g.shift)), + fmt.Sprintf("%.1f", mean(g.shift)), + percent(gained, len(g.shift)), + } +} + +// churn is a set of sub-words present on only one side, so it has no +// displacement -- only a size and a morpheme share. +func churn(n, morphemes int) []string { + return []string{strconv.Itoa(n), percent(morphemes, n), "", "", "", ""} +} + +// cohort is a fixed set of sub-word strings, followed across the sweep. The +// sub-words a variant introduces have no baseline position, so they never +// appear in the displacement columns; tracking them from the tokenizer that +// introduced them is the only way to see where they go. +type cohort struct { + tokens []string + origin float64 // median position in the tokenizer that introduced them +} + +func newCohort(tokens []string, at map[string]int) cohort { + return cohort{tokens: tokens, origin: cohortMedian(tokens, at)} +} + +func cohortMedian(tokens []string, at map[string]int) float64 { + present := make([]int, 0, len(tokens)) + + for _, t := range tokens { + if id, ok := at[t]; ok { + present = append(present, id) + } + } + + return median(present) +} + +func (c cohort) row(at map[string]int) []string { + present := 0 + + for _, t := range c.tokens { + if _, ok := at[t]; ok { + present++ + } + } + + med := cohortMedian(c.tokens, at) + + return []string{ + strconv.Itoa(len(c.tokens)), + strconv.Itoa(present), + percent(present, len(c.tokens)), + fmt.Sprintf("%.1f", med), + fmt.Sprintf("%+.1f", med-c.origin), + } +} + +func main() { + dirs := flag.String("dirs", "results/knobloch/minipile_19_ctrl/%s_minipile", + "tokenizer directory, %s is the alignment name") + baseline := flag.String("baseline", "m000", "alignment to compare against") + mode := flag.String("intersect", "all", + "compare on sub-words shared by `all` tokenizers, or only with the `baseline`") + out := flag.String("out", "rank_shift.csv", "output CSV") + track := flag.String("cohort", "", + "follow the sub-words this alignment introduces across the sweep, split by morpheme") + trackOut := flag.String("cohort-out", "rank_cohort.csv", "output CSV for -cohort") + + flag.Parse() + + if *mode != "all" && *mode != "baseline" { + log.Fatalf("unknown -intersect %q", *mode) + } + + sweep := names(*baseline) + + morph, err := knobloch.Morphemes(shelf.Abs(knobloch.SegmentsPath)) + + if err != nil { + log.Fatal(err) + } + + base, err := positions(fmt.Sprintf(*dirs, *baseline)) + + if err != nil { + log.Fatal(err) + } + + log.Printf("baseline %s: %d sub-words, %d known morphemes", *baseline, len(base), len(morph)) + + // with -intersect all the comparison set is fixed before any variant is + // scored, so every row is computed on the same sub-words. Built in its own + // pass to avoid holding the whole sweep's vocabularies in memory at once. + var common map[string]struct{} + + if *mode == "all" { + common = make(map[string]struct{}, len(base)) + + for token := range base { + common[token] = struct{}{} + } + + for _, n := range sweep[1:] { + p, err := positions(fmt.Sprintf(*dirs, n)) + + if err != nil { + log.Fatal(err) + } + + for token := range common { + if _, ok := p[token]; !ok { + delete(common, token) + } + } + } + + log.Printf("intersection over the whole sweep: %d sub-words", len(common)) + } + + // the cohort is fixed before the sweep is scored: the sub-words the chosen + // alignment adds to the baseline, split by whether they are morphemes + var cohorts map[string]cohort + + if *track != "" { + ref, err := positions(fmt.Sprintf(*dirs, *track)) + + if err != nil { + log.Fatal(err) + } + + var morphTokens, otherTokens []string + + for token := range ref { + if _, inBase := base[token]; inBase { + continue + } + + if _, isMorph := morph[token]; isMorph { + morphTokens = append(morphTokens, token) + } else { + otherTokens = append(otherTokens, token) + } + } + + cohorts = map[string]cohort{ + "morpheme": newCohort(morphTokens, ref), + "other": newCohort(otherTokens, ref), + } + + log.Printf("cohort from %s: %d added sub-words, %d morphemes (%s%%)", + *track, len(morphTokens)+len(otherTokens), len(morphTokens), + percent(len(morphTokens), len(morphTokens)+len(otherTokens))) + } + + f, err := os.Create(*out) + + if err != nil { + log.Fatal(err) + } + + defer f.Close() + + w := csv.NewWriter(f) + defer w.Flush() + + header := []string{"tokenizer", "alignment", "inverted", "class", + "n", "morpheme_pct", "spearman", "median_shift", "mean_shift", "gained_pct"} + + if err := w.Write(header); err != nil { + log.Fatal(err) + } + + var cw *csv.Writer + + if cohorts != nil { + cf, err := os.Create(*trackOut) + + if err != nil { + log.Fatal(err) + } + + defer cf.Close() + + cw = csv.NewWriter(cf) + defer cw.Flush() + + if err := cw.Write([]string{"tokenizer", "alignment", "inverted", "class", + "cohort", "present", "present_pct", "median_id", "shift_from_origin"}); err != nil { + log.Fatal(err) + } + } + + for _, n := range sweep[1:] { + variant, err := positions(fmt.Sprintf(*dirs, n)) + + if err != nil { + log.Fatal(err) + } + + var all, morpheme, other group + var dropped, droppedMorph, added, addedMorph int + + for token, basePos := range base { + _, isMorph := morph[token] + variantPos, ok := variant[token] + + if !ok { + dropped++ + + if isMorph { + droppedMorph++ + } + + continue + } + + if common != nil { + if _, keep := common[token]; !keep { + continue + } + } + + all.add(basePos, variantPos, isMorph) + + if isMorph { + morpheme.add(basePos, variantPos, isMorph) + } else { + other.add(basePos, variantPos, isMorph) + } + } + + for token := range variant { + if _, ok := base[token]; !ok { + added++ + + if _, isMorph := morph[token]; isMorph { + addedMorph++ + } + } + } + + alpha, inverted := n[len(n)-3:], n[:2] == "mi" + + a, err := strconv.Atoi(alpha) + + if err != nil { + log.Fatal(err) + } + + rows := []struct { + label string + cells []string + }{ + {"all", all.row()}, + {"morpheme", morpheme.row()}, + {"other", other.row()}, + {"added", churn(added, addedMorph)}, + {"dropped", churn(dropped, droppedMorph)}, + } + + for _, r := range rows { + row := append([]string{ + n, + fmt.Sprintf("%.1f", float64(a)/100), + strconv.FormatBool(inverted), + r.label, + }, r.cells...) + + if err := w.Write(row); err != nil { + log.Fatal(err) + } + } + + if cw != nil { + for _, c := range []string{"morpheme", "other"} { + row := append([]string{ + n, + fmt.Sprintf("%.1f", float64(a)/100), + strconv.FormatBool(inverted), + c, + }, cohorts[c].row(variant)...) + + if err := cw.Write(row); err != nil { + log.Fatal(err) + } + } + } + + log.Printf("%-6s compared %6d rho %.4f morph %+8.1f other %+8.1f "+ + "added %6d (%s%% morph) dropped %6d (%s%% morph)", + n, len(all.shift), spearman(all.base, all.variant), + median(morpheme.shift), median(other.shift), + added, percent(addedMorph, added), dropped, percent(droppedMorph, dropped)) + } + + log.Printf("wrote %s", *out) +} diff --git a/research/knobloch/cmd/tablea/main.go b/research/knobloch/cmd/tablea/main.go new file mode 100644 index 0000000..37fa877 --- /dev/null +++ b/research/knobloch/cmd/tablea/main.go @@ -0,0 +1,144 @@ +// Command tablea writes table A for a chosen set of tokenizers rather than the +// whole grid. +// +// Table A is a per-tokenizer statistic, so unlike tables B and C it needs no +// intersection and therefore no encode of the tokenizers that are not shown. +// Restricting the set cuts the work proportionally: three alignment levels at +// five vocabulary sizes is fifteen encodes instead of the full hundred and ten. +// +// The alignment column carries an " inv" suffix for the inverted family, which +// the full-grid command does not add. +package main + +import ( + "flag" + "fmt" + "log" + "runtime" + "strconv" + "strings" + "sync" + + "github.com/jonasknobloch/mbpe" + "go.jknobloc.com/x/research/knobloch" + "go.jknobloc.com/x/shelf" +) + +var vocabSizes = []int{8192, 16384, 32768, 50256, 100512} + +// spec derives the alignment level from the tokenizer name, e.g. m050 or mi100. +func spec(size int, name string) (knobloch.TableSpec, error) { + inverted := strings.HasPrefix(name, "mi") + + digits := strings.TrimPrefix(strings.TrimPrefix(name, "mi"), "m") + + alpha, err := strconv.Atoi(digits) + + if err != nil { + return knobloch.TableSpec{}, fmt.Errorf("%s: cannot read an alignment level from the name", name) + } + + alignment := fmt.Sprintf("%.1f", float64(alpha)/100) + + if inverted { + alignment += " inv" + } + + return knobloch.TableSpec{ + Name: name, + Alignment: alignment, + Inverted: inverted, + VocabSize: size, + Dir: shelf.Item(fmt.Sprintf("tokenizers/minipile/tokenizer_gpt2_%d_%s_minipile", size, name)), + }, nil +} + +func main() { + dict := flag.String("dict", "results/knobloch/minipile/dict.txt", "shelf-relative dictionary") + names := flag.String("tokenizers", "m000,m050,m100", "comma separated tokenizer names") + sizes := flag.String("sizes", "", "comma separated vocabulary sizes, empty for all") + out := flag.String("out", "table_a_alphas.csv", "output CSV") + workers := flag.Int("workers", runtime.NumCPU(), "parallel encodes") + + flag.Parse() + + selected := vocabSizes + + if *sizes != "" { + selected = nil + + for _, s := range strings.Split(*sizes, ",") { + v, err := strconv.Atoi(strings.TrimSpace(s)) + + if err != nil { + log.Fatalf("bad vocabulary size %q", s) + } + + selected = append(selected, v) + } + } + + var specs []knobloch.TableSpec + + for _, size := range selected { + for _, name := range strings.Split(*names, ",") { + s, err := spec(size, strings.TrimSpace(name)) + + if err != nil { + log.Fatal(err) + } + + specs = append(specs, s) + } + } + + d := mbpe.NewDict() + + if err := d.Load(shelf.Abs(shelf.Item(*dict))); err != nil { + log.Fatal(err) + } + + items := d.Items() + + log.Printf("dictionary: %d pre-token types", len(items)) + log.Printf("%d encodes: %s at %v", len(specs), *names, selected) + + rows := make([]knobloch.TableARow, len(specs)) + + var wg sync.WaitGroup + + queue := make(chan int) + + for i := 0; i < *workers; i++ { + wg.Add(1) + + go func() { + defer wg.Done() + + for idx := range queue { + e, err := knobloch.EncodeDict(specs[idx], items) + + if err != nil { + log.Fatal(err) + } + + rows[idx] = knobloch.BuildTableA(e) + + log.Printf("%s at %d: encoded", specs[idx].Name, specs[idx].VocabSize) + } + }() + } + + for i := range specs { + queue <- i + } + + close(queue) + wg.Wait() + + if err := knobloch.WriteTableA(*out, rows); err != nil { + log.Fatal(err) + } + + log.Printf("wrote %s", *out) +} diff --git a/research/knobloch/cmd/tableb/main.go b/research/knobloch/cmd/tableb/main.go new file mode 100644 index 0000000..eca5ec9 --- /dev/null +++ b/research/knobloch/cmd/tableb/main.go @@ -0,0 +1,350 @@ +// Command tableb writes table B for a chosen set of tokenizers at one +// vocabulary size, rather than the whole grid. +// +// Everything comes from the dictionary, the segmentation and the tokenizers +// themselves. Nothing here reads a trained model, so the table stays a property +// of the tokenizer and the corpus. +// +// Two schemas: +// +// current what WriteTableB emits today: morph_count, the two morph shares, +// pct_rank_morph / pct_rank_other, shared_morph / shared_other +// legacy the columns of the published table_b.csv: types_used, the shares +// denominated by used types, absolute median frequencies, and the two +// shared_* columns measured against the baseline rather than an +// intersection +// +// The two disagree about more than names. The current schema divides the type +// share by the whole vocabulary and reports the median's percentile rank, which +// is comparable across vocabulary sizes; the legacy one divides by used types +// and reports the median itself, which is not. At a single size either is fine. +// +// Unlike table A, table B needs a vocabulary intersection for the current +// schema's shared_* columns. Building that only reads vocab.json files and costs +// nothing, so it still covers all 22 tokenizers at the size by default even when +// far fewer rows are written — otherwise "shared" would silently mean a +// different thing here than in the full-grid table. Pass -intersect listed to +// restrict it. The legacy schema ignores it and uses -baseline instead. +// +// The alignment column carries an " inv" suffix for the inverted family, which +// the full-grid command does not add. +package main + +import ( + "encoding/csv" + "flag" + "fmt" + "log" + "os" + "runtime" + "slices" + "strconv" + "strings" + "sync" + + "github.com/jonasknobloch/mbpe" + "go.jknobloc.com/x/research/knobloch" + "go.jknobloc.com/x/shelf" +) + +var alphaIDs = []string{"000", "010", "020", "030", "040", "050", "060", "070", "080", "090", "100"} + +func dir(size int, name string) shelf.Item { + return shelf.Item(fmt.Sprintf("tokenizers/minipile/tokenizer_gpt2_%d_%s_minipile", size, name)) +} + +// spec derives the alignment level from the tokenizer name, e.g. m050 or mi100. +func spec(size int, name string) (knobloch.TableSpec, error) { + inverted := strings.HasPrefix(name, "mi") + + digits := strings.TrimPrefix(strings.TrimPrefix(name, "mi"), "m") + + alpha, err := strconv.Atoi(digits) + + if err != nil { + return knobloch.TableSpec{}, fmt.Errorf("%s: cannot read an alignment level from the name", name) + } + + alignment := fmt.Sprintf("%.1f", float64(alpha)/100) + + if inverted { + alignment += " inv" + } + + return knobloch.TableSpec{ + Name: name, + Alignment: alignment, + Inverted: inverted, + VocabSize: size, + Dir: dir(size, name), + }, nil +} + +// median matches the package's own: the upper-middle element of the sorted +// slice, not the average of the middle two. +func median(v []int) int { + if len(v) == 0 { + return 0 + } + + slices.Sort(v) + + return v[len(v)/2] +} + +func share(part, whole int) float64 { + if whole == 0 { + return 0 + } + + return 100 * float64(part) / float64(whole) +} + +// classify splits a vocabulary into the tokens the segmentation calls morphemes +// and the rest. +func classify(e *knobloch.Encoded, morph map[string]int) (morphemes, other map[string]struct{}) { + morphemes = make(map[string]struct{}) + other = make(map[string]struct{}) + + for id := range e.Counts { + token := e.Itoa[int64(id)] + + if _, ok := morph[token]; ok { + morphemes[token] = struct{}{} + } else { + other[token] = struct{}{} + } + } + + return morphemes, other +} + +func retained(base map[string]struct{}, e *knobloch.Encoded) float64 { + kept := 0 + + for id := range e.Counts { + if _, ok := base[e.Itoa[int64(id)]]; ok { + kept++ + } + } + + return share(kept, len(base)) +} + +func legacyRow(e *knobloch.Encoded, morph map[string]int, baseMorph, baseOther map[string]struct{}) []string { + var morphFreq, otherFreq []int + var morphTokens, otherTokens int64 + + typesUsed, typesMorph := 0, 0 + + for id, f := range e.Counts { + token := e.Itoa[int64(id)] + + if f > 0 { + typesUsed++ + } + + if _, ok := morph[token]; ok { + typesMorph++ + morphTokens += int64(f) + morphFreq = append(morphFreq, f) + } else { + otherTokens += int64(f) + otherFreq = append(otherFreq, f) + } + } + + return []string{ + e.Spec.Name, strconv.Itoa(e.Spec.VocabSize), e.Spec.Alignment, + strconv.FormatFloat(e.Fertility(), 'f', 4, 64), + strconv.Itoa(typesUsed), strconv.Itoa(typesMorph), + strconv.FormatFloat(share(typesMorph, typesUsed), 'f', 2, 64), + strconv.FormatFloat(share(int(morphTokens), int(morphTokens+otherTokens)), 'f', 2, 64), + strconv.Itoa(median(morphFreq)), strconv.Itoa(median(otherFreq)), + strconv.FormatFloat(retained(baseMorph, e), 'f', 2, 64), + strconv.FormatFloat(retained(baseOther, e), 'f', 2, 64), + } +} + +func main() { + dict := flag.String("dict", "results/knobloch/minipile/dict.txt", "shelf-relative dictionary") + size := flag.Int("size", 50256, "vocabulary size") + names := flag.String("tokenizers", "", "comma separated tokenizer names, empty for the 11 aligned") + schema := flag.String("schema", "legacy", "column set: legacy or current") + baseline := flag.String("baseline", "m000", "legacy schema: tokenizer the shared_* columns measure retention against") + intersect := flag.String("intersect", "all", "current schema: vocabularies behind shared_*, all (22) or listed") + out := flag.String("out", "table_b_aligned.csv", "output CSV") + workers := flag.Int("workers", runtime.NumCPU(), "parallel encodes") + + flag.Parse() + + var selected []string + + if *names == "" { + for _, a := range alphaIDs { + selected = append(selected, "m"+a) + } + } else { + for _, n := range strings.Split(*names, ",") { + selected = append(selected, strings.TrimSpace(n)) + } + } + + // the legacy shared_* columns need the baseline encoded even if it is not a + // row, so add it and drop it again before writing + encode := slices.Clone(selected) + + if *schema == "legacy" && !slices.Contains(encode, *baseline) { + encode = append(encode, *baseline) + } + + d := mbpe.NewDict() + + if err := d.Load(shelf.Abs(shelf.Item(*dict))); err != nil { + log.Fatal(err) + } + + items := d.Items() + + log.Printf("dictionary: %d pre-token types", len(items)) + log.Printf("segmentation: %s", shelf.Abs(knobloch.SegmentsPath)) + log.Printf("%d encodes at vocab %d: %s", len(encode), *size, strings.Join(encode, ",")) + + encoded := make([]*knobloch.Encoded, len(encode)) + + var wg sync.WaitGroup + + queue := make(chan int) + + for i := 0; i < *workers; i++ { + wg.Add(1) + + go func() { + defer wg.Done() + + for idx := range queue { + s, err := spec(*size, encode[idx]) + + if err != nil { + log.Fatal(err) + } + + e, err := knobloch.EncodeDict(s, items) + + if err != nil { + log.Fatal(err) + } + + encoded[idx] = e + + log.Printf("%s: encoded", encode[idx]) + } + }() + } + + for i := range encode { + queue <- i + } + + close(queue) + wg.Wait() + + at := func(name string) *knobloch.Encoded { + for i, n := range encode { + if n == name { + return encoded[i] + } + } + + log.Fatalf("missing encode for %s", name) + + return nil + } + + if *schema == "current" { + var basis []shelf.Item + + if *intersect == "listed" { + for _, n := range selected { + basis = append(basis, dir(*size, n)) + } + } else { + for _, p := range []string{"m", "mi"} { + for _, a := range alphaIDs { + basis = append(basis, dir(*size, p+a)) + } + } + } + + shared, err := knobloch.VocabIntersection(basis) + + if err != nil { + log.Fatal(err) + } + + log.Printf("intersection over %d vocabularies: %d shared tokens", len(basis), len(shared)) + + rows := make([]knobloch.TableBRow, 0, len(selected)) + + for _, n := range selected { + row, err := knobloch.BuildTableB(at(n), shared) + + if err != nil { + log.Fatal(err) + } + + rows = append(rows, row) + } + + if err := knobloch.WriteTableB(*out, rows); err != nil { + log.Fatal(err) + } + + log.Printf("wrote %s", *out) + + return + } + + morph, err := knobloch.Morphemes(shelf.Abs(knobloch.SegmentsPath)) + + if err != nil { + log.Fatal(err) + } + + baseMorph, baseOther := classify(at(*baseline), morph) + + log.Printf("baseline %s: %d morphemes, %d other", *baseline, len(baseMorph), len(baseOther)) + + file, err := os.Create(*out) + + if err != nil { + log.Fatal(err) + } + + defer file.Close() + + w := csv.NewWriter(file) + + if err := w.Write([]string{ + "tokenizer", "vocab_size", "alignment", "fertility", + "types_used", "types_morph", "types_morph_share", "tokens_morph_share", + "median_freq_morph", "median_freq_other", + "types_shared_morph_share", "types_shared_other_share", + }); err != nil { + log.Fatal(err) + } + + for _, n := range selected { + if err := w.Write(legacyRow(at(n), morph, baseMorph, baseOther)); err != nil { + log.Fatal(err) + } + } + + w.Flush() + + if err := w.Error(); err != nil { + log.Fatal(err) + } + + log.Printf("wrote %s", *out) +} diff --git a/research/knobloch/cmd/tables/main.go b/research/knobloch/cmd/tables/main.go new file mode 100644 index 0000000..27c3f0c --- /dev/null +++ b/research/knobloch/cmd/tables/main.go @@ -0,0 +1,220 @@ +// Command tables writes the tokenizer characterisation CSVs described in +// FREQUENCIES.md. +// +// Coverage is the full grid: every alignment level in both directions, at every +// vocabulary size we have tokenizers for. Statistics are over the MiniPile train +// dictionary. +// +// Encoding the dictionary dominates the runtime and the encodes are independent, +// so they run on a worker pool. One vocabulary size is processed at a time, +// since table C compares tokenizers within a size and the comparison inputs for +// a whole size have to be resident together. +package main + +import ( + "flag" + "fmt" + "log" + "runtime" + "sync" + + "github.com/jonasknobloch/mbpe" + "go.jknobloc.com/x/research/knobloch" + "go.jknobloc.com/x/shelf" +) + +var ( + vocabSizes = []int{8192, 16384, 32768, 50256, 100512} + alphas = []int{0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100} +) + +// name is the tokenizer directory suffix, e.g. m050 or mi050. +func name(alpha int, inverted bool) string { + if inverted { + return fmt.Sprintf("mi%03d", alpha) + } + + return fmt.Sprintf("m%03d", alpha) +} + +func spec(size, alpha int, inverted bool) knobloch.TableSpec { + n := name(alpha, inverted) + + return knobloch.TableSpec{ + Name: n, + Alignment: fmt.Sprintf("%.1f", float64(alpha)/100), + Inverted: inverted, + VocabSize: size, + Dir: shelf.Item(fmt.Sprintf("tokenizers/minipile/tokenizer_gpt2_%d_%s_minipile", size, n)), + } +} + +func main() { + dict := flag.String("dict", "results/knobloch/minipile/dict.txt", "shelf-relative dictionary") + prefix := flag.String("prefix", "table", "output file prefix") + workers := flag.Int("workers", runtime.NumCPU(), "parallel encodes") + only := flag.Int("only", 0, "restrict to a single vocabulary size, for smoke runs") + + flag.Parse() + + sizes := vocabSizes + + if *only != 0 { + sizes = []int{*only} + } + + d := mbpe.NewDict() + + if err := d.Load(shelf.Abs(shelf.Item(*dict))); err != nil { + log.Fatal(err) + } + + items := d.Items() + + log.Printf("dictionary: %d pre-token types", len(items)) + + var ( + rowsA []knobloch.TableARow + rowsB []knobloch.TableBRow + + aligned []knobloch.TableCRow + inverted []knobloch.TableCRow + invVsAlign []knobloch.TableCRow + ) + + for _, size := range sizes { + // every tokenizer at this size, aligned then inverted + var specs []knobloch.TableSpec + + for _, inv := range []bool{false, true} { + for _, a := range alphas { + specs = append(specs, spec(size, a, inv)) + } + } + + dirs := make([]shelf.Item, 0, len(specs)) + + for _, s := range specs { + dirs = append(dirs, s.Dir) + } + + // table B measures sharing against the intersection of every vocabulary + // at this size, so the baseline is just another tokenizer + shared, err := knobloch.VocabIntersection(dirs) + + if err != nil { + log.Fatal(err) + } + + log.Printf("vocab %d: %d tokenizers, intersection %d tokens", size, len(specs), len(shared)) + + encoded := make([]*knobloch.Encoded, len(specs)) + + var wg sync.WaitGroup + + queue := make(chan int) + + for i := 0; i < *workers; i++ { + wg.Add(1) + + go func() { + defer wg.Done() + + for idx := range queue { + e, err := knobloch.EncodeDict(specs[idx], items) + + if err != nil { + log.Fatal(err) + } + + encoded[idx] = e + } + }() + } + + for i := range specs { + queue <- i + } + + close(queue) + wg.Wait() + + log.Printf("vocab %d: encoded", size) + + // index by (alpha, direction) for the pairings below + at := func(alpha int, inv bool) *knobloch.Encoded { + for i, s := range specs { + if s.Inverted == inv && s.Name == name(alpha, inv) { + return encoded[i] + } + } + + log.Fatalf("missing encode for %d/%s", size, name(alpha, inv)) + + return nil + } + + base := at(0, false) + + for _, e := range encoded { + rowsA = append(rowsA, knobloch.BuildTableA(e)) + + b, err := knobloch.BuildTableB(e, shared) + + if err != nil { + log.Fatal(err) + } + + rowsB = append(rowsB, b) + } + + for _, a := range alphas { + al := at(a, false) + inv := at(a, true) + + // aligned vs the alpha=0 baseline + r, err := knobloch.BuildTableC(al, base, items) + + if err != nil { + log.Fatal(err) + } + + aligned = append(aligned, r) + + // inverted vs the alpha=0 baseline + r, err = knobloch.BuildTableC(inv, base, items) + + if err != nil { + log.Fatal(err) + } + + inverted = append(inverted, r) + + // inverted vs aligned at matching alpha + r, err = knobloch.BuildTableC(inv, al, items) + + if err != nil { + log.Fatal(err) + } + + invVsAlign = append(invVsAlign, r) + } + } + + for _, out := range []struct { + name string + err error + }{ + {*prefix + "_a.csv", knobloch.WriteTableA(*prefix+"_a.csv", rowsA)}, + {*prefix + "_b.csv", knobloch.WriteTableB(*prefix+"_b.csv", rowsB)}, + {*prefix + "_c_aligned.csv", knobloch.WriteTableC(*prefix+"_c_aligned.csv", aligned)}, + {*prefix + "_c_inverted.csv", knobloch.WriteTableC(*prefix+"_c_inverted.csv", inverted)}, + {*prefix + "_c_inverted_vs_aligned.csv", knobloch.WriteTableC(*prefix+"_c_inverted_vs_aligned.csv", invVsAlign)}, + } { + if out.err != nil { + log.Fatal(out.err) + } + + log.Printf("wrote %s", out.name) + } +} diff --git a/research/knobloch/cmd/window/main.go b/research/knobloch/cmd/window/main.go new file mode 100644 index 0000000..055e3cb --- /dev/null +++ b/research/knobloch/cmd/window/main.go @@ -0,0 +1,254 @@ +// Command window reports how frequent the tokens in the RDD estimation window +// are, for every alignment level. +// +// The setup mirrors lesci. The window and its constituent filter come from the +// counterfactual tokenizer, which is what lesci builds its rules from. Corpus +// frequencies come from whichever tokenizer actually produces the token: below +// the cutoff that is the model's own tokenizer, above it the token does not +// exist for the model and only the counterfactual produces it. +// +// Frequencies are counted over a dictionary, so pointing -dict at another split +// reports the same statistic over that split. +package main + +import ( + "encoding/csv" + "flag" + "fmt" + "log" + "os" + "runtime" + "slices" + "strconv" + "sync" + + "github.com/jonasknobloch/mbpe" + "go.jknobloc.com/x/research/knobloch" + "go.jknobloc.com/x/shelf" + "go.jknobloc.com/x/tokenizer/bpe" +) + +var alphas = []int{0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100} + +func name(alpha int, inverted bool) string { + if inverted { + return fmt.Sprintf("mi%03d", alpha) + } + + return fmt.Sprintf("m%03d", alpha) +} + +// summary of one group of window tokens +type summary struct { + n int + zero int + median int + q25 int + q75 int + mean float64 +} + +func summarise(freqs []int) summary { + s := summary{n: len(freqs)} + + if len(freqs) == 0 { + return s + } + + slices.Sort(freqs) + + var sum int64 + + for _, f := range freqs { + sum += int64(f) + + if f == 0 { + s.zero++ + } + } + + s.median = freqs[len(freqs)/2] + s.q25 = freqs[len(freqs)/4] + s.q75 = freqs[3*len(freqs)/4] + s.mean = float64(sum) / float64(len(freqs)) + + return s +} + +type row struct { + name string + alignment string + + all summary + observed summary + oov summary +} + +func encode(dir shelf.Item, items []mbpe.Chunk) ([]int, *bpe.Tokenizer) { + tok, err := bpe.NewTokenizerFromFiles( + shelf.Abs(dir+"/vocab.json"), shelf.Abs(dir+"/merges.txt"), + bpe.Config{Recover: false}) + + if err != nil { + log.Fatal(err) + } + + // the dictionary is already pre-tokenised + bpe.MBPE(tok).SetPreTokenizer(&knobloch.NoPreTok{}) + + counts := make([]int, len(bpe.Vocab(tok))) + + for _, v := range items { + for _, id := range tok.Encode(v.Src()) { + counts[id] += v.N() + } + } + + return counts, tok +} + +func main() { + dict := flag.String("dict", "results/knobloch/minipile/dict.txt", "shelf-relative dictionary") + model := flag.String("model", "tokenizers/minipile/tokenizer_gpt2_50256_%s_minipile", "model tokenizer directory, %s is the alignment name") + ctrl := flag.String("ctrl", "results/knobloch/minipile_19_ctrl/%s_minipile", "counterfactual tokenizer directory, %s is the alignment name") + cutoff := flag.Int("cutoff", 50256, "RDD cutoff, i.e. the vocabulary size of the model under test") + window := flag.Int("window", 5000, "half-width of the estimation window in token ids") + out := flag.String("out", "window_frequencies.csv", "output CSV") + workers := flag.Int("workers", runtime.NumCPU(), "parallel encodes") + + flag.Parse() + + // the window selector reads these + knobloch.LesciCutoff = *cutoff + knobloch.LesciWindow = *window + + d := mbpe.NewDict() + + if err := d.Load(shelf.Abs(shelf.Item(*dict))); err != nil { + log.Fatal(err) + } + + items := d.Items() + + log.Printf("dictionary: %d pre-token types", len(items)) + log.Printf("cutoff %d, window ids [%d, %d)", *cutoff, *cutoff-*window, *cutoff+*window) + log.Printf("observed side from %s, counterfactual side from %s", *model, *ctrl) + + type job struct { + name string + alignment string + } + + var jobs []job + + for _, inv := range []bool{false, true} { + for _, a := range alphas { + jobs = append(jobs, job{name(a, inv), fmt.Sprintf("%.1f", float64(a)/100)}) + } + } + + rows := make([]row, len(jobs)) + + var wg sync.WaitGroup + + queue := make(chan int) + + for i := 0; i < *workers; i++ { + wg.Add(1) + + go func() { + defer wg.Done() + + for idx := range queue { + j := jobs[idx] + + observed, _ := encode(shelf.Item(fmt.Sprintf(*model, j.name)), items) + counterfactual, ctfTok := encode(shelf.Item(fmt.Sprintf(*ctrl, j.name)), items) + + if len(counterfactual) <= *cutoff+*window { + log.Fatalf("%s: counterfactual vocabulary %d does not reach the top of the window %d", + j.name, len(counterfactual), *cutoff+*window) + } + + w := knobloch.WindowFrequencies(observed, counterfactual, ctfTok) + + var all, obs, oov []int + + for _, f := range w { + all = append(all, f.Freq) + + if f.OOV { + oov = append(oov, f.Freq) + } else { + obs = append(obs, f.Freq) + } + } + + rows[idx] = row{ + name: j.name, + alignment: j.alignment, + all: summarise(all), + observed: summarise(obs), + oov: summarise(oov), + } + + log.Printf("%s: window %d tokens, median %d (observed %d, oov %d)", + j.name, rows[idx].all.n, rows[idx].all.median, + rows[idx].observed.median, rows[idx].oov.median) + } + }() + } + + for i := range jobs { + queue <- i + } + + close(queue) + wg.Wait() + + file, err := os.Create(*out) + + if err != nil { + log.Fatal(err) + } + + defer file.Close() + + w := csv.NewWriter(file) + + header := []string{"tokenizer", "alignment", "cutoff", "window"} + + for _, g := range []string{"", "observed_", "oov_"} { + header = append(header, + g+"n_tokens", g+"n_zero", g+"median_freq", g+"q25_freq", g+"q75_freq", g+"mean_freq") + } + + if err := w.Write(header); err != nil { + log.Fatal(err) + } + + for _, r := range rows { + rec := []string{ + r.name, r.alignment, strconv.Itoa(*cutoff), strconv.Itoa(*window), + } + + for _, s := range []summary{r.all, r.observed, r.oov} { + rec = append(rec, + strconv.Itoa(s.n), strconv.Itoa(s.zero), strconv.Itoa(s.median), + strconv.Itoa(s.q25), strconv.Itoa(s.q75), + strconv.FormatFloat(s.mean, 'f', 2, 64)) + } + + if err := w.Write(rec); err != nil { + log.Fatal(err) + } + } + + w.Flush() + + if err := w.Error(); err != nil { + log.Fatal(err) + } + + log.Printf("wrote %s", *out) +} diff --git a/research/knobloch/cmd/windowoverlap/main.go b/research/knobloch/cmd/windowoverlap/main.go new file mode 100644 index 0000000..3c651d1 --- /dev/null +++ b/research/knobloch/cmd/windowoverlap/main.go @@ -0,0 +1,190 @@ +// Command windowoverlap reports how much the RDD estimation windows of different +// alignment levels contain the same tokens. +// +// The window is a slice of vocabulary-id space, so each alignment puts different +// tokens in it. If the windows overlap little, the bias estimator is reading a +// largely different token population for each tokenizer, which bears on whether +// their estimates are comparable. +// +// Membership depends only on the counterfactual vocabulary and its merges, so +// this runs in seconds and never touches the corpus. +package main + +import ( + "encoding/csv" + "flag" + "fmt" + "log" + "os" + "strconv" + + "go.jknobloc.com/x/research/knobloch" + "go.jknobloc.com/x/shelf" + "go.jknobloc.com/x/tokenizer/bpe" +) + +var alphas = []int{0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100} + +func name(alpha int, inverted bool) string { + if inverted { + return fmt.Sprintf("mi%03d", alpha) + } + + return fmt.Sprintf("m%03d", alpha) +} + +func set(v []string) map[string]struct{} { + s := make(map[string]struct{}, len(v)) + + for _, x := range v { + s[x] = struct{}{} + } + + return s +} + +// share of a that is also in b +func overlap(a []string, b map[string]struct{}) float64 { + if len(a) == 0 { + return 0 + } + + n := 0 + + for _, x := range a { + if _, ok := b[x]; ok { + n++ + } + } + + return 100 * float64(n) / float64(len(a)) +} + +type entry struct { + name string + alignment string + observed []string + oov []string +} + +func main() { + ctrl := flag.String("ctrl", "results/knobloch/minipile_19_ctrl/%s_minipile", "counterfactual tokenizer directory, %s is the alignment name") + cutoff := flag.Int("cutoff", 50256, "RDD cutoff") + window := flag.Int("window", 5000, "half-width of the estimation window in token ids") + out := flag.String("out", "window_overlap.csv", "output CSV") + + flag.Parse() + + knobloch.LesciCutoff = *cutoff + knobloch.LesciWindow = *window + + log.Printf("cutoff %d, window ids [%d, %d)", *cutoff, *cutoff-*window, *cutoff+*window) + + var entries []entry + + for _, inv := range []bool{false, true} { + for _, a := range alphas { + n := name(a, inv) + + dir := shelf.Item(fmt.Sprintf(*ctrl, n)) + + tok, err := bpe.NewTokenizerFromFiles( + shelf.Abs(dir+"/vocab.json"), shelf.Abs(dir+"/merges.txt"), + bpe.Config{Recover: false}) + + if err != nil { + log.Fatal(err) + } + + obs, oov := knobloch.WindowTokens(tok) + + entries = append(entries, entry{n, fmt.Sprintf("%.1f", float64(a)/100), obs, oov}) + } + } + + // whole-window membership, ignoring which side of the cutoff a token landed + // on, plus the side-matched version; the gap between them is tokens that are + // in both windows but have crossed the cutoff + all := func(e entry) []string { return append(append([]string{}, e.observed...), e.oov...) } + + interAll := set(all(entries[0])) + interObs := set(entries[0].observed) + interOOV := set(entries[0].oov) + + for _, e := range entries[1:] { + cur := set(all(e)) + + for t := range interAll { + if _, ok := cur[t]; !ok { + delete(interAll, t) + } + } + + cur = set(e.observed) + + for t := range interObs { + if _, ok := cur[t]; !ok { + delete(interObs, t) + } + } + + cur = set(e.oov) + + for t := range interOOV { + if _, ok := cur[t]; !ok { + delete(interOOV, t) + } + } + } + + baseAll := set(all(entries[0])) + baseObs := set(entries[0].observed) + baseOOV := set(entries[0].oov) + + log.Printf("intersection across %d tokenizers: %d whole window, %d observed, %d oov", + len(entries), len(interAll), len(interObs), len(interOOV)) + + file, err := os.Create(*out) + + if err != nil { + log.Fatal(err) + } + + defer file.Close() + + w := csv.NewWriter(file) + + if err := w.Write([]string{ + "tokenizer", "alignment", "cutoff", "window", + "n_window", "n_observed", "n_oov", + "window_shared_base", "window_shared_all", + "observed_shared_base", "oov_shared_base", + "observed_shared_all", "oov_shared_all", + }); err != nil { + log.Fatal(err) + } + + for _, e := range entries { + if err := w.Write([]string{ + e.name, e.alignment, strconv.Itoa(*cutoff), strconv.Itoa(*window), + strconv.Itoa(len(e.observed) + len(e.oov)), + strconv.Itoa(len(e.observed)), strconv.Itoa(len(e.oov)), + strconv.FormatFloat(overlap(all(e), baseAll), 'f', 2, 64), + strconv.FormatFloat(overlap(all(e), interAll), 'f', 2, 64), + strconv.FormatFloat(overlap(e.observed, baseObs), 'f', 2, 64), + strconv.FormatFloat(overlap(e.oov, baseOOV), 'f', 2, 64), + strconv.FormatFloat(overlap(e.observed, interObs), 'f', 2, 64), + strconv.FormatFloat(overlap(e.oov, interOOV), 'f', 2, 64), + }); err != nil { + log.Fatal(err) + } + } + + w.Flush() + + if err := w.Error(); err != nil { + log.Fatal(err) + } + + log.Printf("wrote %s", *out) +} diff --git a/research/knobloch/lesci.go b/research/knobloch/lesci.go new file mode 100644 index 0000000..39f182c --- /dev/null +++ b/research/knobloch/lesci.go @@ -0,0 +1,260 @@ +package knobloch + +import ( + "fmt" + "image/color" + + "go.jknobloc.com/x/tokenizer/bpe" + "gonum.org/v1/plot" + "gonum.org/v1/plot/plotter" + "gonum.org/v1/plot/vg" +) + +// The vocabulary cutoff the lesci experiment splits on, and the window either +// side of it that the figure covers. +var ( + LesciCutoff = 32768 + LesciWindow = 5000 +) + +// lesciMask selects the vocab ids inside the window around the cutoff, dropping +// every token that is itself a constituent of another merge rule in that window. +// +// This is lesci.Window followed by lesci.Filter (research/lesci/lesci.go), +// reimplemented rather than imported: lesci is a separate module and its version +// works on a tensor.Dense[int64] merge table we would have to build anyway. The +// behaviour is mirrored exactly so these figures compare against that chapter. +// +// That includes lesci.Filter only dropping constituents below the cutoff, which +// makes the filter asymmetric: above the cutoff nothing is dropped. lesci.OutOfVocab +// is not applied, since keeping only the tokens above the cutoff would empty +// half of this figure. +func lesciMask(n int, t *bpe.Tokenizer) []bool { + atoi := bpe.Atoi(t) + + lo := int64(LesciCutoff - LesciWindow) + hi := int64(LesciCutoff + LesciWindow) + + inWindow := func(id int64) bool { + return id >= lo && id < hi + } + + // every token used to build another token whose result lands in the window + constituent := make(map[int64]struct{}) + + for _, merge := range bpe.Merges(t) { + c, ok := atoi[merge[0]+merge[1]] + + if !ok || !inWindow(c) { + continue + } + + if a, ok := atoi[merge[0]]; ok { + constituent[a] = struct{}{} + } + + if b, ok := atoi[merge[1]]; ok { + constituent[b] = struct{}{} + } + } + + mask := make([]bool, n) + + for id := range mask { + if !inWindow(int64(id)) { + continue + } + + // as in lesci.Filter: only in-vocab tokens are dropped + if _, ok := constituent[int64(id)]; ok && int64(id) < int64(LesciCutoff) { + continue + } + + mask[id] = true + } + + return mask +} + +// WindowTokens returns the token strings that make up the RDD estimation window, +// split by side of the cutoff. Membership depends only on the counterfactual +// vocabulary and its merges, so this needs no corpus pass. +func WindowTokens(ctf *bpe.Tokenizer) (observed, oov []string) { + itoa := bpe.Itoa(ctf) + + for id, keep := range lesciMask(len(bpe.Vocab(ctf)), ctf) { + if !keep { + continue + } + + if id >= LesciCutoff { + oov = append(oov, itoa[int64(id)]) + } else { + observed = append(observed, itoa[int64(id)]) + } + } + + return observed, oov +} + +// WindowFrequency is one token of the RDD estimation window, with the corpus +// frequency the tokenization-bias estimator would read for it. +type WindowFrequency struct { + ID int + Freq int + + // below the cutoff the token exists in the model's own vocabulary and its + // frequency is read from that tokenizer; at or above it the token is + // out-of-vocabulary and only the counterfactual tokenizer produces it + OOV bool +} + +// WindowFrequencies returns the tokens of the RDD estimation window with their +// corpus frequencies, mirroring how lesci reads the two sides of the cutoff. +// +// The window and its constituent filter are taken from the counterfactual +// tokenizer, as in lesci, which builds its rules from bpe.Merges of the +// counterfactual. Frequencies come from whichever tokenizer actually produces +// the token: the model's own tokenizer below the cutoff, the counterfactual +// above it, where the token does not exist for the model at all. +// +// observed is indexed by the model tokenizer's vocab ids and counterfactual by +// the counterfactual's. The two must agree on ids below the cutoff, which holds +// when the smaller vocabulary is an id-preserving prefix of the larger. +func WindowFrequencies(observed, counterfactual []int, ctf *bpe.Tokenizer) []WindowFrequency { + mask := lesciMask(len(counterfactual), ctf) + + out := make([]WindowFrequency, 0, 2*LesciWindow) + + for id, keep := range mask { + if !keep { + continue + } + + w := WindowFrequency{ID: id, OOV: id >= LesciCutoff} + + if w.OOV { + w.Freq = counterfactual[id] + } else if id < len(observed) { + w.Freq = observed[id] + } + + out = append(out, w) + } + + return out +} + +// plotMorphemeFractionLesci is the fraction overview restricted to the lesci +// window. The axis is the token id rather than the frequency rank, since the +// cutoff is a position in merge order and has no meaning on a rank axis. +func plotMorphemeFractionLesci(m []int, shared, unshared []bool, t *bpe.Tokenizer, out string) error { + morph, err := isMorpheme(t) + + if err != nil { + return err + } + + lesci := lesciMask(len(m), t) + + var series []fractionSeries + + for _, c := range []struct { + keep []bool + color color.NRGBA + label string + }{ + {nil, color.NRGBA{R: 90, G: 90, B: 90, A: 255}, "All"}, + {shared, opaque(colorOther), "Shared"}, + {unshared, opaque(colorMorpheme), "Unshared"}, + } { + segments, overall, shown := idFractionCurve(m, and(lesci, c.keep), morph, LesciCutoff-LesciWindow, LesciCutoff+LesciWindow) + + if shown == 0 { + continue + } + + series = append(series, fractionSeries{ + segments: segments, + overall: overall, + color: c.color, + label: fmt.Sprintf("%s (%.1f%%, n=%d)", c.label, overall, shown), + }) + } + + if len(series) == 0 { + return fmt.Errorf("no tokens selected") + } + + return renderMorphemeFractionLesci(series, out) +} + +// and intersects two masks; a nil second mask leaves the first untouched. +func and(a, b []bool) []bool { + if b == nil { + return a + } + + r := make([]bool, len(a)) + + for i := range a { + r[i] = a[i] && b[i] + } + + return r +} + +func renderMorphemeFractionLesci(series []fractionSeries, out string) error { + p := plot.New() + + p.X.Label.Text = "Token ID" + p.Y.Label.Text = "Morphemes in window (%)" + + p.X.Min = float64(LesciCutoff - LesciWindow) + p.X.Max = float64(LesciCutoff + LesciWindow) + + p.Y.Min = 0 + p.Y.Max = 100 + + p.Add(plotter.NewGrid()) + + cutoff, err := plotter.NewLine(plotter.XYs{ + {X: float64(LesciCutoff), Y: 0}, + {X: float64(LesciCutoff), Y: 100}, + }) + + if err != nil { + return err + } + + cutoff.Color = color.NRGBA{R: 131, G: 131, B: 131, A: 255} + cutoff.Width = vg.Points(1) + cutoff.Dashes = []vg.Length{vg.Points(4), vg.Points(3)} + + p.Add(cutoff) + p.Legend.Add(fmt.Sprintf("Cutoff (%d)", LesciCutoff), cutoff) + + for _, s := range series { + for i, pts := range s.segments { + line, err := plotter.NewLine(pts) + + if err != nil { + return err + } + + line.Color = s.color + line.Width = vg.Points(1.5) + + p.Add(line) + + if i == 0 { + p.Legend.Add(s.label, line) + } + } + } + + p.Legend.Top = true + p.Legend.Padding = vg.Points(4) + + return p.Save(12*vg.Inch, 6*vg.Inch, out) +} diff --git a/research/knobloch/share.go b/research/knobloch/share.go new file mode 100644 index 0000000..bc715f1 --- /dev/null +++ b/research/knobloch/share.go @@ -0,0 +1,223 @@ +package knobloch + +// Self-contained plot over the accumulated frequency_stats.csv; nothing else in +// the package depends on it. + +import ( + "encoding/csv" + "fmt" + "image/color" + "os" + "regexp" + "slices" + "strconv" + + "gonum.org/v1/plot" + "gonum.org/v1/plot/plotter" + "gonum.org/v1/plot/vg" + "gonum.org/v1/plot/vg/draw" +) + +// matches the alpha encoded in names like gpt2_50256_mi050_minipile +var modelPattern = regexp.MustCompile(`_(mi?)(\d{3})_`) + +type shareRow struct { + variant string + alpha float64 + types float64 + tokens float64 +} + +func PlotMorphemeShare(name, out string) error { + rows, err := readShareRows(name) + + if err != nil { + return err + } + + if len(rows) == 0 { + return fmt.Errorf("no usable rows in %s", name) + } + + p := plot.New() + + p.X.Label.Text = "Morpheme weight α (%)" + p.Y.Label.Text = "Share of vocabulary / token mass (%)" + + p.Add(plotter.NewGrid()) + + variants := make([]string, 0, 2) + + for _, r := range rows { + if !slices.Contains(variants, r.variant) { + variants = append(variants, r.variant) + } + } + + slices.Sort(variants) + + blue := color.NRGBA{R: 108, G: 126, B: 179, A: 255} + salmon := color.NRGBA{R: 214, G: 96, B: 77, A: 255} + + lo, hi := 100.0, 0.0 + + for _, variant := range variants { + var types, tokens plotter.XYs + + for _, r := range rows { + if r.variant != variant { + continue + } + + types = append(types, plotter.XY{X: r.alpha, Y: r.types * 100}) + tokens = append(tokens, plotter.XY{X: r.alpha, Y: r.tokens * 100}) + + lo = min(lo, r.types*100, r.tokens*100) + hi = max(hi, r.types*100, r.tokens*100) + } + + // a dashed line separates the mi variant from m at the same alpha + var dashes []vg.Length + + if variant != "m" { + dashes = []vg.Length{vg.Points(4), vg.Points(3)} + } + + if err := addShareSeries(p, types, blue, dashes, variant+" types"); err != nil { + return err + } + + if err := addShareSeries(p, tokens, salmon, dashes, variant+" tokens"); err != nil { + return err + } + } + + // keep the series off the frame and away from the legend + pad := max((hi-lo)*0.15, 2) + + p.Y.Min = lo - pad + p.Y.Max = hi + pad + + p.X.Min = -5 + p.X.Max = 105 + + p.Legend.Padding = vg.Points(4) + + return p.Save(7*vg.Inch, 5*vg.Inch, out) +} + +func addShareSeries(p *plot.Plot, pts plotter.XYs, c color.NRGBA, dashes []vg.Length, label string) error { + slices.SortFunc(pts, func(a, b plotter.XY) int { + switch { + case a.X < b.X: + return -1 + case a.X > b.X: + return 1 + default: + return 0 + } + }) + + line, points, err := plotter.NewLinePoints(pts) + + if err != nil { + return err + } + + line.Color = c + line.Width = vg.Points(1.5) + line.Dashes = dashes + + points.Color = c + points.Radius = vg.Points(3) + points.Shape = draw.CircleGlyph{} + + p.Add(line, points) + p.Legend.Add(label, line, points) + + return nil +} + +func readShareRows(name string) ([]shareRow, error) { + file, err := os.Open(name) + + if err != nil { + return nil, err + } + + defer file.Close() + + records, err := csv.NewReader(file).ReadAll() + + if err != nil { + return nil, err + } + + if len(records) == 0 { + return nil, fmt.Errorf("%s is empty", name) + } + + index := make(map[string]int) + + for i, h := range records[0] { + index[h] = i + } + + for _, h := range []string{"model", "type_share", "token_share"} { + if _, ok := index[h]; !ok { + return nil, fmt.Errorf("missing column %q in %s", h, name) + } + } + + // the stats file is appended to, so a rerun can repeat a model + seen := make(map[string]shareRow) + + var order []string + + for _, record := range records[1:] { + model := record[index["model"]] + + m := modelPattern.FindStringSubmatch(model) + + if m == nil { + continue + } + + alpha, err := strconv.ParseFloat(m[2], 64) + + if err != nil { + return nil, err + } + + types, err := strconv.ParseFloat(record[index["type_share"]], 64) + + if err != nil { + return nil, err + } + + tokens, err := strconv.ParseFloat(record[index["token_share"]], 64) + + if err != nil { + return nil, err + } + + if _, ok := seen[model]; !ok { + order = append(order, model) + } + + seen[model] = shareRow{ + variant: m[1], + alpha: alpha, + types: types, + tokens: tokens, + } + } + + rows := make([]shareRow, 0, len(order)) + + for _, model := range order { + rows = append(rows, seen[model]) + } + + return rows, nil +} diff --git a/research/knobloch/shared.go b/research/knobloch/shared.go new file mode 100644 index 0000000..5656668 --- /dev/null +++ b/research/knobloch/shared.go @@ -0,0 +1,152 @@ +package knobloch + +import ( + "encoding/json" + "fmt" + "os" + "sync" + + "go.jknobloc.com/x/shelf" + "go.jknobloc.com/x/tokenizer/bpe" +) + +// SharedVocabs lists the vocabularies intersected for the *_shared plots, which +// restrict every figure to tokens all of these models have in common. Set it to +// the family being swept so a model is only compared against its own kind; an +// empty list skips those plots. +var SharedVocabs = []shelf.Item{ + "models/mbpe/minipile/gpt2_50256_m000_minipile/vocab.json", + "models/mbpe/minipile/gpt2_50256_m030_minipile/vocab.json", + "models/mbpe/minipile/gpt2_50256_m050_minipile/vocab.json", + "models/mbpe/minipile/gpt2_50256_m100_minipile/vocab.json", +} + +var sharedCache struct { + mu sync.Mutex + m map[string]map[string]struct{} +} + +// sharedTokens caches the intersection per vocabulary list, so a sweep that +// switches SharedVocabs between families gets each family's own intersection +// while still reading the vocabularies only once per family. +func sharedTokens() (map[string]struct{}, error) { + key := "" + + for _, v := range SharedVocabs { + key += string(v) + "\n" + } + + sharedCache.mu.Lock() + + defer sharedCache.mu.Unlock() + + if tokens, ok := sharedCache.m[key]; ok { + return tokens, nil + } + + tokens, err := intersectVocabs(SharedVocabs) + + if err != nil { + return nil, err + } + + if sharedCache.m == nil { + sharedCache.m = make(map[string]map[string]struct{}) + } + + sharedCache.m[key] = tokens + + return tokens, nil +} + +func intersectVocabs(vocabs []shelf.Item) (map[string]struct{}, error) { + if len(vocabs) == 0 { + return nil, fmt.Errorf("no vocabularies to intersect") + } + + var keep map[string]struct{} + + for _, v := range vocabs { + tokens, err := loadVocab(shelf.Abs(v)) + + if err != nil { + return nil, err + } + + if keep == nil { + keep = tokens + + continue + } + + for token := range keep { + if _, ok := tokens[token]; !ok { + delete(keep, token) + } + } + } + + return keep, nil +} + +func loadVocab(name string) (map[string]struct{}, error) { + file, err := os.Open(name) + + if err != nil { + return nil, err + } + + defer file.Close() + + var m map[string]int64 + + if err := json.NewDecoder(file).Decode(&m); err != nil { + return nil, err + } + + tokens := make(map[string]struct{}, len(m)) + + for token := range m { + tokens[token] = struct{}{} + } + + return tokens, nil +} + +// sharedMask selects the vocab ids on one side of the intersection: shared marks +// the tokens every vocabulary in SharedVocabs has, and its complement isolates +// what a listed model added on its own. +func sharedMask(n int, t *bpe.Tokenizer, shared bool) ([]bool, error) { + keep, err := sharedTokens() + + if err != nil { + return nil, err + } + + itoa := bpe.Itoa(t) + + mask := make([]bool, n) + + for id := range mask { + _, ok := keep[itoa[int64(id)]] + + mask[id] = ok == shared + } + + return mask, nil +} + +// maskCounts zeroes the counts outside the mask. Every plot skips zero counts +// already, so the existing set of figures works unchanged while the axes stay +// pinned to the full vocabulary. +func maskCounts(r []int, keep []bool) []int { + masked := make([]int, len(r)) + + for id, v := range r { + if keep[id] { + masked[id] = v + } + } + + return masked +} diff --git a/research/knobloch/stats.go b/research/knobloch/stats.go new file mode 100644 index 0000000..e462e1b --- /dev/null +++ b/research/knobloch/stats.go @@ -0,0 +1,244 @@ +package knobloch + +import ( + "encoding/csv" + "os" + "slices" + "strconv" + + "go.jknobloc.com/x/tokenizer/bpe" + "gonum.org/v1/gonum/stat" +) + +// FrequencyStats summarizes how much of a tokenizer's vocabulary, and how much +// of its token mass, lines up with the morpheme inventory. +type FrequencyStats struct { + Model string + + // types are distinct vocabulary entries, occurrences are corpus counts + Vocab int + Used int + MorphemeTypes int + MorphemeTokens int64 + OtherTokens int64 + + MorphemeMedian int + OtherMedian int + + // morphemes among the 1000 most frequent tokens + MorphemeTop1000 int + + // RankID is Spearman's correlation between a token's vocabulary position and + // its corpus frequency rank. A strict frequency objective merges the most + // frequent pair first, so position and frequency rank move together and this + // sits near 1. The further a tokenizer departs from that objective, the more + // the two come apart, so it measures deviation from the frequency criterion + // independently of what the competing criterion happens to be. + RankID float64 +} + +func (s FrequencyStats) TypeShare() float64 { + if s.Used == 0 { + return 0 + } + + return float64(s.MorphemeTypes) / float64(s.Used) +} + +func (s FrequencyStats) TokenShare() float64 { + total := s.MorphemeTokens + s.OtherTokens + + if total == 0 { + return 0 + } + + return float64(s.MorphemeTokens) / float64(total) +} + +func NewFrequencyStats(model string, r []int, t *bpe.Tokenizer) (FrequencyStats, error) { + morph, err := morphemes() + + if err != nil { + return FrequencyStats{}, err + } + + itoa := bpe.Itoa(t) + + s := FrequencyStats{ + Model: model, + Vocab: len(r), + } + + var mFreq, oFreq []int + + for id, f := range r { + if f <= 0 { + continue + } + + s.Used++ + + if _, ok := morph[itoa[int64(id)]]; ok { + s.MorphemeTypes++ + s.MorphemeTokens += int64(f) + + mFreq = append(mFreq, f) + } else { + s.OtherTokens += int64(f) + + oFreq = append(oFreq, f) + } + } + + slices.Sort(mFreq) + slices.Sort(oFreq) + + s.MorphemeMedian = median(mFreq) + s.OtherMedian = median(oFreq) + + ids := make([]int, 0, s.Used) + + for id, f := range r { + if f > 0 { + ids = append(ids, id) + } + } + + slices.SortFunc(ids, func(a, b int) int { + return r[b] - r[a] + }) + + for _, id := range ids[:min(1000, len(ids))] { + if _, ok := morph[itoa[int64(id)]]; ok { + s.MorphemeTop1000++ + } + } + + s.RankID = rankIDCorrelation(r) + + return s, nil +} + +// rankIDCorrelation is Spearman's rho between vocabulary position and corpus +// frequency rank over the used tokens. gonum has no Spearman, so the ranks are +// built here and fed to Pearson, which is the same thing by definition. +func rankIDCorrelation(r []int) float64 { + ids := make([]int, 0, len(r)) + + for id, f := range r { + if f > 0 { + ids = append(ids, id) + } + } + + if len(ids) < 2 { + return 0 + } + + // ids is ascending and has no duplicates, so a token's id rank is its index + position := make([]float64, len(ids)) + + for i := range ids { + position[i] = float64(i + 1) + } + + order := slices.Clone(ids) + + slices.SortFunc(order, func(a, b int) int { + return r[b] - r[a] + }) + + // tied counts share the average of the ranks they span + ranks := make(map[int]float64, len(order)) + + for i := 0; i < len(order); { + j := i + + for j+1 < len(order) && r[order[j+1]] == r[order[i]] { + j++ + } + + avg := float64(i+j+2) / 2 + + for k := i; k <= j; k++ { + ranks[order[k]] = avg + } + + i = j + 1 + } + + frequency := make([]float64, len(ids)) + + for i, id := range ids { + frequency[i] = ranks[id] + } + + return stat.Correlation(position, frequency, nil) +} + +func median(v []int) int { + if len(v) == 0 { + return 0 + } + + return v[len(v)/2] +} + +var frequencyStatsHeader = []string{ + "model", "vocab", "used", "morpheme_types", "type_share", + "morpheme_tokens", "other_tokens", "token_share", + "morpheme_median", "other_median", "morpheme_top_1000", "rank_id_spearman", +} + +func (s FrequencyStats) row() []string { + return []string{ + s.Model, + strconv.Itoa(s.Vocab), + strconv.Itoa(s.Used), + strconv.Itoa(s.MorphemeTypes), + strconv.FormatFloat(s.TypeShare(), 'f', 4, 64), + strconv.FormatInt(s.MorphemeTokens, 10), + strconv.FormatInt(s.OtherTokens, 10), + strconv.FormatFloat(s.TokenShare(), 'f', 4, 64), + strconv.Itoa(s.MorphemeMedian), + strconv.Itoa(s.OtherMedian), + strconv.Itoa(s.MorphemeTop1000), + strconv.FormatFloat(s.RankID, 'f', 4, 64), + } +} + +// AppendFrequencyStats adds one row per run so numbers for different tokenizers +// accumulate in a single table. +func AppendFrequencyStats(name string, s FrequencyStats) error { + _, err := os.Stat(name) + + if err != nil && !os.IsNotExist(err) { + return err + } + + fresh := os.IsNotExist(err) + + file, err := os.OpenFile(name, os.O_CREATE|os.O_WRONLY|os.O_APPEND, 0644) + + if err != nil { + return err + } + + defer file.Close() + + w := csv.NewWriter(file) + + if fresh { + if err := w.Write(frequencyStatsHeader); err != nil { + return err + } + } + + if err := w.Write(s.row()); err != nil { + return err + } + + w.Flush() + + return w.Error() +} diff --git a/research/knobloch/tables.go b/research/knobloch/tables.go new file mode 100644 index 0000000..c5b2dcf --- /dev/null +++ b/research/knobloch/tables.go @@ -0,0 +1,483 @@ +package knobloch + +// Tokenizer characterisation tables. Column meanings are documented in +// FREQUENCIES.md; keep the two in sync. +// +// Terminology, used consistently in identifiers and column names: +// +// type a distinct pre-token, i.e. one dictionary entry +// occurrence a pre-token weighted by its corpus count +// token a subword unit, i.e. a vocabulary entry +// +// Morpheme labels attach to subword tokens, never to pre-token types, so the +// morpheme columns of table B are named morph_* rather than types_*. +// +// Tokenizers are compared by token string, never by id: the same string carries +// a different id in every vocabulary, so comparing ids would measure id +// reassignment rather than segmentation. + +import ( + "encoding/csv" + "encoding/json" + "fmt" + "hash/fnv" + "os" + "slices" + "sort" + "strconv" + + "github.com/jonasknobloch/mbpe" + "go.jknobloc.com/x/shelf" + "go.jknobloc.com/x/tokenizer/bpe" +) + +// TableSpec identifies one tokenizer to profile. +type TableSpec struct { + Name string // tokenizer label, e.g. m050 + Alignment string // alpha as a plain number; direction is carried by Inverted + Inverted bool + VocabSize int + Dir shelf.Item // directory holding vocab.json and merges.txt +} + +// Encoded is one tokenizer's view of the dictionary. +// +// Comparisons need to know, per dictionary entry, whether two tokenizers agree +// and how many pieces each produced. Retaining the pieces themselves costs +// hundreds of megabytes per tokenizer, which does not fit for a whole +// vocabulary-size family at once, so each entry is reduced to a hash of its +// segmentation plus two small counts. That is all tables A, B and C read. +type Encoded struct { + Spec TableSpec + + // corpus count per vocab id, and the id-to-string map + Counts []int + Itoa map[int64]string + + Words int64 + Tokens int64 + + // pieces-per-type distribution, bucketed 1 / 2 / 3+ + TypeBucket [3]int64 + TokenBucket [3]int64 + + // per dictionary entry, in dict order + Sig []uint64 // hash of the piece strings + Len []uint16 // number of pieces + MorphN []uint16 // number of pieces labelled morpheme +} + +// Fertility is subword tokens per pre-token occurrence. +func (e *Encoded) Fertility() float64 { + if e.Words == 0 { + return 0 + } + + return float64(e.Tokens) / float64(e.Words) +} + +// EncodeDict segments every dictionary entry with one tokenizer. +func EncodeDict(spec TableSpec, items []mbpe.Chunk) (*Encoded, error) { + morph, err := morphemes() + + if err != nil { + return nil, err + } + + tok, err := bpe.NewTokenizerFromFiles( + shelf.Abs(spec.Dir+"/vocab.json"), shelf.Abs(spec.Dir+"/merges.txt"), + bpe.Config{Recover: false}) + + if err != nil { + return nil, err + } + + // the dictionary is already pre-tokenised + bpe.MBPE(tok).SetPreTokenizer(&NoPreTok{}) + + e := &Encoded{ + Spec: spec, + Counts: make([]int, len(bpe.Vocab(tok))), + Itoa: bpe.Itoa(tok), + Sig: make([]uint64, len(items)), + Len: make([]uint16, len(items)), + MorphN: make([]uint16, len(items)), + } + + h := fnv.New64a() + + for i, v := range items { + ids := tok.Encode(v.Src()) + + h.Reset() + + var morphN uint16 + + for _, id := range ids { + s := e.Itoa[int64(id)] + + e.Counts[id] += v.N() + + // the separator keeps ab|c distinct from a|bc + h.Write([]byte(s)) + h.Write([]byte{0}) + + if _, ok := morph[s]; ok { + morphN++ + } + } + + e.Sig[i] = h.Sum64() + e.Len[i] = uint16(len(ids)) + e.MorphN[i] = morphN + + n := int64(v.N()) + k := int64(len(ids)) + b := bucket(len(ids)) + + e.Words += n + e.Tokens += n * k + + e.TypeBucket[b]++ + e.TokenBucket[b] += n * k + } + + return e, nil +} + +// bucket maps a piece count onto the 1 / 2 / 3+ buckets used by every table. +func bucket(k int) int { + switch { + case k == 1: + return 0 + case k == 2: + return 1 + default: + return 2 + } +} + +// VocabIntersection returns the token strings present in every one of the given +// vocabularies. Reads vocab.json only, so it never touches the corpus. +func VocabIntersection(dirs []shelf.Item) (map[string]struct{}, error) { + if len(dirs) == 0 { + return nil, fmt.Errorf("no vocabularies given") + } + + var keep map[string]struct{} + + for _, dir := range dirs { + file, err := os.Open(shelf.Abs(dir + "/vocab.json")) + + if err != nil { + return nil, err + } + + var v map[string]int64 + + err = json.NewDecoder(file).Decode(&v) + + file.Close() + + if err != nil { + return nil, err + } + + if keep == nil { + keep = make(map[string]struct{}, len(v)) + + for token := range v { + keep[token] = struct{}{} + } + + continue + } + + for token := range keep { + if _, ok := v[token]; !ok { + delete(keep, token) + } + } + } + + return keep, nil +} + +// TableARow is the segmentation profile of one tokenizer. +type TableARow struct { + Spec TableSpec + Fertility float64 + + Types [3]float64 // share of pre-token types + Tokens [3]float64 // share of subword token occurrences +} + +func BuildTableA(e *Encoded) TableARow { + row := TableARow{Spec: e.Spec, Fertility: e.Fertility()} + + var typeTotal, tokenTotal int64 + + for b := range e.TypeBucket { + typeTotal += e.TypeBucket[b] + tokenTotal += e.TokenBucket[b] + } + + for b := range e.TypeBucket { + row.Types[b] = share(e.TypeBucket[b], typeTotal) + row.Tokens[b] = share(e.TokenBucket[b], tokenTotal) + } + + return row +} + +// TableBRow describes what a vocabulary is made of. +type TableBRow struct { + Spec TableSpec + Fertility float64 + + MorphCount int + MorphShareUnweighted float64 + MorphShareWeighted float64 + + PctRankMorph float64 + PctRankOther float64 + + SharedMorph float64 + SharedOther float64 +} + +// BuildTableB profiles one vocabulary. shared is the intersection of every +// vocabulary at this size, which is what the two shared_* columns measure +// against — so the baseline is just another tokenizer and gets a real value. +func BuildTableB(e *Encoded, shared map[string]struct{}) (TableBRow, error) { + morph, err := morphemes() + + if err != nil { + return TableBRow{}, err + } + + row := TableBRow{Spec: e.Spec, Fertility: e.Fertility()} + + var morphTokens, otherTokens int64 + var morphFreq, otherFreq []int + var morphShared, otherShared, otherCount int + + for id, f := range e.Counts { + token := e.Itoa[int64(id)] + + _, isMorph := morph[token] + _, inShared := shared[token] + + if isMorph { + row.MorphCount++ + morphTokens += int64(f) + morphFreq = append(morphFreq, f) + + if inShared { + morphShared++ + } + } else { + otherCount++ + otherTokens += int64(f) + otherFreq = append(otherFreq, f) + + if inShared { + otherShared++ + } + } + } + + row.MorphShareUnweighted = share(int64(row.MorphCount), int64(len(e.Counts))) + row.MorphShareWeighted = share(morphTokens, morphTokens+otherTokens) + + // Percentile rank of each group's median token within the corpus frequency + // distribution of the whole vocabulary. An absolute median is not comparable + // across vocabulary sizes, since a given token is rarer relative to a larger + // vocabulary; a percentile rank is. + all := slices.Clone(e.Counts) + + slices.Sort(all) + slices.Sort(morphFreq) + slices.Sort(otherFreq) + + row.PctRankMorph = percentileRank(all, median(morphFreq)) + row.PctRankOther = percentileRank(all, median(otherFreq)) + + row.SharedMorph = share(int64(morphShared), int64(row.MorphCount)) + row.SharedOther = share(int64(otherShared), int64(otherCount)) + + return row, nil +} + +// percentileRank is the share of sorted strictly below v, so a higher value +// means a more frequent token. +func percentileRank(sorted []int, v int) float64 { + if len(sorted) == 0 { + return 0 + } + + return 100 * float64(sort.SearchInts(sorted, v)) / float64(len(sorted)) +} + +// TableCRow is the divergence between one tokenizer and a reference. +// +// Everything is measured against the BASELINE segmentation. A pre-token is +// bucketed by how many pieces the baseline produced for it and contributes that +// many token occurrences, so a pre-token that is one token under the baseline +// and two under the variant lands in bucket 1 and counts once. That makes the +// three bucket columns sum to TokensDiff by construction, and keeps the buckets +// the same population as the baseline's table A row. +type TableCRow struct { + Spec TableSpec + Baseline string + + TypesDiff float64 + TokensDiff float64 + + TokensDiffBucket [3]float64 + + // morpheme share of the subword tokens in the differing slice, under each + // side, each normalised by that side's own token count + DiffMorphBase float64 + DiffMorphVar float64 +} + +func BuildTableC(e, base *Encoded, items []mbpe.Chunk) (TableCRow, error) { + if len(e.Sig) != len(base.Sig) { + return TableCRow{}, fmt.Errorf("dictionaries differ in length") + } + + row := TableCRow{Spec: e.Spec, Baseline: base.Spec.Name} + + var typDiff, diffTokens int64 + var diffBucket [3]int64 + var mBase, nBase, mVar, nVar int64 + + for i := range base.Sig { + if e.Sig[i] == base.Sig[i] { + continue + } + + n := int64(items[i].N()) + k := int64(base.Len[i]) + + typDiff++ + diffTokens += n * k + diffBucket[bucket(int(base.Len[i]))] += n * k + + mBase += n * int64(base.MorphN[i]) + nBase += n * k + + mVar += n * int64(e.MorphN[i]) + nVar += n * int64(e.Len[i]) + } + + row.TypesDiff = share(typDiff, int64(len(base.Sig))) + row.TokensDiff = share(diffTokens, base.Tokens) + + for b := range diffBucket { + row.TokensDiffBucket[b] = share(diffBucket[b], base.Tokens) + } + + row.DiffMorphBase = share(mBase, nBase) + row.DiffMorphVar = share(mVar, nVar) + + return row, nil +} + +func share(x, total int64) float64 { + if total == 0 { + return 0 + } + + return 100 * float64(x) / float64(total) +} + +func writeCSV(name string, header []string, rows [][]string) error { + file, err := os.Create(name) + + if err != nil { + return err + } + + defer file.Close() + + w := csv.NewWriter(file) + + if err := w.Write(header); err != nil { + return err + } + + for _, r := range rows { + if err := w.Write(r); err != nil { + return err + } + } + + w.Flush() + + return w.Error() +} + +// percentages are plain numbers, without a percent sign +func f2(v float64) string { return strconv.FormatFloat(v, 'f', 2, 64) } +func f4(v float64) string { return strconv.FormatFloat(v, 'f', 4, 64) } + +func WriteTableA(name string, rows []TableARow) error { + out := make([][]string, 0, len(rows)) + + for _, r := range rows { + out = append(out, []string{ + r.Spec.Name, strconv.Itoa(r.Spec.VocabSize), r.Spec.Alignment, f4(r.Fertility), + f2(r.Types[0]), f2(r.Types[1]), f2(r.Types[2]), + f2(r.Tokens[0]), f2(r.Tokens[1]), f2(r.Tokens[2]), + }) + } + + return writeCSV(name, []string{ + "tokenizer", "vocab_size", "alignment", "fertility", + "types_1", "types_2", "types_3plus", + "tokens_1", "tokens_2", "tokens_3plus", + }, out) +} + +func WriteTableB(name string, rows []TableBRow) error { + out := make([][]string, 0, len(rows)) + + for _, r := range rows { + out = append(out, []string{ + r.Spec.Name, strconv.Itoa(r.Spec.VocabSize), r.Spec.Alignment, f4(r.Fertility), + strconv.Itoa(r.MorphCount), + f2(r.MorphShareUnweighted), f2(r.MorphShareWeighted), + f2(r.PctRankMorph), f2(r.PctRankOther), + f2(r.SharedMorph), f2(r.SharedOther), + }) + } + + return writeCSV(name, []string{ + "tokenizer", "vocab_size", "alignment", "fertility", + "morph_count", "morph_share_unweighted", "morph_share_weighted", + "pct_rank_morph", "pct_rank_other", + "shared_morph", "shared_other", + }, out) +} + +func WriteTableC(name string, rows []TableCRow) error { + out := make([][]string, 0, len(rows)) + + for _, r := range rows { + out = append(out, []string{ + r.Spec.Name, strconv.Itoa(r.Spec.VocabSize), r.Spec.Alignment, r.Baseline, + f2(r.TypesDiff), f2(r.TokensDiff), + f2(r.TokensDiffBucket[0]), f2(r.TokensDiffBucket[1]), f2(r.TokensDiffBucket[2]), + f2(r.DiffMorphBase), f2(r.DiffMorphVar), + }) + } + + return writeCSV(name, []string{ + "tokenizer", "vocab_size", "alignment", "baseline", + "types_diff", "tokens_diff", + "tokens_1_diff", "tokens_2_diff", "tokens_3plus_diff", + "tokens_diff_morph_base", "tokens_diff_morph_var", + }, out) +} |
