8 ms·
Universal Method to Sort Complex Information Found
- macleginn 8y agoThe 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.
- bunderbunder 8y agoIt's a rather large set, but it's got some noteworthy holes. Cosine distance, for example.
- DoctorOetker 8y agomy gut feeling tells me - ln((1+Similarity_cosine(A,B))/2) would satisfy the triangle inequality.
- tlb 8y agoIt produces negative distances, which disqualifies it as a metric.
- Y_Y 8y agoFor a Riemannian metric yes, but a lot of physics gets done in Lorentzian (psuedo-)metric spaces.
- DoctorOetker 8y agohow 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] ?
- DoctorOetker 8y agoI 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.
- tlb 8y agoAh, 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 < a2c: print ' *** fails triangle inequality' main()
- DoctorOetker 8y agogood catch! upvoted
- deleted 8y ago[deleted]
- sshine 8y agoIncidentally, the zone system for the Danish public transit system is not a metric space. (The ticket you need from A to B is not necessarily the same as from B to A.) That's a kind of practical graph where you want efficient shortest path algorithms for.
- deleted 8y ago[deleted]
- gumby 8y agoReally?? Is that true only when there are multiple paths between A & B or is there something else involved?
- CydeWeys 8y agoOther possibilities: Trains going in different directions don't make the same stops (express vs local), and time-based fares applying to a specific direction based on commuting patterns. In the US, on Amtrak, a ticket is specific to an exact train, like buying a plane ticket. There's no generalized "I want a ticket from DC to NYC."
- bunderbunder 8y agoSome of the shorter ones have unreserved coach class tickets that aren't restricted to a specific train. So, while there is no generalized, "I want a ticket from DC to NYC", there is a generalized, "I want a ticket from Chicago to Milwaukee."
- bunderbunder 8y agoChicago 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.
- gumby 8y agoInteresting, thanks!
- def-lkb 8y ago> 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).
- macleginn 8y agoYou 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.
- thesasho 8y agoThe 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.
- macleginn 8y agoBut 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.)
- curious1212 8y agoI don't think the general property of expander graphs is needed, perhaps a relaxed property, such as the following definition: A graph G is a distance(k)-expander if #edges(U, V-U) > c min(#U,#(V-U)) where U is a set of diameter <=k. Now study the embeding. I am also curious about what happens if one use SVM to classify vertices of an expander graph: Let G be an expander graph and let u1,u2 be vertices of G such that d(u1,u2) = diameter of G = an even number 2k. We classify the vertices of G like this: f(u) = 0 if d(u,u1)<=k, f(u)=1 if d(u,u1)>=1, then using SVM applied to the vertices encoded by the rows of the adjancecy matrix. I would expect the SVM algorith to have some special property but I don't know what to expect, the best or worst classification, or the support vectors can gives us some information about symmetries in the graph.
- danharaj 8y agoAh that's so cool. I've been reading about expander graphs lately. Their interesting properties make them pertinent to lots of questions. In particular, you can use expander graphs to cook up error correcting codes and prove the PCP theorem. There's a class of expander graphs called Ramanujan graphs which are characterized by an analogue to the Riemann hypothesis involving a zeta function that counts the prime cycles in a graph.
- fenollp 8y agoI wonder what this can mean for fuzzing, optimization, learning or any kind of task that has to do with tip-toeing into potentially high dimensional spaces?
- fizx 8y agoThere are a lot of places in practical neural nets with attention where you want softmax(queryvector · memorymatrix), where memory can be quite large. If you have a decent ANN implementation, you can approximate by only calculating the dot product for the vectors of memory that neighbor the query. There are currently a ton of mediocre ways to do this because nothing really works very well in high dimensions, and calculating this can easily be the bottleneck in training and evaluation.
- crb002 8y agoCurious to see Timothy Chan develop some screaming fast C code using their method.
- fwilliams 8y agoLink (from the article) to the paper with details: https://www.ilyaraz.org/static/papers/spectral_gap.pdf https://www.ilyaraz.org/static/papers/spectral_gap.pdf
- DoctorOetker 8y agoThe article announces the algorithm, which isn't published yet. This first paper contains the proof that the result is possible, not yet the efficient algoithm.
- ttul 8y agoI await this paper with eager anticipation.
- ilyaraz1990 8y agoThis is the second paper, where we present an actual fast algorithm for general normed spaces: https://ilyaraz.org/static/papers/daher.pdf https://ilyaraz.org/static/papers/daher.pdf . Enjoy!
- DoctorOetker 8y agothank you very much!
- deleted 8y ago[deleted]
- charlescearl 8y agoDoes any of this have implications for libraries like your FALCONN https://falconn-lib.org https://falconn-lib.org? Have not read the paper yet.
- fizx 8y agoOne assumes its an extension of their previous work (https://arxiv.org/pdf/1501.01062.pdf https://arxiv.org/pdf/1501.01062.pdf), which was only valid for Euclidian and Hamming spaces? Edit: The author says its https://ilyaraz.org/static/papers/daher.pdf https://ilyaraz.org/static/papers/daher.pdf, but he got marked dead by HN.
- QML 8y agoI'm curious to if this result will extend to the k-nearest neighbors (k-NN) algorithms. Two problems that have to do with k-NN are 1. It's a non-parametric method: the number of parameters grow linearly with the size of the training set since the distance function must be calculated for all training points and the test point. 2. The curse of dimensionality: distance metrics like the Euclidean distance do not perform well in higher dimensions; points which seem "close" in 2D may be far in 3D, 4D, etc. As a result, we would need an exponential amount of more training data for every additional dimension. Locality sensitive hashing tries to combat this by reducing the dimensionality of the data.
- mlthoughts2018 8y agoI’m curious if it will extend to k q-flats, or other notions of points being near each other purely by being near to the same subspace, rather than pointwise nearness.
- hinkley 8y ago> For example, “Manhattan” distance forces you to make 90-degree turns, as if you were walking on a street grid. Using Manhattan distance, a point 5 miles away as the crow flies might require you to go across town for 3 miles and then uptown another 4 miles. It's interesting that this is called Manhattan distance because it's only relevant in a town where everyone jaywalks... Like Manhattan. It's far from true anywhere where jaywalking is frowned upon. Because of (the lack of) crosswalk synchronization, it's a lot faster to walk to a place 2 blocks over and 2 blocks up than it is to walk to a place 4 blocks in one direction. Because at the first two lights you have the option of crossing in either direction, at which point you may only have to wait a few moments before crossing in the other direction.
- SomewhatLikely 8y agoThe measure is concerned only with the distance traveled, not the time.
- Y_Y 8y agoThat's quite a narrow view. You can certainly model time in a metric space, i.e. it you go one block west and one new-york minute forward.
- mikhailfranco 8y agoYes, this is the value of optionality, as N.N.Taleb would say. I had exactly the same thought about crossing streets when reading one of his books. Always choose a route where you have the choice to keep walking in some direction towards your destination, with a delayed jaywalk to cross to the side you want during a gap in traffic, rather than wait on a corner when a crossing is blocked. The reason for blockage can be a crosswalk light (if you obey them) or traffic itself - the rule applies even without any signal-controlled junctions.
- usgroup 8y agoClick bait. Not universal. Nearest neighbour algo that works well for a family of distant measures.
- EmilStenstrom 8y agoI 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.