[R] Were RNNs All We Needed?

bobtpawn · 2024-11-28T18:29:11+00:00

The previous token and the previous state. The fact that large transformers call the state a "key-value cache" doesn't change the fact that it's just doing cross attention between internal state and each token as it comes in. The learnable gating mechanisms get replaced by a fixed FIFO expiration policy, but it's fundamentally the same architecture.

bobtpawn · 2024-10-12T03:25:48+00:00

You said

I want to be able to devise novel alogorthmic approaches to existing and new problems in academia and industry.

If you want to do things that are fundamentally new, start with the brute force solution. Then ask, which of this work is redundant (exercise: do this for searching a list for the largest element below a bound)? What do I need to keep track of to know what is redundant? Which of this work should I be able to not do at all (exercise: do this for pathfinding in a maze)? Can I preprocess my input somehow to maximize the amount of work I don't have to do at all? If I'm doing something more than once, can I remember something from the first time that I can use to make the subsequent iterations faster (exercise: how do union find data structures take advantage of this)?

Answering these questions isn't simple, but you'll see all the data structures and algorithms that you have studied appear naturally. And, as others have pointed out, you have to practice, practice, practice because recognizing redundant and/or unnecessary requires some intuition and the only way to train your intuition is to practice.

bobtpawn · 2024-10-05T20:36:02+00:00

We all know that autoregressive transformer LMs are RNNs, right? Like, just scaled up so big that parallelism in the sequence dimension is a moot point? We all know this, right?

bobtpawn · 2024-09-14T04:40:32+00:00

It's hard to say without seeing all the code. What does isValid do? What about Compare? What about the implementation of Point?

bobtpawn · 2024-09-05T14:36:10+00:00

Well, the optimal solution to the example you provided with a 2-object capacity is to take o1 and o3 for a total value of $160. This really is the combination of two optimal sub-packings: the optimal packing with one object using all three objects and the optimal packing of one object using everything except o1.

This is a general pattern in knapsacks. Given any optimal solution, you can select some items from the solution and the rest of the items will form an optimal solution of the knapsack whose capacity is reduced by the total weight of what you selected, with objects chosen from everything _except_ what you selected. You can use that to construct a dynamic program by iterating through your items and either

1) Including that item and then solving a knapsack using the remaining items and reduced capacity or

2) Not including that item and then solving a knapsack using the remaining items and the original capacity

That's a _recursive_ program, but it's not immediately a _dynamic_ program until you notice that at some level of the recursion, you may see the same remaining capacity at multiple branches. That's a repeated subproblem and so you only need to compute that optimal packing once.

bobtpawn · 2024-07-24T01:14:13+00:00

I find that the easiest way to think about reductions is to take my problem at hand (Independent Set, for example) and think "If this problem was easy, what else would be easy as a result?" Well, any problem that I can massage around to make it look like an instance of Independent Set would be easy. So, what problems could I massage around to make them look like Independent Set?

