3 ms·

I just want to mention that the "recommendation systems" angle is quite unimportant here. This is a result in complexity theory, a resolution of the question "w

I just want to mention that the "recommendation systems" angle is quite unimportant here. This is a result in complexity theory, a resolution of the question "whether you actually need a quantum computer to sample the rows of a partially-specified low-rank matrix in polylogarithmic time" (as Scott Aaronson puts it [1]). While this problem does occur in matrix factorization based recommenders, there are a lot of solutions for it without quantum computers that perform well, and it's far from being the one method for recommendation. [1] https://www.scottaaronson.com/blog/?p=3880 https://www.scottaaronson.com/blog/?p=3880

vanderZwan 8y ago
> "whether you actually need a quantum computer to sample the rows of a partially-specified low-rank matrix in polylogarithmic time" Could that be used in clustering algorithms in BioInformatics? EDIT: Sorry, Aaronson's writing is just too funny not to put that quote in full context: > On the Hacker News thread, some commenters are lamenting that such a brilliant mind as Ewin’s would spend its time figuring out how to entice consumers to buy even more products that they don’t need. I confess that that’s an angle that hadn’t even occurred to me: I simply thought that it was a beautiful question whether you actually need a quantum computer to sample the rows of a partially-specified low-rank matrix in polylogarithmic time, and if the application to recommendation systems helped to motivate that question, then so much the better. Now, though, I feel compelled to point out that, in addition to the potentially lucrative application to Amazon and Netflix, research on low-rank matrix sampling algorithms might someday find many other, more economically worthless applications as well.
- jtbayly 8y ago
  "research on low-rank matrix sampling algorithms might someday find many other, more economically worthless applications as well." I'm not sure whether this is a typo, and he means to say that there might be more economically worthwhile applications, or whether he's trolling the people complaining that this is useless by pointing out that there are real economic benefits to it right now.
  - gbacon 8y ago
    It is not a typo but a jab at wannabe elitists who are sneering at Ewin’s work because of its ready applicability to Amazon and Netflix recommendations — as though the discovery would be more worthwhile if it had no economically valuable uses.
  - btilly 8y ago
    Neither. He's trolling the people who regret that the result of this research is manipulating people. By pointing out that there is a real potential for applications that they object to less.
    - reitanqild 8y ago
      And this is an example of trolling done right and for the good of (mostly?) everyone :-)
    - rcoveson 8y ago
      It's a very broad definition of "manipulating people" that includes recommendation algorithms. The problem, as stated, seems to call for an implementation of a perfectly benign strategy for recommending content. Clustering users by their ratings of various titles is the kind of thing any hobbyist statistician might do to help their friends find movies they like using online data sets. There are methods to use data to improve people's experiences, and sometimes corporations employ those methods.
      - btilly 8y ago
        With a slight tweak, this is also the kind of algorithm that is used to personalize disinformation campaigns for large numbers of people. As Cambridge Analytica was famously trying to do in the 2016 election. So yes, this algorithm is useful for manipulating people. And not just by using an extremely broad definition of the term.
      - dwaltrip 8y ago
        You must admit that there is a very large difference between a friend doing something for me and a corporation doing the same thing.
joe_the_user 8y ago
Looking at the paper, I think the fact that this is a recommendation algorithm is fairly important. The big thing is that broadly "the recommendation algorithm" is not some single problem in combinatorics. Rather, it a initially ill-posed problem that yields concrete problems based on simplifying assumptions. IE, sure, the FINAL, SOLVED problem is as Aaronson put it but because different researchers make different simplifying assumptions, that final problem actually hadn't studied that much - half the achievement of the paper is finding simplifying assumptions that are real world-plausible and yield tractable problems ("Obviously, without any restrictions on what T looks like, this problem is ill-posed. We make this problem tractable through the standard assumption that T is close to a matrix of small rank k (constant or logarithmic in m and n). This reflects the intuition that users tend to fall into a small number of classes based on their preferences. With this assumption, it becomes possible to infer information from subsampled data. We can determine the classes a user lies in, and use information about those classes to give a likely-to-be-good recommendation") The original quantum recommendation algorithm paper involved both a simplifying assumption about the sorts of consumers one was models and a system of sampling to get a good approximation ("The literature on theoretical recommendation systems is fairly scant, because such algorithms quickly run up against the limits of their model, despite them being somewhat far from the results seen in practice.") https://arxiv.org/pdf/1807.04271.pdf https://arxiv.org/pdf/1807.04271.pdf

