jkabrg

Not only do we have previous knowledge, we know basically everything about what's going on. You only use Bayesian inference if there is something you don't know which can't be computed from the things you do know. Then, after doing an experiment, you work backwards to figure out the value of the things you didn't know.

Don't confuse Bayesian inference with Bayes' theorem, which is a theorem that doesn't have any philosophy attached to it. Bayesian inference makes use of this theorem on top of some philosophical assumptions, which may be questionable depending on how you use them.

Bayesian inference also requires you to give your "prior" beliefs, which are the beliefs you have before you do the experiment. If these beliefs are strongly biased away from the right answer, you will get Garbage Out.

Bayesian statistics is a way of updating your beliefs about the value of some unknown number (or value) after doing an experiment. You have to be uncertain about some variable, and then you work backwards to figure out its value.

In the case of the Monty Hall problem, we have a complete understanding of what's going on, so there are no beliefs to update. There are no hidden rules or magic numbers we haven't been told about and we need to work out. You literally can't use Bayesian statistics if you understand a system completely.

Also, Bayesian statistics is a tool. It's not a law of nature. It can get the wrong answers. There is literally no guarantee that you will get the right answer when using it. Garbage In Garbage Out. It's just that there are cases where, empirically, it can be useful.

Does this comment deserve a downvote? I think he's asking a genuine question.

Do you think there's any hope of finding a practical algorithm for USTON that runs in logarithmic space? Reingold's algorithm needs O(n^64^32) time(!!!)

A qubit is a linear combination of |0> and |1>, and a qutrit is a linear combination of |0>, |1> and |2>. I remember Scott Aaronson once suggested building QCs with qudits (or qu-n-its with n>2).

I think oracle separations are currently only useful as barrier results, showing that certain proof techniques can't solve the full problem.

An implementation: https://github.com/jkabrg/type-segregated-pools

From what I can tell: that while this memory-management strategy can stop a program from seg-faulting or from executing remote code, the style of programming is the same as with `malloc` and `free`. You still have to `alloc_texture()` and `free_texture()` in your code even if those functions return a handle instead of a raw pointer.

Some observations about the strategy based on the article:

  - It does *not* prevent memory leaks. It uses fixed size arrays, so once you allocate more memory
  than there is room in the array, then the program has to exit.
  - It does not prevent use after free. It just makes it easier to detect when this has happened.

This could make debugging easier in some situations. I do wonder though how it interacts with code analyzers.

Also this could work in any language. I wonder if it's common in game development for Android, because of Java and garbage collection spikes.

Oh, and another observation: I think this strategy is fully compatible with RAII and smart pointers. Smart pointers are implemented using malloc/free, and this strategy is isomorphic to malloc/free, so combining them should work fine.

Off topic but I couldn't get hibernate to work on Ubuntu Linux. I purchased a laptop with Linux pre-installed; but apparently, if a manufacturer claims to support Linux on a laptop, that does not include hibernate support. Now that we've reached the milestone of Linux on a desktop, I'm looking forward to the Year Of Linux On The Laptop.

No. The relevant theorem is called Darboux's Theorem. It states that if f(x) has a derivative f'(x) everywhere, then f'(x) satisfies the intermediate value property, meaning: If f'(A) < 0 and f'(B) > 0 then there exists a C between A and B such that f'(C) = 0. Why this is interesting is because f'(x) can be a discontinuous function.

f'(x) being discontinuous is not the same thing as f(x) not having a derivative at some point; for example, the absolute value function |x| is simply not differentiable at x=0. The following function IS differentiable at x=0 but its derivative at x=0 is discontinuous:

      f(x) = x^2 sin(1/x) if x != 0 else 0

You can verify that this function satisfies Darboux's theorem.

Darboux's theorem implies in particular that if f'(x) exists at some point x and is discontinuous at that x then the discontinuity is not a jump discontinuity.

Link to Darboux's theorem: https://en.wikipedia.org/wiki/Darboux%27s_theorem_(analysis)

You're either a troll or an idiot. Not sure yet...

