welderofwords

[welderofwords]

(About: explanations, understanding, why former sometimes do not help w/ the latter)

Oh, I think I get it now, why don’t papers explain

What is an “explanation” really?

Let’s say that an explanation of X is a text (a sequence of words, a sensory experience, w/e) that makes it easy or effortless for a reader to reconfigure their mind into understanding X. “Understanding X” is also rather mysterious, & I don’t have a good definition for it, but consider what one can do iff one understands (a class of objects) X:

easily (S1-ish) recognize objects as Xs

easily recall qualities of Xs relevant to a particular task or question

see how an X fits into a more complicated system & what characteristics of the system its Xness entails

easily translate between semantically equivalent syntactically different representations of Xs

recognize X-shaped holes; questions or problems to which “an X” is a good answer/solution

build an X from pieces

deconstruct X into components, translate questions about an X into questions about components

tinker w/ qualities of components of X to make qualities of X “better”

(etc)

None of these are mental motions you can install in your head by reading a text, right? A text may describe how to build them from simpler motions you might already know, or laborous S2-algorithms for them, but mostly what you need to acquire such abilities is practice.

On the other hand, to practice a skill, you need to be able to distinguish success from failure, and a laborous but definite algorithm for that is a good starting point. Or, when practicing a complex skill, it might be next to impossible to figure out a successful sequence of actions simply by trying, and so it’s good to start from something that definitely succeeds.

In a similar vein, a recurrent experience I have with explanations is that they read quite differently before and after I understand X. The same words come to mind when attempting to “explain” X, I can blank out big technical pieces of an explanation (an algorithm in pseudocode, a proof step) and reconstruct them purely from the mental model of X, and so on.

So what I’m saying is: even among decent explanations, many do not enable the reader to understand X, but only to recognize when they understand X; they provide a blueprint for a classifier (of models of X, into good and bad ones) but not a generator (of good models of X). (It is after all easier to recognize a solution to the problem than to find one; it stands to reason that teaching how to do the first is easier than how to do the second.)

(Not that there aren’t explanations that do help with mechanical understanding. Going through and re-implementing Monadic Parsing in Haskell line-by-line is the single best way I know to learn monadic parsing from a cold start1.)

constantly trying to predict what the paper is going do next might or might not be a necessary ingredient ↩︎

[welderofwords]

(In which there are several really stupid sorting alogirthms, handwavings of correctness proofs of same, and musings on general ways to construct algorithms of various "intelligence")

sorting algos

Let's talk about sorting algorithms.

A "sorting algorithm" is supposed to solve the following task: you have an array of n strictly ordered objects; you can perform constant-time access, comparison, swaps; the goal is to have the array sorted. Equivalently: a given array has n! possible permutations; in a single move we can compare any two elements, or apply any single swap-permutation, or stop; our goal is to reach the one permutation in which the array is sorted and stop there.

brutally simple

A particularly simple (and stupid) solution to the task is Bogosort: force the array into every single permutation in order, stop if it is sorted. That's O(n) to reorder the array into any given permutation1, O(n) to check if it's ordered this time, O(n!) permutations to go through, so O(n×n!) altogether. On the other hand, it's really easy to see that it succeeds: it can check directly whether the current point in the solution-space is the solution, it checks so for every single point, and so of course it will eventually stumble upon the solution itself and report it. (In general, brute force algorithms never rely on any ~internal structure~ of the problem, always obviously "work", but aren't any good at searching through huge solution spaces.)

do no harm

A slightly less stupid algorithm could at least "try to move in the right direction". For example: choose a random pair of elements, swap them if they're in the wrong order, repeat until the array is sorted. This is not quite but almost Spin-the-Bottle sort, which works in O(n² log n); much better.

How do we prove that this works?

Well, we can define some2 measure of "sortedness" of the array, demonstrate that every such swap decreases it, demonstrate that it is 0 (or otherwise has a minimal possible value) iff the array is sorted, and that'd be enough. That is: if every swap decreases the sortedness, if there are no infinitely decreasing sequences of sortednesses, and if 0-sortedness is the victory condition, then we can always keep doing swaps, and will eventually arrive at a sorted array.