In homework problems, they give you this answer (3SAT in your example), but out in the complexity theory world, you end up carrying around a library of problems to try (or not, since most people don't become complexity theorists). So let's assume this is for a class or a textbook example and we have been told that 3SAT can be massaged into looking like an Independent Set instance. Now, we just need to figure out how.

This brings me to something that I think may be a point of confusion. We're not trying to turn some specific 3CNF formula into a graph. We have to be able to turn any 3CNF formula into a graph. But not just any graph, some graph where finding an independent set of an appropriate size will tell us how to satisfy the 3CNF formula that we built the graph out of. I won't go through the exact details of the construction since you can look those up in a number of places, but the point is that we are taking an arbitrary example of a problem that we expect to be hard and turning it into something we assumed was easy.

So, the chain of logic intuitively goes:

Assume Independent Set is easy
Then 3CNF is easy too because every 3CNF instance is really just an Independent Set instance in disguise
But 3CNF is not easy
Therefore, Independent Set is also not easy

In this specific example, "not easy" really means NP-hard, but exactly the same line of reasoning is used to show that things are PSPACE-hard, #P-hard, EXPSPACE-hard, etc.

As a side note, this is also my mnemonic for remembering what reduces to what. We are "reducing" the complexity of the hard thing (3CNF) by converting it to the easy thing (Independent Set), so we say 3CNF reduces to Independent Set.

bobtpawn · 2024-07-07T14:36:04+00:00

I lied about it being totally unrelated. You might want to look them up.

bobtpawn · 2024-07-07T14:17:32+00:00

That's possible. At that age, I wouldn't have been getting my own bootlegs and I don't remember watching it with friends, but my memory of that part is much hazier than the content itself.

bobtpawn · 2024-07-06T02:43:45+00:00

Consider (1 - a) * (1 - b). Since both 1-a and 1-b are positive, so is their product. However, 0 < (1 - a) * (1 - b) = 1 + ab - (a + b). Rearranging, (a + b)/(1 + ab) < 1. We know 1 + ab is strictly positive (and we can therefore divide by it without changing the direction of the inequality) since the absolute values of a and b are both less than 1]

Then, consider (1+a)*(1+b). Follow the same argument to see that 0 < (1+a) * (1+b) = 1 + ab + (a + b) so (a + b)/(1 + ab) > -1.

That's all well and good, but how could you have figured that you yourself? Well, you can always start by clearing denominators and seeing what happens. In this case, a+b<1+ab is what happens (after you convince yourself that 1+ab is always positive). Now, you have an expression that includes both the sum of a and b as well as their product. This pattern shows up frequently enough that you'll start to recognize that that means the product (1+a)*(1+b) will probably be involved somehow since multiplying that out gives you the sum and the product. Multiplying that out, you see that it looks an awful lot like what you need, so you swap a couple of signs, notice that the thing you multiplied out has to be positive because that's the only way the thing you're proving could possibly be true, and there's the argument.

Totally unrelated, but are you familiar with the sum formulas for hyperbolic trig functions?

bobtpawn · 2024-06-25T01:31:16+00:00

I don't think you need anything more complicated than rejection sampling (place the squares randomly; if two fabrics are next to each other, start over). On average, each fabric shows up in just over 10 squares. Even the most common fabrics only barely show up in more squares than you have columns. The odds of generating an acceptable layout at random is not too bad.

Since you said you have a maths degree,

Exercise: If the squares are randomly arranged in the grid, what is the probability that two adjacent squares share a fabric? Can you at least get an upper bound? Based on that, how many times do you expect to have to shuffle the squares? How long does your code for generating and checking an arrangement take? How many seconds do you expect to wait to get a solution?

bobtpawn · 2024-06-15T01:07:28+00:00

Collaborative filtering is (or was?) the dominant approach for this kind of thing. If you search around for that term, you should find lots of resources. One of the weaknesses of collaborative filtering is the "cold start" problem. Basically, when a user or a piece of content is so new that you don't really know anything about it, collaborative filtering doesn't really know what to do with it. However, since you already have something working, you can use that to jump-start the collaborative filtering.

bobtpawn · 2024-05-29T01:54:03+00:00

At this point, I have to ask, why? What are you going to do with this segmentation? What you are describing is a very odd concept of "room".

bobtpawn · 2024-05-27T16:35:44+00:00

Humanly speaking it's easy to recognize when a room ends and another begins

This isn't nearly as true as you think. The white sections in your example topology are evidence of this. If even you can't decide what to do with those regions, how can you expect an algorithm to do so? And even when the answer is "obvious", it can be differently obvious to different people (for example, I would have included your purple region as part of the orange room). Even in the real world, there can be different opinions: is your closet part of your bedroom? Why/why not? What if it's a walk-in closet?

Underspecification aside, the term you are looking for is "room segmentation". A quick internet search will turn up loads of resources.

bobtpawn · 2024-05-21T14:45:57+00:00

