标签: randomizer

Call it Hell, Call it Heaven, it's a probable twelve to seven that the guy's only doing it for some doll— Stubby Kaye and Johnny Silver, Guys and Dolls, 1955 In this column, we will tackle parameter estimation. This discipline is based on the fact that our knowledge of the state of any real-world system is limited to the measurements we can take—measurements that are inevitably corrupted by noise. Our challenge, then, is to determine the true state of the system, based on these imperfect measurements. The general idea is to take more measurements—usually many more—than the minimum needed to determine the system state. Then you crank the data through an algorithm that mitigates the effect of noisy data. The method of least squares is inherently a batch processing sort of method, where you operate on the whole set of data items after they've all been collected. Of course, the whole point of the method of least squares is to smooth out noisy measurements. But I've never addressed the nature of the noise itself. That has to change. In this column, we're going to look noise in the eye, and deal with its nature. We'll discuss the behaviour of random processes , introducing notions like probability and probability distributions . For reasons that will become clear, we'll focus like a laser on a thing variously called the bell curve , Gaussian distribution , or normal distribution . Now, I've been dealing with problems involving the normal distribution for many decades. But to my recollection, no one ever derived it for me. They just sort of plunked it down with little or no explanation. This would usually be the place where I'd start deriving it for you, but I'm not going to do that either. The reason is the same one my professors had: The classical derivation is pretty horrible, involving power series of binomial coefficients. Instead, I'm going to take a different approach here. I'm going to wave my arms a lot, and give you enough examples to convince you that the normal distribution is not only correct, but is inevitable. The nature of noise Whenever I measure any real-world parameter, there is one thing I can be sure of: the value I read off my meter is almost certainly not the actual value of that parameter. Some of the error may be due to flaws in the instrument—scale factor and bias errors, linearisation errors, quantisation errors, temperature sensitivities, etc. Given a thorough enough calibration process (and enough patience), I can compensate for those kinds of errors. But there's one kind of error I have no chance of correcting for: the random noise that's always going to be there, in any real-world sensor. Whenever I try to measure some state variable x, I don't get its true value; I get the measured value   (1) Where n is the noise, changing randomly with time. If I take only a single measurement, I can say nothing at all about the true value of x , because I have no idea what the instantaneous value of n is. But there is a way we can make an educated guess as to the value of x : measure it more than once. That's the whole idea behind the method of least squares. Why would we calculate the parameters describing the nature of the noise—like the mean , variance , and standard deviation —if we're trying to make the noise go away? The answer is, we have this nagging suspicion that, by understanding the nature of the noise, we may be able to make a better estimate of x . At the very least, we can use these parameters to calculate error bounds for the measurements. If there's any one thing that sets the Kalman filter apart from all other approaches, it's the fact that it doesn't just maintain a running estimate of the noise parameters; it uses them to get a better estimate—an optimal one, in fact—of the state variables. That being the case, we find ourselves highly motivated to learn more about noise. Random thoughts Where does noise come from, anyhow? For our purposes, we'll say that it comes from some random process , which runs independently of the dynamic system. But what does that term mean, exactly? That question has an easy answer. A random process is one whose output is unpredictable . In fact, "unpredictable" is a very synonym for "random". So in our imagination, at least, we can envision some random process—a physical machine, if you will –that's free-running in our otherwise pristine, state-of-the-art embedded system. The random process has no apparent purpose except to muck up that system. But since that process is, by definition, unpredictable, how can we get a handle on its behaviour? One thing's for sure: Although you might get some insight using a spectrum analyser, you're not likely to learn much by watching white noise marching across the face of your oscilloscope. If we're going to learn anything at all about the noise generated by a random process, we need to be able to study its outputs, one by one. We need the equivalent of a software break point that will let us freeze the process in place. We need a single-step "randomizer" that gives us one, and only one, new value every time we push its "go" button. Fortunately, suitable candidates are all around us. As a kid, I played board games like Monopoly , Risk , or the Game of Life . Such games depend on the use of "randomizers" like coins, dice, or spinning arrows. Or, come to think of it, spinning bottles. The unpredictability adds to the enjoyment of the game. These primitive game randomizers have three things in common. - When "activated" by a flip, roll, or spin, they must eventually come to rest in a stable state, so we can read the results. - There must be more than one possible end state. Multiple values are sort of the point of the whole thing. - The results must be unpredictable. I should note that, because they are all mechanical devices, none of these gadgets are truly random. Being mechanical, they all obey Newton's laws of motion. If we could know, in advance, not only the air density, temperature, etc., but also the impulse given by the player's toss, roll, or spin, we could theoretically predict exactly what the end state would be. The thing that makes the gadgets useful as randomizers is that we can't and don't know these things. We trust the devices to be fair because we assume that no ordinary human is so skilled that he can flip a coin, and make it come up heads every time. Don't bet the farm on that last assumption. People can do remarkable things, especially if there's money to be made. Even so, we can analyse the nature of the devices by assuming that the results are both fair and random. Part 2 of this series delves further into the concept of probability.  

