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

Universal Method to Sort Complex Information Found

quantamagazine.org

Post reply on HN
Print view View original

51–60 of 68 posts

Re: Universal Method to Sort Complex Information Found

#51

Post by thesasho »

macleginn wrote: post #2

The subtitle claims that a “universal way” was found to solve the nearest-neighbour-search problem for any kind of data, but actually the result is restricted to the (rather huge, of course) set of normed spaces, i.e. spaces whose distance measures obey the triangle inequality.

The method gives a data structure for any metric space, and the quality of the data structure is controlled by how well expanders embed in the metric space. This implies interesting results for metrics which are not norms, like geodesics on certain manifolds. The surprise to us was how well this approach works for any norm, however. (I am one of the authors.)

Also, a math correction: spaces which obey the triangle inequality are called metric spaces. The class of normed spaces is more restricted, but still very large.

Re: Universal Method to Sort Complex Information Found

#52

Post by gumby »

Lewton wrote: post #38
gumby wrote: post #10

Earlier quoted context omitted.

Really?? Is that true only when there are multiple paths between A & B or is there something else involved?

They use a zone system, and you don’t have to pay for a zone if you get off at the first stop after entering it. This creates the asymmetry

thanks

Re: Universal Method to Sort Complex Information Found

#53

Post by EmilStenstrom »

I really hope this leads to databases with good support for fast nearest neighbour search. This would be especially useful in word2vec cases, where you have millions of word vectors, and want to find "words similar to this one" without either having all of them in memory, or going through all of them to find out.

Re: Universal Method to Sort Complex Information Found

#54

Post by DoctorOetker »

tlb wrote: post #36
DoctorOetker wrote: post #13

Earlier quoted context omitted.

my gut feeling tells me - ln((1+Similarity_cosine(A,B))/2) would satisfy the triangle inequality.

It produces negative distances, which disqualifies it as a metric.

how does it produce negative distances?

cosine similarity is [1,-1], so add one [2,0], now halve [1,0] now take logarithm [0,-inf] finally negate [0,+inf]

?

Re: Universal Method to Sort Complex Information Found

#55

Post by bunderbunder »

notyourwork wrote: post #39
bunderbunder wrote: post #23

Earlier quoted context omitted.

Chicago has a minor version of this, even without zone fares: The entry fee to get on a train is $2.50 everywhere except O'Hare Airport, where it's $5.

The tourist fee.

Nah. Most the people I see on that train are people commuting to/from work, and locals who live along the blue line corridor. Some tourists, but I think most of them are opting to pay a driver 8x as much to take even longer to get them downtown.

Re: Universal Method to Sort Complex Information Found

#56

Post by DoctorOetker »

DoctorOetker wrote: post #54
tlb wrote: post #36

Earlier quoted context omitted.

It produces negative distances, which disqualifies it as a metric.

how does it produce negative distances? cosine similarity is [1,-1], so add one [2,0], now halve [1,0] now take logarithm [0,-inf] finally negate [0,+inf] ?

I guess the best conversion of cosine similiarity to distance would of course be d(A,B) = arcCos(Cosine_similiarity(A,B)), i.e. the angle between the 2 directions, which would have the property that subdividing a geodesic arc and calculating the sum of distances along the subdivision results in the same distance as the start and end point.

Re: Universal Method to Sort Complex Information Found

#57

Post by tlb »

DoctorOetker wrote: post #54
tlb wrote: post #36

Earlier quoted context omitted.

It produces negative distances, which disqualifies it as a metric.

how does it produce negative distances? cosine similarity is [1,-1], so add one [2,0], now halve [1,0] now take logarithm [0,-inf] finally negate [0,+inf] ?

Ah, I mistook the - at the beginning for a separator.

It does fail the triangle inequality, though, as the following python snippit demonstrates:

  import numpy as np

  def randomvec():
      return np.random.rand(4)*2-1

  def cossim(a, b):
      return np.dot(a,b) / np.sqrt(np.dot(a, a) * np.dot(b, b))

  def metric(a, b):
      return -np.log((1+cossim(a, b))/2)

  def main():
      for i in range(20):
          a = randomvec()
          b = randomvec()
          c = randomvec()
          a2b = metric(a, b)
          b2c = metric(b, c)
          a2c = metric(a, c)
          print a2b, b2c, a2c
          if a2b + b2c

Re: Universal Method to Sort Complex Information Found

#58

Post by macleginn »

thesasho wrote: post #51
macleginn wrote: post #2

The subtitle claims that a “universal way” was found to solve the nearest-neighbour-search problem for any kind of data, but actually the result is restricted to the (rather huge, of course) set of normed spaces, i.e. spaces whose distance measures obey the triangle inequality.

The method gives a data structure for any metric space, and the quality of the data structure is controlled by how well expanders embed in the metric space. This implies interesting results for metrics which are not norms, like geodesics on certain manifolds. The surprise to us was how well this approach works for any norm, however. (I am one of the authors.) Also, a math correction: spaces which obey the triangle in…

But these more general results are kind of small print, right? The abstracts to both linked articles talk specifically about normed spaces.

(Thanks for the correction. I just gave one of the properties, but should’ve been more precise.)

Re: Universal Method to Sort Complex Information Found

#59

Post by macleginn »

def-lkb wrote: post #9
macleginn wrote: post #2

The subtitle claims that a “universal way” was found to solve the nearest-neighbour-search problem for any kind of data, but actually the result is restricted to the (rather huge, of course) set of normed spaces, i.e. spaces whose distance measures obey the triangle inequality.

> spaces whose distance measures obey the triangle inequality That would be a metric space, and a distance obey the triangle inequality by definition. The element of the space are otherwise quite arbitrary. Unfortunately, Normed spaces are a subset of metric spaces which are much less general (in particular they have to be vector spaces).

You are right, I wantonly omitted some of the important properties. Cf. the response of one of the authors in another comment on how their method tackles general metric spaces.

Re: Universal Method to Sort Complex Information Found

#60

Post by DoctorOetker »

tlb wrote: post #57
DoctorOetker wrote: post #54

Earlier quoted context omitted.

how does it produce negative distances? cosine similarity is [1,-1], so add one [2,0], now halve [1,0] now take logarithm [0,-inf] finally negate [0,+inf] ?

Ah, I mistook the - at the beginning for a separator. It does fail the triangle inequality, though, as the following python snippit demonstrates: import numpy as np def randomvec(): return np.random.rand(4)*2-1 def cossim(a, b): return np.dot(a,b) / np.sqrt(np.dot(a, a) * np.dot(b, b)) def metric(a, b): return -np.log((1+cossim(a, b))/2) def main(): for i in range(20): a = randomvec() b = randomvec() c = randomvec()…

good catch! upvoted
Post reply on HN