5 ms·

>"Nothing I learned in CS has an application to industry programming" is a regular complaint in discussion on education here and elsewhere. This is a good cours

>"Nothing I learned in CS has an application to industry programming" is a regular complaint in discussion on education here and elsewhere. This is a good course to point to for people who have this very limited view on CS. > Lecture 11 (Mon 5/2): Graphs as matrices and the Laplacian of a graph. Interpretations of the largest and smallest eigenvectors/eigenvalues of the Laplacian. Spectral embeddings, and an overview of applications (e.g. graph coloring, spectral clustering.) What industry fields does this apply to? Machine Learning?

noelwelsh 4y ago
Here's an example: The web is a graph. Each node in the graph is a web page. Each edge is a connection a hyperlink between pages. You can represent a graph as a matrix. If you random click on links you'll end up visiting some web pages (the more connected ones) more often than others. You can define a probability distribution over pages as "what is the probability I'll end up at this web page after an infinite number of clicks". This is the stationary distribution of a Markov chain. The stationary distribution is the largest eigenvector of the matrix that represents the graph. This gives a way to compute the stationary distribution via well studied algorithms. You can use this idea to 1) assign importance to pages based on the magnitude of the probability, to improve web search. You might call this algorithm PageRank. 2) found a company called Google that is currently worth USDtrillions.
- zamfi 4y ago
  ...or, you could just 1) use the raw count of inbound links, weighted by the count of inbound links of the linking pages, normalize by the total number of links on that page, and run it a few iterations to get a first approximation of the probability distribution. This is a pretty intuitive approach, would almost certainly have been good enough for Google, and avoids all the jargon, probability, and "well studied algorithms". 2) found a company called Google that is currently worth US$trillions. I love algorithms as much as the next guy, but PageRank is not a fantastic example of success-because-I-knew-eigenvectors despite what their PR folks would have you believe. One can't deny, though, that Google's PR has definitely attracted them a lot of super smart engineers over the decades, especially in the early days!
  - hhmc 4y ago
    I think it's pretty easy to construct adversarial examples to your (1) that are dealt with cleanly by real pagerank. e.g. if A is a Huge Important website, and A -> B -> C, then locally looking at {B, C} will underweight C significantly. (And, sure, you might say to look at k-th order inbound links for your iterative approach, but the adversary can just move the weight to k+1). Perhaps, as you claim, your approach would have been good enough, but clearly understanding the theory got them something better.
    - zamfi 4y ago
      This argument that it’s pretty easy to construct adversarial examples would be much more convincing if…it were not what PageRank actually is. PageRank itself initially ran iteratively and would have had exactly this same problem. In any case, I’m not sure your example is actually adversarial, as there’s not an action that an adversary could take implied by it? Maybe you meant “poorly handled case”? But yes, run it iteratively. 10 steps? 20? Until convergence for some epsilon? Nothing against theory, but I think they did fine without it.
      - hhmc 4y ago
        > Maybe you meant “poorly handled case”? No, I meant adversarial. It's standard languge (jargon if you wish) from mathematical proofs.
        zamfi 4y ago
        Huh, interesting. In the ML and CS theory literature I’ve only ever seen “adversarial example” used to mean an input explicitly designed to produce a specific unexpected output, not just a worst-case output that isn’t what you want. Do you have an example use of this sense that I could look at to update myself?
        hhmc 4y ago
        Eg https://courses.engr.illinois.edu/cs473/sp2010/notes/20-adversary.pdf https://courses.engr.illinois.edu/cs473/sp2010/notes/20-adve...
TheaomBen 4y ago
Photogrammetry & image processing, anything to do with dimension reduction (basically every field with real-world sensor data), ontology/semantic data processing...

noelwelsh 4y ago

Here's an example: The web is a graph. Each node in the graph is a web page. Each edge is a connection a hyperlink between pages. You can represent a graph as a matrix. If you random click on links you'll end up visiting some web pages (the more connected ones) more often than others. You can define a probability distribution over pages as "what is the probability I'll end up at this web page after an infinite number of clicks". This is the stationary distribution of a Markov chain. The stationary distribution is the largest eigenvector of the matrix that represents the graph. This gives a way to compute the stationary distribution via well studied algorithms. You can use this idea to 1) assign importance to pages based on the magnitude of the probability, to improve web search. You might call this algorithm PageRank. 2) found a company called Google that is currently worth USDtrillions.

zamfi 4y ago
...or, you could just 1) use the raw count of inbound links, weighted by the count of inbound links of the linking pages, normalize by the total number of links on that page, and run it a few iterations to get a first approximation of the probability distribution. This is a pretty intuitive approach, would almost certainly have been good enough for Google, and avoids all the jargon, probability, and "well studied algorithms". 2) found a company called Google that is currently worth US$trillions. I love algorithms as much as the next guy, but PageRank is not a fantastic example of success-because-I-knew-eigenvectors despite what their PR folks would have you believe. One can't deny, though, that Google's PR has definitely attracted them a lot of super smart engineers over the decades, especially in the early days!
- hhmc 4y ago
  I think it's pretty easy to construct adversarial examples to your (1) that are dealt with cleanly by real pagerank. e.g. if A is a Huge Important website, and A -> B -> C, then locally looking at {B, C} will underweight C significantly. (And, sure, you might say to look at k-th order inbound links for your iterative approach, but the adversary can just move the weight to k+1). Perhaps, as you claim, your approach would have been good enough, but clearly understanding the theory got them something better.
  - zamfi 4y ago
    This argument that it’s pretty easy to construct adversarial examples would be much more convincing if…it were not what PageRank actually is. PageRank itself initially ran iteratively and would have had exactly this same problem. In any case, I’m not sure your example is actually adversarial, as there’s not an action that an adversary could take implied by it? Maybe you meant “poorly handled case”? But yes, run it iteratively. 10 steps? 20? Until convergence for some epsilon? Nothing against theory, but I think they did fine without it.
    - hhmc 4y ago
      > Maybe you meant “poorly handled case”? No, I meant adversarial. It's standard languge (jargon if you wish) from mathematical proofs.
      - zamfi 4y ago
        Huh, interesting. In the ML and CS theory literature I’ve only ever seen “adversarial example” used to mean an input explicitly designed to produce a specific unexpected output, not just a worst-case output that isn’t what you want. Do you have an example use of this sense that I could look at to update myself?
        hhmc 4y ago
        Eg https://courses.engr.illinois.edu/cs473/sp2010/notes/20-adversary.pdf https://courses.engr.illinois.edu/cs473/sp2010/notes/20-adve...

TheaomBen 4y ago

Photogrammetry & image processing, anything to do with dimension reduction (basically every field with real-world sensor data), ontology/semantic data processing...