A suitable measure of sortedness is the count of array inversions; the count of pairs (a_i, a_j) that are misordered: a_i > a_j but i<j.

count of inversions is a nonnegative integer; as long as it decreases, it will eventually hit 0

an inversion-free array is indeed sorted; every pair of elements in it is in located in the correct order

suppose we try to swap elements a and b, such that a > b and there are some elements between them, [..., a, x_i, ..., x_j, b, ...]. Let's count all changes in the inversion count.

if some x_k < b < a, then (x_k, a) was misordered and now isn't, and (x_k, b) wasn't misordered and now is; inversion count is unchanged.

if some x_k > a > b, then it's the other way around.

if some b < x_k < a, then both (x_k, a) and (x_k, b) were misordered, and now aren't; -2 inversions.

finally, (a, b) ceased to be misordered; -1 inversion.

so, swapping a and b definitely decreased the inversion count. QED.

there's a way

If we have an idea of a "right direction" to move in, we can try to be cleverer about it. Say, we could start from the beginning, search for an adjacent misordered pair [.., a, b, ..] and swap it into [.., b, a, ..]. Then, why not check for obvious improvements: maybe [.., c, b, ..] is now misordered. And so on, floating b as far left as obviously necessary, then continuing the search for misordered adjacents from a onwards. Oh look it's Gnome sort. (We're down to O(n²) sorts!) The proof of correctness is significantly easier3 here:

by construction, there are no misordered adjacent pairs to the left of the "current position"; every time a swap might introduce one, we check up on it and correct that

every step to the right requires only so many "propagating" steps back to the left

after we've stepped all the way to the right, there are no misordered pairs at all, and we're done.

step by step

There's another good principle we could use: pick a small subproblem, solve it entirely, never touch it again, repeat until done. A convenient small subproblem for sorting is "what element would be first in the sorted array?"; repeatedly doing that is Selection sort, also of O(n²). Correctness of that one is comparatively easy: again, we define some measure of "complexity" of the rest of the problem, we demonstrate that we can always pick a subproblem that leaves the whole problem less complicated unless we're done, we repeatedly pick a subproblem, we're done. In particular, a complexity measure for selection sort is "how many rightmost elements of the array are not yet guaranteed to be sorted?"; it decreases by 1 with every selection, until we're at 0, a sorted array.

the holy grail

Finally, we could split the problem into several strictly smaller instances of the same problem, and somehow combine them into a solution to the original. For sorting this means quicksort or mergesort; in general those are divide and conquer algorithms. Formal correctness proofs of these are somewhat finicky, relying on:

careful definition of "strictly smaller"

ability to combine smaller solutions into a larger solution

correctness in a number of "trivial" cases: at some point we need to stop recursing and solve the problem directly

what if we tried more power?

Sorting algorithms can't really do better than O(n log n). An argument goes as follows: at the start, you have absolutely no idea which one of n! orders is the right one. As you start comparing elements, every comparison allows you to ignore at most half of conceivable orders as incorrect; and to get n! down to 1 by repeated divisions, you need at least O(log(n!)) = O(n log n) comparisons, and that's that.

One big assumption the argument relies on is that all possible orders are a) possible, b) equiprobable. This might or might not hold in real life, and if you know something about the distribution of possible orders, you can exploit that to get better results than O(n log n)4.

Another one is that all constraints are as described: all comparisons are strict, there's no other way to extract ordering information than comparisons, there's no other way to reorder than swaps, etc.

you can be more efficient by choosing close-by permutations, but really, if you have intelligence to spare to optimize the order of permutations in bogosort, you can just as well do not-bogosort. ↩︎

well-founded ↩︎

To be fair, this is also a proof by finitely decreasing measure; it's just that the relevant measure is slightly awkward. ↩︎

at least in expectation. ↩︎

[welderofwords]

self-blackmail