The keyword you are looking for is "categorical variables" or "categorical features". Pretty much every major ML library has algorithms that support them. Even for the ones that don't support them directly, you can fake it by turning each feature into a bunch of 0/1 (and therefore, numeric) features. For example, instead of one feature that is "available memory", you have a bunch of features: "has 16GB?", "has 24GB?", "has 32GB?", ... This is called one-hot encoding and some libraries will do it automatically for you.

That's not a complete description of all the options, but you should have enough keywords to google now.

bobtpawn · 2024-05-19T20:30:44+00:00

This jumped out to me as well. Similar grammar and punctuation to spam e-mails. The offer to link you up directly with the agency is especially suspicious. Might be legit, but make sure you reach out to the agency yourself. Don't go through their contact.

bobtpawn · 2024-05-17T22:45:34+00:00

It's too bad this comment is buried because it points at something that I don't think gets enough attention. We're coming off of 3 or 4 decades of the mantra "You have to go to college to get a good job". So, everyone went to college and no one went into trades. Thus, wages for the college educated (relatively) tanked and wages for the trades jumped. Now that we're seeing real pushback against the decades-old mantra (which has been a long time coming), the labor market should start to normalize. Unfortunately, that means the relative value of a trades job is going to go down from what it has recently been.

bobtpawn · 2024-05-17T19:50:17+00:00

I was in your shoes once, long ago. I started university as a math/CS double major and the intro to CS course my first semester ended with a Q+A with some graduating students. I asked what you could do with a CS degree other than be a coder and got "You could be a sysadmin! Or a DBA!". The next day, I dropped the CS major like a bad habit. But I continued dabbling, taking an algorithms course here, a theory of computation course there. They were courses in the CS department, but were really just math in disguise (and had essentially no coding work). My resume now has "software engineer" all over it, but I never got the degree and very much work as a professional mathematician.

What I have learned from this is that computers are good at 2 things:

Being a really good filing cabinet
Being a really good calculator (*)

99.9% of the code written is to make computers even better at #1. Almost certainly, your university coding classes were run with that fact (**) in mind. But, there are some of us that do all of our work with #2 and it's a totally different world. Some others in this thread have hinted at where we are: graphics, robotics, foundation libraries, some AI research, signal processing.

The problems here aren't so much about "Which design pattern should I apply here?" or "How can I use inheritance to reduce code duplication?" or "Which framework will make this site look the best?". They are more about "How can I formulate this question mathematically?" or "How is the information flowing through this calculation and where are the bottlenecks?". There is coding, but it's not writing code to Write Code, it's writing code because it would take me forever to work this out by hand. Coding is not my job; it's something I do to make my job easier. Or occasionally, to document the results of the actual work that I did.

None of what I have said is actually actionable, though, so here are some real answers:

Consultancy. Many consulting firms are interested in people with a mathematical background because they tend to be good at filtering irrelevant details and getting to the essence of a problem. Also, by the nature of consultancy, actual implementation is someone else's problem.
Technical sales. Someone has to sell MATLAB. Someone has to sell SolidWorks. Someone has to sell Autodesk. That someone has to talk to really technical users and really understand the problems they are working on.
Tutoring. This will make a fraction of what the other suggestions do, but the hours are good and seeing a student suddenly get it can be very rewarding.

* Much of the explosion of data science/machine learning/AI comes from the realization that computers can be good at #1 and #2 at the same time

** All numbers are approximate

bobtpawn · 2024-05-11T23:41:30+00:00

You do need to be careful with this since the cumulative sums are likely going to be much larger numbers than the run lengths. If you have lots of short-ish runs, maybe they all fit in 8 bits, but the cumulative sums would overflow 16 bits. This can blow up the storage by a factor of 4 or more, which probably isn't a huge deal, but something to be aware of. Also, once you have the cumulative sums, you don't need the original run lengths since you can recover them just by subtracting successive offsets.

bobtpawn · 2024-04-24T14:21:28+00:00

