Friday, May 18, 2007

Modified Delta Learning Rule Part 2

Another modification to my delta learning rule is motivated by my preference for working with real time values (t=0.13s, t=0.16s, t=0.19s, ...) as opposed to abstract discrete time values (t=1, t=2, t=3, ...). This distinction is important for interactive real time applications, like robotics and video games.

I want to be able to specify how much error is reduced per second (e.g., an error reduction rate of 0.3 means that the error is reduced by 30% per second). Here's how I do it:

error_reduction_rate = 1 - exp(-step_size / error_reduction_tc)

"step_size" is the amount of real elapsed time between weight updates (it's best if this is a fixed constant, both for stable learning and to avoid recomputing the error reduction rate constantly). "error_reduction_tc" is a time constant which determines how fast errors are reduced.

For example, an error reduction time constant of 2.0 means that the error will be reduced to about 37% of its original value after 2.0 seconds of updates. If weight updates occur every 0.05 seconds, this yields an error reduction rate of 0.02469. If we change the time constant to 0.1, leaving the step size at 0.05, the error reduction rate jumps up to 0.3935 since the time constant is much faster. Note: it's important to keep the step size smaller than the time constant; otherwise, things can get unstable.

A Delta Learning Rule with a Meaningful Learning Rate

Recently I was looking for a way to train a simple linear neural network using the delta rule in such a way that I could specify exactly how much error is reduced on each weight update. The usual delta learning rule for a single linear neuron is:

delta_w_i = learning_rate * error * x_i

In my opinion, the learning rate parameter lacks an intuitive interpretation. Ideally it would represent exactly how much error is reduced per update, but it doesn't. It is usually just set to some small constant, like 0.01, which is hopefully not too small (slow convergence) or too large (instability). My goal was to find a modified learning rule with a learning rate-like parameter which could reduce the error by a specific amount on each weight update (e.g., a value of 0.2 would reduce the error by 20% per update).

Temporarily assume a network with only one input/weight. Also assume that the goal is to reduce the error by 100% within a single step. (These assumptions will be relaxed later.) The output function is:

y = w * x

The error is:

error = target - y

In order to achieve zero error in one step, we need the following to be true:

y = target = (w + delta_w) * x

So we need to solve for the learning rate which yields zero error after one step:

delta_w = target / x - w
learning_rate * error * x = target / x - w
learning_rate = (target / x - w) / (error * x)
= [(target / x - w) / (error * x)] * (x / x)
= (target - w * x) / (error * x^2)
= (target - w * x) / ((target - w * x) * x^2)
= 1 / (x^2)

So a learning rate of 1 / (x * x) will reduce the error in the system to zero after one step. We can easily make this work for multiple inputs/weights by simply dividing by the size of the input/weight space n:

learning_rate = 1 / (n * x^2)

Of course, we don't usually want to reduce the error completely in one step, so we replace the 1 with an "error reduction rate." This quantity, which is a value within [0, 1], determines the amount of error to be reduced on each weight update. It is a rate with meaningful units (0.01 x error reduction percent per weight update). For example, an error reduction rate of 0.4 will reduce the error by 40% on each update compared to the error value on the previous step. It is equivalent to 1 - error(t+1) / error(t). Now the desired learning rate becomes the following:

learning_rate = error_reduction_rate / (n * x^2)

Now we can modify the delta learning rule by replacing the traditional learning rate:

delta_w_i = error_reduction_rate * error * x_i / (n * x_i * x_i)
= error_reduction_rate * error / (n * x_i)

One problem remains: we can't divide by zero when the input (x_i) values are zero. To remedy this, we only update weights associated with active (non-zero) inputs. Also, instead of dividing by n, we divide by the number of active inputs m:

only for non-zero x_i:
delta_w_i = error_reduction_rate * error / (m * x_i)

This looks very similar to the original delta rule except for three major differences:
  1. The learning rate has been replaced with the error reduction rate, a quantity with a much more meaningful interpretation.
  2. The weight deltas are divided by m, the number of active inputs. This essentially scales the error by the number of weights that contribute to the error.
  3. The weight deltas are divided by their associated input (x_i) values. This is an interesting deviation from the original delta rule which instead multiplies them by their input values.
UPDATE (5/23/07): It turns out that there's a problem with this modified delta rule. My assumptions concerning how the single input/weight case generalize to multiple inputs/weights were incorrect. Fortunately, only a small change is needed. Instead of dividing by the input value squared, we need to divide by the input vector length squared, which serves to normalize the weight deltas by the energy of the input vector:

delta_w_i = error_reduction_rate * error * x_i / length(x)^2

length(x) here is the Euclidean norm of the input vector. If length(x) is zero, we simply avoid modifying any weights, which is valid because all x_i values are zero which would produce weight deltas of zero. We are still able to specify the error reduction rate in an intuitive way, which was the motivation behind my search for a better delta rule.

Interestingly, this turns out to be equivalent to the normalized LMS rule. (LMS, or least-mean-square, is another name for the delta rule). Normalized LMS is described here and in Haykin's Neural Networks book, 2nd edition, p. 152.

Monday, May 14, 2007

Randall C. O'Reilly's Wiki

This is one of the best things I've read in a while. It's a very detailed, personal account of Randall O'Reilly's belief system, covering the brain, epistemology, religion, physics, politics, and much more. I just finished reading the whole thing, which was very refreshing.

I especially enjoyed the constant focus on developing self-consistent beliefs as a practical goal: "Self-consistency is probably the only useful criterion for establishing the "truth" of a belief system. It is itself consistent with the fact that we cannot escape our fundamental subjectivity..." Here's another great quote: "You might argue that this is all circular. It is. However, if you make a big enough circle that encompasses all of experience, then I don't see what the problem is."

I think self-consistency is implemented in the brain as a Bayesian network. New pieces of evidences are constantly coming in through sensors and being passed around among nodes to update their beliefs about the world. The whole belief propagation mechanism is designed to maintain self-consistent beliefs as well as possible; complete self-consistency isn't always achieved, but it's at least maximized. Interestingly, we are still able to bias the system by focusing attention on certain details while ignoring others, which can basically keep certain pieces of knowledge from affecting our belief systems.

Monday, May 07, 2007

Polyphasic Sleeping Log

Back in 2005 I tried a polyphasic sleep schedule (specifically, the Uberman schedule) for almost a month. It was loads of fun after the first two weeks were over. I'd say I have a much different perspective on sleep now. During the process I kept a daily log, which I forgot about until now. I thought I'd post it here...
Related links:
http://www.kuro5hin.org/story/2002/4/15/103358/720
http://www.jonnyhenderson.com/secret/sleeping.php?week=1

General comments:
* Take vitamins daily.
* Keep a healthy diet.
* Drink lots of fluids.
* Learn to fall asleep fast. With only 20 minutes to sleep at a time, you'll need to fall asleep as soon as possible. Be able to make yourself extremely bored when you're lying down; immediately forget any thoughts that come up. This takes practice.
* Don't oversleep, and don't miss naps. Having a rigid sleep schedule helps your body adjust faster.
* I found that during the induction period, it's much harder to stay awake at night. Be especially careful during the nightly naps that you don't oversleep.
* Before the evening starts, have a list of projects written down. It's really hard to think of new things to do later.
* If you start to get overpowered by the urge to sleep, do something different: eat, play a video game (much better than watching a movie since it's interactive), go for a walk (I enjoy walking in the morning at sunrise), etc.. Don't just sit (or lie) there wishing you weren't so tired.
* If you get heartburn, it's probably from eating within 2 hours before sleep. Lying down lets fluids travel up the esophagus easier. (I would think the sphincter muscle down there would keep everything in the stomach, but maybe it's not perfect.) Something that helps is sleeping on an incline. Try putting a few wadded up blankets under the head of your mattress.
* Summary of my induction period:
- Days 1 & 2: Felt like I had missed a lot of sleep.
- Days 3 & 4: Didn't feel terribly sleepy anymore most of the time. Felt generally normal.
- Days 5 & 6: Felt kind of queasy all day. Felt sleepy during the night if I didn't keep busy.
- Days 7 - 10: Felt mostly normal, but still a little sleepy during the night if I didn't keep busy.
- After day 10: Felt mostly normal.

------------------------------------------------------

Day 1: Saturday, 7-23-05
Total sleep: 1:40
* Started at 12 a.m.
* 4 a.m.: I took my first nap. I slept most of the time and woke up easily. After getting up, I didn't feel too much different; I just felt like I was up really late.
* 4:20 a.m. to 6 a.m.: I read a magazine.
* 6:30 a.m. to 7:30 a.m.: I took a walk and listened to the Lord of the Rings BBC radio show.
* 8 a.m. to 8:20 a.m.: I took my second nap. I felt more tired after waking up this time, but I was still able to get up easily.
* 8:20 a.m. to 12 p.m.: I ate breakfast and played video games.
* 12 p.m. to 12:20 p.m.: I took my third nap. I felt rested afterwards, though a little groggy. Still not bad. Once I get up and move around, I feel pretty awake.
* 12:20 p.m. to 4:15 p.m.: Ate lunch. Ran errands around town... but accidentally didn't get home till after 4pm.
* 4:25 p.m. to 4:45 p.m.: Took a nap, but probably only slept for less than half the time. I was really awake from running errands in the 101 degree heat; also, I had just found that I received a scholarship for the next school year, so that made it a little hard to sleep.
* 4:45 p.m. to 8 p.m.: At supper with Ken.
* 8 p.m. to 8:20 p.m.: Took a nap at Ken's place. Didn't sleep very much.
* 8:20 p.m. to 11:30 p.m.: Played video games with Ken until I felt pretty tired.
* 11:30 p.m. to 12 a.m.: Drove home from Ken's. Got ready for a nap.

------------------------------------------------------

Day 2: Sunday, 7-24-05
Total sleep: 4:10
* 12 a.m. to 12:20 a.m. Took a nap.
* 12:20 a.m. to 4 a.m.: When I woke up from my nap, I really wanted to keep sleeping. It took a long time before I started feeling awake. Played computer games and watched TV.
* 4 a.m. to 6:30 a.m.: Tried to take a nap, but accidentally slept way too long.
* 6:30 a.m. to 8 a.m.: Listened to the Lord of the Rings BBC radio show while trying to stay awake.
* 8 a.m. to 8:20 a.m.: Took a nap.
* 8:20 a.m. to 12:15 p.m.: Went to church.
* 12:20 p.m. to 12:40 p.m.: Took a nap.
* 12:40 p.m. to 4 p.m.: Watched TV and listened to the Lord of the Rings BBC radio show.
* 4 p.m. to 4:20 p.m.: Took a nap. I've noticed that it's much easier to get up after a nap during the day than after one at night. Maybe this will change after another week or so.
* 4:20 p.m. to 8 p.m.: Priced computer parts online.
* 8 p.m. to 8:20 p.m.: Took a nap.
* 8:20 p.m. to 12 a.m. Read Uberman sleep schedule info on the web.

------------------------------------------------------

Day 3: Monday, 7-25-05
Total sleep: 2:10
* 12 a.m. to 12:20 a.m. Took a nap.
* 12:20 a.m. to 4 a.m.: Read more Uberman sleep schedule experiences.
* 4 a.m. to 4:10 a.m.: Took a nap. Woke up early because I had to use the bathroom. I didn't want to try to go back to sleep for ten minutes.
* 4:30 a.m. to 5:15 a.m.: Took a walk and listened to the Lord of the Rings BBC radio show.
* 5:15 a.m. to 8 a.m.: Read about C++ threading libraries. Took a shower.
* 8 a.m. to 8:20 a.m.: Took a nap.
* 8:20 a.m. to 12 p.m.: Thesis work.
* 12 p.m. to 12:40 p.m.: Took a nap. I woke up easily, but I didn't actually sit up. Instead, I fell asleep for another 20 minutes.
* 12:40 p.m. - 4 p.m.: Thesis work. I'm glad I can actually do something productive at this point. I felt sort of lousy earlier today, but my 8 a.m. nap really helped. I almost feel normal.
* 4 p.m. to 4:20 p.m.: Took a nap.
* 4:20 p.m. to 8:20 p.m.: Went out for supper and bought groceries. Didn' finish groceries quite on time, though.
* 8:20 p.m. to 8:40 p.m.: Took a nap.
* 8:40 p.m. to 12 a.m.: Played video games, read a book, and read about 'gnuplot'.

------------------------------------------------------

Day 4: Tuesday, 7-26-05
Total sleep: 7:30
* 12 a.m. to 6:30 a.m.: Took a nap. This was really disappointing after doing so well yesterday. I just didn't wake up to my alarm. I decided to skip my 8 a.m. nap and then continue napping like normal.
* 6:30 a.m. to 11:45 a.m.: Ate breakfast. Read literature on threading and OpenMP.
* 11:45 a.m. to 12:05 p.m.: Took a nap.
* 12:05 p.m. to 4 p.m.: Ate lunch. Tried to buy a motherboard at Best Buy, but they didn't have any in stock.
* 4 p.m. to 4:20 p.m.: Took a nap.
* 4:20 p.m. to 8 p.m.: Priced computers online and read about wiki software. Ate supper.
* 8 p.m. to 8:20 p.m.: Took a nap.
* 8:20 p.m. to 12 a.m.: Read more stuff online. Played video games.

------------------------------------------------------



Day 5: Wednesday, 7-27-05
Total sleep: 2:00
* Worked at VRAC throughout the night, which was pretty fun. I felt alert most of the time, but I didn't end up being too productive. Did research throughout the day.

------------------------------------------------------

Day 6: Thursday, 7-28-05
Total sleep: 2:00
* Worked at VRAC throughout the night again. I felt more sleepy this time, though. I must be adjusting still. Worked on research/code throughout the day.

------------------------------------------------------

Day 7: Friday, 7-29-05
Total sleep: 2:00
* Stayed home during the night. It was difficult to stay awake while I wasn't working on the computer. For the past day or so I've felt a weird queasy feeling with stomach cramps. I hope that goes away soon.

------------------------------------------------------

Day 8: Saturday, 7-30-05
Total sleep: 3:20
* Accidentally slept from 12 a.m. to 2:30 a.m. Skipped 4 a.m. nap. Didn't sleep during 12 p.m. nap (on Ken's trampoline outside). Slept 10 minutes during 4 p.m. nap. Still have the weird stomach pains sometimes.

