The language learning premise in this post is a bit ridiculous - if I started with the goal of learning a language and ended up worrying about the asymptotic complexity of my automated k-book recommendation algorithm for arbitrary values of k, then I think I should worry about a serious case of procrastination.

But the algorithms are interesting, so I think a better title would have been "why submodular NP hard problems are cool" or something similar.

This reminds me of "Thousand Character Text"(千字文), which is a Chinese poem that has been used as a primer for teaching Chinese characters to children from the sixth century onward. It contains exactly one thousand characters, each used only once, arranged into 250 lines of four characters apiece and grouped into four line rhyming stanzas to facilitate easy memorization.

See Also: https://en.wikipedia.org/wiki/Thousand_Character_Classic

My language learning problem is slightly different and quite under-served because my motivation is not the most common one.

I want to learn so that I can read/understand publications in mathematics in a foreign language, mostly Swedish, French, German. (*) For this exercise, the typical apps do not help much.

(*) I would have liked to add Latin and Greek too but that's mostly a pipe dream.

Reading old mathematicians and scholars I have realized something that runs quite counter to the common perception we have, especially in my country.

That common perception is school kids, especially in mid and high school are overwhelmingly burdened by sheer volume of subject matter to learn at a very young age. But then I look at educated teenagers from 17th - 18th centuries, who went on to become mathematicians or scholars, they were so immensely well read at a very young age. I understand this is a biased sample, but many of these people, Newton, for example, were ordinary folks (socio-economically speaking)

Hamilton (I concede that one cannot compare Hamilton with a typical modern teenager) was already quite fluent in thirteen languages in his pre-teens. Apart from the usual suspects, he knew Arabic, Hebrew, Farsi, Sanskrit, Hindi, Marathi.

This might sound atypical but this was not unheard of. One of the poets in my language was fluent in Hebrew, Greek, Italian, French, Latin, Sanskrit, Telugu, Tamil, Bengali, English.

In every hobby there are 2 groups of people: those who enjoy the actual act of doing the thing, and those who enjoy the tooling (equipment, methodologies, discussions around the thing etc).

Not saying that one is inherently more worthy than the other, but no surprise- the first group is usually better at actually _doing_ the thing

I fully agree with this approach! 5 years ago I built a prototype to execute that same concept of language covering. But instead of just using words, I used n-grams. It ii trained on subtitles to model spoken language. Combined with sqlite in the browser to get the next sentence with the most impact.

github here: https://github.com/fdietze/ravioli

prototype deployed here: https://raviolio.web.app/

> People have many ways to learn a language, different for each person. Suppose you wanted to improve your vocabulary by reading books in that language. To get the most impact, you’d like to pick books that cover as many common words in the language as possible.

I think the article is just using this as a hook to introduce the submodularity of the maximum weighted cover problem. But I'll talk about a different way of using the same collection of books to learn a language that I think is better.

First of all, you'll probably want to take into account which words you already know, instead of just removing stopwords. If a book uses lots of common words, but you already know them, you're not learning much.

Secondly, no matter how much or how little you already know, you're unlikely to find a book that fits your level well. If you're just beginning to learn the language, no matter which book you pick, the very first sentence will be full of new words, but most of those will be rare ones that you won't encounter again until much later. If on the other hand you already have a very good command of the language, you might be able to breeze through entire chapters and only pick up a handful of new words. (If your primary goal is to enjoy books rather than achieving mastery of the language, this is of course perfectly fine.)

So what I do is split the entire collection into sentences, and for each word from most common to least, pick a small number of sentences using this word, ideally without also having much rarer words, try to read and understand them all, and then use the most suitable sentence to make an Anki flashcard. It's much easier to find a sentence at the right level than an entire book.

It can be a bit weird to learn about the plot of a book piecemeal out of order, especially if multiple books are mixed together, but I think it's an interesting experience.

The same principle can also be applied to recordings from Mozilla Common Voice: https://commonvoice.mozilla.org/en/datasets I like to use them for dictation exercises in Anki, where the card plays a recording and I type in what I thought I heard to check whether I got it right.

I am fiddling with some language learning utilities myself. Can anyone recommend some relatively simple ways of tracking users' knowledge of a given language? Something like having a sorted frequency list of words/phrases/concepts, and tracking how many times each word has been seen vs used correctly vs used incorrectly, etc.?

I believe this does not have to be perfect, simplicity is preferred. But it should be just enough for an LLM to take a glimpse and estimate users' level in given language.

This is a bad way to go about it. You want to consume more material, and you want each piece of it to have the least impact on your vocabulary.

So maybe looking for high frequency words is good, but only high frequency words that you know. So the most coverage of the most high frequency words would be very bad. To get the most coverage of the most high frequency words, they'd have to be used in a lower frequency than they are normally, with less repetition in natural contexts, which enable the learner to build meaning. Unless the books were longer which makes degenerate the concept of concentrating common vocabulary in very few books (just read two 2000 page books!)

Reading a bunch of stuff with a concentrated dose of tons of words you don't know will leave you with absolutely no retention. If you know every word but one in e.g. a chapter, you'll probably remember that word forever. The concept is called comprehensible input - you set unfamiliar things in a background of familiar things.

If you want a book with the most unfamiliar vocabulary, it's called a dictionary. It contains all of the most commonly used words, and the least commonly used, too.

In fact, maybe this makes sense if you're going to be locked in a cell for 10 years, you want to learn a language starting from zero*, and only get to have a pocket dictionary and two other books (with a size limit.) You might want to have sample natural sentences for as many of the best words to know as you could.

The real algorithmic language learning trick is to write books that are interesting that use the fewest words (which would inevitably be the most important words to use to communicate but not the necessarily the most common words that natives use to communicate), and introduce new, useful words at a steady rate. That seems like how Capretz put together French in Action. It's also graded readers: I still remember the moment I realized that I could not only understand what was happening in the basic graded reader I'd accidentally picked up on a whim, but also I was interested in finding out what was going to happen next. It's been downhill from there.

-----

[*] or maybe from one? You would have to have some familiarity with the script, and it had better be a phonetic one. Otherwise, this would be just learning how to read a language. No English, no French, no Portuguese, no Chinese... although having poetry books might help, because you can be surer of vowel similarities and syllable breaks. Poetry books are not dense, however, and might bump against any size limit. And the vocabulary would be weird and not representative.

There are many apps that have utilized formal methods in an attempt to teach languages as optimally as possible. But Duolingo is still the leader in language learning. Why? Language learning is an emotional process. Every word you can bring to mind likely has some specific memories tied to them, from another time and place. So even though Duolingo is far from optimal in terms of how and when to present new items to learn, it is close to optimal in vibes, and apparently in the market of language learning this is what consumers prioritize over all else. I believe it is for good reason. Whoever displaces Duolingo will do so not because they teach more efficiently, but because they improve on embedding particular emotions and sentiments into the lessons.