Ask HN: How does Google test its ranking algorithm?
3 comments
There's no automatic way to determine the quality of results. If you could do that, it would be incorporated as a signal into the search algorithm itself. Fundamentally you must have a human with enough domain knowledge make the decision on which version of the code produced better results.
There's two ways you could achieve that:
a) Create a set of search queries, have humans come up with the best possible result for all of them, and test every version of the software against the golden results. Only accept changes that are a net improvement on that golden set. Possibly change the golden set every now and then.
b) Run two versions of the code on a very large number of queries. Have a human look at the results produced by both queries, and rank one of them as better. Only accept changes that are a net positive. If too many queries are changed, you can try to do some heuristic processing to only look at sufficiently major changes. (For example you'd rather spend time on cases where a result in the top 3 is replaced than one where the 9th and 10th results swap places).
When I say "change", I could mean a change in data, algorithms, or both. And I could mean evaluating a single discrete commit, or evaluating the total effect of all the changes since the last release a weeks or months ago. Or most likely both.
The benefit of the first approach is that you can completely automate the testing. But other than that, it's kind of rubbish. First, the "best" result is not a static thing over time. Second, there's no particular reason to believe that anyone can even figure out what the "best" result is. Third, it means there's a big risk you're going to be optimizing the algorithms for a specific query set. If you don't have golden results, you also don't need to have a predetermined query set but can use random data. In general my experience is that maintaining golden results is just not worth it if you have a system with code and data changes.
The problem with the second approach is that it can be incredibly expensive, both in terms of human and computing resources.
BTW, this kind of side-by-side testing can be a very powerful tool for many different kinds of problems as well. I used to work on the implementation of a programming language with millions of lines of code written in it by thousands of programmers.
But the neat part was that all of these programs were in a single repository. And what's more, we had a database of all the external environment dependencies for every single invocation of the interpreter. (So any environment variables read by a program, any command line flags passed, the exact values returned by any functions that accessed the filesystem, etc).
So we could essentially test every single change to the language implementation against the whole universe of programs ever run in the language, and compare the outputs. And then either notice that our change was buggy since it broke some program, or go and pre-emptively fix any invalid programs that had just happened to work before.
There's two ways you could achieve that:
a) Create a set of search queries, have humans come up with the best possible result for all of them, and test every version of the software against the golden results. Only accept changes that are a net improvement on that golden set. Possibly change the golden set every now and then.
b) Run two versions of the code on a very large number of queries. Have a human look at the results produced by both queries, and rank one of them as better. Only accept changes that are a net positive. If too many queries are changed, you can try to do some heuristic processing to only look at sufficiently major changes. (For example you'd rather spend time on cases where a result in the top 3 is replaced than one where the 9th and 10th results swap places).
When I say "change", I could mean a change in data, algorithms, or both. And I could mean evaluating a single discrete commit, or evaluating the total effect of all the changes since the last release a weeks or months ago. Or most likely both.
The benefit of the first approach is that you can completely automate the testing. But other than that, it's kind of rubbish. First, the "best" result is not a static thing over time. Second, there's no particular reason to believe that anyone can even figure out what the "best" result is. Third, it means there's a big risk you're going to be optimizing the algorithms for a specific query set. If you don't have golden results, you also don't need to have a predetermined query set but can use random data. In general my experience is that maintaining golden results is just not worth it if you have a system with code and data changes.
The problem with the second approach is that it can be incredibly expensive, both in terms of human and computing resources.
BTW, this kind of side-by-side testing can be a very powerful tool for many different kinds of problems as well. I used to work on the implementation of a programming language with millions of lines of code written in it by thousands of programmers.
But the neat part was that all of these programs were in a single repository. And what's more, we had a database of all the external environment dependencies for every single invocation of the interpreter. (So any environment variables read by a program, any command line flags passed, the exact values returned by any functions that accessed the filesystem, etc).
So we could essentially test every single change to the language implementation against the whole universe of programs ever run in the language, and compare the outputs. And then either notice that our change was buggy since it broke some program, or go and pre-emptively fix any invalid programs that had just happened to work before.
What a great question. It scares me every time I release a new update on an MMO that I work on with only 2,000 concurrent users, let alone changing an algorithm that affects millions of peoples financial.
I would love to hear if anyone has insight on this as well.
I would love to hear if anyone has insight on this as well.
They employ (via contractors) "search quality raters":
http://searchengineland.com/library/google/google-search-qua...
Do you have to create an algorithm ranking algorithm? For large enough systems when does that stop?