How did I publish a paper in ACMKDD as an undergraduate?

Original link: 我是如何在本科期间发表顶会论文的？
Posted August 13, 2022
Co-Translator: Shom (@ShomLinEd) / Twitter

I recently stumbled upon the article “How I wrote a top-conference paper from scratch” by @ZhongJianWuFeng on my timeline, where the author sorted out his research journey, which was quite inspiring to me. I have published a paper in ACM SIGKDD and another in the Journal of Chinese Information Processing as an undergraduate. I want to record the journey and serendipities here.

My paper at KDD: A Stochastic Shortest Path Algorithm for Optimizing Spaced Repetition Scheduling | Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

The implementation of my algorithm on Anki: open-spaced-repetition/fsrs4anki: An Anki custom scheduling based on free spaced repetition scheduler algorithm (github.com)

I focus on spaced repetition scheduling optimization, i.e., to improve students’ memorization efficiency by adjusting the review schedule. It has two parts: first, modeling students’ memory; second, designing the algorithm based on the model and the target to find the optimal memorization strategy. Each of the two papers only took less than a month to write, but behind them underlies four years’ worth of exploration and thinking. Compared with other researchers, it is not too much to say that I am a heretic. After all, at present, peer review and “tenure track” are all the rage; who would look for their research direction from non-academic content at the stress and risk of failing to form a paper out of it? So my experience may not have much reference value, but I also believe that there are people in the world who are in a similar situation as I once was, and I hope this reminiscence of mine can help you.

Spark of Interest

To trace the origins of these two papers, I would like to start with my interest in the field of spaced repetition. Though most people find it very abstract and mysterious, scientific research as a human activity must be connected to concrete people, concrete life, and concrete interests.

I first met spaced repetition in 2017, when I went from being a high school student who hated reviews to one bent on doing it more efficiently. In April 2017, I searched for review scheduling software on Zhihu, a question and answer website like Quora, and through the answer by @YuShiXing found Anki, an open-source spaced repetition software. After using Anki for over a year, I saw my grade soar by 100 points. Ultimately, I was admitted into the computer science department of Harbin Institute of Technology, Shenzhen. This process sparked my interest in the principle of this niche software.

I learned about spaced repetition, spacing effects, test effects, and other cognitive psychology-related concepts through Anki. Since Anki is open source software and I found a question about the Anki algorithm on Zhihu, I read the source code of Anki and wrote an article about it. It was about August 2018.

Approach to Tradition

Reading the source code and checking the manual, I learned that Anki’s schedule algorithm was a variant of the SuperMemo 2 algorithm, which made me curious about SuperMemo. But at that time, I was still busy promoting Anki, selling Anki decks to earn money, and making products designed to mimic Anki, so I put these explorations on hold. It wasn’t until late 2019 that I began to “translate” (DeepL is fantastic) the History of Spaced Repetition on the SuperMemo website, as I felt incompetent amid a failed startup. I learned about the tradition of spaced repetition practice, which was shaped by Dr. Wozniak, the creator of that tradition.

Wozniak, the creator of SuperMemo, is a man of legends. He is passionate and stubborn, reflected in the History of Spaced Repetition series that almost counts as his autobiography. Coincidentally, he met the same problem as I did with learning, and for a geek in pursuit of extreme efficiency, random forgetting and inefficient review were unbearable. From there, Wozniak set a 30-year path of pursuing optimum memory algorithms. His career inspired me, and I believe it was something I could devote my life to.

Woz’s theory of memory is not complicated. In his two-component model of memory, the state of atomic memory in the human brain can be described by two variables:

1. Memory retrievability
2. Memory stability

Memory retrievability is the probability that I can recall a particular memory at a specific moment. Why is it a probability? Today I read an idea in a new book that I may remember at this moment, but ten days later, I can neither guarantee that I will remember it nor be sure that I will forget it. It is a stochastic event; then, it can be described with probability.

But memory retrievability does not fully describe a memory. It is impossible to know when a car will reach its destination just by how far it has driven. Nor does knowing the probability of recalling a memory at this moment tell us when it will be forgotten entirely. Therefore, Woz introduced the concept of memory stability as a measure of the rate of forgetting. The following equation illustrates the relationship between memory retrievability, memory stability, and elapsed time:

