Hacker News new | past | comments | ask | show | jobs | submit login
Customers who liked this Recommendation Engine may also like its Dequantization (scottaaronson.com)
87 points by beefman on July 12, 2018 | hide | past | favorite | 30 comments

Scott: Your student is brilliant. Kudos to you for not insisting on sharing authorship on the paper, like some academic advisors in your position would do.

Thanks! In theoretical computer science as a whole, authorship is only for those who made a direct intellectual contribution. It’s one of the things I like best about the culture of our field.

A fantastic result, and a nice story behind it. Per the abstract of Tang's paper, the current best results are linear in m and n.

Prof Aaronson said the best upper bound they have so far is O(log(n)^33)... to give that more meaning, O(log(n)^33) grows faster than O(n) until about n = 10^15, so "not practical" is a bit of an understatement!

I still get why this is an interesting result, though. And if Scott thinks that lower bounds are achievable he is probably right.

10^15 is not that big. We could construct and compute on sparse matrices that large today.

I'm glad to know where the crossover point is, and yeah, hearing that it's around 10^15 tells me it's just a few orders of magnitude of improvement away from being a practical machine learning tool.

How is it possible for an 18 year old to be so accomplished? Insane.

Apparently he is the son of a bioengineering professor and was able to work in his father's nanotechnology lab while growing up. He also started taking college courses at a local university when he was 12 (UT Arlington) before going to UT Austin. http://www.uta.edu/utamagazine/archive-issues/2010-13/2012/1...

Brings to mind a recent quote that goes something like "Many of our brightest scientists are trying to figure out how to get you to buy one more thing or stay on a website a few seconds longer, instead of spending their time and genius tackling pressing issues desperate for more attention."

Meh, some problems are theoretically very interesting, but presently have limited practical applications. Everyone has to find means to survive. For some people those theoretical problems, that understanding, are one of very few things that keep oneself whole.

That fine line between genius and insanity, it really does exist. I'm not saying that because I think I'm a genius. Just, for some people, the only things that 'ground' us are things that are abstract (I say this with great awareness of the irony).

Trying to make the pieces fit with the world, that's sometimes hard. You can throw the whole understanding you've built in the garbage, but then you lose yourself, and, I dunno. I don't think it's desperation for attention. I think it's a compulsion for things to make sense, because, a chaotic world. Some things just have to make sense.

You don't subscribe to the notion that there might be a market failure here? There is marketmaking, then there is pro-consumption manipulation, how much is each in adtech is debatable, but it is a waste of investment for advanced degree holders to spend time manipulating people.

Yea, I agree with that too, I can't say I fully like recommendation engines, as someone who has always veered on the side of 'independent artist' in terms of 'preference philosophy' I find them somewhat pointless, but whatever works.

I do like them when they actually yield a correct product that is coming from informed consumers. I waste less money that way as a consumer. I'm talking mainly about books and art supplies here, that's pretty much what I've used them for. Makeup too, but that one, lots of money wasted because the beauty industry is it's own insane beast of navigating trends.

I don't like them when they are manipulated by additional entities to dilute the quality of recommendation, and I think honestly this was the reason for their initial creation. But, open system, many recommendation engines work great so long as the consumer base follows the rules. The more lucrative it gets, the more layers of reasoning you need (to compete against bad actors diluting the data quality). The more layers, the greater the need for computational speed.

Worthy problem, worthless problem, I don't really know. I know the people working on this stuff aren't necessarily the ones inventing the problems. It's more that the original intent has been corrupted, and that makes some people unhappy. So, people work on fixing the problems.

I think you are really missing the point here. "How", "why", and especially "where" quantum computers outperform classical computers is a question of foundational importance in the field of computational complexity, and that field itself is fairly close to the foundations of logic and math.

The practical implications of this algorithm are just a side note for many of the people working on this research.

Also "whether" remains an open question...

Indeed! For all the great things that would come from practical quantum computing, the less probable outcome is way more exciting: If it turns out that we were completely wrong and quantum computers are not more powerful than classical ones, then explaining how that is possible (it really does not seem plausible) would be a great scientific revolution.

Better movie recommendations may not be as visibly worthy as building sewers, but they are genuinely life-enhancing. As the amount of cultural works produced grows exponentially and human curators remain only human, this problem grows ever more important.