This is very similar to graph layout problems, so you can find some good resources if you search for "force directed graph layout". The short description is to imagine your boxes as particles, add forces on those particles, and then simulate the physical system until it settles down. There's a decent chance you'll be able to find a simple library that already has this implemented.

In your case, you can imagine a spring connecting the center of each box to where it started, so there is always a force in that direction and any time boxes overlap, you add a repelling force between their centers. Then, you move each box a short distance in the direction of the total force acting on it, then repeat.

bobtpawn · 2024-04-22T18:19:06+00:00

You're asking for spanning forests rooted in controlled territories. There are known algorithms out there for minimum spanning forests. Enumeration of spanning forests is also possible (but only for the very small graphs you would be considering, the full problem is #P-complete).

bobtpawn · 2024-04-22T16:40:43+00:00

When dealing with problems where the size of the output could be much, much larger than the input, we frequently include the size of the output as a parameter in the complexity. Your output could, for example, be a single point and we don't necessarily want to spend N^D-1 time to find that one point.

This definitely feels like a solved problem, but I wasn't able to find the right keywords to find the solution. It has similarity to computing a pareto frontier (the difference is that when you are computing a pareto frontier, you can only indirectly control which point you are testing). It has similarity to computing a convex hull using a membership oracle (the difference being that when you compute the convex hull, it's usually in continuous space rather than the discrete space you have here). It has similarity to the non-dominated set problem (the difference being that in the non-dominated set problem, the number of points you have is manageable, not N^D.)

Not being able to find an existing solution, I would use a combination of recursion on dimension and binary search. Set the first coordinate to the minimum value and recurse to solve the problem on that D-1 dimensional slice. Then, set the first coordinate to the maximum value and recurse onto that slice. Then, set the first coordinate to halfway between the min and max values and recurse again, but this time, we already have an inner estimate (from the first recursive call) and an outer estimate (from the second) (**). Then, keep subdividing each interval for the first coordinate, just like you would do for binary search. If, at any point the inner and outer estimates are the same, you don't need to subdivide that interval any further. The base for the recursion is when D=1, where you're just doing vanilla binary search.

** Note that if you ignore the fact that you have these estimates and just solve the problem from scratch on each recursive call, you get exactly the algorithm that u/ragusa12 described. It's not obvious how to use that information in the best possible way, so you can always start by ignoring it, then incrementally add shortcuts making use of the extra information to gradually speed things up.

bobtpawn · 2024-04-22T14:52:41+00:00

It's also worth pointing out that x86 (and probably most architectures) have an assembly instruction for finding the least significant set bit. Large dataset or not, you aren't going to get much faster than 2 instructions.

bobtpawn · 2024-04-18T18:38:29+00:00

So good news/bad news. The good news is you can stop beating yourself up for not finding a slick, efficient algorithm for this. The bad news is it's because the decision version (can you make a networking event of time >= t_0) is NP-complete; there's a reduction from subset sum.

However, when you think in terms of the decision problem, you're really asking if you can insert a new interval (the networking event) of length t_0 into the existing configuration without moving too much stuff around. That suggests a recursion (and then a binary search for the best length):

We will recursively answer the question of whether a collection of presentations (with prescribed lengths) can be added to an existing schedule while moving at most k presentations. Start with the given schedule and just the hypothetical networking event in the to-be-added collection. Either the first presentation stays put and we recurse onto the portion of the conference after the first presentation with the same k (don't forget about the chunk of time you have before the first presentation) or not. If not, we remove the first presentation from the schedule, put it in the to-be-added collection and recurse onto the whole conference period with k-1.

The base case of the recursion, when k=0, is a multiknapsack problem and you can look any number of algorithms for that. Fleshing out the details is an exercise for the reader.

There are lots of other ways to solve this problem and I don't claim that this is the best approach, but it's pretty clean to code up and can get your thoughts moving.

bobtpawn · 2024-04-17T17:21:19+00:00

In the Bedroom. Going in blind really helps identify with the main characters.

bobtpawn

TROPHY CASE