undefined | Better HN

0 pointseru5y ago0 comments

> Adding to this, most metrics can't be embedded well in euclidean space. Even something as simple as 4 nodes in a loop using the shortest path as your metric -- there's a minimum amount of error for any embedding into any euclidean space, and it's well above 0.

Are you talking about a 2d Euclidean space, or about any number of dimensions?

0 comments

4 comments · 2 top-level

hansvm5y ago· 1 in thread

Any number of dimensions actually :)

For that example it suffices to show it in 3D since any euclidean embedding of n+1 points can be isometrically embedded in an n-dimensional space, so if a 3D embedding with error E doesn't exist then neither does an ND embedding for any N>3.

Finding the minimum error requires a tad more effort, but it's not too bad to show that no embedding has 0 error:

Take a cycle a->b->c->d->a where every edge has length 1. Suppose a 0-error embedding exists. Points (a), (b), and (c) must be embedded colinearly, and then the only possible location for point (d) satisfying the distance requirements |a-d|=|c-d|=1 is precisely wherever we placed point (b), but then point (d) can't possibly have distance 2 from point (b).

By itself that doesn't show that infinitely small errors are impossible, but that assertion is also true in practice.

eruOP5y ago

Thanks!

jqgatsby5y ago· 1 in thread

He's talking about curvature.

PaulHoule5y ago

no, global topology, which is related to curvature.

For instance, I can go from Sydney to Sao Paulo going either East or West on the territory, but on the 2-d map you can only draw one path. You can map one point on the territory to multiple points on the map but that is itself a mismatch with the territory.

A model like WordNet, for instance, loses information about out-of-dictionary words. Words like "if", and "and" and "bit" are in the dictionary, maybe 95% of the words in your text are in the dictionary, but 50% of the meaning is in the out-of-dictionary words. There are things like FastText that do a little better (have a fighting chance of guessing at latin and greek words smushed together) but still make mistakes at an early phase of analysis which can't be recovered at later stages of analysis.

For a domain such as medical notes (say abstract of a medical case study) you might want to answer some question like "Did the patient die?" or "What code would I bill insurance for this?" and much more than half the time an embedding throws out an piece of information which is essential to computing the right answer as opposed to guessing at the answer.

j / k navigate · click thread line to collapse