On the Cybernetic Instability of Deterministic Ranking
Geometers know input perturbation like the front of their hands, which are always in some general position.
But, what about output perturbation, and output randomization?
(The original title of this blog entry was "perturbations in your milk, cereal, and I/O" but my mindform took another state before I published it.)
That is, the algorithms in Motwani and Raghavan seem to consider only problems that have a single answer (or a set of equivalent, optimal answers).
They describe a Las Vegas algorithm as one that "always gives the correct solution" but the running time varies (for example, randomized quicksort).
In contrast, they note, a Monte Carlo algorithm "may sometimes produce a solution that is incorrect," but one can "bound the probability of such an incorrect solution." For example, pseudoprimality testing can be used to return an integer which is probably prime.
Fine, but what if the solution is not a permutation or an integer, but a probability distribution of possible answers (some of which are 'correct' and some less so :)?
That's deeply perturbed you say! You're an enginerd and you need strict guarantees about what you emit.
Umm, okay, but guess what, it's possible to strictly define that the "right" answer is not an atom or set of atoms but a probability distribution of atomic terms.
Forget the One True Atomic Answer. What's the One True Distribution? :)
Motwani and Raghavan get to game theory in chapter two, but it seems they only wanted to use zir to derive Yao's Minimax. Hmmph.
To be more specific, what kind of algorithm would want to output a distribution? Rock, paper, scissors is an easy guess, but The Answer to any (non-trivial) balls and bin problems isn't really just a cardinality, a counting, but an underlying distribution.
Random walks are also an easy guess (Random California Surfer anyone?), which include Markov Chain abstractions and their applications such as PageRank.
Okee dokee, you say, but IANAT! What have randomized output distributions done for me today?
[Game theory shuffles to the side.] Let's talk engineering. Any experienced engineer worth her salt knows that you have to think about input distributions. What if someone sends me bad input? What if an orcish horde gets hungry and starts to bang on my door with some unevenly spread distribution over time?
Then you do your analysis and develop a component that has a deterministic output, a single output. It's correct, you say.
Fine, but your adviser comes along and says, [your name], done already? why don't you integrate your component into our beta system?
No, not Riemann integration (sorry Riemann), but integration of your lil component as part of a larger whole. Guess what, somebody is going to use your output as their input. What a concept!
Cool, you say. The enginerds and PMs stay up late and much code is written. Almost as much deleted. Finally, it works!
Non-pointy Hair Boss comes along though, as says, team, good work, but we really need the system to adapt to our userbase. It takes you some time to figure out what "user" means, but the enginerds go away and have long boring meetings about the difference between a null pointer and a pointer to null, and the philosophy of the URI as a global pointer in some universal matrix.
This time, though, the users have figured out to talk back. Non-pointy Hair Boss introduces the (non-EE) enginerds to a thing called feedback. You see, the system can answer the user's queries and can rank things and play tetris too, but the user takes your output, munches it like a non-creamy peanut, and (gasp) uses that knowledge to drive input into your system.
The non-dull enginerds are angry! How dare you introduce a feedback loop into our system. It's perfect already, the users are broken. We know best. (The CEO agrees secretly but says so publicly as he doesn't know how to install a filter on his verbal I/O loop.)
The enginerds go back to their one-dimensional recursive bisections (which they pretend can put a sock in the curse of dimensionality), their lovely as a B-tree's knees, and hold midnight vigils to destroy any cycles in their Architecture.
But guess what, any real system has cycles, feedback. A tree is not enough! You need a web.
(Enginerds in the audience here nod, while some physicists turned googlers hack Python, not really thinking too hard about how "there's only one way to do it" can be thought of as "there's only one path to any solution" which implies that your solution space is well approximated by a tree, as trees can be equivalently defined (graph theoretically) as a connected acyclic graph, or more simply, a graph with only /one/ path between any two vertices (!). Rubyists in the audience cheer, please :)
A web? Can't I just form a minimum spanning tree (with you as the Emperor's new Root) and print pretty pictures of the Internet and stick colorful pushpins in said pictures, amusingly tagged with "I was here"?
[No comment.]
Let's jump back now (a dirty cycle) to what we talked about earlier in this essay (the horrors of self-reference!). Good old quicksort. Surely, your dear friend Hoare sort won't let you down when it comes to your fancy pants k-d (still intrinsically 1-D, girl, it's the embedding that's k-d)
B's knees tree. The one true Total Order (Treebeard's Treebase of Knowledge).
Surely surely, there are no cycles in something as simple as a sort, you mutter.
Oh really?
Let's take perhaps the most often seen set of sorted results on the interweb. Hint: if you google for it, you're looking at the answer.
Yes, Sergey and Larry's ol Googol-type thingy. Step right up, type in your keywords and get a sorted list of results, with the most relevant results at the top!
Hurray, the problem is solved, however they did it. Ain't no cycles where I'm from.
But wait there's more. Deterministic self-interest comes into the picture and real money passes hands. Corporations rise and fall with their PageRank. Advertisers bid non-Monopoly money on slots and Googoo-type companies shell out similar kinds of currency to well-trafficked sites (someSpace let's say). Little guys run around unsure of what to do, click fraud abounds, comment spam seems to copulate (reproduce) you up the wall wherever you go, and armies of Engine Optimizers fight like little boys for the alpha spot, the coveted 2-click head-of-the-Pareto-like-distribution you're-the-dog-now top of the hot list.
You're it! You're the first search result returned. At least for a while. You get the primo(geniture) type privilege, the deterministic winner-take-all-ity, 80% of "the clicky cut".
Well, but what about number two? Do you just poop on him as a puppet dog would strongly suggest? (Probably.)
Let's formalize this a bit. No page, no search engine is an island. What comes out, must come back in, like love, garbage, tide, and violence.
Let our input R be the discrete distribution of relevance (determined by some search engine G) over the web for a given keyword search. Let us model the distribution of the abstract transfer function T which takes as input R (relevance) and U (our collective user base), and has a kind of resource fan-out distribution (the wealth of everybody else).
Now, for a given keyword search, there's no one true R, no one optimal relevance function. Why? People are different. Language is messy. The world changes. We change and are changed along the way. When I say tomato you say bless you, and we have no idea what we're talking about at all.
Confused? Let's simplify the problem. Instead of considering the discrete distribution of relevance over a set of nodes on the web, let's just consider a total ordering, a deterministic ranking if you will. After all, most of us don't know how G (the Googoo search engine let's say) is implemented, whether by flying monkeys or bonobos that prefer public transportation. G just gives us back an ordered, ranked, list of results.
Let's simplify the transfer function T as well. Let's just think in terms of play money, we'll call them Gees. First, there were electrons, and it was good. Then stuff happened (thanks Tim)... and the web was born and grew up quickly. One day, a polygot fish comes along and, for a single keyword search (Britney Spears of course), distributes mad Gees amongst the web pages which feature Britney prominently, and Spearsurfers (a modern form of the non-random surfer) were also given mad Gees to give out.
The Britney nodes are happy. They have their Gees and every so often, Spearsurfers visit them with some probability (Tp, determined by the Googoo search engine's rankings), and pay the Britneys with a couple Gees. Wow.
Cool, top ranked Britneys tend to get visited alot, and the Spearsurfers leave a couple Gees at their feet along the way.
Did you notice what happened to the Best of the Britneys? They're taking in hella Gees. They know they're the alpha click and that justifies their primacy and wealth.
That makes sense for the short term, but what about the long term? Let's zoom in and consider the top two Britneys, one called LuckyB and the other called BabyB (a.k.a. HitMe). They were almost identical twins, you see, born right after one another. LuckyB was born first, of course, and happened to be a little lighter (ahem, thinner) too. Ze was also exposed to different pre-, peri-, and post- natal hormone levels too (along with some host of epigenetic factors).
More simply, LuckyB hit the micro-jackpot. She is 3% smarter, 1+sqrt(5)% more symmetrical (and better at dancing), 6% thinner, 5% more extroverted, with a 2.4% better sense of style, direction, and the amazing ability to predict the water level of any cylindrical cup of finite extent, even under a rotation group.
Who do you think is going to win the Britney clicklist contest? Yes, that's right, LuckyB. Not only that, but if people come at their conclusions "independently" -- that is, they notice that LuckyB is a wee bit prettier, subconsciously or not, and give him Gees (Gee!) most of the time.
Rolling back, how does this affect our thought experiment? LuckyB and AlmostAsLuckyB were pretty similar, but LuckyB gets placed first most of the time, and 80% of the winnings go to her (yes, my pronoun use is as designed). Whoa batman, talk about unstable eigensystems!
What you say? Someone set us up this way? Best is best and second isn't. Every single time. That's the One True Acyclic Way. Nothing you can do but Reaganomics and/or FreakAndGeekanomics.
Here is where 2% of the audience says, hey, weren't you just talking about the evils of the deterministic PSPACE hierarchy the other day? And earlier in this entry, you wrote about the usefulness of posing problems that have probability distributions as outputs?
Why yes, Jeff, here's a sliceofpizza for you, even if your neighbors still think There Ain't No Such Thing As A Randomized Lunch.
Let's think a bit more about this, and reminisce about someone's first class in computer science, where the two things they learned were eval, bubblesort, and the recursion fairy. But let's stick to sorting, but we'll talk about it as ranking instead, to make it a little less confusing. (Given a list of integers, one possible ranking is the ordered list of integers sorted in ascending order.)
What does it mean to think about a distribution of possible rankings? (Yea, yea, I ought to talk about a probability distribution function where each distinct ranking yada yada, IANAT, etc.)
It turns out (according to me, haha, at least) that one seemingly natural way to think about a discrete distribution function is to consider the base case and generalize. Given two different objects, with some relevance score, how should they be compared? If the object with the greater relevance "wins" all the time, then the classical spaceship operator always returns what rubyists from the twentieth century think it should, no matter how much greater one object is compared to another.
Code please.
Nothing special. We have an array of two elements, and we return a ranking as defined by the standard 20th century spaceship operator. ranking[-1] corresponds to the 'most relevant' object (priority, really), and ranking[-2] is the second most relevant. (The index -1 here refers to the last element in the array. Does your language support this? If not, plz try another :)
Looks okay. It might have taken over a decade to actually implement a mostly-correct quick Hoare-ish version of the sort back in the day, and late 20th century implementations of it probably suffered overflow when they added two indices and divided by two to get the average, but hey, unless your username is djb or dek, your code most likely has bugs in it.
Trackback to deterministic One True ranking schemes [todo: implement a better system for referring back to previous paragraphs and subtexts]. We kind of have a hand-wavey (hi mom! *waves*. mom starts criticizing my experimental design once more. d'oh) way of proposing a simple model for cybernetic stability (thanks to the original cyberpeeps) and applying some intuitive eigenanalysis over a large number of trials, and we saw that the 20th century spaceship operator worked really well in the small scale of a single trial, but may just fail to grow up as our userbase and graph complexity grow enormously.
Is there really an alternative? Maybe. When I went to see Prabhakar talk, he spoke about some non-random auction pricing scheme for keywords. It was early morning (I just got up and missed the first part of his talk) but on his first or second slide I said to myself, heyy, that's not really fair. Where's the social justice?!
I scribbled furiously and whispered to Pat (which I think annoyed the person in front of me during another talk) that non-randomness doesn't make much sense, and that deterministic hierarchies should go screw themselves (not that I said screw). I told ArtO about this and he told me I should prove these things rather than rambling, as you may have noticed I like to do in as many words as my fingers can muster down, as so here we are, me, Not A Theorist, trying to figure out how to prove the algorithm which I had yet to write.
How shall we write it? I realized that we could consider the base case (yes, that's the spaceship operator here) of two objects with (relative? let's say objective for now) relevance scores. Now, an object whose relevance score is twice as high ought to show up twice as much as the other guy (in this base case) in the alpha spot of index -1 (or 0, depending on which way your sorting swings).
After some coursework in Ruby-based spaceship operators and randomized combinatorial algorithms, we have the following code, which I wrote last night (after I told P about my plan to re-write the web).
The 20th century spaceship operator, (x <=> y), if you haven't looked it up yet, returns a single integer in the set {-1, 0, +1}.
My I_can't_tell_it's_not_Russian 21st century space operator introduces randomness into the picture. (Strictly speaking, rand might return the same float twice and so on, but we won't account for such seemingly astro-small bias here. Something something general position of randomness.)
The offending block in question:
What does it really mean? My first guess is to just think of it with a randomized BST lens. In other words, quicksort. Assume that this sort picks the pivot randomly (it may or may not in your version of Ruby, depending on if you're a time traveler from the future or the past), then elements are partitioned quasi-randomly. Quasi- in that we don't flip an unbiased coin to figure out less than or greater (equal), we flip a biased coin. That's the second multiplicative term in this double spaceship operator, which is biased towards the greater element, in some but-is-it-golden? appropriately relative proportion (yay!).
Think about a simple case, relevance or priority scores of 2 and 1, and work through this simple case in your head. It's good for you :)
As I said before, it may be that we don't need a double spaceship operator, but multiplying two terms gives us an intuitive way of thinking about flipping a biased coin which in turn may or may not swap two elements, according to the probabilities defined by their relative priorities. Make sense? Probably or probably not ^_^.
What does this really gives us? I don't really know, but I have some ideas. Broadly, I think it makes sense for algorithms to start thinking about probability distributions in their outputs as much as they think about the distribution of their inputs. Randomness gives us a very big and bad-ass coin which we can use to flip out of deterministically bad situations. In other words, it's a big hammer. Use it wisely.
Distributions of input parameters and distributions of output parameters, I would imagine, are critical once you get to a scale where a tree is not enough (?), where you need feedback and a cybernetic cycle. In other words, you grow up and realize the whole wide world's nothing but a web.
(Okay, so I happen to think you can use my sampling scheme, triple-u sampling I've been calling it, to run auctions with randomized distributions in their inputs /and/ outputs, to build a better search engine, hack on college admissions, think critically about racism, sexism, and other forms of statistical * ( prejudice plus power ), nicely schedule your todo list to get things done, engineer a better Internet, and fight for social justice. I haven't done any of these things yet, I think, but perhaps I and random you will one future, past, and present day. Want to help? You might be able to email me at my last name dot com ;)
~L dot Wu
But, what about output perturbation, and output randomization?
(The original title of this blog entry was "perturbations in your milk, cereal, and I/O" but my mindform took another state before I published it.)
That is, the algorithms in Motwani and Raghavan seem to consider only problems that have a single answer (or a set of equivalent, optimal answers).
They describe a Las Vegas algorithm as one that "always gives the correct solution" but the running time varies (for example, randomized quicksort).
In contrast, they note, a Monte Carlo algorithm "may sometimes produce a solution that is incorrect," but one can "bound the probability of such an incorrect solution." For example, pseudoprimality testing can be used to return an integer which is probably prime.
Fine, but what if the solution is not a permutation or an integer, but a probability distribution of possible answers (some of which are 'correct' and some less so :)?
That's deeply perturbed you say! You're an enginerd and you need strict guarantees about what you emit.
Umm, okay, but guess what, it's possible to strictly define that the "right" answer is not an atom or set of atoms but a probability distribution of atomic terms.
Forget the One True Atomic Answer. What's the One True Distribution? :)
Motwani and Raghavan get to game theory in chapter two, but it seems they only wanted to use zir to derive Yao's Minimax. Hmmph.
To be more specific, what kind of algorithm would want to output a distribution? Rock, paper, scissors is an easy guess, but The Answer to any (non-trivial) balls and bin problems isn't really just a cardinality, a counting, but an underlying distribution.
Random walks are also an easy guess (Random California Surfer anyone?), which include Markov Chain abstractions and their applications such as PageRank.
Okee dokee, you say, but IANAT! What have randomized output distributions done for me today?
[Game theory shuffles to the side.] Let's talk engineering. Any experienced engineer worth her salt knows that you have to think about input distributions. What if someone sends me bad input? What if an orcish horde gets hungry and starts to bang on my door with some unevenly spread distribution over time?
Then you do your analysis and develop a component that has a deterministic output, a single output. It's correct, you say.
Fine, but your adviser comes along and says, [your name], done already? why don't you integrate your component into our beta system?
No, not Riemann integration (sorry Riemann), but integration of your lil component as part of a larger whole. Guess what, somebody is going to use your output as their input. What a concept!
Cool, you say. The enginerds and PMs stay up late and much code is written. Almost as much deleted. Finally, it works!
Non-pointy Hair Boss comes along though, as says, team, good work, but we really need the system to adapt to our userbase. It takes you some time to figure out what "user" means, but the enginerds go away and have long boring meetings about the difference between a null pointer and a pointer to null, and the philosophy of the URI as a global pointer in some universal matrix.
This time, though, the users have figured out to talk back. Non-pointy Hair Boss introduces the (non-EE) enginerds to a thing called feedback. You see, the system can answer the user's queries and can rank things and play tetris too, but the user takes your output, munches it like a non-creamy peanut, and (gasp) uses that knowledge to drive input into your system.
The non-dull enginerds are angry! How dare you introduce a feedback loop into our system. It's perfect already, the users are broken. We know best. (The CEO agrees secretly but says so publicly as he doesn't know how to install a filter on his verbal I/O loop.)
The enginerds go back to their one-dimensional recursive bisections (which they pretend can put a sock in the curse of dimensionality), their lovely as a B-tree's knees, and hold midnight vigils to destroy any cycles in their Architecture.
But guess what, any real system has cycles, feedback. A tree is not enough! You need a web.
(Enginerds in the audience here nod, while some physicists turned googlers hack Python, not really thinking too hard about how "there's only one way to do it" can be thought of as "there's only one path to any solution" which implies that your solution space is well approximated by a tree, as trees can be equivalently defined (graph theoretically) as a connected acyclic graph, or more simply, a graph with only /one/ path between any two vertices (!). Rubyists in the audience cheer, please :)
A web? Can't I just form a minimum spanning tree (with you as the Emperor's new Root) and print pretty pictures of the Internet and stick colorful pushpins in said pictures, amusingly tagged with "I was here"?
[No comment.]
Let's jump back now (a dirty cycle) to what we talked about earlier in this essay (the horrors of self-reference!). Good old quicksort. Surely, your dear friend Hoare sort won't let you down when it comes to your fancy pants k-d (still intrinsically 1-D, girl, it's the embedding that's k-d)
B's knees tree. The one true Total Order (Treebeard's Treebase of Knowledge).
Surely surely, there are no cycles in something as simple as a sort, you mutter.
Oh really?
Let's take perhaps the most often seen set of sorted results on the interweb. Hint: if you google for it, you're looking at the answer.
Yes, Sergey and Larry's ol Googol-type thingy. Step right up, type in your keywords and get a sorted list of results, with the most relevant results at the top!
Hurray, the problem is solved, however they did it. Ain't no cycles where I'm from.
But wait there's more. Deterministic self-interest comes into the picture and real money passes hands. Corporations rise and fall with their PageRank. Advertisers bid non-Monopoly money on slots and Googoo-type companies shell out similar kinds of currency to well-trafficked sites (someSpace let's say). Little guys run around unsure of what to do, click fraud abounds, comment spam seems to copulate (reproduce) you up the wall wherever you go, and armies of Engine Optimizers fight like little boys for the alpha spot, the coveted 2-click head-of-the-Pareto-like-distribution you're-the-dog-now top of the hot list.
You're it! You're the first search result returned. At least for a while. You get the primo(geniture) type privilege, the deterministic winner-take-all-ity, 80% of "the clicky cut".
Well, but what about number two? Do you just poop on him as a puppet dog would strongly suggest? (Probably.)
Let's formalize this a bit. No page, no search engine is an island. What comes out, must come back in, like love, garbage, tide, and violence.
Let our input R be the discrete distribution of relevance (determined by some search engine G) over the web for a given keyword search. Let us model the distribution of the abstract transfer function T which takes as input R (relevance) and U (our collective user base), and has a kind of resource fan-out distribution (the wealth of everybody else).
Now, for a given keyword search, there's no one true R, no one optimal relevance function. Why? People are different. Language is messy. The world changes. We change and are changed along the way. When I say tomato you say bless you, and we have no idea what we're talking about at all.
Confused? Let's simplify the problem. Instead of considering the discrete distribution of relevance over a set of nodes on the web, let's just consider a total ordering, a deterministic ranking if you will. After all, most of us don't know how G (the Googoo search engine let's say) is implemented, whether by flying monkeys or bonobos that prefer public transportation. G just gives us back an ordered, ranked, list of results.
Let's simplify the transfer function T as well. Let's just think in terms of play money, we'll call them Gees. First, there were electrons, and it was good. Then stuff happened (thanks Tim)... and the web was born and grew up quickly. One day, a polygot fish comes along and, for a single keyword search (Britney Spears of course), distributes mad Gees amongst the web pages which feature Britney prominently, and Spearsurfers (a modern form of the non-random surfer) were also given mad Gees to give out.
The Britney nodes are happy. They have their Gees and every so often, Spearsurfers visit them with some probability (Tp, determined by the Googoo search engine's rankings), and pay the Britneys with a couple Gees. Wow.
Cool, top ranked Britneys tend to get visited alot, and the Spearsurfers leave a couple Gees at their feet along the way.
Did you notice what happened to the Best of the Britneys? They're taking in hella Gees. They know they're the alpha click and that justifies their primacy and wealth.
That makes sense for the short term, but what about the long term? Let's zoom in and consider the top two Britneys, one called LuckyB and the other called BabyB (a.k.a. HitMe). They were almost identical twins, you see, born right after one another. LuckyB was born first, of course, and happened to be a little lighter (ahem, thinner) too. Ze was also exposed to different pre-, peri-, and post- natal hormone levels too (along with some host of epigenetic factors).
More simply, LuckyB hit the micro-jackpot. She is 3% smarter, 1+sqrt(5)% more symmetrical (and better at dancing), 6% thinner, 5% more extroverted, with a 2.4% better sense of style, direction, and the amazing ability to predict the water level of any cylindrical cup of finite extent, even under a rotation group.
Who do you think is going to win the Britney clicklist contest? Yes, that's right, LuckyB. Not only that, but if people come at their conclusions "independently" -- that is, they notice that LuckyB is a wee bit prettier, subconsciously or not, and give him Gees (Gee!) most of the time.
Rolling back, how does this affect our thought experiment? LuckyB and AlmostAsLuckyB were pretty similar, but LuckyB gets placed first most of the time, and 80% of the winnings go to her (yes, my pronoun use is as designed). Whoa batman, talk about unstable eigensystems!
What you say? Someone set us up this way? Best is best and second isn't. Every single time. That's the One True Acyclic Way. Nothing you can do but Reaganomics and/or FreakAndGeekanomics.
Here is where 2% of the audience says, hey, weren't you just talking about the evils of the deterministic PSPACE hierarchy the other day? And earlier in this entry, you wrote about the usefulness of posing problems that have probability distributions as outputs?
Why yes, Jeff, here's a sliceofpizza for you, even if your neighbors still think There Ain't No Such Thing As A Randomized Lunch.
Let's think a bit more about this, and reminisce about someone's first class in computer science, where the two things they learned were eval, bubblesort, and the recursion fairy. But let's stick to sorting, but we'll talk about it as ranking instead, to make it a little less confusing. (Given a list of integers, one possible ranking is the ordered list of integers sorted in ascending order.)
What does it mean to think about a distribution of possible rankings? (Yea, yea, I ought to talk about a probability distribution function where each distinct ranking yada yada, IANAT, etc.)
It turns out (according to me, haha, at least) that one seemingly natural way to think about a discrete distribution function is to consider the base case and generalize. Given two different objects, with some relevance score, how should they be compared? If the object with the greater relevance "wins" all the time, then the classical spaceship operator always returns what rubyists from the twentieth century think it should, no matter how much greater one object is compared to another.
Code please.
#!/usr/bin/env ruby
prios = [2.7, 1.4] # relevance scores: a higher score means 'more relevant'
ranking = prios.sort { |x, y| x <=> y } # equivalent to prios.sort
Nothing special. We have an array of two elements, and we return a ranking as defined by the standard 20th century spaceship operator. ranking[-1] corresponds to the 'most relevant' object (priority, really), and ranking[-2] is the second most relevant. (The index -1 here refers to the last element in the array. Does your language support this? If not, plz try another :)
Looks okay. It might have taken over a decade to actually implement a mostly-correct quick Hoare-ish version of the sort back in the day, and late 20th century implementations of it probably suffered overflow when they added two indices and divided by two to get the average, but hey, unless your username is djb or dek, your code most likely has bugs in it.
Trackback to deterministic One True ranking schemes [todo: implement a better system for referring back to previous paragraphs and subtexts]. We kind of have a hand-wavey (hi mom! *waves*. mom starts criticizing my experimental design once more. d'oh) way of proposing a simple model for cybernetic stability (thanks to the original cyberpeeps) and applying some intuitive eigenanalysis over a large number of trials, and we saw that the 20th century spaceship operator worked really well in the small scale of a single trial, but may just fail to grow up as our userbase and graph complexity grow enormously.
Is there really an alternative? Maybe. When I went to see Prabhakar talk, he spoke about some non-random auction pricing scheme for keywords. It was early morning (I just got up and missed the first part of his talk) but on his first or second slide I said to myself, heyy, that's not really fair. Where's the social justice?!
I scribbled furiously and whispered to Pat (which I think annoyed the person in front of me during another talk) that non-randomness doesn't make much sense, and that deterministic hierarchies should go screw themselves (not that I said screw). I told ArtO about this and he told me I should prove these things rather than rambling, as you may have noticed I like to do in as many words as my fingers can muster down, as so here we are, me, Not A Theorist, trying to figure out how to prove the algorithm which I had yet to write.
How shall we write it? I realized that we could consider the base case (yes, that's the spaceship operator here) of two objects with (relative? let's say objective for now) relevance scores. Now, an object whose relevance score is twice as high ought to show up twice as much as the other guy (in this base case) in the alpha spot of index -1 (or 0, depending on which way your sorting swings).
After some coursework in Ruby-based spaceship operators and randomized combinatorial algorithms, we have the following code, which I wrote last night (after I told P about my plan to re-write the web).
Yes, girls and boys, that's a double spaceship operator. I figure you could write it in a single leap, but this was my first pass, and it makes sense to me intuitively.def triple_u_sort(arr)
arr.sort { |x,y| (x <=> y) * (rand <=> [x,y].max/(x+y)) }
end
The 20th century spaceship operator, (x <=> y), if you haven't looked it up yet, returns a single integer in the set {-1, 0, +1}.
My I_can't_tell_it's_not_Russian 21st century space operator introduces randomness into the picture. (Strictly speaking, rand might return the same float twice and so on, but we won't account for such seemingly astro-small bias here. Something something general position of randomness.)
The offending block in question:
Isn't it cute? How modern, sleek. How wonderfully random.{ |x,y| (x <=> y) * (rand <=> [x,y].max / (x+y)) }
What does it really mean? My first guess is to just think of it with a randomized BST lens. In other words, quicksort. Assume that this sort picks the pivot randomly (it may or may not in your version of Ruby, depending on if you're a time traveler from the future or the past), then elements are partitioned quasi-randomly. Quasi- in that we don't flip an unbiased coin to figure out less than or greater (equal), we flip a biased coin. That's the second multiplicative term in this double spaceship operator, which is biased towards the greater element, in some but-is-it-golden? appropriately relative proportion (yay!).
Think about a simple case, relevance or priority scores of 2 and 1, and work through this simple case in your head. It's good for you :)
As I said before, it may be that we don't need a double spaceship operator, but multiplying two terms gives us an intuitive way of thinking about flipping a biased coin which in turn may or may not swap two elements, according to the probabilities defined by their relative priorities. Make sense? Probably or probably not ^_^.
What does this really gives us? I don't really know, but I have some ideas. Broadly, I think it makes sense for algorithms to start thinking about probability distributions in their outputs as much as they think about the distribution of their inputs. Randomness gives us a very big and bad-ass coin which we can use to flip out of deterministically bad situations. In other words, it's a big hammer. Use it wisely.
Distributions of input parameters and distributions of output parameters, I would imagine, are critical once you get to a scale where a tree is not enough (?), where you need feedback and a cybernetic cycle. In other words, you grow up and realize the whole wide world's nothing but a web.
(Okay, so I happen to think you can use my sampling scheme, triple-u sampling I've been calling it, to run auctions with randomized distributions in their inputs /and/ outputs, to build a better search engine, hack on college admissions, think critically about racism, sexism, and other forms of statistical * ( prejudice plus power ), nicely schedule your todo list to get things done, engineer a better Internet, and fight for social justice. I haven't done any of these things yet, I think, but perhaps I and random you will one future, past, and present day. Want to help? You might be able to email me at my last name dot com ;)
~L dot Wu
posted by L. Wu @ 6:37 AM
0 Comments:
Post a Comment
<< Home