It recently occurred to me that calculus is really about finding good local polynomial approximations of functions. The derivative is often first introduced as finding the slope of a function "at a point". What this of course really means is we want to find the slope of the line which best locally approximates the function within a sufficiently small region of that point. When we learn about second derivatives we are told that we are simply taking the derivative of the first derivative which is true enough. But what we are really doing is we are finding the coefficient of the x^2 term in the best local quadratic approximator of the function. In general taking derivatives of a function just means finding the best local polynomial approximators and then looking at the appropriate coefficients for the order of derivative you want.
Of course in practice it goes exactly the other way. If you want a good polynomial approximimation of a function around a point you use the taylor series expansion of the function which you build up from its derivatives.
Monday, July 13, 2009
Intelligence and Delay
You know all this thinking about q-learning has made me have a new perspective on the nature of delayed rewards. If you go around in psychological circles you will probably hear the term delayed gratification instead of delayed reward which is used in AI. There was a study done wherein children were asked to choose between eating one marshmallow now or getting 2 to eat when the researcher returned in 15 minutes. At any time before the 15 minutes were up the child could ring a bell and the researcher would come back and give the child one marshmallow but would not get the second one. The results of the study showed that those children who held out for the full 15 minutes at age 4 had SAT scores an average of 210 points higher than those 4 year olds who held out for only 30 seconds.
I remember hearing about a study very similar to this although I am pretty sure the study I heard of actually involved IQ tests. When I first heard this sort of result I thought it was interesting though not terribly surprising. Delayed gratification seemed like a perfectly logical effect of higher intelligence. The way I thought about the correlation between the ability to delay gratification and intelligence was simply that smarter people better realized the benefit of the delay. I now think this is very probably almost entirely wrong. The arrow of causation very probably goes completely the other way. After all the desirability of 2 marshmallows over 1 was apparently very clear to these children. It isn't really that only the smart ones figured out that 2 marshmallows is better than 1 or even that (as I thought) that the smarter ones can better understand and judge how much better the 2 marshmallows are. If our brains work anything at all like reinforcement learning machines (and I think they do) then the point is that people with smaller discount factors are smarter! A discount factor is sort of a means by which you can control the level that a reinforcement learning agent prefers rewards sooner to larger later rewards. In theory we don't really want a discount factor at all but in practice it is actually helpful and to some extent necessary to have one. In essence the problem is that if you don't have a discount factor then your reward estimates don't necessarily converge but they do converge if you do have a discount factor. In fact the smaller your discount factor (meaning the more you prefer short term to long term rewards) then the faster the convergence of the value estimates.
So maybe it isn't that delayed gratification is a side effect of higher intelligence. Maybe intelligence is a side effect of delayed gratification!!! In fact I think that a useful (if not necessarily the best) definition of intelligence might be "the ability to delay reward"
I remember hearing about a study very similar to this although I am pretty sure the study I heard of actually involved IQ tests. When I first heard this sort of result I thought it was interesting though not terribly surprising. Delayed gratification seemed like a perfectly logical effect of higher intelligence. The way I thought about the correlation between the ability to delay gratification and intelligence was simply that smarter people better realized the benefit of the delay. I now think this is very probably almost entirely wrong. The arrow of causation very probably goes completely the other way. After all the desirability of 2 marshmallows over 1 was apparently very clear to these children. It isn't really that only the smart ones figured out that 2 marshmallows is better than 1 or even that (as I thought) that the smarter ones can better understand and judge how much better the 2 marshmallows are. If our brains work anything at all like reinforcement learning machines (and I think they do) then the point is that people with smaller discount factors are smarter! A discount factor is sort of a means by which you can control the level that a reinforcement learning agent prefers rewards sooner to larger later rewards. In theory we don't really want a discount factor at all but in practice it is actually helpful and to some extent necessary to have one. In essence the problem is that if you don't have a discount factor then your reward estimates don't necessarily converge but they do converge if you do have a discount factor. In fact the smaller your discount factor (meaning the more you prefer short term to long term rewards) then the faster the convergence of the value estimates.
So maybe it isn't that delayed gratification is a side effect of higher intelligence. Maybe intelligence is a side effect of delayed gratification!!! In fact I think that a useful (if not necessarily the best) definition of intelligence might be "the ability to delay reward"
Monday, July 6, 2009
Learning stuff is rewarding
I have spent a great deal of time over the past few months thinking about Q-learning and other types of reinforcement learning. In a reinforcement learning problem you have a reward function which is given to to you as part of the problem and then you go about trying to maximize your reward. When it comes down to it though ultimately the reward function is something that a general AI would have to come up with on its own. As humans we are capable of figuring out what is good and what is bad and by how much. the reward function of each individual is rather unique, one person might find reading superman comics highly rewarding and another find it to be a complete waste of time. Although I don't really have much to say as for what one should do to try and create a good general reward function for human level intelligence. That doesn't mean, however, that I don't have some interesting ideas that could be turned into interesting experiments.
The best idea I have is to give rewards for learning the correct Q-values which we add onto the usual rewards. Lets say that for the moment we are working in a finite mdp for which we already have available the real values for each state. Then we could use the real values for each state to give a reward or punishment to the Q-learner based on how close their Q values are to the real values. This would be an awfully interesting way of encouraging exploration. In more general scenarios of course we would not have the true values available (after all if we do have them available why do we care about doing q learning?). So instead we would have to use some sort of heuristic which would give us a basic idea of how good our q values are at the moment. We could for instance just look at the rate of change of our q values and a low rate of change would be associated with good q-values.
The best idea I have is to give rewards for learning the correct Q-values which we add onto the usual rewards. Lets say that for the moment we are working in a finite mdp for which we already have available the real values for each state. Then we could use the real values for each state to give a reward or punishment to the Q-learner based on how close their Q values are to the real values. This would be an awfully interesting way of encouraging exploration. In more general scenarios of course we would not have the true values available (after all if we do have them available why do we care about doing q learning?). So instead we would have to use some sort of heuristic which would give us a basic idea of how good our q values are at the moment. We could for instance just look at the rate of change of our q values and a low rate of change would be associated with good q-values.
Conservation Laws
Sometimes it seems really amazing to me that energy is conserved exactly. Although it is possible that energy is only conserved approximately but to an incredible degree I think I'm going to go with occam on this one and say that energy must be conserved exactly. Energy is not the only thing though Also rotational and linear momentum and electric charge and baryon number and.... All this stuff remains completely unchanged in time although it wouldn't really surprise me to learn somewhere down the line that baryon number is not really conserved and to a lesser extent I could believe that electric charge might also not be conserved and there are a bunch of other conservation laws that I don't really understand so I should just keep my mouth shut about those particulars.
If you think too long and hard about the conservation of linear momentum you eventually come to the conclusion that it is a consequence of the homogenous nature of space (thank you Emmy Noether) and the conservation of angular momentum is due to the isotropy of space. I often like to think that perhaps our notion of completely closed dimensions within the multiverse is not at all true. In a multiverse it seems to me that the closest dimensions should overlap with one another. There would be no discernible difference between such dimensional neighbors and so there would be no reason for this overlap to cause problems. However I worry sometimes about this world view because it would seem to me that such an overlap between dimensions would suggest a tiny amount of leeway with respect to the conservation laws. Of course the laws would still hold absolutely but it would just be that the conservation would have to be smeared over all universes in order to survive. But such non-conservation events it would seem to me would very probably already have been observed. I don't have a solution though, it is just a troubling challenge for the view I hold of the multiverse.
If you think too long and hard about the conservation of linear momentum you eventually come to the conclusion that it is a consequence of the homogenous nature of space (thank you Emmy Noether) and the conservation of angular momentum is due to the isotropy of space. I often like to think that perhaps our notion of completely closed dimensions within the multiverse is not at all true. In a multiverse it seems to me that the closest dimensions should overlap with one another. There would be no discernible difference between such dimensional neighbors and so there would be no reason for this overlap to cause problems. However I worry sometimes about this world view because it would seem to me that such an overlap between dimensions would suggest a tiny amount of leeway with respect to the conservation laws. Of course the laws would still hold absolutely but it would just be that the conservation would have to be smeared over all universes in order to survive. But such non-conservation events it would seem to me would very probably already have been observed. I don't have a solution though, it is just a troubling challenge for the view I hold of the multiverse.
Sunday, July 5, 2009
Aliens and Pictures
It is extremely interesting that our eyes can be so very effective in sorting out spectral information even while they are so easily fooled. I don't exactly know what our eyes do in order to get spectral information but if you stop and think about it for a second it is really pretty amazing that we can fool our eyes into seeing any color we like simply by combining three wavelengths of light with different intensities. It is a rather profoudnly odd thought to realize that all of our nice colorful pictures might turn out to be completely unrecognizable for some alien species whose eyes work on a slightly different heuristic in order to extract spectral data from whatever they are looking at. Line art and the like would no doubt still be recognizable and print would also probably be easily seen correctly (if not understood) but a picture of a flower would likely be percieved by some other entity as some strange color distorted and possibly totally unrecognizable blob of primary colors.
Saturday, July 4, 2009
Happy fourth
I'm just kicking back and relaxing today. In fact this is all I'm going to write for my post today. Happy fourth everyone!
Friday, July 3, 2009
approximate Q learning
So usually if a q learning problem is interesting it will have too many states to make it practical to keep track of the value of each individual state separately. So in approximate q learning you replace states with a set of features of the state and then you try to learn a value function on those features. So for instance in chess instead of keeping track of the value of each board configuration (since there are about 35^50 of them) you keep track of only a few features of the board configuration. You might for instance keep track of the total number of squares your pieces are attacking and the total number of squares your opponent is attacking. In general if your pieces are attacking a larger number of squares than your opponent then that denotes a board position that is good for you. In the case of normal linear approximation q learning you assume that the value function associated to a feature is a linear function through the origin. So say you find on one q learning update step that your reward and end feature state evaluation give you a value of 10 for a feature value of 5 then you would expect the value function for that feature to be a line with a slope of 2. Generally every time you make an observation you would nudge the slope of the function a bit towards the slope that you observe.
A linear function through the origin does not seem to me to be a particularly hopeful candidate for being able to accurately describe a utility function. In fact if I were to choose a family of one parameter functions to try and describe a utility functions I would probably go for exponential decay. (since sparsity is a good thing maybe this is in fact exactly what I should do) But for my wavelets end of term project last semester I decided that it might be more interesting to instead allow for totally general utility functions but try and make good guesses by assuming that they are sparse in a wavelet basis. With that assumption you could even use compressive sensing in order to make efficient use of your observations and then even if you are wrong about the sparsity of the utility function in the wavelet basis thats ok because you still have the ability to learn an arbitrarily good approximation of that function.
I actually implemented said learning algorithm and used it on the pacman problem but it kinda sucked. My wavelets professor thought that the work was cool enough that I might want to pursue publication of some sort. I have been talking to Hal my AI professor and he also seems to think it is potentially publishable. So possibly the aftermath of the pacman competition could also give me my first publication!
A linear function through the origin does not seem to me to be a particularly hopeful candidate for being able to accurately describe a utility function. In fact if I were to choose a family of one parameter functions to try and describe a utility functions I would probably go for exponential decay. (since sparsity is a good thing maybe this is in fact exactly what I should do) But for my wavelets end of term project last semester I decided that it might be more interesting to instead allow for totally general utility functions but try and make good guesses by assuming that they are sparse in a wavelet basis. With that assumption you could even use compressive sensing in order to make efficient use of your observations and then even if you are wrong about the sparsity of the utility function in the wavelet basis thats ok because you still have the ability to learn an arbitrarily good approximation of that function.
I actually implemented said learning algorithm and used it on the pacman problem but it kinda sucked. My wavelets professor thought that the work was cool enough that I might want to pursue publication of some sort. I have been talking to Hal my AI professor and he also seems to think it is potentially publishable. So possibly the aftermath of the pacman competition could also give me my first publication!
Wednesday, July 1, 2009
Q-Learning
A Markov Decision Process MDP is defined by a set of states together with a set of allowed actions for each state a transition model which gives the transition probabilities between states when an action is taken and finally a reward model which gives a numerical reward for any (beginning state, action, end state) triple. A great many things can be described as MDP's Pacman for instance is an MDP. In fact just about every game is an MDP. Games with hidden information are POMDP's that is Partially Observable Markov Decision Processes.
If you want to win a game one way of doing it is treating the game as a MDP and then try to solve for the optimal value function over the states. The optimal value function on the states is the expected total cumulative value of all the rewards you can expect by acting optimally once in that state. Since a lot of games don't have an absolute stopping point beyond which you can't move generally you use a discounted reward model instead which basically means you prefer short term rewards to long term rewards to some extent. To figure out what to do in a MDP you can try to learn the transition model for the states and learn the reward model and from there you can try to solve the MDP to get the optimal value function.
Because trying to learn the transition model as well as the rewards is kind of a pain a popular alternative is to instead try to learn values over all pairs of actions and states, this is called Q learning. In Q-learning what you do is you keep track of what you think the value of any particular state is and then pick an action going from that state and update the value of the state action pair composed of the state you came from and the action you took based both on your current belief about the value of the state you transitioned into (which you can find by taking the maximum of the Q values of the new state) and any rewards you might have gotten along the way. Viola! you have a working means of picking actions in any state, you just look at the Q values and pick the action associated to the one with the highest Q value.
Sorry if this explanation is horrible (because it is) you should probably look it up on wikipedia or something or if you really care then google "sutton and barto reinforcement learning" and you can read a book about it online.
Now my beef with Q learning is this, in game theory you spend a bunch of time figuring out that pure strategies optimally solve only a very small fraction of games. I am talking here about two player zero sum games. Actually my beef is not so much with Q learning in general tasks but specifically in the case of two player zero sum games. Consider the game paper rock scissors. There are three strategies namely the strategy rock the strategy scissors and the strategy paper. A q learner set loose on this game would at first try something at random say paper and win because their opponent chose rock. Now the q-learner thinks that paper is the best strategy because the first time it tried it it won so next time around it tries it again and loses because their opponent chose the strategy scissors. The point is that someone else who knows that their opponent is a q-learner will know that the q-learner will tend to avoid whatever they just chose if they lost with it and tend to pick whatever they just won with over again. So q-learners fail at figuring out RPS. From a game theoretic standpoint what a deterministic q-learner is doing is assuming that every game has a saddle point (which is to say it has an optimal pure strategy). A popular alternative to the deterministic Q learner is a Q learner which chooses between different options by not choosing the "best" Q value but rather choosing from among the different actions using a boltzmann distribution with some temperature. The lower the temperature the closer the Q-learner is to deterministic but with any finite temperature a boltzmann (or softmax as they are actually called) Q learner will learn to play RPS correctly eventually. However the current wisdom is to use the temperature of the boltzmann Q learner as simply a means to allow for convergence and then limiting the temperature to 0 (meaning making the thing become deterministic). But from my perspective the temperature is clearly a feature. In fact I wonder if it might not be the case that picking a finite "equilibrium" temperature for each state would actually yield the correct optimum game theoretic mixed strategy. I don't really have any reason to believe that the distribution over the actions would converge to values in the appropriate way so that you could use the boltzmann distribution to get the correct mixed strategy but it is just so pretty that even if it isn't true it couldn't hurt to apply it and see how it goes.
Now that I have been thinking about it a bit more the pretty idea is sunk or at the very least incomplete. That is because the whole point of optimal mixed strategies is that the expected payoff of following each pure strategy is the same as all the others (assuming that the opponent is playing according to their optimal mixed strategy). So if the Q learner were in fact to come to learn the optimal values for each action/strategy it would learn that they were all the same. And yet we shouldn't allow it to choose between them with equal probability or we would not be acting optimally. I guess even trying to do something fancy like that the normal Q value system is just sunk as far as game theoretic actual optimality goes.
I guess what you would have to do is what my first thought for correcting this problem was. That is you solve a small matrix game for every state. This small matrix would consist of rows of all the actions you could take and then columns consisting of all the actions your opponent could take. You could then fill in the entries in the matrix by getting the values of the resulting states after those actions and then solve the matrix for the optimal strategy. Following the optimal strategy you can then do a one step update from your destination state.
If you want to win a game one way of doing it is treating the game as a MDP and then try to solve for the optimal value function over the states. The optimal value function on the states is the expected total cumulative value of all the rewards you can expect by acting optimally once in that state. Since a lot of games don't have an absolute stopping point beyond which you can't move generally you use a discounted reward model instead which basically means you prefer short term rewards to long term rewards to some extent. To figure out what to do in a MDP you can try to learn the transition model for the states and learn the reward model and from there you can try to solve the MDP to get the optimal value function.
Because trying to learn the transition model as well as the rewards is kind of a pain a popular alternative is to instead try to learn values over all pairs of actions and states, this is called Q learning. In Q-learning what you do is you keep track of what you think the value of any particular state is and then pick an action going from that state and update the value of the state action pair composed of the state you came from and the action you took based both on your current belief about the value of the state you transitioned into (which you can find by taking the maximum of the Q values of the new state) and any rewards you might have gotten along the way. Viola! you have a working means of picking actions in any state, you just look at the Q values and pick the action associated to the one with the highest Q value.
Sorry if this explanation is horrible (because it is) you should probably look it up on wikipedia or something or if you really care then google "sutton and barto reinforcement learning" and you can read a book about it online.
Now my beef with Q learning is this, in game theory you spend a bunch of time figuring out that pure strategies optimally solve only a very small fraction of games. I am talking here about two player zero sum games. Actually my beef is not so much with Q learning in general tasks but specifically in the case of two player zero sum games. Consider the game paper rock scissors. There are three strategies namely the strategy rock the strategy scissors and the strategy paper. A q learner set loose on this game would at first try something at random say paper and win because their opponent chose rock. Now the q-learner thinks that paper is the best strategy because the first time it tried it it won so next time around it tries it again and loses because their opponent chose the strategy scissors. The point is that someone else who knows that their opponent is a q-learner will know that the q-learner will tend to avoid whatever they just chose if they lost with it and tend to pick whatever they just won with over again. So q-learners fail at figuring out RPS. From a game theoretic standpoint what a deterministic q-learner is doing is assuming that every game has a saddle point (which is to say it has an optimal pure strategy). A popular alternative to the deterministic Q learner is a Q learner which chooses between different options by not choosing the "best" Q value but rather choosing from among the different actions using a boltzmann distribution with some temperature. The lower the temperature the closer the Q-learner is to deterministic but with any finite temperature a boltzmann (or softmax as they are actually called) Q learner will learn to play RPS correctly eventually. However the current wisdom is to use the temperature of the boltzmann Q learner as simply a means to allow for convergence and then limiting the temperature to 0 (meaning making the thing become deterministic). But from my perspective the temperature is clearly a feature. In fact I wonder if it might not be the case that picking a finite "equilibrium" temperature for each state would actually yield the correct optimum game theoretic mixed strategy. I don't really have any reason to believe that the distribution over the actions would converge to values in the appropriate way so that you could use the boltzmann distribution to get the correct mixed strategy but it is just so pretty that even if it isn't true it couldn't hurt to apply it and see how it goes.
Now that I have been thinking about it a bit more the pretty idea is sunk or at the very least incomplete. That is because the whole point of optimal mixed strategies is that the expected payoff of following each pure strategy is the same as all the others (assuming that the opponent is playing according to their optimal mixed strategy). So if the Q learner were in fact to come to learn the optimal values for each action/strategy it would learn that they were all the same. And yet we shouldn't allow it to choose between them with equal probability or we would not be acting optimally. I guess even trying to do something fancy like that the normal Q value system is just sunk as far as game theoretic actual optimality goes.
I guess what you would have to do is what my first thought for correcting this problem was. That is you solve a small matrix game for every state. This small matrix would consist of rows of all the actions you could take and then columns consisting of all the actions your opponent could take. You could then fill in the entries in the matrix by getting the values of the resulting states after those actions and then solve the matrix for the optimal strategy. Following the optimal strategy you can then do a one step update from your destination state.
Artificial Intelligence and Brain Damage
Lets suppose for a moment that we achieve in the next decade or so a series of breakthroughs in nanotechnology and AI to allow the creation of essentially perfect duplications of someones personality as an AI construct. I would be willing to say that if a person receives massive brain damage at some point in this era it would make sense to equip them with something of an artificial brain. Now remember that I said that the reproduction of their personality would be exact and so all of their characteristics would remain intact when this change took place. I would be an advocate of this sort of procedure and actually I would be an advocate of essentially the same procedure even if it was death instead of brain damage that had occurred. For the moment ignoring the moral implications of the resulting overpopulation problems and possible stagnation problems.
But what about people (like my mother) who experienced debilitating brain damage decades ago and has since evolved into someone who is very different from their original self although still sharing similarities? What if you could go in and "correct" their brain and restore their old capacities and old personality while letting them retain their accumulated memories of the intervening time. That would be unfair to the person living now but leaving things as they are is perhaps unfair to the person as they were. The problem is of course not really very much of a problem because the moral dillemma really only has one solution. The person who exists now can choose what they want. I guess I'm just babbling isn't the internet wonderful? I can post crap like this and nobody cares! wait... nobody cares... /sob
But what about people (like my mother) who experienced debilitating brain damage decades ago and has since evolved into someone who is very different from their original self although still sharing similarities? What if you could go in and "correct" their brain and restore their old capacities and old personality while letting them retain their accumulated memories of the intervening time. That would be unfair to the person living now but leaving things as they are is perhaps unfair to the person as they were. The problem is of course not really very much of a problem because the moral dillemma really only has one solution. The person who exists now can choose what they want. I guess I'm just babbling isn't the internet wonderful? I can post crap like this and nobody cares! wait... nobody cares... /sob
Compressive Sensing
The idea behind compressive sensing is that any interesting signal is not going to look like noise. If you want to reconstruct the signal you probably don't need to sample all the data in the signal but just enough to capture the information in the signal. Say for instance you know the signal is a perfect linear signal. You can just sample two points and be done with it. In essence the idea behind compressive sensing is that real signals tend to be approximately sparse in most bases. Here being approximately sparse in a wavelet basis means that most of the coefficients of the wavelet transformation are either zero or close to zero. The compressive sensing community uses the terminology that a vector is k sparse if the vector has k non zero entries, and approximately k sparse if all but k entries are close to zero. Now the oh so nifty thing about compressive sensing is that you only need something like k*log(N/k) measurements to get the data in the signal where N is the number of coefficients in the signal. What you do is you take your measurements at random, you use these measurements to create constraints on a linear program whose variables are the coefficients of the signal you want to recreate and then minimize the sum of those coefficients.
coding up something like that however would be a bit complicated, at some point it would be great if I were to program something capable of doing the simplex algorithm for linear programming but for the moment it is a project I am not willing to undertake. I wanted to use compressive sensing for my wavelets project at the end of the semester but I ended up not doing it because I couldn't code it (at least in time) and I didn't understand it all that well. What I ended up using was an algorithm that I just made up. The algorithm was relatively easy to code (compared to a general LP solver) and that is essentially why I ended up using it. The algorithm takes a set of direct measurements of a signal and then makes a bad guess for what the signal ought to look like. It then takes this bad guess and takes its wavelet transform. It also takes the wavelet transform of a vector of 1's where the measurements were made. This keeps track of where the wavelet coefficients contain direct information about the signal and where not. Starting at the lowest level of the wavelet transform we look at the transform of the information vector and if it has a non-zero coefficient in a certain place then we do a reverse wavelet transform ignoring the detail coefficients and put the value for that place in the reverse transform in that place in the signal. We continue to do this for every level all the way up until the last step is simply putting the observed measurements in place.
The algorithm as I just described it is pretty sucky, it is slow and inefficient but does give pretty good estimates of the signal. An interesting thing to note however is that iteration of the algorithm with the same observations but starting with the output of the algorithm as the "bad guess" input for the next iteration yields better results. I suppose I haven't really tested how much "better" the results are but the iterated version is totally a compressive sensing algorithm of sorts. Intuitively it makes perfect sense that since we throw away the detail coefficients every time we do an iteration we get closer and closer to a sparse vector in the wavelet basis. I haven't really done a proper analysis so I don't know if that is really true or not. I certainly am not willing to go so far as to say that the iteration converges onto the L1 minimization but I am willing to say that it does in fact do that in at least some simple cases.
coding up something like that however would be a bit complicated, at some point it would be great if I were to program something capable of doing the simplex algorithm for linear programming but for the moment it is a project I am not willing to undertake. I wanted to use compressive sensing for my wavelets project at the end of the semester but I ended up not doing it because I couldn't code it (at least in time) and I didn't understand it all that well. What I ended up using was an algorithm that I just made up. The algorithm was relatively easy to code (compared to a general LP solver) and that is essentially why I ended up using it. The algorithm takes a set of direct measurements of a signal and then makes a bad guess for what the signal ought to look like. It then takes this bad guess and takes its wavelet transform. It also takes the wavelet transform of a vector of 1's where the measurements were made. This keeps track of where the wavelet coefficients contain direct information about the signal and where not. Starting at the lowest level of the wavelet transform we look at the transform of the information vector and if it has a non-zero coefficient in a certain place then we do a reverse wavelet transform ignoring the detail coefficients and put the value for that place in the reverse transform in that place in the signal. We continue to do this for every level all the way up until the last step is simply putting the observed measurements in place.
The algorithm as I just described it is pretty sucky, it is slow and inefficient but does give pretty good estimates of the signal. An interesting thing to note however is that iteration of the algorithm with the same observations but starting with the output of the algorithm as the "bad guess" input for the next iteration yields better results. I suppose I haven't really tested how much "better" the results are but the iterated version is totally a compressive sensing algorithm of sorts. Intuitively it makes perfect sense that since we throw away the detail coefficients every time we do an iteration we get closer and closer to a sparse vector in the wavelet basis. I haven't really done a proper analysis so I don't know if that is really true or not. I certainly am not willing to go so far as to say that the iteration converges onto the L1 minimization but I am willing to say that it does in fact do that in at least some simple cases.
Subscribe to:
Posts (Atom)