You know about the practice of self-blackmail: telling yourself “I want myself to not do X, so when I catch myself doing X, I’ll punish myself w/ something unpleasant Y”? This only works if “you” are in sufficient agreement w/ yourself about wanting to do X, such that parts of you in charge of deciding what to do will not go at war with themselves over this little manipulation (And also if parts of you in charge of decision-making are at all capable of taking into account distant punishment, which they might not natively be) So, it may not work for the same reason as ordinary blackmail: if the blackmailee is precommitted to/by nature/by FDT not gonna be responsive to blackmail It can work if blackmailer and blackmailee parts of you are already in alignment, & blackmailee does not mind changing their incentive structure to achieve the agreed-upon goals better But w/o that agreement it is pretty natural for the blackmailee to go “how about fuck you; let me teach you the hard way why blackmailing me is a bad idea” Same thing for the inverse situation, “I want myself to do X, so when I do X, I’ll reward our brain w/ Y” An objecting part can also easily go “Nope, I did not agree to be manipulated into doing more X; I’ll reward our brain w/ Y whenever I like and I will resent you for trying to manipulate me”

So, what to do instead? Diplomacy! Noticing when you both want and do not want to do X; figuring why not (usually for much sillier reasons than fundamental disagreement!); inventing workarounds and hacks for parts of doing X you dislike. Then, after all of you agrees on the course of action, you could revisit the blackmail idea, though chances are by that point it doesn’t get you anything new: you can’t really beat the incentive power of “if we don’t do X, we get less of what we-all want”.

(What about parts of you who do decide what to do, but aren’t verbal / communicative enough that you can meaningfully convince them? Or those whose decision making is so automatic you don’t even notice it & can’t introspect on it?) (Uh. You can still model them & try to figure out what they want & try to come to agreement in absentia?) (Tbh I don’t know yet.)

[welderofwords]

the nerve, to do hard things

There’s a pattern of thought that goes:

I want to X

out of many who try X, few succeed

therefore, X is ~hard~

therefore, I’m unlikely to succeed @ X

therefore, instead of trying & being frustrated w/ failure, I should stop wanting X, or convince myself that I don’t want it that much.

I’d like to wage war on it.

First, let’s dissolve the “X is ~hard~ step”; few people who try X succeed, what of it? People fail or succeed at X for mechanical reasons, not because some magical process looks at the abstract hardness of X and randomly chooses a proportion of those who will succeed. Looking at people who succeeded and failed may be useful if it tells you these mechanical reasons, or if you can learn what to do and not do to succeed. However, after you extracted this, how likely you’re to succeed is determined by your actions, not by how many tried before.

Second: I find that a whole lotta things feel hard when I don’t know how to do them, and trivial when I do. Hence, a motto: Few things are hard; some things are long, and some things I haven’t yet figured out how to do.

There are times when I don’t know how to decompose a hard task into a series of easy steps, but that’s also susceptible to decomposition: learn how people go around doing this task, observe small steps, do them, recurse as necessary. Read some theory, read some advice, follow some.

There are times when there isn’t really a good theory about doing X, and advice about doing X is all overly general or next to useless. (Learning Japanese was like that for me.) Still doable: you can look at what people do and try that, keeping in mind whether it helps, how much, and whether you can improve on that. Somewhere along the way you might ask yourself why some things help and others don’t, and fragments of theory might fall out.

Third: it’s not necessary to have a complete 146k-step plan that brings you from here to victory. A lot of information you’ll need you don’t have right now, but can find along the way (automatically or deliberately). A lot of actions you can’t do now, or aren’t even aware you can do or will need to do, but can encounter, learn, and master as you go.

[welderofwords]

What I wish I had known (about work)

feeling terrible doesn’t mean I can’t do things, nor that doing things is a bad idea

feeling dreadful about doing something does not imply I can’t have fun & get satisfaction from doing it

anxiety means I’m not doing things I implicitly promised myself to do; doing them makes it go away & life more pleasant