I used to believe this. I even created a recommendation algorithm / company that got acquired some years ago. I'm less sure today. Just as I do not think that high frequency trading firms are really providing value to society, I neither think that squeezing out a little bit more of a recommendation provides all that much more value either. We watch enough TV, and the best music wasn't brought to me via algorithm. I never would have discovered Emancipator via algorithm, I was too stuck in my own music bubble. Human interaction and human recommendation is nicer. I still listen to the recommended lists, but they rarely compete with simply hanging out with cool friends and seeing what they're listening to.

> We watch enough TV

Agreed, which makes better curation all the more important - if there was enough time to watch more than a tiny fraction of what's out there then recommendation would matter less.

> I still listen to the recommended lists, but they rarely compete with simply hanging out with cool friends and seeing what they're listening to.

Doesn't that very fact prove that there's plenty of room for improvement in recommended lists?

> Doesn't that very fact prove that there's plenty of room for improvement in recommended lists?

No, this does not automatically follow, there could be other situations that provide the same given but don't lead to that conclusion. For example, the value of lists provided by friends could be a purely emotional one: The items on the list seem better because your friends love them, and you like them more because you can discuss them later.

Yeah. And it's also a bit like trying to read signal out of noise. Someone into a certain genre may grow into a different one for all sorts of reasons. I've been increasingly thinking that a true recommender system would require some sort of consciousness. Plus a recommendation from a friend usually comes with some sort of explanation of why its good and can be useful to push past reasons to dismiss it. For example, I hate most cop shows but I love The Wire. It took someone trusted saying "it's more of a social commentary on the dynamics of a crumbling American city" for me to really give it a shot.

> I do not think that high frequency trading firms are really providing value to society

Define "value to society"

I will start by saying that HFT firms employ people, gives them jobs, purpose, and most importantly, a pay check. This in turn generates tax revenue for any government and society. Your turn.

> HFT firms employ people, gives them jobs, purpose, and most importantly, a pay check. This in turn generates tax revenue for any government and society.

That's putting the cart before the horse. People get a sense of purpose and a paycheck from a job because jobs are generally providing value to society - the money ultimately comes from people who get value from what they do paying it. If the money is coming from a government regulation rather than because people actually want to buy what they're selling, it's a make-work scheme, not a business.

The sub-penny rule is, essentially, a tax on investors that is then handed to the winners of a mostly-meaningless competition. You could equally take the same tax on investors and hand the money to whoever dug the longest ditch (or whatever) and that would "employ people, gives them jobs, purpose, and most importantly, a pay check", but that wouldn't be contributing anything valuable to society either.

I don't have any particular antipathy towards HFT, so I will just note that organized crime does all of the above (though it notoriously under-reports its economic activity, and consequently underpays taxes on it.)

Extracting value is not at all the same as contributing value. Contributed value cannot be measured by people's bank accounts.

That might be one of the many riffs off Allan Ginsberg's opening line of Howl:

"I saw the best minds of my generation destroyed by madness, starving hysterical naked,"


My most memorable/saddening adaption of that is from an early Facebook employee:

"The best minds of my generation are thinking about how to make people click ads,"

I'd like to point out that recommender algorithms are also used in biology/biomedical research.

In this case, both.

When your economic system incenctivises shipping the biggest amount of crap you possibly can, this is what you get. People happily going to extreme efforts to optimise for this target only, even if the side effects are what you mentioned, plus pollution, plus unhappiness from constant bombardment by hyperoptimised ads, plus depletion of resources, plus...

You are severely misrepresenting what this work is about. As I mentioned in a sibling comment, this work is exciting for purely intellectual reasons. The applications to Amazon's business model is a side note.

I concur, its difficult to get funding for this type of research without having a tangible way to benefit your potential benefactors.

From personal experience, I've had to work on numerous applications that I didn't really care for but provided me with the funding to actually pursue my research.

On another note, the subject matter Ewin & Professor Aaronson are talking about is pretty complex even for the average CompSci person; I'd wager if there was no mention of a corporate entity or real-world example this article would be met with so many questions about its applications to those same real-world problems.

Rant concluded :P

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact