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

21–30 of 68 posts

Re: Universal Method to Sort Complex Information Found

#21

Post by [deleted] »

buckminster wrote: post #12
sshine wrote: post #5

Earlier quoted context omitted.

Incidentally, 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.

The rail network in the UK is also strange. On some routes it is cheaper to split your journey across multiple tickets. On others it is cheaper to buy a ticket for a longer journey. However, this is illegal and the train companies do attempt prosecutions.

[deleted]

Re: Universal Method to Sort Complex Information Found

#22

Post by fizx »

fenollp wrote: post #6

I 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?

There 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.

Re: Universal Method to Sort Complex Information Found

#23

Post by bunderbunder »

gumby wrote: post #10
sshine wrote: post #5

Earlier quoted context omitted.

Incidentally, 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.

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

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.

Re: Universal Method to Sort Complex Information Found

#24

Post by bunderbunder »

CydeWeys wrote: post #15
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?

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

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

Re: Universal Method to Sort Complex Information Found

#25

Post by QML »

I'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.

Re: Universal Method to Sort Complex Information Found

#26

Post by hinkley »

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

Re: Universal Method to Sort Complex Information Found

#27

Post by buckminster »

saganus wrote: post #18
buckminster wrote: post #12

Earlier quoted context omitted.

The rail network in the UK is also strange. On some routes it is cheaper to split your journey across multiple tickets. On others it is cheaper to buy a ticket for a longer journey. However, this is illegal and the train companies do attempt prosecutions.

Why is it illegal and how do they enforce it? I know that something similar happens with airplane tickets but they get you with the luggage and with terms & conditions AFAIK. How is it similar/different with train tickets?

It is illegal because the railway byelaws make it illegal. The railway doesn't just have its own law, it also has its own police force, The British Transport Police, though as far as I know they don't do the ticket enforcement.

You are not allowed to break a journey either, so a ticket inspector can spot a ticket for a longer journey at one end of the other. The multiple tickets ruse is more of a grey area.

Re: Universal Method to Sort Complex Information Found

#28

Post by DonaldFisk »

buckminster wrote: post #12
sshine wrote: post #5

Earlier quoted context omitted.

Incidentally, 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.

The rail network in the UK is also strange. On some routes it is cheaper to split your journey across multiple tickets. On others it is cheaper to buy a ticket for a longer journey. However, this is illegal and the train companies do attempt prosecutions.

It's legal:

https://www.telegraph.co.uk/money/consumer-affairs/fare-spli...

https://www.bbc.co.uk/news/uk-england-19217111

and there are web sites which do split ticketing:

http://www.raileasy.co.uk/home/split-ticketing/

http://www.splitticketing.co.uk

https://www.splityourticket.co.uk

Re: Universal Method to Sort Complex Information Found

#29

Post by mlthoughts2018 »

QML wrote: post #25

I'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…

I’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.

Re: Universal Method to Sort Complex Information Found

#30

Post by novia »

fizx wrote: post #19
DoctorOetker wrote: post #14

Earlier quoted context omitted.

The 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.

One assumes its an extension of their previous work ( 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 , but he got marked dead by HN.

I vouched for the author's comment. Any clue why people are downvoting/flagging it?
Post reply on HN