------------------------------------------------------

Day 9: Sunday, 7-31-05
Total sleep: 3:25
* Accidentally slept from 8 a.m. to 9:45 a.m. No other problems.

------------------------------------------------------

Day 10: Monday, 8-1-05
Total sleep: 2:00
* Worked at VRAC 1 a.m. to 6:30 a.m. I still have stomach pains most of the time. I can't tell if it's muscle cramps or heartburn (located just under my breastbone).

------------------------------------------------------

Day 11: Tuesday, 8-2-05
Total sleep: 2:00
* Worked at VRAC 2 a.m. to 7:30 a.m. (replaced the motherboard in my old desktop computer that died about a year ago). I think the stomach pains aren't as bad when I don't eat large meals, so I'll try to spread out my eating more throughout the day.

------------------------------------------------------

Day 12: Wednesday, 8-3-05
Total sleep: 3:00
* Worked at VRAC 2 a.m. to 7:30 a.m. It took a while to wake up after my 12 a.m. nap. I hope that within a few days (the 2 week mark) I won't be as tired during the night. Oops, I accidentally slept from 12 p.m. to 1:20 p.m.

------------------------------------------------------

Day 13: Thursday, 8-4-05
Total sleep: 2:00
* Worked at VRAC 2 a.m. to 7:30 a.m.