Where R is memory retrievability, S is memory stability, and t is the time since the last review, and this formula is the mathematical model of the forgetting curve. After analyzing data collected in SuperMemo, Woz found that the decay of memory over time was best fitted with an exponential function. We can draw simple conclusions by observing the formula:

• The longer the time, the lower the probability of recall.
• The speed of forgetting after a review is faster and then slower.
• The higher the memory stability, the slower its forgetting speed.

In this way, the forgetting of memory is illustrated. But it is not enough to schedule the review. Why? Because this model omits the effect of review on memory. So, based on this, Woz proposed a three-component model of memory:

By observing the data, Woz found that memory stability increases after recall in review while stability decreases after forgetting. But such a qualitative analysis is not enough to schedule reviews. We also want to know how much it increased or decreased; for the sake of discussion, we might call this stability increase (C in the above equation.) Woz argues that stability increase is only related to the current state of memory, i.e., given memory stability and memory retrievability, stability increase is determined (similar to a Markov chain). The theory painted a rosy picture against the bleak reality. The data does not perfectly support Woz’s theory, so he patched it by introducing the third variable, item difficulty. Given item difficulty, the relationship between stability increase and memory state became apparent.

To me, this is just a diversion from the paradox because the nature of item difficulty remains to be found. Woz’s subsequent research indeed focused on the prediction of difficulty, but with all due respect, there was more magic than solid math. However, there is nothing wrong with introducing the difficulty variable, essentially a transformation of the native Markov model into the Hidden Markov model.

By the way, it surprised me that Woz would tell stories about his research process in the middle of his theoretical research articles, such as evaporating for 100 days to do research in a mountain cabin. It’s so interesting. His passion also impressed me as I was reading his articles.

Enter into Industry

Nothing can be done with passion alone, and it is hard to make innovations and improvements just by studying traditional theories. Self-absorbed in traditions and self-indulged in theory, they do not substantially change the world. The most embarrassing thing is that memory is full of uncertainty, and it is impossible to verify hypotheses and ideas without a lot of data. In the summer of 2020, I submitted a data mining internship at ByteDance, only to have my resume rejected. By pure coincidence, the next day, I received an internship offer from the leader of Data & Algorithm department at Maimemo. He also studied the SuperMemo algorithm and searched for my translation on Zhihu. After being rejected by ByteDance, I realized that there are tens of billions of data about memorizing words in Maimemo. I immediately went to Qingyuan, where Maimemo is headquartered, to continue my exploration of the industry.

First, I used Maimemo’s data to verify SuperMemo’s theory and found that most patterns were consistent, which gave me comfort and confidence. At least it was not in vain to study the theory for so long. Meanwhile, the laws of memory do not change with the change in learners and memory materials. Then, I pushed for changes in Maimemo’s data collection system to better study memory. Research is difficult to predict and arrange, and if the research questions are not asked correctly, I may be wrong in collecting the data. Woz is always thinking about his memory stability, memory retrievability, and difficulty, and I believe he has simplified the model too early. One should start with the most primitive data for more in-depth memory analysis. For this reason, I thought it was essential to record the complete memory data, such as the content and time of each review by each user, the success or failure of recall, the whole review history, and so on. Later I realized that what I wanted to record is the time-series information of memory behavior, which is the basis to support my research on memory.

Independent Thinking

I gradually discovered the problem of Wozniak’s theory as I delved into memory data. Two variables In his three-component memory model, memory stability and memory retrievability, have corresponding patterns in the data of Maimemo. However, item difficulty remained elusive. Also, his efficient memorization is ill-defined. This led me to think independently and try to fill in the gaps in the puzzle myself.

My first entry point was to find the most efficient review policy by simulating the memory process. I wrote the Spaced Repetition Simulator in early 2021 based on Woz’s theory and Maimemo’s memory data. It modeled a learner’s memory under various strategies to verify their efficiency. First, I imposed several constraints on the memory process, such as fixing the total number of reviews per day, the simulation period, etc. Then I measured the strategy’s efficiency by the total amount of memorization at the end of the simulation. This is a Monte Carlo simulation, and although I didn’t learn it systematically, it didn’t prevent me from using it.