`For` expressions are not boolean blind compared to map/flatmap/filter. (Boolean blindness: https://existentialtype.wordpress.com/2011/03/15/boolean-bli...)

That might be an advantage.

`map` is not going to make it faster. `map` is a loop. Only vectorized code is faster.

Here's a diagram [1] of a one-hidden-layer NN. It has 2 activation functions. Their NN is of the same type.

[1] - https://raw.githubusercontent.com/qingkaikong/blog/master/40...

One thing I don't like about Python libraries, from the top of my head: That there is a distinction between functions and methods, e.g. between nansum(a) and a.sum() where a is a numpy array. The distinction is illogical and just has to be memorized, much like the difference between different categories of verbs in French.

In contrast, R uses an exotic form of object oriented programming called multimethods, which doesn't make a distinction between object.method() and method(object). And if you like chaining methods together like object.method1().method2().method3(), then you can do that in R using the piping operator from the Dplyr package: object %>% method1() %>% method2() %>% method3(), which is rightly equivalent to method3(method2(method1(object)))

You're wrong. See section 5.1. I've drawn a graph of it that shows it to be a classical NN with a single output node.

> The "depth-three" model in this paper is a bit strange in that their second layer has only one output, so the third linear layer doesn't have any effect. I would have called this "depth two"; but it is internally consistent with their definition of depth.

No, it does have an effect: It takes a linear combination of the outputs of the previous layer, and then applies a non-linearity $\sigma'$. If $\sigma'$ is the logistic function, then the output of the last layer is a probability.

It's probably referring to policy iteration[1].

It works by iterating two steps:

- Keep the policy $\pi$ fixed, and determine the $Q$ values for that policy

- Keep the $Q$ value estimates fixed, and create a policy $\pi'$ such that

   -- $\pi'(s) = \arg\max_a Q(s,a)$ for the ordinary greedy algorithm,

   -- $\pi'(s,a) \propto \exp Q(s, a)$ if using greedy soft-max.

[1] - Lecture 3 of http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html

How is this different from Pypy, other than the fact that ones uses RPython and the other uses Rust?

I had another idea for making constant time programs. The idea is that you create a virtual machine without loops or branch instructions, in which each instruction is tested so that the amount of time it takes is independent of the instruction's input or output. You then compile your C code to this instruction set, and execute it on the VM. A program running on this VM, no matter how it's produced, will execute for the same amount of time.

Why not do this for crypto?

Slightly off-topic, but maybe we need a fully standardized and unambiguous CSV dialect with its own file extension. Or maybe just use SQLite tables or Parquet?

Some things I dislike about CSV:

* No distinction between categorical data and strings. R thinks your strings are categories, and Pandas thinks your categories are strings.

* I'm not a fan of the empty field. Pandas thinks it's a floating point NaN, while R doesn't. So is it a NaN? Is it an empty string? Does it mean Not Applicable? Does it mean Don't Know? Maybe it should be removed altogether.

* No agreement about escape characters.

* No agreement about separator characters.

* No agreement about line endings.

* No agreement about encoding. Is it ASCII, or UTF-8, or UTF-16, or Latin-whatever?

* None of the choices above are made explicit in the file itself. They all have the same extension "CSV".

These use up a bit of time whenever I get a CSV from a colleague, or even when I change operating system. Sometimes I end up clobbering the file itself.

Good things: * Human readable. * Simple.

I think the addition of some rules, and a standard interpretation of them, could go some way to improving the format.

Here's a way of thinking about the undecidability of the halting problem. Let's say you've got a person who's amazing at reading minds, and you bring someone off the street and tell them they can either have steak or a cupcake (but not both). You then ask the mindreader to decide if the person will have the cupcake or the steak. Conceivably, they might be able to figure out which one the person will have. Now let's say that you add a twist: you walk up to the person from the street and tell them what the mindreader predicted; in that case, the mindreader can't succeed because the subject can choose to do the opposite. That's similar to how the undecidability proof of the halting problem works.

Now instead of a mindreader, we have a halting oracle, and to make its job impossible we have a test program that is "made aware" of the halting oracle, and does the opposite of what the oracle says. Impossible problem for the oracle. But that then begs the question, how many potential applications of the halting problem will involve test subjects that actually know what the halting oracle thinks? How many test subjects even know about the halting oracle? For instance, how can a program that looks for counterexamples to the Goldbach conjecture know anything about your halting oracle? In these cases, the undecidability proof doesn't apply.

So the answer to your question is conceivably yes.

There are 6 mentions of the word Markov in the paper, not counting citations.

The search bar is soon to be hidden by default -- you'll have the option to turn it on. [1]

[1] - https://news.slashdot.org/story/17/09/08/2330232/firefox-57-...

[technical stuff] An algebra is just a vector space V with a bilinear operation * :VxV->V. [/technical stuff] There are plenty of interesting and intuitive algebras other than the stuff you get from the Cayley-Dickson constructions.

Some interesting algebras:

* you can have some fun making the imaginary unit i square to 0 instead of -1. The resulting algebra is called the dual numbers, and has some surprising properties. You can gain a bit of understanding of it by using analogies with the complex numbers.

* You can make i square to +1 without being equal to +1 or -1. Again you can gain some understanding using analogies with the complex numbers. It's perhaps not the most useful examples because it's isomorphic to R \oplus R.

* Another family of examples, a very important one actually, is the algebra of 2x2 or 3x3 or nxn matrices over the real numbers or the complex numbers.

The first two examples are useful for understanding the general concept of a quotient ring. They're hardly exhaustive, but they are easy to picture.

Now I can return to your claim about CD: What makes the Cayley-Dickson family significant is that it produces all the division algebras over the real numbers, which are the algebras for which division by nonzero elements is always possible.

[edit]

Needed to escape an asterisk. Third time lucky.

Corrected grammar.

> pdqsort is a hybrid sort; when it encounters apparently pathological input, it switches from a strategy resembling quicksort to heapsort—it doesn't share quicksort's worst case characteristics.

I understand how hybrid sorts work. I thought that would be clear enough. I guess when you're a stranger on the internet, people don't automatically trust you to know what you're talking about. I imagine this is even truer when you say something counterintuitive or controversial. In spite of learning that, I'm responding chiefly because of that quote.

> Your thesis is wrong: > > Heapsort has a variable runtime

Let's not get hung up on heapsort. My thesis is if you have an algorithm with a gap between the worst case and average case, then you shouldn't use it on the web. That gap might not manifest as gap in the big O -- it could be 4x slower in the worst case than the average case, and that would still be bad.

To see why, try imagining this world of pure evil:

You create a website that uses gapsort. Gapsort is an algorithm that is 4x slower in the worst case than it is in the average case, for a fixed value of n (the size of the input). On top of that, triggering the worst case by accident is hard. You deploy your site for several months, buy servers, and get a userbase. In your performance testing, you only encountered the average case, so you only provisioned hardware for the average case. Now imagine that suddenly all your users turn evil, and start triggering the worst case; this leads to a sudden 4x performance drop. You may have underprovisioned for this.

So my thesis is it looks like having differences from the worst case and average case is great, on average. But in a hostile world, that actually makes things more complicated. When doing empirical performance testing, you'll test for the average. Moreover the gap can be just 4x; this will not manifest as a difference between the big Os of the worst and average cases (as I've said previously).

