Hacker Newsnew | comments | show | ask | jobs | submit | login

I write tests not to convince myself my code is correct (it often is, and repl and ad-hoc testing are more than enough to make sure it does the right thing now) but to prevent myself & future others from breaking it as they maintain it in the future.

-----


Regarding the perceptron, most modern texts also have a regret analysis for the perceptron, which coupled with an online-to-batch conversion tells you how well do you expect a perceptron to perform on unseen data after a single pass, and it's usually a very good estimate (the answer is on average about as well as it did on the examples in the training data).

-----


This isn't often discussed in my field (NLP) -- thanks!

We usually use averaged perceptron though, which seems like it would make this hard to analyse.

-----


The averaged perceptron is the one to which the proof applies :-)

-----


ML PhD student here. The reason why this is different is that the parallel monte carlo simulations are running on different subsets of the data in each machine, and then averaged.

It is not obvious that this can work at all in some cases. Think, for example, a clustering model. If there are two clusters, but one machine calls them A B and the other machine calls them B A, averaging will give you useless results.

So the contribution of this paper is finding a set of models on which naive averaging works, and showing an efficient mapreduce implementation of it.

That said, I don't find the paper particularly interesting.

-----


Ph.D student in Stats here. That we can even sample the full posterior with so much data is interesting in and of itself. The method isn't particularly revolutionary, especially compared to a method Zaiyang Huang and Andy Gelman[1] came up with 8 years ago, but it's practical (for a restricted class of models). Steve Scott spoke to my department about a month ago, describing the problem. It's not a solution that works for all posteriors, but it certainly allows more freedom than restricting oneself to conjugate priors and allows computation on large datasets.

Academics tend to trivialize the implementation (we had some pretty strong critics of his talk in my dept), but some kudos are in order for that, even if the algorithm itself isn't revolutionary.

[1]: http://www.stat.columbia.edu/~gelman/research/unpublished/co...

-----


Honestly, more people should use stabilizer http://plasma.cs.umass.edu/emery/stabilizer . The best can still be an outlier.

-----


haven't heard of it - thanks for the link. looks great.

-----


Fun fact: this is pretty much the same dynamic program as CKY, the parsing algorithm that can parse any context-free language in the appropriate normal form (only productions looking like A->BC or A->a) in time cubic on the length of the sentence.

-----


Wow, I didn't know that...thanks, I will look into it

-----


The fallacy behind arguments like this is that when someone says that we're "proposing to push people to speak at conferences who aren't necessarily the most knowledgeable speakers" it is implicitly assumed that it is known how to rank the speakers, and that doing so is easy.

In practice, however, while one can often tell a really bad speaker and a really good speaker apart there are plenty of bordeline cases and the variance is big, so using minority-biased criteria to "break ties" will not necessarily lead to worse speakers on average, as long as these criteria are uncorrelated with actual skills.

(and I'm not sure they are, as the mean quality of a woman-presented talk in conferences I've attended has been consistently higher than the mean man-presented talk)

-----


The fact that a decision process is noisy and imperfect doesn't mean that deliberately adding errors to it won't give worse results.

All it does is give you statistical noise, making it easier to bury your head in the sand.

-----


When you have a 22:1 male to female ratio and a 23:0 white to non-white ratio, it'll take more than a tie-breaker to make it look as diverse as a PBS cartoon.

-----


Indeed. It's more a case of 'we know we collectively have an unfair bias against women, let's try to consciously adjust our bias a bit.'

-----


A foot a second is off by several orders of magnitude. It's closer to 300 thousand km per second in vacuum, and around 200 thousand km per second in fiber.

-----


He obviously means a foot in a nanosecond.

-----


The above construction is a not a breakthrough and it is how I was taught in my approximate algorithms class. Also the way the optimization problem is usually defined is not as "give a circuit with minimal cost" but "what is the cost of the minimal-cost circuit?", which is easier to reason about in an approximate way.

-----


Same here. Intuitively, a decider that can answer "Is there an answer less than X?" will give you one bit of the lowest cost each time you query it. Do it repeatedly until you have all of the bits, and you're done.

-----