------------------------------------------------------

Day 14: Friday, 8-5-05
Total sleep: 3:30
* Stayed home during the morning this time. Overslept from 4 a.m. to 5:50 a.m. Didn't skip my 8 a.m. nap.

------------------------------------------------------

Day 15: Saturday, 8-6-05
Total sleep: 2:00
* Stayed home during the morning. I think that my stomach pains were probably intense heartburn. I read today that eating just before lying down can cause heartburn (because gravity isn't keeping the stomach acid down). So I think I'll try to limit how much I eat within the 2 hours before a nap.

------------------------------------------------------

Day 16: Sunday, 8-7-05
Total sleep: 3:10
* Overslept from 8:20 a.m. to 9:50 a.m.

------------------------------------------------------

Day 17: Monday, 8-8-05
Total sleep: 3:30
* Overslept from 8:20 a.m. to 10:10 a.m.

------------------------------------------------------

Day 18: Tuesday, 8-9-05
Total sleep: 2:00
* Took my 8 p.m. nap at 9 p.m. since we were in Des Moines at that time. I've noticed something weird over the past 3-4 days: periodically I have the sensation of something pressing against my forehead. It feels like someone's fingers. Also, the more I focus on it, the stronger the feeling. If I think about something else, the feeling goes away. It also goes away if I briefly touch my forehead.

------------------------------------------------------

Day 19: Wednesday, 8-10-05
Total sleep: 7:30
* Overslept from 12 a.m. to 6:30 a.m. Wow. I don't know how that happened. I did feel really rested when I woke up, even if I was overwhelmed with guilt. I'm going to skip my 8 a.m. nap and start again at noon.

------------------------------------------------------

Day 20: Thursday, 8-11-05
Total sleep: 2:00
* Today I didn't feel too much different than normal, which was surprising after sleeping so long yesterday. I got a new computer yesterday and spent the whole day today installing software.

------------------------------------------------------

Day 21: Friday, 8-12-05
Total sleep: 2:00
* Went camping Friday through Sunday.

------------------------------------------------------

Day 22: Saturday, 8-13-05
Total sleep: 6:00
* Fell asleep multiple times during the morning.

------------------------------------------------------

Day 23: Sunday, 8-14-05
Total sleep: 3:10
* Overslept 8 a.m. to 9:30 a.m.

------------------------------------------------------

Day 24: Monday, 8-15-05
Total sleep: 2:50
* Overslept 4 p.m. to 5:10 p.m. The sensations on my forehead are pretty constant now. I notice them more when I lie down for a nap.

------------------------------------------------------

Day 25: Tuesday, 8-16-05
Total sleep: 2:30
* Overslept 12 p.m. to 12:50 p.m.

------------------------------------------------------

Day 26: Wednesday, 8-17-05
Total sleep: N/A (I am no longer doing polyphasic sleep.)
* Overslept 12 a.m. to 2:20 a.m.

I'm making the conscious decision (not affected by lack of sleep, as far as I can tell) to go back to monophasic sleeping. My reasons are the following:

- So far I haven't felt up to my normal mental capacity. This is fine in most situations, but not when doing research. I never succeeded in going a full week without oversleeping, though. Maybe then I would have felt normal.
- Of course, there are still unknown health risks as this hasn't been studied in people for long periods of time (i.e. years).
- Even though I can now mostly avoid heartburn, I still feel a weird lump in my chest underneath my breastbone. I feel it when I lean forward. I have no idea what this is, but it has only developed since I started polyphasic sleep.
- I feel like I've gained a lot of weight since I started. I would guess about 10 pounds (started at 182, now up to about 192). This is strange to me since I thought staying up around the clock would help me burn more calories. I even started exercising (using elliptical machines) for 30 minutes a day, 3 times a week, over the past two weeks. Maybe sleep stages 3 and 4 (which I'm not getting) are involved in regulating metabolism.
- My wife doesn't like sleeping in an empty bed most of the night.
- If I am going to stop, now is a good time since school is starting in a few days (on Monday).

That being said, I'm going to miss polyphasic sleeping. It was great having so much free time that I actively had to think of things to do. Maybe I'll try it again someday. I think it'll be easier to start next time since I know what to expect.

------------------------------------------------------

Day 27: Thursday, 8-17-05
Total sleep: 12 hours! (This includes part of yesterday: 8 p.m. to 8 a.m.)
* I feel good today. I can't quite explain it, but I just feel generally good... and sad. I'm a little groggy after having slept for 12 hours, but that should only last a day or two. The weird lump in my chest is gone. I can't help feeling like I failed, but I don't think that's the right attitude. At least I got a month of experience with polyphasic sleep.