« prev | content
Reading list. Part 2.
👉 Andrews, Askey, Roy — Special Functions A broad and serious reference on special functions. Useful if you want to see the q-binomial theorem as part of the larger world of special functions.
👉 Kathleen O’Hara — Unimodality of Gaussian coefficients: A constructive proof, 1990 A famous paper on the unimodality of Gaussian coefficients. Difficult, but important if you are interested in the shape of the distribution: why the coefficients rise toward the middle and then fall.
👉 Doron Zeilberger — Kathy O’Hara’s Constructive Proof of the Unimodality of the Gaussian Polynomials, 1989 A more explanatory bridge to O’Hara’s proof. Still not easy, but easier than starting with the original paper.
👉 Pak, Panova — Strict unimodality of q-binomial coefficients, 2013 A serious paper on strict unimodality of q-binomial coefficients. Interesting if you want to go beyond “there is a maximum near the centre” and understand finer shape properties of the distribution.
👉 Dhand — A combinatorial proof of strict unimodality for q-binomial coefficients, 2014 A combinatorial proof of strict unimodality in large cases. Hard, but closer in spirit to the combinatorial nature of our problem.
Sources connecting this to ROC AUC
👉 Donald Bamber — The area above the ordinal dominance graph and the area below the receiver operating characteristic graph, 1975 A very important bridge between ROC AUC and the Mann–Whitney U statistic. A good reference for the claim that the area under the ROC curve is a pairwise ranking statistic.
👉 Hanley, McNeil — The meaning and use of the area under a receiver operating characteristic curve, 1982 A classic applied paper on the meaning of ROC AUC. Useful for the interpretation of AUC as the probability that a randomly chosen positive example receives a higher score than a randomly chosen negative example.
👉 Green, Swets — Signal Detection Theory and Psychophysics, 1966 Classic background on signal detection theory and ROC curves. Less about discrete tied score blocks, more about the historical and conceptual origins of ROC analysis.
Suggested reading order for the stochastic ROC project
First:
👉 Wikipedia — Gaussian binomial coefficient
👉 An Invitation to Enumeration — q-analogues
Then:
👉 Andrews, Eriksson — Integer Partitions
👉 Bamber — area below ROC and the Mann–Whitney connection
Then, for a more serious foundation:
👉 Stanley — Enumerative Combinatorics
👉 Mann, Whitney, 1947
And only then, if you want to go deeper into the shape of the distribution:
👉 O’Hara — Unimodality of Gaussian coefficients
👉 Pak, Panova — Strict unimodality of q-binomial coefficients
Reading list. Part 2.
👉 Andrews, Askey, Roy — Special Functions A broad and serious reference on special functions. Useful if you want to see the q-binomial theorem as part of the larger world of special functions.
👉 Kathleen O’Hara — Unimodality of Gaussian coefficients: A constructive proof, 1990 A famous paper on the unimodality of Gaussian coefficients. Difficult, but important if you are interested in the shape of the distribution: why the coefficients rise toward the middle and then fall.
👉 Doron Zeilberger — Kathy O’Hara’s Constructive Proof of the Unimodality of the Gaussian Polynomials, 1989 A more explanatory bridge to O’Hara’s proof. Still not easy, but easier than starting with the original paper.
👉 Pak, Panova — Strict unimodality of q-binomial coefficients, 2013 A serious paper on strict unimodality of q-binomial coefficients. Interesting if you want to go beyond “there is a maximum near the centre” and understand finer shape properties of the distribution.
👉 Dhand — A combinatorial proof of strict unimodality for q-binomial coefficients, 2014 A combinatorial proof of strict unimodality in large cases. Hard, but closer in spirit to the combinatorial nature of our problem.
Sources connecting this to ROC AUC
👉 Donald Bamber — The area above the ordinal dominance graph and the area below the receiver operating characteristic graph, 1975 A very important bridge between ROC AUC and the Mann–Whitney U statistic. A good reference for the claim that the area under the ROC curve is a pairwise ranking statistic.
👉 Hanley, McNeil — The meaning and use of the area under a receiver operating characteristic curve, 1982 A classic applied paper on the meaning of ROC AUC. Useful for the interpretation of AUC as the probability that a randomly chosen positive example receives a higher score than a randomly chosen negative example.
👉 Green, Swets — Signal Detection Theory and Psychophysics, 1966 Classic background on signal detection theory and ROC curves. Less about discrete tied score blocks, more about the historical and conceptual origins of ROC analysis.
Suggested reading order for the stochastic ROC project
First:
👉 Wikipedia — Gaussian binomial coefficient
👉 An Invitation to Enumeration — q-analogues
Then:
👉 Andrews, Eriksson — Integer Partitions
👉 Bamber — area below ROC and the Mann–Whitney connection
Then, for a more serious foundation:
👉 Stanley — Enumerative Combinatorics
👉 Mann, Whitney, 1947
And only then, if you want to go deeper into the shape of the distribution:
👉 O’Hara — Unimodality of Gaussian coefficients
👉 Pak, Panova — Strict unimodality of q-binomial coefficients
Friday trash
Be careful, the first photo is really a kind of trash. 100 kilometers north of Moscow, kids are playing with a dead snake. If your toys were wooden, you were lucky.
Near Zvenigorod there is a bunch of identical houses. I don't know why, but it still looks funny to me. I heard that there is a business around some legislative procedures: before signing a contract, you place some dummy structures on your plot and pay less for registration, or something like that. The next year, all these houses were removed.
Round-leaved sundew. Near the artificial lake Sima.
Be careful, the first photo is really a kind of trash. 100 kilometers north of Moscow, kids are playing with a dead snake. If your toys were wooden, you were lucky.
Near Zvenigorod there is a bunch of identical houses. I don't know why, but it still looks funny to me. I heard that there is a business around some legislative procedures: before signing a contract, you place some dummy structures on your plot and pay less for registration, or something like that. The next year, all these houses were removed.
Round-leaved sundew. Near the artificial lake Sima.
👀2
Implicit Curriculum aka skill graph
Why should I read all these articles? - I asked myself this week, when I suddenly found this diamond.
To explain why I jumped out of my chair, let me tell you about my previous team. It was Schoolbook. My second assignment after I joined it was to figure out how to build, store and edit a skill graph. It is quite an intuitive idea: in order to solve quadratic equations, you have to understand square roots, summation, multiplication and so on. These simple skills are prerequisites. You can represent these dependencies using a DAG (directed acyclic graph). There were a lot of professional teachers who built mathematics and Russian language graphs in our team. While the idea seems quite straightforward and intuitive, its implementation is the opposite of simple and clear. It took me half a year to understand how it should work and how to implement it in a production environment.
But what about the article? It gives a nice landscape of how skills emerge during model training on unstructured internet data. The described articles give important understanding of how skills emerge in large language models, how to evaluate them, how to detect phase transitions in a model and how to find internal representations of skills inside the model.
For me, these findings are very important because they are very close to the bridge between model training and human education. I believe that our brain is just a very complex classical computer and that insights can be transferred from human education practice to machine learning and back. After reading the article, I feel much more confident that the skill graph is a real thing, not just a figment of our teachers' imagination.
There is quite a well-shaped method of model evaluation. Probably, it can be transferred to the realities of educational platforms and give us metrics for educational efficiency.
Why should I read all these articles? - I asked myself this week, when I suddenly found this diamond.
To explain why I jumped out of my chair, let me tell you about my previous team. It was Schoolbook. My second assignment after I joined it was to figure out how to build, store and edit a skill graph. It is quite an intuitive idea: in order to solve quadratic equations, you have to understand square roots, summation, multiplication and so on. These simple skills are prerequisites. You can represent these dependencies using a DAG (directed acyclic graph). There were a lot of professional teachers who built mathematics and Russian language graphs in our team. While the idea seems quite straightforward and intuitive, its implementation is the opposite of simple and clear. It took me half a year to understand how it should work and how to implement it in a production environment.
But what about the article? It gives a nice landscape of how skills emerge during model training on unstructured internet data. The described articles give important understanding of how skills emerge in large language models, how to evaluate them, how to detect phase transitions in a model and how to find internal representations of skills inside the model.
For me, these findings are very important because they are very close to the bridge between model training and human education. I believe that our brain is just a very complex classical computer and that insights can be transferred from human education practice to machine learning and back. After reading the article, I feel much more confident that the skill graph is a real thing, not just a figment of our teachers' imagination.
There is quite a well-shaped method of model evaluation. Probably, it can be transferred to the realities of educational platforms and give us metrics for educational efficiency.
👍3❤1
This media is not supported in your browser
VIEW IN TELEGRAM
The simplest cacti sort
At the last moment I got a request to write the smallest possible program which sorts cacti in The Farmer Was Replaced game.
Here is my version:
Let's work through this solution:
Here I both set the world size to 8 and introduce a new variable n for the world size.
Let's check an interesting idiom:
I introduce the flag disorder_detected and put this flag up before the loop. This way the loop will be executed at least once. Then, at the beginning of the loop, I put it down. It means that if there are no disorders, the field is ready for harvest. Disorders are: absence of cactus, or cacti in the wrong order.
Navigation is very simple. I have two nested loops. The inner loop moves the drone horizontally from left to right. The outer loop moves it vertically. The map is toroidal, therefore the drone appears on the left after crossing the right boundary; similarly, it appears at the bottom after crossing the upper boundary.
When we start the script, the field is empty. So we plant cactus on empty cell and count it as a disorder. Cactus requires Soil, we ensure it with till().
And finally, the main thing:
If our current cactus is higher than its neighbor to the right or above, we swap them. This way each pass of the drone brings more order into the field, and one day the field becomes sorted. On a sorted field no swaps occur, therefore no disorder is detected and the while loop ends.
The drone stops at the left bottom end of the field, and we can call harvest() function, which picks up all cacti with a big bonus.
At the last moment I got a request to write the smallest possible program which sorts cacti in The Farmer Was Replaced game.
Here is my version:
n = 8
set_world_size(n)
disorder_detected = True
while(disorder_detected):
disorder_detected = False
for y in range(n):
for x in range(n):
if get_entity_type() != Entities.Cactus:
if get_ground_type() != Grounds.Soil:
till()
if plant(Entities.Cactus):
disorder_detected = True
if measure() != None and measure(East) != None and measure() > measure(East):
if swap(East):
disorder_detected = True
if measure() != None and measure(North) != None and measure() > measure(North):
if swap(North):
disorder_detected = True
move(East)
move(North)
harvest()
Let's work through this solution:
n = 8
set_world_size(n)
Here I both set the world size to 8 and introduce a new variable n for the world size.
Let's check an interesting idiom:
disorder_detected = True
while(disorder_detected):
disorder_detected = False
...
if plant(Entities.Cactus):
disorder_detected = True
if swap(East):
disorder_detected = True
I introduce the flag disorder_detected and put this flag up before the loop. This way the loop will be executed at least once. Then, at the beginning of the loop, I put it down. It means that if there are no disorders, the field is ready for harvest. Disorders are: absence of cactus, or cacti in the wrong order.
Navigation is very simple. I have two nested loops. The inner loop moves the drone horizontally from left to right. The outer loop moves it vertically. The map is toroidal, therefore the drone appears on the left after crossing the right boundary; similarly, it appears at the bottom after crossing the upper boundary.
if get_entity_type() != Entities.Cactus:
if get_ground_type() != Grounds.Soil:
till()
if plant(Entities.Cactus):
disorder_detected = True
When we start the script, the field is empty. So we plant cactus on empty cell and count it as a disorder. Cactus requires Soil, we ensure it with till().
And finally, the main thing:
if measure() != None and measure(East) != None and measure() > measure(East):
if swap(East):
disorder_detected = True
if measure() != None and measure(North) != None and measure() > measure(North):
if swap(North):
disorder_detected = True
If our current cactus is higher than its neighbor to the right or above, we swap them. This way each pass of the drone brings more order into the field, and one day the field becomes sorted. On a sorted field no swaps occur, therefore no disorder is detected and the while loop ends.
The drone stops at the left bottom end of the field, and we can call harvest() function, which picks up all cacti with a big bonus.
👍2
5. Longest Palindromic Substring
My friend is solving some LeetCode problems now, and I couldn't help but join him.
I know, I know... LeetCode is dead, all this is trash, and we shouldn't solve it. But for now the standards of interviews in Big Tech are settled, and you can, at least, laugh at us, who spend tons of time performing cargo cult rituals.
First of all, it's like a 20-minute problem. In these 20 minutes you have to:
— 0 min
✒️ read the problem statement
✒️ come up with a few test cases - it helps both to understand the problem better and to have test cases for the later testing session
✒️ figure out a working solution for the problem
✒️ explain your approach to the interviewer, give them T=O(...), M=O(...) estimations
✒️ get approval from the interviewer to go on with this solution
- 5 min
✒️ implement your approach
✒️ test your implementation on your test cases
✒️ fix it, if necessary
✒️ check that your T=O(...), M=O(...) are true
- 18 min
✒️ discuss pros and cons
- 20 min
I'm not a quick thinker, and in order to be able to take part in this competition, I thought a lot and came up with some tricks which I want to share. First of all, how to read the statement and how to approach a solution.
"the longest palindromic substring" - if you, like me, start to think "I read really beautiful algorithms which solve it in linear time, what was that book..." - poof, you have already lost this game. Nice thought. But you have to mention it really quickly and move on. What is the real complexity you want to aim at? Check s.length <= 1000 and think about the naive approach. All substrings - n squared, palindrome check - n => n cubed. Rough estimation for time - 10 secs in Python - doesn't look good.
Here you have to recall at least a glimpse of that wonderful algorithm you read about. There was something... about... middle points of palindromes! Let's check. n middle points, linear check => n squared. 0.01s for n = 1000. Sounds promising.
In the program I want to share a trick: decomposition. Of course, you can try to write a program in one long sheet of text. But if you split it into logical parts, it's better for you. Python gives you a great opportunity - iterators. In the function you can generate candidates and then select the best using just the max function.
In order to use just max, we are to be careful about an empty sequence. It is not a case here, because n >= 1. If an empty sequence is possible, default = ... in the max function is your friend.
For odd-length palindromes, candidate generation is quite boring. We start with the trivial one-letter palindrome and extend it, if it is possible. No problem.
Even-length palindromes have a real chance to be absent at all. One more trick - make a step back and set up variables in the previous position before they form a valid even palindrome. Then we can check whether the variables are still in this weird initial position. If they are, we don't have a candidate.
So, here we are. A few tricks, and the problem is solved.
My friend is solving some LeetCode problems now, and I couldn't help but join him.
I know, I know... LeetCode is dead, all this is trash, and we shouldn't solve it. But for now the standards of interviews in Big Tech are settled, and you can, at least, laugh at us, who spend tons of time performing cargo cult rituals.
First of all, it's like a 20-minute problem. In these 20 minutes you have to:
— 0 min
✒️ read the problem statement
✒️ come up with a few test cases - it helps both to understand the problem better and to have test cases for the later testing session
✒️ figure out a working solution for the problem
✒️ explain your approach to the interviewer, give them T=O(...), M=O(...) estimations
✒️ get approval from the interviewer to go on with this solution
- 5 min
✒️ implement your approach
✒️ test your implementation on your test cases
✒️ fix it, if necessary
✒️ check that your T=O(...), M=O(...) are true
- 18 min
✒️ discuss pros and cons
- 20 min
I'm not a quick thinker, and in order to be able to take part in this competition, I thought a lot and came up with some tricks which I want to share. First of all, how to read the statement and how to approach a solution.
"the longest palindromic substring" - if you, like me, start to think "I read really beautiful algorithms which solve it in linear time, what was that book..." - poof, you have already lost this game. Nice thought. But you have to mention it really quickly and move on. What is the real complexity you want to aim at? Check s.length <= 1000 and think about the naive approach. All substrings - n squared, palindrome check - n => n cubed. Rough estimation for time - 10 secs in Python - doesn't look good.
Here you have to recall at least a glimpse of that wonderful algorithm you read about. There was something... about... middle points of palindromes! Let's check. n middle points, linear check => n squared. 0.01s for n = 1000. Sounds promising.
In the program I want to share a trick: decomposition. Of course, you can try to write a program in one long sheet of text. But if you split it into logical parts, it's better for you. Python gives you a great opportunity - iterators. In the function you can generate candidates and then select the best using just the max function.
In order to use just max, we are to be careful about an empty sequence. It is not a case here, because n >= 1. If an empty sequence is possible, default = ... in the max function is your friend.
For odd-length palindromes, candidate generation is quite boring. We start with the trivial one-letter palindrome and extend it, if it is possible. No problem.
Even-length palindromes have a real chance to be absent at all. One more trick - make a step back and set up variables in the previous position before they form a valid even palindrome. Then we can check whether the variables are still in this weird initial position. If they are, we don't have a candidate.
So, here we are. A few tricks, and the problem is solved.
🗿2
3D-printed Dragon Curve
Once I stumbled upon a big glass box in the middle of the App in the Air office. I asked, "What is it?" Turned out it was a 3D printer. An expensive one. I didn't get a believable answer about what this thing was for, but I got permission to play with it.
One day I'll tell you the story of my first 3D model in life - it's epic. Now the small story is about the Dragon Curve. Unfortunately, I'm not educated enough to write the whole story about this object, but it is certainly worth your time if you are a fan of math. The Dragon Curve can be obtained by folding and unfolding a strip of paper, as a recursive procedure, as powering up complex numbers...
This model I created myself by writing a small Python program which calculates the path for a Dragon Curve - the easy part - and makes a 3D model out of it - the slightly trickier part. The output of this program was an .stl file, then conversion to gcode, and finally printing this thing out.
I really appreciate the chance to play with this machine. Thanks, Sergey, Bayram!
Once I stumbled upon a big glass box in the middle of the App in the Air office. I asked, "What is it?" Turned out it was a 3D printer. An expensive one. I didn't get a believable answer about what this thing was for, but I got permission to play with it.
One day I'll tell you the story of my first 3D model in life - it's epic. Now the small story is about the Dragon Curve. Unfortunately, I'm not educated enough to write the whole story about this object, but it is certainly worth your time if you are a fan of math. The Dragon Curve can be obtained by folding and unfolding a strip of paper, as a recursive procedure, as powering up complex numbers...
This model I created myself by writing a small Python program which calculates the path for a Dragon Curve - the easy part - and makes a 3D model out of it - the slightly trickier part. The output of this program was an .stl file, then conversion to gcode, and finally printing this thing out.
I really appreciate the chance to play with this machine. Thanks, Sergey, Bayram!
🔥3