not knowing the obvious next step is not “I’m bad” but “I need to decompose the task”

more decomposition

more than that

if I haven’t done anything for a couple minutes straight, it probably means I don’t know what’d be a good next step, which means more decomposition

writing down “so how do I do X” is a fantastic first step towards having done X

“what do I even need to do” also works

copy-paste is a perfectly servicable tool

so’re google and stackoverflow

there are reasons and ways to avoid it, but they’re higher level; learn to use it first, learn how do better than that later

in general, taking pieces of things that work and gluing them together is not worse (better, honestly) than making everything from scratch

there are times to carefully read the whole manual and times to Ctrl-F the exact five words you need to know

estimating how long tasks will take is a potent anxiolytic

for non-work tasks too

overestimation is an act of self-care

with the added benefit that it’s gonna be closer to real estimate

writing down what we did today or this week brings a lot of self-worth and satisfaction

asking colleagues small or seemingly stupid things: good; they will not think less of us, and it can save us a lot of time & cost them only a little

especially when we’re not sure what’s the right call

trying shit on small scale: very good for building familiarity and understanding

editing is easy; therefore, agonizing over doing things right right off the bat is a wasted motion; do things in any way at all that gets you to the next step, and clean them up later

prioritize tasks that produce immediately visible improvements in the state of work

planning (a week, a day, an hour, next 3 steps) is good, it tells us what to do

plans will not survive contact with the unknown; keep them short, scrap them and replan as often as needed; thrice in 15 minutes if need be

food is important

it also takes energy to process; a bout of disfunction right after a food is normal

temperature is important

fresh air is important

[welderofwords]

One of the good parts of capitalism-as-social-technology is that it channels egoistical goals of an enterpreneur into prosocial actions. If you found something you can create cheaply that other people value (& are willing/able to pay for), you can take the difference & live on it; conversely, if you want money, success, power, etc, one way to do that is to find a new way to generate surplus value & to capitalize on that.

People might value your thing and pay for it only a little, not enough to cover your costs. That’s to be expected, really.

It might be hard to make people pay for your thing even if they value it a lot.

Example: video games: it seems that piracy pretty much won over DRM, and (some part of) gamedevs are reliant on the fact that players will buy their games even when they could pirate them. This is slightly awkward but gamedev makes do.

But there are also situations where people value your thing a lot, but the world is not set up such that they can, or will, pay you for it much.

Example: roads, or, in general, well-run traffic infrastructures. Pretty much everyone benefits personally from quick, cheap, conventient commute. Legends say that second-order economic effects of making cities bigger and denser are enormous. Extracting all of that value is the problem.

Adjacently, there’re situations where a business (something that only ever tries to make money) can extract more money from a system, and in the process destroy a lot of unclaimable value.

Example: paywalls bring profits to publishers, sure, but at the (huge) cost of inaccessibility of most scientific papers to non-institutions, and therefore decreased general ability to research, innovate, etc.

Example: lootboxes are obvious if you’re in charge of a game-as-a-product and your job is to make money off it; they will also make the game less fun (which players value!).

(Perhaps if your players could tell you precisely how much less fun they now have & how much less they’re willing to pay for your game, you would try lootboxes once and stop, but alas we do not live in this world.)

Some such ventures do get funded somehow. Roads, archetypically.

(Q: how do roads get funded?)

(A: good fucking question! I suspect mostly via blues government but don’t actually know.)

And on the other hand, venture capital is known to fund huge startups that fail to materialize monetization or profits. Uber, legendarily.

And so forms an idea: pehaps the world would be better off if the drive to make money above all else was slightly less harsh; if somehow businesses in position to rent-seek did not do that (because, I dunno, anyone could bring the rent-seeking scheme and a prevention mechanism to the Ministry of Rent-Seeking, collect their valuable prize, and then that scheme would cease to be possible?); if there was enough free something in the world to prosocial but unprofitable projects

(This is probably impossible, or merely extremely hard, for more-or-less usual nontrivial reasons which this margin is too small to contain)