Changing from quicksort to heapsort on some inputs may manifest as a performance gap between the QS case and fallback case. Maybe that's not such a good idea. In fact, maybe you shouldn't use any quicksort variant, even introsort, in a potentially hostile environment, because of the unavoidable average-to-worst-case gap. In introsort, that gap is merely a different coefficient, but it's still a gap.

I hope that wasn't too repetitive.

[edit] I deleted and reposted this because the edits weren't being applied.

[edit] Done it twice now.

Thanks for your reply.

> Your logic also would mean that any sorting function that is publicly facing (which is basically any interface on the internet, like a sorted list of Facebook friends) would need to use heapsort (which is 2-4 times as slow), as otherwise DoS attacks are simply done by constructing worst case inputs.

Why is that a wrong conclusion? It might be, I'm not a dev. But if I found myself caring about that sort of minutiae, I would reach exactly that conclusion.

Reasons:

* the paranoid possibility that enough users can trigger enough DoS attacks that your system can fall over. If this is likely enough, maybe you should design for the 2-4x worst case, and make your testing and provisioning of resources easier.

* a desire for simplicity when predicting performance, which you're losing by going your route because you're adding the possibility of a 2-4x performance drop depending on the content of the list. Ideally, you want the performance to solely be a function of n, where n is the size of your list; not n and the time-varying distribution of evilness over your users.

Finally, adding a fallback doesn't seem free to me, because it might fool you into not addressing the points I just made. That O(n^2) for Quicksort might be a good way to get people to think; your O(n log n) is hiding factors which don't just depend on n.

[Post-edit] I made several edits to the post below. First, to make an argument. Second, to add paragraphs. [/Post-edit]

Tl;dr version: It seems to me you should either use heapsort or plain quicksort; the latter with the sort of optimisations described in the linked article, but not including the fallback to heapsort.

Long version:

Here's my reasoning for the above:

You're either working with lists that are reasonably likely to trigger the worst case of randomised quicksort, or you're not working with such lists. By likely, I mean the probability is not extremely small.

Consider the case when the worst case is very unlikely: you're so unlikely to have a worst case that you're gaining almost nothing for accounting for it except extra complexity. So you might as well only use quicksort with optimisations that are likely to actually help.

Next is the case that a worst case might actually happen. Again, this is not by chance; it has to be because someone can predict your "random" pivot and screw with your algorithm; in that case, I propose just using heapsort. Why? This might be long, so I apologise. It's because usually when you design something, you design it to a high tolerance; a high tolerance in this case ought to be the worst case of your sorting algorithm. In which case, when designing and testing your system, you'll have to do extra work to tease out the worst case. To avoid doing that, you might as well use an algorithm that takes the same amount of time every time, which I think means heapsort.