There is no guarantee that the number of bits in 'all the bits' is finite. Because of that, there is no guarantee that such an algorithm finishes. The simplest counterexample is N=2, with a distance of 1/3 between the nodes, and shortest (and only) tour with length 2/3.

-----


You don't need to represent the actual length of the solution in a finite number of bits, you just need to represent the solution itself. The solution can be represented as the set of edges contained within it. Each edge is either present or not, so a solution can be represented as a bit set the size of the number of edges in the graph, or at most n^2 bits where n is the number of vertices.

For a practical idea of how you'd do this, I think you'd just modify your binary search based on the possible circuit values. Basically, figure out what number excludes half of the remaining solutions, rather than just half of the range, and use that in your binary search.

-----


Yes, any algorithm that halves the set of potential solutions in each iteration will work, but I do not see how one can get such an iteration step from "a decider that can answer "is there an answer less than X?". If suspect (but cannot prove or even have reasonably solid arguments) that the "figure out what number excludes half of the remaining solutions" step will be at least as hard as the problem itself.

Now, if I had such an oracle, I would let it loose on all graphs equal to the target graph with one edge removed. I think (but cannot prove (yet?)) that that is a way to prove, for each edge, whether it is by necessity part of the shortest tour. I also supect that, for most graphs, the set of remaining "might be in the shortest tour" will be so small that an exhaustive search will be easy.

-----


No nonempty interval of real numbers can be represented in a finite number of bits.

-----


That's exactly what floating point numbers are: representations of real number intervals as finite length bit strings. The number of bits simply determines the granularity of the representation (ie. the width of the intervals).

-----


Floating point numbers are approximations of real numbers, which isn't sufficient in this context. Solving a lossy representation of the problem isn't a reduction in the complexity theoretic sense.

-----


In the case of this problem the set of possible paths is finite so it can, in principle, be sorted in order of increasing cost. The smallest cost delta between any 2 paths in the sorted list is the lowest cost edge in the graph (this probably assumes that all edge costs are positive) so you only need to continue the binary search until intervals of this size are reached. At that point the exact solution has been found.

EDIT: There might be multiple paths with the same minimal cost but binary search will still find this value.

-----


That depends on how you define your representation. It is useful for some problems to represent an interval with it's first bits, e.g. to take 0.101 as representing all numbers in the [0.101, 0.110) interval.

-----


You are correct. What I meant to say was: You cannot represent all the distinct real numbers in a nonempty interval using a finite number of bits.

-----


Why is that relevant?

-----


Fortunately, non-empty intervals of real numbers do not exist in computer science.

-----


Did I get my mathematical terms wrong or are you confusing number representations on computers with computer science?

-----


I choose the nonempty interval [0, 1]. I have just represented it here in 48 bits (many of which are unnecessary, but bits are cheap). I don't think your statement is correct.

-----


A temp agency?

-----


One built from the ground up with the idea that people can hire online. Can I rent a clown for my kids birthday party through a temp agency? Can I hire someone to clean my house from that same temp agency? Can I hire someone to detail my car?

-----


It's interesting, but you're going to get a lot of human complication involved. You'll need administrators with the expertise to vet all those types of people. If money is flowing through you, customers will expect you to guarantee quality. And guarantee you don't send a criminal into their house to entertain their kids. I did essentially this just for math tutors for the math portion of the SAT for high schoolers. By far the most work was in hiring and managing staff.

If money is not flowing through you then the product is Angie's List.

-----


taskrabbit, exec, craigslist, etc.

-----


Regarding finding the higgs boson, regardless of whether you agree that it's what they're actually doing, the main people actually building the first quantum computer are D-Wave, a private company.

-----


citation please? First, what does quantum computers have to do with finding the higgs boson? Second, is D-wave not standing on the shoulders of decades of academic research in designing their computer?

-----


D-Wave are making more exaggerated press release claims. Universities have better working quantum computers (i.e. any at all)

-----


They've got some serious-business Quantum Computing experiments at NIST, as well.

-----

More

Applications are open for YC Summer 2015

Guidelines | FAQ | Support | API | Lists | Bookmarklet | DMCA | Y Combinator | Apply | Contact

Search: