Firstly, Kalman filtering is optimal, that is, it produces exactly the correct posterior distribution. As you mention, particle filters cannot achieve this.
It's a rough heuristic that to achieve a certain accuracy for a linear/Gaussian system with a particle filter, you need a number of particles exponential in the number of dimensions of the system. I feel like this could probably be stated more formally and shown, but I don't think I've seen anything in that vein. The Kalman filter, being simply matrix operations, should scale as the number of dimensions cubed.
So yes, Kalman filtering is computationally more efficient, and (obviously) more accurate.
I also wouldn't discount the fact that the Kalman filter is, in a sense, simpler than the particle filter for a linear/Gaussian system; you don't need to worry about resampling or setting a good number of particles, and you don't need to compute estimates of the mean/covariance statistics (which are sufficient since the posterior should be a Gaussian).
Under the same conditions of linearity and Gaussian noise you can get essentially optimal performance. Of course, why would you when the KF is so much more efficient.
They're usually used synonymously. Yes, Cantor's diagonal argument can still be used to show the uncountability of real numbers in a constructive setting.
It seems misleading to say that intuitionistic logic assigns statements to one of the two values, True or False. There's no symmetry between the notions of truth and falsity as there is in boolean logic.
You need to be very, very careful when talking about the size of the constructive reals. If you are working within constructive mathematics, if you describe the real numbers as setoids of Cauchy sequences with Cauchy-equivalence as the equivalence relation, then there are uncountably many real numbers. From a meta-theoretic perspective, it is obvious (as we are working in constructive mathematics) that every real number is in some sense "computable".
Your notion that there are countably many constructive reals probably comes from definitions of the constructive reals from within classical set theory, wherein you must internalize some notion of what it means for a real number to be constructible, and so you are, in a sense, working meta-theoretically. Then it is no surprise that the computable real numbers are countable. After all, Skolem's paradox says that, meta-theoretically, we could have countable models of the classical real numbers as well.
Additionally, meta-theoretically, we see that our definition of real numbers in constructive mathematics will also have a countable model when seen from the outside.
if you describe the real numbers as setoids of Cauchy sequences
with Cauchy-equivalence as the equivalence relation, then there
are uncountably many real numbers.
I start with computable sequences (or — if want — with turing machines), define natural numbers based on them, go to the rational numbers, define real numbers as a setoid of cauchy-sequences (note: all these sequences will be computable by the way we constructed them) of rational numbers, and end up with countably many. So, it depends on what you start your constructive world with. I see no way to start with something uncountable.
You talk about meta-theory and models. I never saw the reason to complicate things with that. Care to elaborate?
The reals one defines thee reals constructively in essentially the same way as one does classically. When the parent commenter says the reals in constructive mathematics are uncountable, he means that inside of a constructive system one can prove the statement
There does not exist a bijection between the natural numbers and the real numbers.
which is true. You are free to interpret constructive logic in various ways. If you interpret it as the logic of computable things, in which case this statement becomes interpreted as something like
There is no computable bijection between the natural numbers and the computable reals.
If you interpret it into classical logic, it becomes (now in the classical sense)
There is no bijection between the natural numbers and the reals.
ihm's response to you I think did a great job explaining what I meant to say, but let me elaborate further.
Just like you might define computable real numbers, you may similarly describe the "definable" real numbers, that is, those numbers which are uniquely specified by logical statements. You will inevitably find that the definable real numbers, like the computable reals, appear to be countable.
So the fact that something is computable, per se, isn't exactly what makes the real numbers countable rather than uncountable.
I use the vocabulary of meta-theory and models, because the practice of defining either the countable reals or the definable reals within a formal system looks a whole lot like defining a formal system within itself (i.e., metatheory). So the fact that the computable reals and the definable reals appear countable, is, at least to me, much like the statement that there are countable models of your favorite formal system.
HN doesn't allow comments with multiple parents, so I needed to choose one to reply to. ihm, please consider this comment also a reply to yours.
The more I talk about constructivism the less I feel it's adequate to label what I'm talking about, even though my approach to mathematics is completely constructive. Please don't treat every word I use as totally definite.
Mathematics is the science of formal reasoning. I call the rules of reasoning, that is the rules of manipulation of statements including their lexicon, syntax and semantic, a logic. I see intuitionistic logic as the most intuitive, universal and fruitful logic, in short: the logic.
To reason, we need something to reason about. Said somethings should be respresentable, so we can communicate about it. Let me call the things we reason about objects. What do we use to represent objects? Symbols, pictures, sounds, smells and many more things we have senses for. We transmit objects as a literal, or as an algorithm ("a turing machine") of how to recreate the object. All turing machines can be encoded with finite bit arrays.
It turns out we are able to make digital computers recreate symbols and pictures and sounds to a fidelity such that we can't notice any difference compared to the original. I see no fundamental difficulty besides physical limitations to recreate other literals. All literals in a computer can be encoded with finite bit arrays.
Finally, I conclude that finite bit arrays are the most general objects we can reason about; they have rich semantics by the possibility to interpret them as turing machines. What we end up with looks a lot like common programming languages.
Based on intuitionistic logic, finite bit arrays, and the ability to interpret them as turing machines, we can follow the canonical construction of the reals. In this world, every object is a finite bit array, plus some annotated interpretation ("a type"), which is just notation for a bigger finite array. There is simply no place for non-countability.
I long for a software that lets me mix logic and usual programming seamlessly, without unnecessary like meta-theories, meta-logic. Coq is near, but the programming is too unnatural.
One can reason about the logic of a Rust programm, discuss it with others, and even the compiler understands some of the meaning, but richer intuitionistic logic statements about the output or behaviour of the code are sadly beyond the compiler.
I'm about to start applying for my graduate studies of mathematics. Do you have any recommendations which university to apply to to research in the area I talked about?
This video is somewhat misleading. I appreciate the attempt at making Banach-Tarski accessible to a general audience, but it dwells on the wrong aspects of what makes Banach-Tarski interesting, making the construction look more like a magic trick with sleight-of-hand. I wish the video had at least mentioned the Axiom of Choice somewhere, as that is fundamentally what Banach-Tarski is about.
The sleight-of-hand comes in around 14:30 into the video, where we are told to create the sequence for an "uncountably infinite number of starting points." That's exactly the point where the construction is non-constructive, and the infamous Axiom of Choice is used. There is no construction - in the sense of constructive mathematics - that can achieve what is described at this point.
Banach-Tarski is not generally regarded as some deep fact about mathematics, a point the video mistakenly belabors. Rather, it is a consequence about particular axiomatizations of set theory which admit the Axiom of Choice. Banach-Tarski is only valid with the Axiom of Choice, and in fact that is the main interest in the paradox.
In my personal opinion, the Banach-Tarski paradox isn't much more enlightening than the simpler construction of the Vitali set (assuming the Axiom of Choice), which is a non-measurable set of real numbers (with Lebesgue measure, i.e., length).
Another part of the video I find misleading has to do with the hyper-dictionary, where he describes the hyper-dictionary by putting some parts of the dictionary "after" other parts which are infinitely long.
The putative applications of Banach-Tarski to physics are ridiculous. Uncountable sets are fundamentally unphysical. The Axiom of Choice serves mainly as a convenience to mathematicians when either a proof avoiding the Axiom of Choice would be more complicated, or so that mathematicians can state properties of objects which are set-theoretically larger than anything that can be relevant to physics anyways.
I think he did: you don't need real numbers to formulate classical physics. Everything measurable has finite precision so you can always get away without postulating that your limits actually converge to something.
Of course, the reality is that then you would wind up with awkward limit-taking machinery in your answers. Real numbers encapsulate that complexity so you might as well use them to simplify both the notation and manipulation of limits. But you don't need to.
Yep, this is what I meant to allude to, and you've worded it much better than I could have.
Perhaps a nice way to say it is that the mathematical objects necessary for physics that I can think of are separable (such as the real numbers). Basically, whenever you have uncountable sets, they come along with some topological structure which must be handled continuously.
There's even an argument that separability is sufficient for most of mathematics let alone physics (http://arxiv.org/pdf/math/0509245.pdf) but you're going to have to work very hard to persuade me that if we're going to describe any sets as physical then uncountable ones are less physical than countable ones.
The set of real numbers is uncountable. There are infinitely many members.
The set of natural numbers is countable. There are infinitely many members.
It would be better to say that infinite sets are fundamentally unphysical, since there are no actual infinities. Talk about uncountable versus countable is tangential.
I have to commend Michael Stevens (VSauce) for the courage to take on Banach-Tarski at all. I was surprised that someone could make it that accessible inside of 20 minutes.
I do agree that a "there is mathematical dispute [++] over whether this operation is valid" disclaimer could have accompanied the part where AoC was used.
[++] Side note: "mathematical dispute" doesn't mean what many non-mathematicians think it does. AoC isn't as "controversial" as some make it out to be. There is no disagreement over whether it's "true" or "false" in any Platonic sense. Rather, there is nearly universal acknowledgement that a valid mathematical system exists with AoC and that a valid mathematical system exists without it... and that both have useful properties. Mathematical dispute over an axiom means that a valid mathematics exists with or without the axiom-- not necessarily that mathematicians hold strong and divergent opinions on whether to include it.
As for the physical interpretations, he's right in that nothing that we know about physics rules out a Banach-Tarski-like behavior at the subatomic level. That said, it's obviously impossible to Banach-Tarski an orange or a ball of gold, since we'd have to literally split every atom. A macroscopic Banach-Tarski event is almost certainly impossible and would be, even with some unforeseen physical capability that made it possible, extremely expensive in terms of energy due to mass-energy equivalence.
One problem with introducing it the way the article does is that it's hard to see why the variance is never negative, and is zero exactly when the R.V. is constant.
This is a very important property, to say the least.
It would be better to say you measure the "energy" with
E x^2
but that this is not immune to level shifts, so you need to subtract some constant off first. And it so happens that the optimal constant to subtract off is our friend E x.
Edited to add: The notion of introducing the ideas of a sample space and a random variable (in the technical sense), as is done in the article, and at the same time being shy about calculus, is rather contradictory. That is, the intersection of
{ people who want measure-theoretic probability concepts }
It looks like an enthusiastic newbie with some clipart and an equation. Fair play for trying.
I would suggest adding the following.
1. What the poster above said.
2. The reason for the E[(x_{bar} - x_i)^2] choice. Why not E[|x_{bar} - x_i|]? Was it a mathematical convencience? Was it, perhaps, because Gauss had the integral of e_{t^2} from -Inf to plus Inf lying around in a letter from Laplace?
3. It is an equation with a square. Use a square somewhere.
4. The square root of the variance happens to be the horizontal distance between the mean and the point of inflection in the normal distribution. How cool is that?
I like (3) in particular. You could introduce, in a very simple way, the idea that the "error" (X - E X) is perpendicular to the "estimate" (E X). That's the two legs of the right triangle; the hypotenuse is "X" itself.
The treatment of Big O notation is not only misleading (and poorly conveyed) but wrong in several ways. Big O is an upper bound that does not need to be tight. The table displaying the "limit of N for 1 second (standard processor)" and the accompanying note that the chart will eventually become outdated is manifestly wrong and misleading. Big O ignores constant factors and so no such comparisons can be made. For any particular duration of time (or for any particular number of elements), an algorithm with complexity `O(f(N))` may be faster than one with complexity `O(g(N))` regardless of `f` and `g`. Big O is not something that can obsolesce.
Also, it is not necessary that there be a base case for recursion (only well-founded recursion). For instance, the Haskell definition
repeat :: a -> [a]
repeat x = x : repeat x
is a recursive definition but it has no base case. Of course, there can also be multiple base cases or other more complicated structures.
Saying unconditionally that all operations for a hash set or hash map are O(1) is wrong.
Opening quotation in LaTeX is accomplished by "``".
I also think that the comparison between the human brain and CPU is completely unjustified. Given that most people could not remember the sequence of results of 32 coin tosses, why shouldn't I say they have no greater than 4 bytes of memory? (For myself, I think the most appropriate unit of memory is "10 seconds of commonly spoken English language").
There are already so many terrific sources for learning algorithms that I don't understand why the author created this book. It is not only inaccurate, but more difficult to understand than other resources I have come across (e.g., Coursera).
In the type theory literature, it is rather the other way: Void is synonymous with the bottom type. I don't know who has first claim to the name "void", but from the type theory perspective, it is C, Java, et. al. who have it backwards.
It is in fact Markov; Markov just means that the probability distribution of the future depends only on the present, and so the past adds no additional information in conjunction with the present. That's certainly the case here.
This is an example of a Markov chain that is not aperiodic; what that means is that, given a starting node, at any point in time in the future, it will always be the case that it is impossible to be at a certain node. This ends up meaning that the Markov chain never ends up reaching a steady state; rather, its behavior is periodic!
fix some n in n. if my starting state is [1; 0] then the probability of the occupancy being [1; 0] after n cycles is either 1 or 0. If the starting state is [0; 1] then the probabilty of the occupancy being [1; 0] is exactly the opposite, so for a fixed point in the future, the probability is tightly past-dependent.
It's certainly worth looking at. I personally find Jaynes's acerbic commentary entertaining, although I imagine it grates for many. His overall view of probability is satisfyingly coherent, but I do not consider myself sufficiently expert to assess whether it is meaningfully better than the alternatives. And there are places where I believe he is just wrong, e.g. he seems to reject Bell's inequality and view quantum probability as just another case of limited information.
There are also times, like in the chapter linked in the parent, where his zeal is bothersome. He begins the discussion of ESP by saying it would be too dogmatic to assign a probability of 0 to ESP. But, when faced with the evidence, he just throws in a bunch of other possible hypotheses that can explain it:
Therefore, this kind of experiment can never convince me of the reality of Mrs. Stewart’s ESP; not because I assert Pf = 0 dogmatically at the start, but because the verifiable facts can be accounted for by many alternative hypotheses, every one of which I consider inherently more plausible than Hf, and none of which is ruled out by the information available to me.
Of course the choice of priors for those other hypotheses were subjective, and there's no limit on how many other hypotheses one might add to explain away unpleasant data. This strikes me as more rationalizing than rationalist.
Really? Do you actually think that Jaynes is being unreasonable when he assigns ESP a prior that is lower than "has some sort of trick" or some other thing that generally turns out to be the explanatory factor for a magician?
He's saying that ESP is an unlikely explanation. He's saying that it is Probably Something Else. The experimental data cannot distinguish them. That's why it's not compelling. It has very little to do with rationalization. It's a terrible test.
No, clearly the underlying mechanism that he describes is good. However, as he admits in the passage I quote, he is so unconvinced by the possibility of ESP that no tests of this sort could ever convince him. The issue isn't just that naive tests of ESP are easily cheated, either, because you can apply the same logic to more stringently controlled tests.
It just seems more honest to me to admit up front in this situation that you cannot be convinced of ESP (give it prior probability of 0) instead of playing these games to essentially shift the "dogmatism" onto the choice of alternative hypotheses and their prior probabilities (which seem chosen to enforce a posterior probability of ESP of ~0.)
Look. I'll explain it really simple. He's saying it has to be > 0, because he is unwilling to rule out ESP as a logical possibility. If he assigned it 0, no matter how good the experimental design was, and no matter what the test was, he would be unmovable from this position. 0 is forbidden if you want to accept it as a possibility. This is why he says this. He also is being honest about his appraisal of the general likelihood of ESP. It's very low. He doesn't bother to explain how low because it turns out it's IRRELEVANT.
You literally have to believe ESP is the most likely explanation among all the usual alternatives ALREADY in order to think it was ESP after ingesting the data, because the data in this test is not EVIDENCE for ESP, because P(E|sort of works ESP) and P(E|one of the assistants wore glasses and Stewart could see some reflections) or whatever your remotely plausible alternative - all look pretty identical.
It is not evidence, in the sense that you cannot do 500, 37,100, or a 1 million card guessing attempts in this setup with this level of detail and expect it to shift belief of a rational agent. The ratio between the priors of the usual suspects is going to look the same as your ratio of posteriors between all the hypotheses after the test.
In order to convince someone of ESP rationally, you need to demonstrate that it is extremely difficult to cheat under the test conditions, in the sense that P(E|trickery) goes down.
Your alternative theory ISN'T the null hypothesis. It's a garden variety non-magical trickster, which exist in great numbers, whereas nobody has yet seen even a single instance of ESP as it is normally meant.
> It is not evidence, in the sense that you cannot do 500, 37,100, or a 1 million card guessing attempts in this setup with this level of detail and expect it to shift belief of a rational agent. The ratio between the priors of the usual suspects is going to look the same as your ratio of posteriors between all the hypotheses after the test.
Exactly. When you suspect that the evidence is biased (or in other words, generated by a process other than genuine new physics or supernatural activity), more iterations of the process cannot give you much more evidence. What more iterations does is reduce sampling error from random variation, but it does nothing about systematic error. The idea that you can run a biased experiment 1000 times and get a much more accurate answer than if you ran it 10 times is an example of what Jaynes calls 'the Emperor of China' fallacy, which he discusses in another chapter (I excerpt it in http://www.gwern.net/DNB%20FAQ#flaws-in-mainstream-science-a... ).
That this is so surprising and novel is an interesting example of a general problem with null-hypothesis testing: when a significance test 'rejects the null', the temptation is to take it as confirming the alternative hypothesis. But this is a fallacy - when you reject the null, you just reject the null. There's an entire universe of other alternative hypotheses which may fit better or worse than the null, of which your favored theory is but one vanishingly small member.
What is necessary to show ESP specifically is to take all the criticisms and alternatives, and run different experiments which will have different results based on whether the alternative or ESP is true. (The real problem comes when it looks like the best experiments showing ESP are at least as rigorous as regular science and it's starting to become difficult to think of what exactly could be driving the positive results besides something like ESP: http://slatestarcodex.com/2014/04/28/the-control-group-is-ou... )
I understand all of this, and yes, plainly in the case of ESP cheating seems much more likely than genuine ESP. My point is that there's nothing in the overall process to prevent this sort of subversion:
* do an experiment;
* get result that doesn't comport with your beliefs;
* retroactively decide "aha, a hypothesis I hadn't considered!" and assign it a greater prior, thereby making it the thing for which you are actually generating evidence.
What I am trying to argue is that this last step is uncontrolled and highly gameable since there's no limit to the amount of possible hypotheses you could dream up (and thus you could keep fishing until you find one you like.) I don't feel that all of the maxent stuff later in the book does much to help you choose priors for this sort of thing.
Oh, part of that explanation assumes you know how to use Bayes' Theorem. If you don't, this doesn't look like a simple explanation, it probably looks like the ravings of a madman because I'm assuming you know a few of the properties and common manipulations of the formula.
> His overall view of probability is satisfyingly coherent, but I do not consider myself sufficiently expert to assess whether it is meaningfully better than the alternatives.
You're probably under-confident. I have read the first two chapters, and they just felt obvious to me. While I understand we could refine probability theory, I think we can say that anything that contradicts it is probably bollocks.
> And there are places where I believe he is just wrong, e.g. he seems to reject Bell's inequality and view quantum probability as just another case of limited information.
There is a part where he's definitely right, though: the so called "quantum probability" is not a probability at all. No matter how much it looks like a probability, it's something out there in the territory, and probability is in the mind. Besides, the idea that complex numbers (amplitude) could be probabilities is rather ridiculous. And of course, the then popular interpretation of quantum mechanics was crazy: it was either contradicting or denying the very equations that made so good predictions in the first place!
Now he could have criticized Many World as well, for it may seem it's a cop-out as well. We have reduced the Born statistics to an anthropic problem, but we haven't solved it yet.
Is that a full book? It seems that it has only first 3 chapters. However, I found the other chapters in the directory with the original submission, but they seem to weirdly overlap with content.
