It seems like any method for solving this problem could be interpreted in a Bayesian way: At any time, you consider all the different possible distributions each arm could have, and assign each a probability which is how likely you think that distribution is to occur.
The probabilities are initialized to some value (the "prior"), then when you pull the arm, you get some new information, which you use to update the probabilities based on evidence.
It would be interesting to try to see if you could analytically solve this problem for a simple family of distributions. For example, assume each lever produces Gaussian results, but has an unknown mean and SD. Set the prior to be that the means are normally distributed with mean 0 and SD 1, and the SD's are exponentially distributed with mean 1.
Your intuition is spot on. With this line of argument you will end up with Thompson Sampling [0]. TS is an old algorithm from the 1930s. It is disconcertingly effective, even when the underlying Bayesian assumptions are not correct. It is also extremely hard to analyze. This led to a weird state of affairs - TS gave excellent empirical performance but we could not make any theoretical statements about its efficacy. It is only very recently that this has changed.
I think that's how you derive UCB, but optimizing cumulative regret rather than finding the probability distribution directly. Pls correct me if I'm wrong
I'm thinking the baseball spinning counterclockwise when viewed from above will curve to the pitcher's right (the same direction shown by Trefil).
Basically friction will cause the ball to push air molecules near its surface in its direction of spin. So air molecules in front will fly off to the left. By conservation of momentum, the ball will be pushed to the right.
The same effect at the back of the ball will push the ball to the left. But there would be fewer air molecules behind the ball, because that's the space which has just been vacated by the ball. Air molecules haven't yet had time to rush in to fill the space behind the ball at the same density as they fill the space in front of the ball.
This makes the rightward push at the front stronger than the leftward push at the back, causing the ball to move to the right.
Now I'm going to finish reading the article and see if my hypothesis is correct.
Crud. I assumed the left and right side were symmetric and would cancel, but they're not -- the air's moving at different relative velocity on each side.
> real numbers. In an open interval like (0, 1), there is no single real number which is less than one but is greater than all other real numbers less than one.
The rational numbers are like this too.
All the rational numbers between 0 and 1 also increase arbitrarily close to 1 with no largest element. You can prove this by simple contradiction: For every rational number x < 1, there is another rational number y = (x+1)/2 with x < y < 1. So the set of rational numbers less than 1 also has no largest element.
Actually real numbers can be defined (axiomatized) in terms of the least upper bound property -- every set of real numbers that's bounded above has a least upper bound. So you could actually have a set S of rational numbers that gets arbitrarily close to something like sqrt(2) from below. S then has no rational least upper bound -- for every rational number x greater than or equal to every element of S, there is another rational number y greater than or equal to every element of S but smaller than x.
Note that a set of real numbers need not contain its upper bound -- as you noted, a bounded open interval doesn't contain its upper bound.
The sign-exponent-mantissa nature of IEEE format means (basically by design) that you have a much finer resolution near 0 (smaller absolute value) than you do away from 0 (larger absolute value).
We're talking about sin(x) with x ~ pi. In this situation the output's absolute value is much much smaller than the input's absolute value. So the output will have much finer resolution than the input.
The output being appreciably non-zero comes from the output having much higher resolution than the input. The output wouldn't be anywhere near small enough to be subnormal.
It's about time. I was just using ffmpeg today, wanted libx264 lossless encoding, noticed the deprecation message and lack of libx264 support in the Ubuntu package, recompiled from source.
Wow. This is epic. I totally had this exact idea a few years ago -- that every mathematically possible universe physically exists, with some probability distribution. I was thinking maybe the probability of finding yourself in a given universe is related to the length of the computer program that runs that universe. And also, of course, to the probability of intelligent life evolving in that universe (a formalization of the anthropic principle).
It's always neat when you discover you've independently invented an idea proposed by someone famous :)
Although, to be fair to Tegmark, he goes further than I ever did: "The predictions of the theory take the form of probability distributions for the outcome of experiments, which makes it testable." This is a natural consequence of the form of the theory, but I didn't really think in that direction -- but now that Tegmark's pointed it out, it seems like an obvious direction in hindsight.
I've been recommending this book left and right around these parts, but can't hurt to say it again: you should probably read "Permutation City."[1] As far as literature, character development and style goes, there is nothing much to it. As far as (hard-ish) scifi goes, it's a big deal. In a way, what MT calls MUH Egan calls "dust theory" (roughly). It's a very interesting exploration of the whole idea, and it involves cellular automata, etc etc.
There's also a short story of his, "Wang's Carpets" (which you can read online[2]) - it was later incorporated (as a chapter) into his book "Diaspora"[3] (which is also a great read that I've thoroughly enjoyed.)
> Although, to be fair to Tegmark, he goes further than I ever did: "The predictions of the theory take the form of probability distributions for the outcome of experiments, which makes it testable."
I wonder, though, if this is not a bit of a stretch. I certainly understand what he (and you) mean by probability distributions, but it seems to be there because he really wants to be able to call it a "scientific theory," which requires it to be falsifiable (<=> testable.) But, yeah, it's pretty neat!
> I was thinking maybe the probability of finding yourself in a given universe is related to the length of the computer program that runs that universe.
Now, can some of those programs run a (say, finite-tape-version-of) Turing machine[4] (can some of them not run it)? Does this have any implications (re: / in relation to the halting problem, for example)? I don't have the faintest idea. Tegmark has a thing to say about mathematically incomplete (in the Godel sense) universes, but again, I'm not sure how much of it is just him having fun. ;) (which is the best way of having fun, as far as I'm concerned.)
...anyway. Good stuff! Let's try and not go insane within our heads with these things. Then again, some insanity is always a good thing, imo.
editedit P.P.S. if you haven't, maybe also read the (very) short story of Borges, "The Library of Babel."[5] It's basically an articulation of the idea that a "description" of a universe is that universe. And a "description" can very well be thought of as a program. And if you imagine a multidimensional "computational-symbol-space," a "path" to that program/description (first choose this symbol/predicate, then that one..) is that program (and, by extension, "kinda-is" that particular universe.) These ideas are not new in themselves in the very least. e.g. I'm still yet to try and honestly delve into Kant's "Critique of Pure Reason," which actually addresses some of that stuff (in its own very particular vocabulary and context.) Also, lots of stuff to read from the theoretical CS side of things. And mathematics (Yoneda lemma in category theory, and other things which I like to pretend to understand!)
This comment is mostly speaking to the author of the parent post, who seems to be a founder of prmatch.com [1].
I think OP represents an underserved market -- people who have a great product idea [2] and want to crowdfund, but don't have a clue about how to do marketing. For crowdfunding, it would be very helpful if the PR folks are rewarded with a percentage [3] of the crowdfunding proceeds when the campaign is successful, rather than cash up front -- this fits the "pay-for-performance" philosophy. And it helps entrepreneurs get another form of feedback -- if no marketers are interested in your product, it may be a sign that your product is so bad it's unmarketable, or your crowdfunding goal is too high, or your reward for the marketer is too low.
Also, "creating a press wishlist" assumes the customer knows something about marketing already. This may be fine for customers who are migrating from other advertising options, but it sounds like a place where people like OP would need hand-holding. I know little about marketing myself, so if I was hiring a marketing expert, I would certainly want to get their input as to the most cost-effective places to put ads or try to get press.
I guess it comes down to whether you're trying to target (A) people who are familiar with marketing, already know what they want, and are just having trouble finding it, or (B) people who have good products but are total noobs when it comes to marketing.
I think types (A) and (B) are both big enough markets to justify your platform catering to both of them, especially if the PR freelancers have a way to distinguish between (A) and (B) type clients (some freelancers might only want to work with one type of client, and it may be a negative experience all around if they get matched to the other type). But it seems like the current website copy is targeted more toward the (A) type.
[2] Judging from other comments in this thread, the OP's product idea may need some refinement.
[3] A fixed reward amount would also be possible, but a percentage reward encourages the marketer to keep working and hit stretch goals after the minimum funding goal is reached.
The key is a "hook," a goal, a source motivation. Seeing how a particular technology enables new capabilities and applications is a powerful encouragement to learning it, even for professional adult hackers.
"Make your own computer games" is a hook with many kids (not all). I suggest writing your own implementation of a few very simple games (Hangman, Yahtzee, Boggle, ...) as "lesson prep," this way you're familiar with the strategy and can identify stumbling blocks, needed libraries, etc. I suggest sticking with print / terminal at first (GUI / web stuff introduces a lot of baggage since the model is more complicated).
Then sit next to your daughter and tell her what to type. Of course you should explain what your code does as you go along, and you should ideally do this without looking at your earlier implementation. This helps emphasize the thought process -- you're not just copying magic words from somewhere else, you're using your mind to figure out the right magic words for what you want to do. You should also use an iterative development method -- frequently run it and see the product slowly taking shape.
The initial lessons are more about driving home the fact "You can type in these magic words and make the computer do anything you want" than about the precise details of what the magic words for your particular programming language are, or what they represent. Once the kids realize what sorts of things magic words can do, they are then motivated to learn the particular details. This makes it way easier to teach them, and also encourages them to seek resources on your own.
Source: This was how my dad introduced me to programming at age 5-6. It worked :)
Also, buy the book at http://www.laurenipsum.org/ -- it makes a great bedtime story. Hackers of any age will really enjoy it.
This is really neat. Somehow I always assumed realloc() copied stuff instead of using the page table.
But say you have 4K page table size. You malloc() in turn a 2K object, a 256K object, and another 2K object, ending up with 2K, 256K, 2K in memory. Then your 256K is not aligned on a page boundary. If you realloc() the 256K it has to move since it's surrounded by two objects. When you do that, you'll wind up with the two pages on the end being mapped to multiple addresses. Which is actually just fine...Interesting...
The libc memory allocator does not simply hand out memory contiguously. In your example, the 256K block will end up being 4K aligned.
In fact, that's what the article already explains: the large alloc will just end up being passed through to the kernel, which only deals at page granularity.
What the article revealed to me is that there is no guarantee a contiguous block of allocated virtual memory will be backed by contiguous physical memory. In hindsight, that should be obvious.
But what does this mean for locality? Will I be thrashing the cache if I use realloc frequently? Do I even have the promise that malloc will return unfragmented memory?
Do I even have the promise that malloc will return unfragmented memory?
What do you mean by this? malloc returns memory that is contiguous in the virtual address space. It may not be contiguous in the physical address space, but that should be irrelevant for cache behavior.
Will I be thrashing the cache if I use realloc frequently?
I suppose. But if you use realloc, you should anyway ensure that you realloc geometrically growing chunks of memory (e.g., whenever you need a new buffer, you multiply its size by a constant factor like 1.2 instead of just adding an element at a time). As a result, realloc() should be infrequent enough that it normally doesn't matter.
TLDR: You can't write the first compiler for a language in the language. However, you can write the second compiler in the language and use the first compiler to compile it.
If you already have a compiler in the language you're compiling, you can update the compiler with new features by the following process, called "bootstrapping". This process is used in gcc for example:
1. Use the old binary version to compile the new source version.
2. Use the binary produced in step 1 to compile the new source version.
3. Use the binary provided in step 2 to compile the new source version.
The results of stages 2 and 3 should be the same (assuming the old and new compilers assign the same semantics to the compiler source code and don't have non-determinism, e.g. using wall-clock time to determine when to stop searching for optimizations).
The bootstrap process can't be used on the first compiler for a brand-new language, because there is no "old compiler" that can be used in stage 1. The only way around this is to write the first compiler in a different language that already exists.
Of course, if a self-hosted compiler is your goal, you can afford letting the very first compiler (the one written in another language) be limited, "dirty," or "hacky". You don't have to implement the entire language in the first compiler; the first compiler just has to support enough of the new language to allow you to write the second compiler.
Anyway, once you have the first compiler, you write the first version of the second compiler in whatever subset of the language the first compiler supports. Once the first compiler builds the first version of the second compiler, the first compiler is no longer needed; you can add all new features to the second compiler only.
New versions of the second compiler (perhaps supporting more language features) can now be produced by bootstrapping. Of course, you can also use the second compiler to compile a totally different compiler implementation written in the new language (this would be the third compiler for the new language).
The probabilities are initialized to some value (the "prior"), then when you pull the arm, you get some new information, which you use to update the probabilities based on evidence.
It would be interesting to try to see if you could analytically solve this problem for a simple family of distributions. For example, assume each lever produces Gaussian results, but has an unknown mean and SD. Set the prior to be that the means are normally distributed with mean 0 and SD 1, and the SD's are exponentially distributed with mean 1.