During the simulation validation, I found that Woz’s strategy of maximizing expected memory stability was not the most efficient. This led me to a new zone in the research. I began to realize that the three-component memory model was also insufficient to support my search for efficient memory strategies because the model did not include a constraint on memory cost. So, in a hazy intuition, I defined a new concept on my own: review stress.

I believe efficient memorization is about forming long-term memories under minimal review stress. There are some intuitions here, such as that as each review succeeds and stability increases, the review stress becomes less and less. Then review stress must be related to the number of reviews. But I wasn’t proficient enough to formulate the relation in math language, so I had to keep deducing and attempting with sheets of draft paper. Through this exploration, I found that review stress is the expectation of reviews. And for calculating this expectation. I need the state transfer equation of memory and the review policy. This process includes specific models and strategies, as well as stochastic forgetting. I remembered a mathematical tool I read on Zhihu that fits to describe this process — the stochastic process.

I was ecstatic to find the mathematical tool, so I immediately got Ross’s Introduction to Probability Models and started learning it. I soon found an example problem very similar to the one I had in mind for calculating review stress.

This question is about a miner facing three doors, one door taking two hours to reach the destination, and the other two doors taking three and five hours and returning him; if the doors are chosen with equal probability, then what is the expectation of the time needed to reach the destination.

You may wonder what this question has to do with the review stress. Let me make a simple analogy. Suppose there are only two doors, one door is called a successful review, and one door is called a failed review. A successful review will increase memory stability and bring you closer to the goal of forming long-term memory. A failed review will result in no increase (or decrease) in memory stability, standing still or further away from the goal. Each time a door is selected, there is a time cost (review takes time), so the review stress is the total time cost required to form a long-term memory, which is the expected time for the miner to reach his destination. Only the scenario faced by memorization is more complex. For example, depending on the review interval, the probability of walking into one of the doors will change, and the door to be walked through may be different each time. But the essence of both problems remains the same, and soon I manipulated this mathematical tool to describe the problem clearly.

When a vague real-world problem is transformed into an apparent mathematical problem, it is halfway to success. But the above problem is calculating the expectation of review stress given a review policy, so is there any opposite problem — figuring the review policy minimizes the expected review stress? I continued my search for tools in stochastic processes and found the Markov Decision Problem.

Review schedule optimization optimizes policy to minimize review stress based on a known memory model. But Ross’s book doesn’t go into much detail about how to optimize policy. I had to search for Markov decision process-related articles on Zhihu to learn that this thing is dynamic programming. But with some randomness added, it needs to calculate the expectation.

Then I continued to associate and found that if I treat memory stability as a series of discrete states, with the cost of the review as the path weights among states and the probability of recall as the probability of these paths going through, then in effect this is a stochastic shortest path problem. I quickly combined my existing knowledge of dynamic programming with my understanding of stochastic processes. Then I wrote the first version of an iterative algorithm that can be used to compute the recall probability corresponding to the optimal review interval under each memory stability.

At this point, I think I have solved the problem of optimizing my review policy. I started working on sorting out the whole memory scheduling system.

Start Writing

First Paper

Essentially, optimizing interval repetition scheduling can be divided into memory modeling and strategy optimization. My first paper, “A Long-term Memory Prediction Model for Language Learning via LSTM,” focuses on the former.

It was September 2021, and I was forced back to school to do my Graduation Design. Still, I wanted to continue my research at Maimemo, so I struck a deal with my supervisor that I would publish my paper, and he would let me continue my internship, so I spent about a month writing my first paper. Since this was my first academic paper, I started reading the relevant literature. I found that Duolingo published the most recent paper on memory modeling in 2016, and I summarized it in a note on Zhihu. They proposed a memory half-life regression model, which uses some statistical features to predict the half-life of memory. And what is memory half-life? It’s memory stability. I breezed through their paper and found colossal room for improvement. Because they use statistical features, and a memory process is a time-series event. So some time-series features + a time-series model would be enough for a paper. The most commonly used time-series model related to neural networks is the LSTM.

So I started reading the PyTorch documentation, copied the LSTM call code that others wrote on GitHub, and then used Pandas and Numpy to turn Maimemo’s data into a Tensor format that could be fed into the LSTM, and finished the experiment in a week. My poor MacBook suffered (which I bought with Maimemo’s internship salary) because I didn’t have even one graphics card. Then, to connect my paper with the academic literature (Woz’s article is like a folk scientist article), I replaced the term memory stability with half-life and memory retrievability with recall probability, and the model was named LSTM-HLR to show that my work is an improvement on Duolingo.

After that, I spent about a week finishing the first draft of the paper (in Chinese). Then my supervisor asked me to investigate research conferences to which I could submit my paper. The funny thing is that almost none of the conferences at the intersection of AI+Education were accepted by CCF. Finally, my supervisor asked me to submit the paper to the Journal of Chinese Information Processing. I submitted it in October and got one rebuttal and one formatting request before it was accepted in November. Then I rushed back to work in Maimemo; of course, the name is also very legitimate, called off-campus Graduation Design, lol. (Chinese universities require juniors to write a paper before they can graduate)

Figure: Hello, The manuscript you submitted on October 14, 2021, titled A Long-term Memory Prediction Model for Language Learning via LSTM (numbered 2021_0238), was accepted after expert review. Due to the limited number of works, we cannot inform you of the specific issue number. I hope you can understand the inconvenience.

Hereby notified.

Second paper

After I returned to Maimemo, I applied the review policy I had previously thought about to the actual business and conducted AB tests. The results were promising, and my years of research finally paid off, helping millions of users improve their review efficiency. I planned to continue optimizing the algorithm when my supervisor came to see me again, probably around January 2022. I thought he was asking me how my thesis was going, but he caught me off guard by asking me to publish another one. He said that it would be advantageous to have the paper accepted by the CCF B Chinese core journal and that sending another paper to the CCF A English conference would be better. I did not want to write one, but I considered that if I could send an international paper, my research could be used by more people and help more people, so I pushed myself a bit and started my second paper, A Stochastic Shortest Path Algorithm for Optimizing Spaced Repetition.

The main focus of this paper is to write a review policy optimization, for which I read a lot more literature where it seemed everyone likes reinforcement learning so much. I am not a big fan of this method because the rewards are hard to set, and it is hard to implement online reinforcement learning in Maimemo. The disappointment vanished when I came across an article on doing it with marker point processes and optimal control, where the math inside felt beautiful (but I couldn’t understand the stochastic partial differential equations). I then thought about how to wrap up the minimal review stress iterative algorithm I had come up with earlier in more elegant mathematical language. At that time, I searched for articles about stochastic shortest circuits and found @WangYuan’s notes on reinforcement learning and optimal control. It turned out that there existed mathematical tools in optimal control theory to describe this problem, so I rewrote my previous draft using the Bellman equation.

But I have another problem: which memory model should I use? My LSTM-HLR model had been accepted but not published, and it felt like it would be problematic to introduce it again in a new paper. So I introduced Woz’s three-component model and tried to use machine learning to compute the model parameters. In this process, I first considered how to downscale the time-series memory data to better see the patterns in the memory data. Woz’s SInc matrix inspired me to represent each memory behavior in terms of stability, retrievability, difficulty, and stability after review. The remaining three attributes can be projected into 3-D space if we represent difficulty as color. For this purpose, I learned plotly.py, a library for data visualization, on the recommendation of a friend, and then manipulated the data of Maimemo.

After visualization, I found that a simple linear regression model would suffice, with at most some non-linear transformations for the features. Here I refer to the form of Woz’s stability increase function.

Then the artificial time-series model was created. The next step was to compare it with the HLR model. The results were excellent. This shows that statistical features are inherently flawed, with no wonder. The statistical features didn’t account for time-series information, which is essential in the change of memory state, so I was not surprised that the results were good. Still, I was astonished that no one had previously used time-series information for memory modeling and prediction. (Actually, there was, but the paper was too old and didn’t use machine learning, and I couldn’t even figure out how to calculate their parameters). Then I discovered that the only open source dataset in the field of memory is that of Duolingo. To make the paper more easily reproduced by others, I discussed making the dataset open-source with the leader in charge of the company. Finally, I made the dataset and the experimental code public for further development in this field.

