# How to Write a Neurips Paper [3]

Sup guys, I’m back with the 3rd installment, been busy. Don’t worry though, I will see this blog series through.

Since last time, you decided that you wanted to spend the next few months of your life working on a specific topic. However, it is rarely the case that you are fully equipped to carry out your work, you’ll have to gear up. A rule of gears is that, they should serve your goal — to perform original research. How do we walk the fine line between well equipped and being too distracted by shining things? Hopefully this chapter will give you some hints on the process of acquiring sufficient knowledge for your works.

## you don’t have to prove a point

Before we continue, I really want to get this meta-point out of the way. MIT has this motto of learning as “drinking from a firehose”. That is *not* good for your health. You don’t have to prove to anyone that you are capable of learning difficult subjects (you’re already doing research). It is mastery that you are after, not unwarranted struggles.

# have a check point

While everyone learns differently, we can readily check when a piece of knowledge is attained: One can demonstratively do things that they cannot do before. It is extremely helpful to have a check point of the form “If I learned X, then I should be able to perform Y” and write down Y explicitly as a quiz before you start learning X. For our purpose, Y should be an aspect of your research that you could not do before.

Notice the duality between the easiness of check (demonstration of Y) vs the difficulty of attainment (actually learning X). This is a telltale sign of **search problems**, which are ubiquitous in research and in life. I want to take a detour to just talk about this concept exclusively.

# concept 1. search problems

What do the game of sudoku, program synthesis, coming up with research ideas, reinforcement learning, writing a paper, 3SAT, and making a delicious sausage have in common? The answer is that they are all **search problems** where the answer is *easy to check* and the solution is *difficult to find* — While David Hilbert can easily discern a tasty sausage, it is unlikely that he knew how to make one. Let’s formally define what a search problem is.

## def : search problem

A search problem is a tuple (X, v) where X is the space of all possible solutions and v is a scoring function that, for each x in X, gives a score. The objective of a search problem is to propose a particular x that maximizes the score.

## generate and check

The standard way of solving a search problem is generate and check: an algorithm generates a stream of proposals x1, x2, x3 … and gives one that has the highest score using v. For instance, one can enumerate potential solutions to a sudoku puzzle one after another, and check if the rules of sudoku is satisfied each time (score of 1 and 0). One can also find the inverse of a matrix A by, humor me if you will, enumerating all possible matrices B1, B2, B3, … and checking each one if AB=1.

## knowledge of X → better generation

One can improve generation by leveraging the structure of X to perform intelligent generations. For instance, by realizing that the loss function (AB-1)² is convex, one can use gradient descent to generate a sequence B1,B2,… which quickly approaches the true inverse of A. Further, you can just follow the algorithm for inverting a matrix. Intelligent generations (through knowledge of X) applies beyond algorithms: A better researcher has a higher success rate in generating research because they understands the field better.

## search problems in this blog series

Formulating a problem as a search allows for a very clean **separation of concerns**, separating the problem definition (how do we check if a solution x is good?) from the problem solution (actually generating an x that is good). This separation is a powerful *thinking tool* that allow you to set a well-defined goal unconstrained by your current capabilities of achieving it, while being creative in generating a solution without fear of getting lost. For instance, in the topic of coming up with research ideas, Chapter 1 gives hints on how to *generate* good research ideas with an emphasis on being *chaotic*, while Chapter 2 gives the *check* on whether the idea is worth pursuing further with an emphasis on being *disciplined*.

Now that we’re finished with our detour, let’s get back on track of how to acquire knowledge under the lens of search problems. We have already established the *checking* part, in the form of a demonstration: “If I learned X, then I should be able to perform Y”. How do we actually go about acquiring X?

# an alignment chart

Unfortunately best answer I have for acquiring knowledge “It depends on the situation”. Nonetheless, we can still categorize the landscape of our search space, that of acquiring knowledge, into two axis.

## established or novel?

The first question you should ask while learning something is: “How many times have people tried to teach this?”. From a subject’s original exposition in a research paper, to its appearance in special seminars, until finally appearing in a textbook, its expositions improve and become systemized over time. As researchers, we ingest knowledge on the whole spectrum from established knowledge to novel research, and it pays to know where it is.

## interactive of literary?

The second question deals with the mode of consumption. In the literary mode, the information is presented as-is and you cannot ask immediate clarifications. Whereas in the interactive mode, you can coordinate with a partner to resolve any ambiguities on the fly.

If I were to suggest a “procedure” of learning, I’d say first try to quantify how established is this piece of knowledge, then try to find a medium that is most interactive. Below is an “alignment chart” sorts outlining some mediums of acquiring knowledge and where they lie on these two axis. For instance, if you can afford a one-on-one with an author, you can save a lot of time trying to understand a research paper by yourself.

# short story time

Let’s wrap up with a quick behind the scenes in pragmatic program synthesis. Kevin and I knew of a hilarious instance where one of our lab member, when requested to order something paleo by another lab member, simply ordered 2 whole trays of boiled broccoli without any seasonings. Rational speech acts, the particular form of pragmatics we were looking into, promised a way to explain this phenomenon with an algorithm. We thus decided that our **check** (Y) should be of the form: Can we run a simple pragmatic algorithm so that the “literal” answer would be 2 trays of broccoli, whereas the pragmatic answer would be something more tasty?

Rational speech acts (RSA) was first described around 2006, and it has barely made its way into specialized courseworks in computational cognitive science. Thus one can say this piece of knowledge is **novel**. Thus, I immediately took the opportunity when my friend Max offered to connect me with someone who studies it for a living, and booked 1–1 tutor session which is **interactive**.

I then spent a week playing out the math of pragmatics, trying to connect it back to some research I was doing on informative example selection.

Finally, I was able to perform the check. On paper and pen, we represented all our lab members and their dietary preferences, and a list of restaurants matching these preferences. We then performed pragmatic inference using RSA, and obtained the results that we hoped for: A pragmatic listener will have a lower probability of buying trays of broccoli than a literal listener.

## see you in the next chapter !

In this chapter, we gave some hints on how to **acquire knowledge** to do research, under the lens of **search problems**. Next chapter we will cover building a small prototype (think mvp) both as a mean of giving yourself confidence and as a mean of communicating to your friends of your idea.

I will be updating this series once every couple weeks (or months, as it turned out KEKW), depending on how much free times I have. I will be announcing the new updates on my twitter, so if you can follow it that’d be great :)

thanks for reading and high five!

— evan

chapters list :

- [0] overview : a look behind the scenes
- [1] getting a research idea : series of voodoo rituals
- [2] vetting a research idea : be honest and disciplined
- [3] acquiring knowledge : set a goal first
- [4] building a prototype : <under construction>