Call it Hell, Call it Heaven, it's a probable twelve to seven that the guy's only doing it for some doll— Stubby Kaye and Johnny Silver, Guys and Dolls, 1955 This column delves on parameter estimation, a discipline is based on the fact that our knowledge of the state of any real-world system is limited to the measurements we can take—measurements that are inevitably corrupted by noise. Our challenge, then, is to determine the true state of the system, based on these imperfect measurements. The general idea is to take more measurements—usually many more—than the minimum needed to determine the system state. Then you crank the data through an algorithm that mitigates the effect of noisy data. The method of least squares is inherently a batch processing sort of method, where you operate on the whole set of data items after they've all been collected. Of course, the whole point of the method of least squares is to smooth out noisy measurements. But I've never addressed the nature of the noise itself. That has to change. In this column, we're going to look noise in the eye, and deal with its nature. We'll discuss the behaviour of random processes , introducing notions like probability and probability distributions . For reasons that will become clear, we'll focus like a laser on a thing variously called the bell curve , Gaussian distribution , or normal distribution . Now, I've been dealing with problems involving the normal distribution for many decades. But to my recollection, no one ever derived it for me. They just sort of plunked it down with little or no explanation. This would usually be the place where I'd start deriving it for you, but I'm not going to do that either. The reason is the same one my professors had: The classical derivation is pretty horrible, involving power series of binomial coefficients. Instead, I'm going to take a different approach here. I'm going to wave my arms a lot, and give you enough examples to convince you that the normal distribution is not only correct, but is inevitable. The nature of noise Whenever I measure any real-world parameter, there is one thing I can be sure of: the value I read off my meter is almost certainly not the actual value of that parameter. Some of the error may be due to flaws in the instrument—scale factor and bias errors, linearisation errors, quantisation errors, temperature sensitivities, etc. Given a thorough enough calibration process (and enough patience), I can compensate for those kinds of errors. But there's one kind of error I have no chance of correcting for: the random noise that's always going to be there, in any real-world sensor. Whenever I try to measure some state variable x, I don't get its true value; I get the measured value   (1) Where n is the noise, changing randomly with time. If I take only a single measurement, I can say nothing at all about the true value of x , because I have no idea what the instantaneous value of n is. But there is a way we can make an educated guess as to the value of x : measure it more than once. That's the whole idea behind the method of least squares. Why would we calculate the parameters describing the nature of the noise—like the mean , variance , and standard deviation —if we're trying to make the noise go away? The answer is, we have this nagging suspicion that, by understanding the nature of the noise, we may be able to make a better estimate of x . At the very least, we can use these parameters to calculate error bounds for the measurements. If there's any one thing that sets the Kalman filter apart from all other approaches, it's the fact that it doesn't just maintain a running estimate of the noise parameters; it uses them to get a better estimate—an optimal one, in fact—of the state variables. That being the case, we find ourselves highly motivated to learn more about noise. Random thoughts Where does noise come from, anyhow? For our purposes, we'll say that it comes from some random process , which runs independently of the dynamic system. But what does that term mean, exactly? That question has an easy answer. A random process is one whose output is unpredictable . In fact, "unpredictable" is a very synonym for "random". So in our imagination, at least, we can envision some random process—a physical machine, if you will –that's free-running in our otherwise pristine, state-of-the-art embedded system. The random process has no apparent purpose except to muck up that system. But since that process is, by definition, unpredictable, how can we get a handle on its behaviour? One thing's for sure: Although you might get some insight using a spectrum analyser, you're not likely to learn much by watching white noise marching across the face of your oscilloscope. If we're going to learn anything at all about the noise generated by a random process, we need to be able to study its outputs, one by one. We need the equivalent of a software break point that will let us freeze the process in place. We need a single-step "randomizer" that gives us one, and only one, new value every time we push its "go" button. Fortunately, suitable candidates are all around us. As a kid, I played board games like Monopoly , Risk , or the Game of Life . Such games depend on the use of "randomizers" like coins, dice, or spinning arrows. Or, come to think of it, spinning bottles. The unpredictability adds to the enjoyment of the game. These primitive game randomizers have three things in common. - When "activated" by a flip, roll, or spin, they must eventually come to rest in a stable state, so we can read the results. - There must be more than one possible end state. Multiple values are sort of the point of the whole thing. - The results must be unpredictable. I should note that, because they are all mechanical devices, none of these gadgets are truly random. Being mechanical, they all obey Newton's laws of motion. If we could know, in advance, not only the air density, temperature, etc., but also the impulse given by the player's toss, roll, or spin, we could theoretically predict exactly what the end state would be. The thing that makes the gadgets useful as randomizers is that we can't and don't know these things. We trust the devices to be fair because we assume that no ordinary human is so skilled that he can flip a coin, and make it come up heads every time. Don't bet the farm on that last assumption. People can do remarkable things, especially if there's money to be made. Even so, we can analyse the nature of the devices by assuming that the results are both fair and random. Part 2 of this article delves further into the concept of probability.