Ye, Junyao, 2022, “Replication Data for: A Stochastic Shortest Path Algorithm for Optimizing Spaced Repetition Scheduling”, https://doi.org/10.7910/DVN/VAGUL0, Harvard Dataverse, V1

Returning to this time-series model, I looked at the method for solving the optimal policy in the case of known state transfer equations in Reinforcement Learning and Optimal Control. I found that the iteration method I wrote before was the value iteration method, which I then described in pseudo-code.

It is pretty decent, J is the cost matrix, π is the policy matrix, f is the memory state transfer equation, d is the difficulty, h is the memory half-life, p is the recall probability, and a and b are the costs of successful or failed review. By continuously iterating through the review intervals in each memory state, calculating the expected review cost, finding the review interval that minimizes the expected cost, and continuously iterating, the optimal cost matrix and the optimal strategy matrix can eventually be converged.

After these contents were almost written, I synchronized the progress with my supervisor; I said I didn’t use deep learning, was it not easy to submit, and he said that you submit it to KDD. Then I researched KDD and found that KDD is quite a lot of companies that send papers on it, and there is a particular applied data science track, so I started to change the paper according to the requirements of KDD. I didn’t expect KDD to have nine pages in two columns, so I had to add some fantastic visual images to it because I heard from my senior that it would be easy to be considered not solid enough if I didn’t write a full paper, and I died laughing.

So I started to think of a valid reason to add visualization images, and I thought of a bunch of deep reinforcement learning methods that were black-box and not very interpretable, so I could visualize the model weights and the pattern of optimal strategies on the grounds of explaining the model mechanism.

And then it’s a matter of explaining the figures. Here are a few observations from the memory model:

1. As difficulty increases, the potential increase of half-life decays.
2. As the probability of recall decreases, the potential increase of the half-life grows, which means that it is a “desirable difficulty.”
3. As the half-life increases, the potential increase of the half-life decays, meaning that memory cannot be consolidated indefinitely.

There are also phenomena observed from optimal review policy:

1. The higher the difficulty, the higher the expected cost of review.
2. The expected cost of review decreases as the half-life increases.
3. The optimal review interval increases with difficulty when the half-life is the same.

Later, to visualize the time-series model and the stochastic shortest path problem, we drew a flow chart with draw.io.

Then I worked with my supervisor to polish the paper, finally caught up with the deadline in February when the Spring Festival was over, and submitted the manuscript. Then I received the acceptance notice in May, and the story here is almost over.

Easter egg

The story is not over yet; at the end of April, my supervisor came to me again, saying that it is challenging to be accepted by KDD, and asked me to prepare another paper for NeurIPS. Half a month into my preparation, my KDD paper was accepted, making my supervisor change his mind and say, “Let’s expand it into a journal paper.” So I’ve been writing a journal paper for the past two months, and writing 12 pages in two columns has made my head spin. But I still finished it and added my previous idea to it, so I hope I can have it accepted this year.

Summary

Looking back on my research journey, I found it full of coincidences and surprises, and I dare not say I have made an outstanding contribution to this research. Without Anki’s help, Wozniak’s theory, data from Maimemo, and the various learning materials produced by Zhihu users, this research could not have made progress.

But one thing is undeniable: I have chosen my path, learning freely through exploration, driven by passion, and finding ways to escape the control of schools.

I firmly believe that memory research can drive educational technology’s development and allow lower-cost learning tools to reach every learner.

I found my path in life through free learning, transforming from a small-town swot to a research engineer in an education technology company, and becoming a researcher in the field of memory. I believe that in the future, every student will be able to break free from the shackles of decaying mandatory schooling, realize themselves through free learning, and live a commonly recognized good life.

I am Jarrett Ye, and I hope to continue to share with you in the future!

Reference

Spaced Repetition for Efficient Learning · Gwern.net

History of spaced repetition — supermemo.guru

L-M-Sherlock/space_repetition_simulators: 间隔重复模拟器 (github.com)