vanderZwan 8y ago

> "whether you actually need a quantum computer to sample the rows of a partially-specified low-rank matrix in polylogarithmic time" Could that be used in clustering algorithms in BioInformatics? EDIT: Sorry, Aaronson's writing is just too funny not to put that quote in full context: > On the Hacker News thread, some commenters are lamenting that such a brilliant mind as Ewin’s would spend its time figuring out how to entice consumers to buy even more products that they don’t need. I confess that that’s an angle that hadn’t even occurred to me: I simply thought that it was a beautiful question whether you actually need a quantum computer to sample the rows of a partially-specified low-rank matrix in polylogarithmic time, and if the application to recommendation systems helped to motivate that question, then so much the better. Now, though, I feel compelled to point out that, in addition to the potentially lucrative application to Amazon and Netflix, research on low-rank matrix sampling algorithms might someday find many other, more economically worthless applications as well.

jtbayly 8y ago
"research on low-rank matrix sampling algorithms might someday find many other, more economically worthless applications as well." I'm not sure whether this is a typo, and he means to say that there might be more economically worthwhile applications, or whether he's trolling the people complaining that this is useless by pointing out that there are real economic benefits to it right now.
- gbacon 8y ago
  It is not a typo but a jab at wannabe elitists who are sneering at Ewin’s work because of its ready applicability to Amazon and Netflix recommendations — as though the discovery would be more worthwhile if it had no economically valuable uses.
- btilly 8y ago
  Neither. He's trolling the people who regret that the result of this research is manipulating people. By pointing out that there is a real potential for applications that they object to less.
  - reitanqild 8y ago
    And this is an example of trolling done right and for the good of (mostly?) everyone :-)
  - rcoveson 8y ago
    It's a very broad definition of "manipulating people" that includes recommendation algorithms. The problem, as stated, seems to call for an implementation of a perfectly benign strategy for recommending content. Clustering users by their ratings of various titles is the kind of thing any hobbyist statistician might do to help their friends find movies they like using online data sets. There are methods to use data to improve people's experiences, and sometimes corporations employ those methods.
    - btilly 8y ago
      With a slight tweak, this is also the kind of algorithm that is used to personalize disinformation campaigns for large numbers of people. As Cambridge Analytica was famously trying to do in the 2016 election. So yes, this algorithm is useful for manipulating people. And not just by using an extremely broad definition of the term.
    - dwaltrip 8y ago
      You must admit that there is a very large difference between a friend doing something for me and a corporation doing the same thing.

joe_the_user 8y ago

Looking at the paper, I think the fact that this is a recommendation algorithm is fairly important. The big thing is that broadly "the recommendation algorithm" is not some single problem in combinatorics. Rather, it a initially ill-posed problem that yields concrete problems based on simplifying assumptions. IE, sure, the FINAL, SOLVED problem is as Aaronson put it but because different researchers make different simplifying assumptions, that final problem actually hadn't studied that much - half the achievement of the paper is finding simplifying assumptions that are real world-plausible and yield tractable problems ("Obviously, without any restrictions on what T looks like, this problem is ill-posed. We make this problem tractable through the standard assumption that T is close to a matrix of small rank k (constant or logarithmic in m and n). This reflects the intuition that users tend to fall into a small number of classes based on their preferences. With this assumption, it becomes possible to infer information from subsampled data. We can determine the classes a user lies in, and use information about those classes to give a likely-to-be-good recommendation") The original quantum recommendation algorithm paper involved both a simplifying assumption about the sorts of consumers one was models and a system of sampling to get a good approximation ("The literature on theoretical recommendation systems is fairly scant, because such algorithms quickly run up against the limits of their model, despite them being somewhat far from the results seen in practice.") https://arxiv.org/pdf/1807.04271.pdf https://arxiv.org/pdf/1807.04271.pdf