Ideacrank.net

Using Back Propagation To Train A Neural Network

Maxwell — Wed, 16 Jun 2010 23:02:39 +0000

(download)

I made this very simple program to figure out how to implement "back propagation," a method of training a neural network. In the previous program I published, I was using a genetic algorithm to adjust the weights of every network based on a fitness scale. The method required a gene pool of a good size, made up of the weight information of each network, in order to successfully adapt. Using a genetic algorithm this way made it impossible for a single network alone to improve. Back propagation does not require more than one network, only one thing: a measurable goal. Using back propagation, a network can hone in on the best values for each of weights it contains (which range from .0000 to .9999), adjusting them slightly every time the network runs a single generation. The result is incredibly successful in this particular case.

On the left is a set of color values you can modify for four squares in the middle. You can type values in (0-255), use the slidebar, or choose to generate colors randomly. Pressing the large "Start" button on the right will start up the networks (one for each square) and begin the back propagation. While it is running, you can modify any color value or click to randomize the values and the networks will readjust every time.

The key here is that there is a very easy goal for the networks to achieve. Each square has only three inputs and three outputs: red, green and blue, each an integer between 0 and 255. The program adjusts each weight by a ratio, so as an output value get closer to the goal, less is added to or subtracted from the weights.

This program is very simple and pointless in what it does, but the concept, even this particular application, can be used in other ways. It would be possible to create, for instance, enemies in a game that can camouflage themselves based on whatever their around (or above, if you're looking down on a two dimensional game). I've drawn some sketches and mapped out the idea for making a cameleon like creature that, when approached by the mouse, would move away, taking the image of whatever it was on with it. The trouble in this case is that, to make a good quality camouflage effect, each pixel would have to be modified as each would most likely require its own network. A simpler use could be something such as light finding or light avoiding bots. I'll post more details about how the propagation works once I've finished the next project.

Posted via email from ideacrank.net

Finally, A Completed Neural Network

Maxwell — Tue, 25 May 2010 03:00:22 +0000

(download)

For the browser sized program: http://www.ideacrank.net/projects/NeuralNetSeekers.swf
To read the full post: http://writing.ideacrank.net

In early April, I posted my genetic algorithm program, and when it was out, I moved on, taking what I learned about genetic selection based algorithms, and started working on a simple "food seeking" program based on neural networks. The above program is the result.

Each moving agent on the screen is an independent neural network, taking in information about its current position, where it is and where the goal is (on a Cartesian plane), running it through a series of "neural" layers, weighing the values of the inputs and producing new values, which in turn go through their own layers, until two values are put out: distances to travel on the x and y axes. This output is fed to the movement control of the agent (the code representing the object on the screen) and the little seeking agent moves in that direction. However, unchanged, the configuration of the network will send the agent in the same direction forever.

Things really get fascinating when the agents reproduce. The agents that are heading to the goal at the fastest, most direct pace are given the highest fitness, but every agent is given some fitness value. The higher an agent's fitness, the more likely it will pass on roughly half or more of its "genes". In the last program the genetic information being passed on was binary strings, forty bits in length. This time, actual values between 0 and 1 are used, but the splicing process is the same:

Mate One's weight at [layer2][neuron7][weight2]: .6730
Mate Two's weight at [layer2][neuron7][weight2]: .1094

A splice randomly chosen to occur after second digit yields: .6794. The program randomly chooses who the first and second mate are, so if they were flipped, the new weight would be: .1030. This weight, and all the other new weights (if the splice point is before the first number or after the last, the whole of one mate's old weight is passed on), are given to an offspring network.

Unlike natural selection, the weakest are replaced every time without room for the chance that their betters get destroyed first by unexpected accident (flood, virus, comet, etc..). Based on fitness, the networks are sorted in descending order, and the least fit are replaced by the next generation of offspring. There is still always a chance for these agents to be replaced by their own offspring. On the screen no new objects are created by this process; the old vehicles for the weakest neural networks are taken over by their kin. The one exception is when agents stray too far out of bounds. If an agent wanders away (perhaps rejecting their goal seeking life), it is destroyed and an offspring is created somewhere on the board.

The rate of replacement in this case is set to a tenth the size of the whole population, rounded up. Before replacement, though, the offspring go through a mutation roll. In binary, bits marked for mutation simply switched, 0 to 1, 1 to 0. In the interest of keeping mutations from changing too much, mutated digits will only go up or down one integer. This allows for a range of impacts from a single mutation: a mutation on the first digit after a decimal will greatly change the weight (especially if a 9 is increased to a 0) whereas one on the last digit will have nearly unseen change.

The selection process was mostly finished a few days ago and I've spent the last few days tweaking the parameters and making the program look a little nicer. Lag from processing too much put a lot of constraints on what I could do, particularly in the process of mating/mutating networks. Allowing the program to lag makes for a poor visual program, so I spent today trying to write more efficient code, but so far I haven't made significant progress. Each network is built as a multidimensional array which, as far as I can figure out, requires an long, irreducible structure:

//for every network, a loop is run
for(a=0; a{
    //within every network, the user's desired amount of layers are looped
    for(b=0; b    {
       //each layer has a desired amount of neurons which are looped
        for(c=0; c        {
            //and each neuron has the amount of weights equal to the amount of inputs it receives
            //neurons also have an additional weight that acts as an activation bias
            //the activation bias weight is subtracted from the combined value of all weights * inputs and the result is the output
            for(d=0;d            {
                //network[a][b][c][d] is assigned or used for something here…
            }//d
        }//c
    }//b
}//a

Each amount, the number of networks, layers, and neurons per layer, can be adjusted, but again, lag set an upper limit in this case. The above is actually a simplified version of the code. The first and last layers have to specialized; the first must have an equal amount of weights as the amount of initial inputs (plus one for the activation bias), whereas every middle layer has the same amount of weights: equal to the amount of neurons of the previous layer plus one. The last layer has to have an amount of neurons equal to the amount of final outputs, as each neuron acts as a single output. The result is three separate sets of the code above.

I found that the more layers and neurons I used, the better the program was at performing its task. Few layers and neurons resulted in agents drifting much farther away from their goal before adjusting to a better direction. Often, you'll see the agents headed slightly to one side of the goal, at some point passing it. More layers correlated with a faster "turn around" time for the agents, though I'm still trying to figure out exactly why. Anyway, lag limited my ability to see how far this trend went, and it also set the upper limit to just about four layers (five including output), with nine neurons each. I set the maximum number of networks to 30 on the slider bar at the bottom of the program. That is 9 neurons * 5 weights for the input layer, 9*10 for the next four layers, and 2*10 for the output layer – 425 weights per network time thirty networks. At the set maximum, 12750 weights are created at the start of the program; every twenty five milliseconds they are multiplied against their inputs and produce outputs; every fifty milliseconds (every other tick on the game "clock"), 1275 new weights are created, roughly ten percent of which mutate after they all run through the mutation dice roll. After that, the sorting and replacement is fairly efficient.

I had the program running with two hundred networks, ignoring the amount of time the program hung, and saw enough to get the sense that too many networks actually hindered the selection process. One result I've noticed from the way the selection is set up in this program is that a small handful agents making smart moves can alter the course of the whole crowd if the agents are mostly in a group together (something that occurs on its own from the seeking process). If the goal is centered among distributed agents, the whole thing can go haywire. It will always work out, but it is hard to say when this is just because some random mutant baby happens down the right trajectory or if it is truly the result of corrective selective pressure.

The pressure system seems to work pretty well though. A good agent can quickly hem in strays or stop the whole crowd rapidly, the most fit sending the whole group careening toward the goal. In this constrained environment, speed often results in slower goal achievement, as the whole group has to adjust for a longer period of time. If the whole group is going in the same direction, their children are going to have approximate trajectories, showing the importance of mutation and the rapid spread of successful mutants. A group, it seems, is best collected, but still spread out enough to allow for a greater cloud of fitness.

It may be that I am alone in my excitement about this, but the promise of this sort of program is mind boggling. I do often have a mixed reaction to watching the program: I am amazed that a minimally complex program is able to perform such seemingly intelligent actions, its ability to "learn" built into its code. I am amazed that this sort of thing can be built by a novice programmer (I'm really only five or six programs into using Flash and ActionScript), and that selective pressure and evolutionary concepts work so well in such a simple medium of abstract representation. I am also amazed at how unintelligent the program can be. Earlier in the spring, I made a program that show homing missiles at where ever the mouse was. With a tenth of the code that I used here, the missiles did a far better job at hitting their goal as fast as possible. This program does things that look almost random because their is sometimes no clear reason why it acted the way it did. Sometimes an agent, far ahead of the others, with no interference, will nearly reach its goal, only to abruptly backtrack, immediately becoming the least fit (as everyone else is catching up). The result is a flailing agent, moving left and right, adjusting over and over. Though this setting opens the door to strange occurrences, there are definite applications, with more constrained environment, that this sort of program is very useful for that are within my range of ability.

I added the semi-transparent circles because, watching the program, I am reminded of videos of microscopic environments. I remember watching an amoeba chase a small, bacteria meal, shifting and turning as it followed.

Posted via email from ideacrank.net

Initial Forays into Genetic Algorithms

Maxwell — Wed, 07 Apr 2010 02:50:51 +0000

(download)

I've been interested in genetic algorithms and neural networks, but only recently had it occurred to me that I could create them with ActionScript 3.0. The idea and general processes for this program came from a great resource for this sort of stuff www.ai-junkie.com. The example code, however, was written in C++, so beyond the concepts, the code had to be written from scratch.

I threw the interface together pretty quickly once the algorithm functioned, so it isn't the best looking program, nor does it show you what happens when the algorithm runs. I am still really excited. The whole thing is fairly simple, but the result is pretty damn cool to me. When the algorithm runs, ten "chromosomes" of forty binary digits are randomly generated, each set of four digits representing a number, 0-9, or an operator, +, -, *, or /. The chromosomes are decoded and computed in order:

0110 0111 1100 0000 0101 1001 1010 0100 0001 1011

6 7 * 0 5 9 + 4 1 -

The result (in this case, (67 * 59) + 41 = 3994) is compared to the goal (the default is 20), and given a reproductive fitness: the closer a chromosome's value is to the goal, the more opportunities it is given to reproduce. After all ten individual chromosomes are decoded and given a fitness, individuals are randomly selected from the weighted gene pool to produce a new individual made up of a randomly spliced combination of the two parent chromosomes.

0110011111000000010110011010010000011011 parent one
1111000101001101001001001110100010011010 parent two
1111000101001100010110011010010000011011 new child

After the ten old individuals are replaced by new offspring, each chromosome is run through a mutation chance. In this algorithm, the mutation rate is set to .001, so each digit in every chromosome essentially has a one in a thousand chance to be flipped from 0 to 1 or 1 to 0. The mutation rate is low, but depending on where the mutation occurs, it could the result greatly. For example, some binary combinations, 1111, for example, don't represent anything, so they are ignored. A 0111 (7) changing to a 1111 would knock the 7 out of the equation entirely (or the opposite could occur, and a number could appear suddenly). A less drastic change could be something like a 0001 changing to a 0011, flipping a 1 to a 3. This, coupled with reproductive fitness, makes for a pretty successful system. Mutation prevents a whole population from being overrun for too long by a genetically fit, but not fully successful equation (this can be seen if the generations are listed out every time.. an equation the produces 7 instead of 8 is still so close that every individual becomes that equation, effectively removing reproductive variation and any chance of the equation getting closer), while on the other hand, only mutations that increase fitness are likely to be continued to the next generation.

Once the chance for mutations has passed, the ten new individuals are then run through the whole process again. In the end, one of two things occurs: either an individual's value is equal to the goal and the problem is solved, or the algorithm runs out of time and produces the best result available. I've set it run 2000 generations, one every .005 seconds, so it has roughly ten seconds. Some calculations slow the process down (the program can find equations for fractions, for instance, but the whole process crawls as it if it runs into equations that produce long or repeating numbers, so they were removed for now), which results in a longer time before the algorithm gives up.

Running the program a bunch of times yields two common results: either a solution is found, usually very rapidly, or the program gives up after dealing with an approximation of the goal (i.e. 19.925 instead of 20).

For speed and simplicity, I kept the population at ten individuals and assigned a limit that gives only a small window of time for the algorithm to find an equation. If the program had a larger population and more time, I am confident it could find solution at a much greater rate of success. Still, the fact that it works as well as it does is astounding to me. The next step is to implement this sort of algorithm in a neural network!

Posted via email from ideacrank.net

testing

Maxwell — Tue, 06 Apr 2010 03:11:23 +0000

(download)

testing

Posted via email from ideacrank.net

testing

Maxwell — Tue, 06 Apr 2010 03:10:06 +0000

Click here to download:

GeneticNumberComputer.fla (1392 KB)

testing

Posted via email from ideacrank.net

This is a test for configuring .swf file posts into posterous

Maxwell — Fri, 12 Mar 2010 14:22:52 +0000

(download)

I'm trying to figure out a way to configure the way flash programs are handled in posterous. I would prefer to post them directly to the blog, however, when I tried to with the Pattern Generator, it produced white spaces on either side of the program.

Posted via email from ideacrank.net

A Fully Operational Pattern Creator

Maxwell — Fri, 12 Mar 2010 04:40:29 +0000

http://www.ideacrank.net/projects/PatternCreator/Drawing.html

I have reached a good stopping place with my pattern project. It starts with all variables randomly selected. Click "Generate Pattern." If you like any part of the pattern, uncheck the "random" checkbox and it will stay the same, or add your own variables to see what it produces. When you've found something you like, you can choose to export it as either a .jpeg or .png image.

There is still more I want to add, but as of now, the program works. All the inputs and check-boxes work and the input provides the information for all the variables of the current pattern. I also cleaned up the look a bit and added a .png export button. Jpeg is good for tiled desktop backgrounds and the like, but I wanted to be able to get png files for things like web design. For now, I am going to take a break from the program and start applying what I've learned to some other, smaller programs. In store for the future:

Slide bars for easy variable changing with results displayed immediately (i.e. dragging a slider that makes the pattern bigger without changing any other variable.
A larger set of pattern choices. I have the code written for circles, hexagons, dodecagons and eight-point stars, but an interface would need to be made that could make them available without making the pixel size of the program much bigger.
A nicer look overall.

Though there is more to do, I am happy with how it turned out.

Posted via email from ideacrank.net

A Fully Operational Pattern Creator

Maxwell — Fri, 12 Mar 2010 04:30:59 +0000

(download)

Slide bars for easy variable changing with results displayed immediately (i.e. dragging a slider that makes the pattern bigger without changing any other variable.
A larger set of pattern choices. I have the code written for circles, hexagons, dodecagons and eight-point stars, but an interface would need to be made that could make them available without making the pixel size of the program much bigger.
A nicer look overall.

Though there is more to do, I am happy with how it turned out.

Posted via email from ideacrank.net

A Working Program

Maxwell — Thu, 25 Feb 2010 19:29:56 +0000

Though there is still a lot more for me to work on, a functional pattern generating program is online, here. Currently, a lot of the interface is still under development. For instance, none of the input boxes or check boxes are hooked up yet, they are more of an example of what the finished program will have. The buttons at the bottom, however, do work. Click "Regenerate Pattern," to produce a pattern. When you have one you like, click "Export to JPEG." A tab should open up, and prompt you to give the file a name, then download the pattern. The pattern is automatically cropped to allow tiling, so you can put it up as a tiled background.

One thing to note: I am still working out resource recycling for the patterns that are generated, so after a handful of regenerated patterns, the program will noticeably slow down (the old patterns are still present, drawn over by the new ones, which slows things down a bit). Refreshing the page will speed the program up again.

At the moment, all variables are random. The size of the stars and ribbons, the colors, and the opacity are all selected randomly within a set range. The background is also always black (which actually makes for some pretty cool results.. better, in my opinion than a white background). The pattern is also always a six pointed star. These will all eventually be modifiable.

Success!

http://www.ideacrank.net/projects/PatternCreator/Drawing.html is the address.

Posted via email from ideacrank.net

Norway conquers infections by cutting use of antibiotics

Maxwell — Thu, 18 Feb 2010 14:57:45 +0000

OSLO, Norway — Aker University Hospital is a dingy place to heal. The floors are streaked and scratched. A light layer of dust coats the blood pressure monitors. A faint stench of urine and bleach wafts from a pile of soiled bedsheets dropped in a corner.

Look closer, however, at a microscopic level, and this place is pristine. There is no sign of a dangerous and contagious staph infection that killed tens of thousands of patients in the most sophisticated hospitals of Europe, North America and Asia last year, soaring virtually unchecked.

The reason: Norwegians stopped taking so many drugs.

Twenty-five years ago, Norwegians were also losing their lives to this bacteria. But Norway’s public health system fought back with an aggressive program that made it the most infection-free country in the world. A key part of that program was cutting back severely on the use of antibiotics.

Now a spate of new studies from around the world prove that Norway’s model can be replicated with extraordinary success, and public health experts are saying these deaths — 19,000 in the U.S. each year alone, more than from AIDS — are unnecessary.

“It’s a very sad situation that in some places so many are dying from this, because we have shown here in Norway that Methicillin-resistant Staphylococcus aureus [MRSA] can be controlled, and with not too much effort,” said Jan Hendrik-Binder, Oslo’s MRSA medical advisor. “But you have to take it seriously, you have to give it attention and you must not give up.”

The World Health Organization says antibiotic resistance is one of the leading public health threats on the planet. A six-month investigation by The Associated Press found overuse and misuse of medicines has led to mutations in once curable diseases like tuberculosis and malaria, making them harder and in some cases impossible to treat.

Now, in Norway’s simple solution, there’s a glimmer of hope.

ANTIBIOTICS MISSING

Dr. John Birger Haug shuffles down Aker’s scuffed corridors, patting the pocket of his baggy white scrubs. “My bible,” the infectious disease specialist says, pulling out a little red Antibiotic Guide that details this country’s impressive MRSA solution.

It’s what’s missing from this book — an array of antibiotics — that makes it so remarkable.

“There are times I must show these golden rules to our doctors and tell them they cannot prescribe something, but our patients do not suffer more and our nation, as a result, is mostly infection free,” he says.

Norway’s model is surprisingly straightforward.

%u2022 Norwegian doctors prescribe fewer antibiotics than any other country, so people do not have a chance to develop resistance to them.

%u2022 Patients with MRSA are isolated and medical staff who test positive stay home.

%u2022 Doctors track each case of MRSA by its individual strain, interviewing patients about where they’ve been and who they’ve been with, testing anyone who has been in contact with them.

“We don’t throw antibiotics at every person with a fever,” says Haug. “We tell them to hang on, wait and see, and we give them a Tylenol to feel better.”

U.S. REACTION

Dr. John Jernigan at the U.S. Centers for Disease Control and Prevention said they incorporate some of Norway’s solutions in varying degrees, and his agency “requires hospitals to move the needle, to show improvement, and if they don’t show improvement they need to do more.”

And if they don’t?

“Nobody is accountable to our recommendations,” he said, “but I assume hospitals and institutions are interested in doing the right thing.”

Around the world, various medical providers have successfully adapted Norway’s program with encouraging results. A medical center in Billings, Mont., cut MRSA infections by 89 percent by increasing screening, isolating patients and making all staff — not just doctors — responsible for increasing hygiene.

In 2001, the CDC approached a Veterans Affairs hospital in Pittsburgh about conducting a small test program. It started in one unit, and within four years, the entire hospital was screening everyone who came through the door for MRSA. The result: an 80 percent decrease in MRSA infections.

The program has now been expanded to all 153 VA hospitals, resulting in a 50 percent drop in MRSA bloodstream infections, said Dr. Robert Muder, chief of infectious diseases at the VA Pittsburgh Healthcare System.

“It’s kind of a no-brainer,” he said. “You save people pain, you save people the work of taking care of them, you save money, you save lives and you can export what you learn to other hospital-acquired infections.”

“So, how do you pay for it?” Muder asked. “Well, we just don’t pay for MRSA infections, that’s all.”

via miamiherald.com

Posted via web from ideacrank.net