Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

CS 168: The Modern Algorithmic Toolbox

web.stanford.edu

Post reply on HN
Print view View original

91–100 of 101 posts

Re: CS 168: The Modern Algorithmic Toolbox

#91

Post by zamfi »

hhmc wrote: post #49
zamfi wrote: post #15

Earlier quoted context omitted.

...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 alg…

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 wo…

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.

Re: CS 168: The Modern Algorithmic Toolbox

#92

Post by hhmc »

zamfi wrote: post #91
hhmc wrote: post #49

Earlier quoted context omitted.

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 wo…

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 it…

> Maybe you meant “poorly handled case”?

No, I meant adversarial. It's standard languge (jargon if you wish) from mathematical proofs.

Re: CS 168: The Modern Algorithmic Toolbox

#93

Post by zamfi »

hhmc wrote: post #92
zamfi wrote: post #91

Earlier quoted context omitted.

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 it…

> Maybe you meant “poorly handled case”? No, I meant adversarial. It's standard languge (jargon if you wish) from mathematical proofs.

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?

Re: CS 168: The Modern Algorithmic Toolbox

#94

Post by noelwelsh »

zamfi wrote: post #89
noelwelsh wrote: post #64

Earlier quoted context omitted.

0. Why so anti-intellectual? 1. The algorithm you're attempting to describe in 1) above is either exactly PageRank or an approximation to it, so I don't get the point you're trying to make. 2. The point of jargon and well studied algorithms is that you can recognize when your problem is a problem someone else has already tackled. In the specific case of PageRank, if you recognise it's an eigenvalue problem you can 1)…

0. Hah, yeah. Pretty sure you’re the first person to accuse me of being anti-intellectual...I can’t say for certain, but I think this interpretation here might be on you. 1. Indeed I think you missed my point: the causality implied in your earlier post reads as “well, if you know math, PageRank pops right out!” — my point is, you don’t need to know anything about eigenvalues for PageRank to be an intuitive solution;…

I wasn't using jargon for jargon's sake. The original question quoted this little passage:

"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.)"

My response used the same terms to quickly sketch how they relate to PageRank, and hence try to show how the theory relates to an application. If I was trying to explain PageRank to someone who wasn't familiar with the maths I would take a different approach, but this is a tiny little textbox and there are already many very nice visualizations and other explanations that one can Google.

Re: CS 168: The Modern Algorithmic Toolbox

#95

Post by fjkdlsjflkds »

buttery101 wrote: post #39

In the lecture note 6 about regularization, section 3.4: the l1 norm of a vector is simply the sum of the absolute values of the coordinates, and hence it is continuous (and linear). I don't think that the l1 norm is linear since |x+y| # |x| + |y|.

They probably meant that it is positively homogeneous (i.e. |ax|=|a||x|), I would assume, since it's definitely not a linear function.

Re: CS 168: The Modern Algorithmic Toolbox

#96

Post by hhmc »

zamfi wrote: post #93
hhmc wrote: post #92

Earlier quoted context omitted.

> Maybe you meant “poorly handled case”? No, I meant adversarial. It's standard languge (jargon if you wish) from mathematical proofs.

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?

Eg https://courses.engr.illinois.edu/cs473/sp2010/notes/20-adve...

Re: CS 168: The Modern Algorithmic Toolbox

#97

Post by zamfi »

hhmc wrote: post #96
zamfi wrote: post #93

Earlier quoted context omitted.

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?

Eg https://courses.engr.illinois.edu/cs473/sp2010/notes/20-adve...

Thanks!

Re: CS 168: The Modern Algorithmic Toolbox

#98

Post by zamfi »

noelwelsh wrote: post #94
zamfi wrote: post #89

Earlier quoted context omitted.

0. Hah, yeah. Pretty sure you’re the first person to accuse me of being anti-intellectual...I can’t say for certain, but I think this interpretation here might be on you. 1. Indeed I think you missed my point: the causality implied in your earlier post reads as “well, if you know math, PageRank pops right out!” — my point is, you don’t need to know anything about eigenvalues for PageRank to be an intuitive solution;…

I wasn't using jargon for jargon's sake. The original question quoted this little passage: "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.)" My response used the same terms to quickly sketch how they relate to PageRank, and hence try t…

Oh, I wasn't accusing you of using jargon for jargon's sake, and nor do I believe that you were -- you used the appropriate jargon appropriately and correctly! And certainly representing graphs as matrices and then applying matrix math to them is valuable, I am absolutely not arguing against that.

I'm just taking issue with the (probably tongue-in-cheek!) framing of your "quick sketch": rather than merely demonstrate the connection ("hey look, PageRank uses this stuff!"), the sketch implied that if one knew theory about graphs and their representation as matrices, then PageRank is pretty obvious and falls out of the math (and then you could start a US$trillions business!). I was content to just leave it at that with a snarky version of "hey, sure, this math is relevant, but it wasn't a requirement to come up with the PageRank insight" -- but then I got triggered by your "anti-intellectual" comment. :)

So now I feel compelled to say, in case any impressionable young minds read this thread: that sketch (which I likely grossly misrepresented above) is a fantasy portrayal of how the insights behind technologies like PageRank come about; matrix knowledge isn't necessary (but not unhelpful, of course) to create PageRank or similar things. I've met too many (not necessarily you!) who tell themselves some version of this story: "PageRank? That's just the largest eigenvector the edge matrix" followed by some variant of "Those guys just got lucky! / Those guys just commercialized some known math! / I do math, and math can be worth billions!"

That story ignores the actual insights required to get to PageRank, even if you already know the theory; it ignores the hard work of actually building a company and commercializing such an insight.

Anyway, thanks for coming to my therapy session.

Re: CS 168: The Modern Algorithmic Toolbox

#99

Post by Hermitian »

melling wrote: post #45
t_mann wrote: post #25

Earlier quoted context omitted.

> (i) ideas that are non-obvious , even to the well-trained computer scientist > In the first lesson, they discuss consistent hashing, and they seem to have achieved their goals. I was really excited when I read your comment here before clicking the link, but having had a look at the rest of the curriculum, I'm slightly underwhelmed. - Generalization ... Empirical risk minimization. - lossy compression - Similarity S…

All those topics are unimpressive? I’ve spent quite a bit of time trying to teach myself them. I’ve seen several Stanford courses (e.g CS229) so the low course number of 168 would seem to indicate that it’s taken within the first couple years of college.

The course description states that this is intended for senior as a capstone course, hopefully that help clarifies.

Re: CS 168: The Modern Algorithmic Toolbox

#100

Post by grubby »

this is Za. wish my school had stanford level classes, im caught at a t20 research focused university that isn’t a industry pillar of CS (Cal, MIT, stanford), and they don’t seem motivated to update the classes to be challenging and relevant, just dated and unnecessarily difficult niche topics
Post reply on HN