Adventures in Programming and Machine Learning

Bulletproof code.

2011-03-05T05:57:00.001-08:00

What has been helping me out is the phrase: "Code that cannot fail is infinitely easier to maintain then code that has many paths through it which might fail."

Murphy's law: "What can go wrong WILL go wrong". So go over every line of code and ask: "How might this function do something unintended?". If you find any answer to that question then you need to change how the function works until the answer is: "This function physically cannot do something unintended". If the hardware and compiler are working to specification then the ONLY path through this code is the correct way through (or a pretty exception/error that tells you what the programmer/user did wrong or what the hardware/compiler failure was).

For example: you have a function calculate() which takes a collection of Strings which represents items to process. The problem is that function foo() might run incorrectly and some String items may become invalid or incorrect. Then calculate() will make its best attempt, then calculate may throw an exception/error or worst of all, it may work. The solution here is to make it physically impossible for the items in the list to become invalid/wrong, don't use an array of String, use an array of class Student/Airplane/Book/ProcessItem which has a constructor which validates its own existence as soon as it is made, it will produce a runtime error (or better yet a compile time error) the instant the programmer/user made a mistake.

The millions of unintended paths through calculate() which may throw a cryptic runtime exception has been eliminated. Imagine how much easier it is to diagnose a "InputProcessItemException" than a cryptic off-by-one error inside calculate();

ASP.NET Script injection quiz.

2010-10-20T09:03:00.000-07:00

What is wrong with using this in your ASP.NET code?

<%= textbox.value >

Answer: It allows script injection. Any user generated content should be considered malicious. This line gives someone access to run commands.

Get PowerShell for Windows XP.

2010-09-11T13:44:00.000-07:00

Get Windows Power Shell for Windows XP, it'll blow you away!

http://machinesentience.com/windows_xp_powershell_evaluation.html

Real life uses for Genetic Algorithms.

2010-09-11T07:47:00.000-07:00

I just had a huge idea, just now, a genetic algorithm program that has instantaneous access to your brain's mental state, and can play music/video or sound files. The computer would play things, then examine your mental state after that, then you can tell the computer to optimize for a mental state. Woah, I sense a billion dollars to be made championing something like that. Every human would want it. A bliss machine.

Evolutionary Sodoku solver:
http://watchmaker.uncommons.org/examples/sudoku.php

Professional stock trading:
http://stackoverflow.com/questions/1538235/what-problems-have-you-solved-using-genetic-algorithms-genetic-programming/1538464#1538464

Identify stolen credit cards inside MMO's.
http://stackoverflow.com/questions/1538235/what-problems-have-you-solved-using-genetic-algorithms-genetic-programming/1589627#1589627

Best way to load freight into a truck:
http://stackoverflow.com/questions/1538235/what-problems-have-you-solved-using-genetic-algorithms-genetic-programming/1589612#1589612

Little digital critters in a world with eyes and ears collaborating:
http://stackoverflow.com/questions/1538235/what-problems-have-you-solved-using-genetic-algorithms-genetic-programming/1575154#1575154

Football Tipping:
http://stackoverflow.com/questions/1538235/what-problems-have-you-solved-using-genetic-algorithms-genetic-programming/1575855#1575855

Profile of a Sociopath

2010-09-10T07:56:00.000-07:00

Profile of a Sociopath

I know it's not much to do with programming, but it tends to run in some programmers themselves so I thought it was extremely relevant.

http://www.mcafee.cc/Bin/sb.html

How to install Apache 7 on Windows 7

2010-09-07T09:59:00.000-07:00

Here is how to install Apache 7 on Windows 7:

1. Go to http://tomcat.apache.org/download-70.cgi

2. Download the '32-bit/64-bit Windows Service Installer'

3. Run the exe installer, follow the directions.

4. Restart the computer.

5. In the start menu, find the 'configure apache' button. You have to run it as administrator or it will fail.

6. Navigate to http://localhost:8080

7. Do the tutorials.

Changing the colors of the console.

2010-08-18T13:36:00.000-07:00

Changing the colors of your Linux console/shell is important when your scrolling through black text and you want your eyes to spot the shell line quickly.

If you want to change the colors of your Fedora Linux console line you have to change the PS1 Variable. Here is how I did it:

Step 1: Open up a console.
Step 2: Login as super user.
Step 3: Open up the file /home/yourhome/.bashrc
Step 4: Add this line anywhere after the invocation of /etc/bashrc (outside of the if block):

export PS1="[\e[0;31m\u\e[m@\e[0;34m\h \W \e[m]\$ "

Step 5: Save the file and restart the console.
Step 6: You should see red and blue showing for your shell.

If the codes above confuse you, don't worry, it seems to be a home-brew bash code system. \e[x;y means 'begin color' and \e[m means 'end color'. The escape codes are somewhat straight forward though.

Check out this website for more info on the escape codes:
http://www.cyberciti.biz/faq/bash-shell-change-the-color-of-my-shell-prompt-under-linux-or-unix/

Really good Java Tutorials

2010-08-17T14:58:00.000-07:00

I'm always in search of a good tutorial, this Java tutorial is Amazing, it lets you know everything you need to know, while omitting the unnecessary.

There are 39 chapters, broken out into bite sized bits of knowledge. I'll be spending a few days chomping on this.

http://www.java2s.com/Tutorial/Java/0160__Thread/Catalog0160__Thread.htm

Cleaning a url from the klipboard and opening the file.

2010-08-16T13:02:00.000-07:00

I find myself wanting to open a file that I've copied from the url quite a bit.

1. Copy the url.
2. Open the necessary program.
3. Choose open, paste the link.
4. Edit the file.

I want to reduce this 4 step process to one. The problem is that the full URL has 'localhost' junk in front of it, and I want to trim that out.

It would be faster if I could bind all these actions to F6. Here is how to do it:

Here is a little script that yanks the clipboard content of what you just copied and returns it:

Put this in a bash script, give it permissions to execute:

#!/bin/sh
clipboard_contents=$(dcop klipper klipper getClipboardHistoryMenu > /tmp/klippercontents; head -1 /tmp/klippercontents)
clean_the_url=$(echo $clipboard_contents|sed 's/file:\/\/localhost//g')
echo $clean_the_url

Then go to the control panel, go to accessibility and 'input actions' and add a new keyboard shortcut. Bind it to F6 and use the following command:

bluefish `clean_bluefish_url.sh`

I've been using it all the time. It's a nice little hack.

Burnout, how to recover.

2010-07-26T09:26:00.000-07:00

Eric's short and skinny list on what you are doing to cause burnout in yourself and how to modify/remedy those behaviors

Here is what you do wrong:
1. You feel that you have too much responsibility, and your worth is determined by the productivity of others or the goodness of some process, you perceive them/it as being low-quality and measure your self-worth from that.

2. You do not feel that you are sufficiently appreciated for what you do on a day-to-day basis, you perceive that someone might appreciate you, but they don't.

3. You measure your self-worth by how many useful productive items you can cram into your day.

4. You can't stand it when people question your capability or intelligence, regardless of how high your capability/intelligence is.

5. You are working 60 hours a week or more, work defined as focused goal setting, focused effort, breaking down barriers to progress, mental labor that you perceive as boring or a waste of time.

6. Your entire life is defined by your job, your experiences outside the office are small in comparison.

7. There are cots in your office, and people routinely pull all-nighters/all-weekend/no vacation work. You wake up to work, you stop only to eat and sleep.

8. You find yourself thinking about the other people/processes/events that are causing your productivity to drop (an incorrect understanding of problem).

9. You get mad or angry that someone is saying you are spending too much time working (especially when you are).

10. You think friends, hobbies, useless playing, relationships, games, exercise, and pointless distractions are a complete waste of time.

11. You think the other co-workers are out to get you, and you start getting conspiracy theories going.

12. You think your co workers have lesser value because they don't produce as much as you do.

13. If you are using more and more aggressive behavior to micromanage or control other people's behavior.

14. You are using chemicals to optimize your productivity during the day: Caffeine, chocolate, cocoa, cocaine, soda, sweets, 5 hour power, monster, expresso, etc.

15. Your told that you may be suffering from burnout, and you get defensive and find 27 reasons why you are not suffering burnout.

16. You are feeling depressed.

17. You are feeling a great void in your life, and life seems meaningless, you become fatalist, life is not more valuable than non living material, nothing matters, some alien could squish us like the bug we just stomped and it would be no different.

18. You show up to work, and sit down, but nothing important happens, only meaningless stuff gets shuffled around.

19. If you show up to work and feel that your time is being wasted doing this thing.

20. You are not sleeping enough, you set your alarm clock to get by with as little sleep as possible. You wake up really hard. You disrupted and deprived the brain's of its desired number and depth of cycles of sleep.

21. You think emotions are a useless appendage of the human mind, you think it would be better if everyone made decisions based on cost-benefit analysis, logic and reason.

Eric's short and skinny list; How to remedy your burnout:
1. You feel the work you do is meaningless, stop that work and write down what work would excite you, write down what you want written on your tombstone. Change the work you do so that it works toward something that is filled with meaning and something you care about.

2. Your taking caffeine or sugar or sodas and uppers to increase your productivity. STOP taking those uppers, cold turkey. When you get the munchies eat fruit/vegetables and water.

3. Your taking high octane drugs/alcohol to calm yourself or work yourself up. Cut that out. Alcohol and drugs make the problem worse.

4. You don't feel appreciated, DO NOT work harder to become appreciated, that is the burnout feedback loop. Work to get praise back as a daily requirement. When all that fails, change your job description/bosses/career/work. When that fails, find your passion with other work.

5. You measure your self-worth by how many productive items are in your day. STOP that. Measure your self worth by the number of high-fives you give or your overall health, and set aside 2 hours every day for joining your fitness step aerobics class.

6. You can't stand it when people question your capability. Learn how to shrug it off and say: "Not everyone can be the best performer". And accept their murmurs of your lack of intelligence/capability as totally expected and something to ignore.

7. You are working 60+ hours a week, stop that. Workweeks are 40 hours for a strong reason. On the 40 hours you are not working, do something that cannot be called work by intelligent people.

8. Your entire life is defined by your job, cut out that belief. Your life is now defined by: family cohesion, friends/support group, health/wellness, overall happiness, things other than your work. Stop asking people at parties: "what do you do?". Ask them "What do you think about".

9. You blame other people/processes for your lack of productivity. Move the blame back to yourself and your irresponsible management of your mind. Your lack of productivity is because you screwed up somewhere.

10. You think friends, hobbies, useless playing, relationships, games, exercise, and pointless distractions are a waste of time, they are not, it is time best spent.

11. You think co-workers are out to get you, if it is real, then you can acquire evidence and thus proof and send it to HR, if you can't create an iron-clad case with proof, lose the conspiracy theories.

12. You think your co workers have lesser value for being less productive. NOT true. The less productive employees are terrific, celebrate them every week with a "average employee appreciation day". Treat them with the respect you would give a CEO, and plastic toys from think geek.

13. Stop working on doing a better job, and start working on LOOKING like your doing a better job. Drum up some sustainable routine celebrations for the great things that already are working. Your burning out because nobody is recognizing what work you ARE doing.

14. Work less on making the wiring underneath better and make the presentation better. Everyone is going to attempt to take responsibility for creating the "oohs and aahs". Make sure the recognition comes back to YOU. Don't let people steal the recognition for your work. Burnout comes from being deprived of that appreciation.

15. You have too much responsibility, get LESS responsibility. Make it so that the performance of other humans does not reflect on your performance.

16. If your self worth is determined by how many molecules you shuffle around in a certain way, you'll always be unhappy because there is always more work to do. Derive your self worth from something immovable. One way to do this is to believe that we are fish in a fishtank, and our worth is determined by the fact that the fish-tank still exists and serves a higher purpose. The glory/shame of everything that happens belongs to that, not you.

17. You are letting your health fall behind, spend a few hours a day set aside for exercising and healthy living. Your self worth is not determined by your work, it IS determined by your emotional/mental/physical health.

18. Take your alarm clock and throw it out the window, become an early bird and go to bed by 9PM and wake up early, leaving plenty of time to get ready. Spend 2 months waking up when you naturally feel like waking up. Don't let the alarm clock disturb your sleep cycles. If you can't do that, give yourself at least 9 solid hours of sleep per night. If you can't do that, then continue enjoying the symptoms of burnout.

19. You think emotions are useless. You may be right, but you must still express them, read them in other people, react to them, and manage them. The belief that emotions are a waste of energy will cause critical meters and gauges in your mind to stop measuring and gauging.

You got to burnout by putting your emotional/mental/physical health on the back burner. Put it back as the most important thing you wake up to do.

Good luck, this process will take a year.

If you ignore everything in this list:

OK so you ignored everything in this list. Powered through it, here is what to expect as advanced symptoms of burnout:

1. You will sit down on your computer, and your conscious mind tells the rest of your brain to start performing a work item. You know what to do, you know how to do it, you can think of a series of sub-actions to perform the task, but work will not even begin. A task such as double clicking a certain icon becomes mysteriously difficult, as if your mind is resisting you.

2. Incredible loss of motivation, you could be looking at the source code for the fountain of youth, and you'll fire up your browser to play games and do other time wasting activities. Even though you want to investigate it more.

3. Your circadian rhythms will start moving around, you will experiment with abnormal sleeping patterns, 30 hours days, 4 hour naps during the day, 2 hours awake two hours asleep. This is not healthy unless you have consulted a sleep specialist.

4. Mental errors/illness, you will start making scary lapses of judgment, logic errors and fundamental mistakes will become more frequent, you will become delusional, for example finding the link between terrorist behavior and global warming, and having reasons for believing that.

5. Thoughts of suicide, putting together a 50 item list on why it is better to not be alive than to be burdened with the task of living.

6. Cynicism in overdrive. You will start evaluating people only in terms of their faults and failures, governing change based only on what they have done wrong. Good things done are ignored.

7. You will become ANGRY. More than the regular kind of angry, you'll pound the keyboard, yell on the phone, write emails while snarling and become passive aggressive. You will become angry at little things you normally would deal with easily.

8. You will damage your relationships with family and friends. Leaving you alone in your crystal fortress whom nobody cares about. The computer will not satisfy your every need.

Take it from someone who saw all this play out in a super-achiever over the course of 2-3 years.

Build an Hello World SWT application tutorial.

2010-07-23T08:15:00.000-07:00

I wrote this tutorial for all who want to build a hello world GUI application with the Standard Widget Toolkit.

screenshot_walkthrough_java_application_using_the_standard_widget_toolkit.html

O3D open source web API by google

2010-07-23T05:22:00.000-07:00

I was looking through the source code for Google Chrome browser and bumped into the o3d API. It supports 3D rendering in the browser, check out these videos:

http://www.chromeplugins.org/chrome/o3d-api-a-new-open-source-web-api-by-google

If you are able to get thousands of visitors browsing your site, you could load those processors with rendering tasks and report them back to the server. Then you can sell the CPU power to people who need them.

Click here for the rotating 3d box rendered in the browser:

http://o3d.googlecode.com/svn/trunk/samples/simpleviewer/simpleviewer.html

StackVM Virtual Machine.

2010-07-21T09:19:00.000-07:00

Virtual machines on the browser:

http://catonmat.net/blog/i-am-doing-a-startup?signup=ok

http://news.ycombinator.com/item?id=1534973

StackVM running from within StackVM:
http://www.youtube.com/watch?v=EKFjJ9m_P8Y

Access to human genetic information.

2010-07-15T07:27:00.000-07:00

Hacking the codes that built your mind.

http://www.sanger.ac.uk/resources/downloads/human/

Putting this on my todo list to write some apps and get my hands dirty with human DNA.

Download some DNA and some DNA tools:

http://www.genecodes.com/

Download some of the human genetic information here:

http://completegenomics.com/dataRelease/variations.aspx

Professor Messer

2010-07-14T07:53:00.000-07:00

Epic Video Lectures on computer hardware and software inside and out.

ProfessorMesser Comptia video lectures:

http://www.professormesser.com/free-a-plus-training/220-701/professor-messers-free-220-70x-comptia-a-training-course

Predictive analytics

2010-06-17T12:06:00.000-07:00

Predictive Analytics, the ability to correctly predict the future with enough accuracy to be useful.

Essentially, learning is 'predictive analytics'. "Learning to drive a car" is really predicting the future of what will happen when you manipulate a control.

Here some eggheads at Yale talk about how Insurance houses do their own form of predictive analytics to manage risk and maximize profit:
http://academicearth.org/lectures/real-estate-finance

Check out IBM's Watson, solves jeopardy questions faster than some top contestants, it uses predictive analytics to determine the probability of a correct answer to a jeopardy question:
http://www.nytimes.com/2010/06/20/magazine/20Computer-t.html?hp

Tutorials on Data Mining, Probability, and decision trees, cousins of Predictive analytics:
http://www.autonlab.org/tutorials/

Better than Grandmaster Chess algorithms are a form of predictive modeling that beat out humans:
http://www.research.ibm.com/deepblue/home/html/b.shtml
http://www.shredderchess.com/play-chess-online.html

Introspection robot:
http://www.technovelgy.com/ct/Science-Fiction-News.asp?NewsNum=823

Predictive Analytics World 2010 - The New Data Economy featuring Andreas Weigend
http://www.youtube.com/watch?v=l9NsJXiLhEM&feature=related

Installing the WAMP stack on Windows XP.

2009-11-07T15:36:00.000-08:00

For all of you interested in setting up the WAMP stack. I've created a step-by-step newbie guide on how to do it.

http://machinesentience.com/eric_leschinski_resume/ProgrammingWork/installing_and_configuring_wamp_stack.html

Go forth, wannabees, and make John Carmack, Jack Dorsey and Rob Mallda Proud! Riches beyond measure are there for the taking.

Visual as Audio.

2009-10-31T15:38:00.001-07:00

So I bought this Samsung Netbook NC10 netbook right, Got it for $388:

Then I put this software onto it:
http://www.seeingwithsound.com/

Then I put in my stereo Headphones into it.

Then I took my web cam and duct taped it to the dumbest looking hat I could find.

Plugged in the web Cam.

I put the laptop into a backpack (make sure it's well ventilated and constantly check for overheating) and put duct tape over my eyes and walk around my house for 4 hours bumping into stuff, picking things up, tilting my head like a dog, discovering what objects sound like through this software.

You know those lights you get when you press on your eyes? After 4 hours of practice (with the help of a big dose of caffeine and a hard headed determination and intention to succeed) those light fireworks were starting to correspond to the contours in the room. I was able to hear the locations of various objects in my house.

The grass outside sounds like dropping rice on the floor. The larger the grass it sounds more like a waterfall. Looking at the keyboard adds a tapping like sound. Looking at a wall of uniform color sounds like the wind. Circles, Squares, triangles all have their own unique sound. The hard part is linking which one is which.

I could walk across the room, spin around to get dizzy, reorient myself with only data from the audio, and pinpoint contours in color to within a few inches. However I could not actually figure out what the contour was. The theory goes if you immerse yourself in this you can see depth.

So in conclusion, yes, the Broca's area and Wernecke's area of the left hemisphere of my brain either processes the sound itself as visual data and passes it up to my consciousness. Or it patches the data through to the Visual Cortex for processing. An interesting idea.

I plan on practicing a little bit every day for a while to see how good I can use it. Then the sky is the limit, infrared, wide band radar. Seeing around corners, seeing through walls. This could be huge. We are Borg, your unique properties will be assimilated.

We are indeed machines. Firefighters could probably use this. Swap out the information gathered to lidar, radar, sonar or infrared. Probably should keep these ideas quiet. Probably make a million to champion these ideas and bring a product to wal-mart.

I got this entire setup for under $500. Email me if you want to know more about this. I can get you setup and bumping into stuff in under a week. eric.leschinski@hotmail.com

Infinite Mario Brothers refactoring.

2009-10-20T12:28:00.000-07:00

I just got done decompiling / recompiling Infinite Mario Brothers from source and served it up on my webspace:

http://machinesentience.com/infinite_mario_brothers_applet.html

I'm quite proud I got it up and working, now I can start fooling around with the source and see if I can get some kind of AI to happen.

Throwing in my lot with the programming greats.

L11 Inference.

2009-09-30T07:38:00.000-07:00

In this lesson I'm going to talk about inference.

Good to review what inference is:
http://en.wikipedia.org/wiki/Inference

First read the above wikipedia page, if it hurts your brain, good, that means it's working.

Lets suppose you have a headache, lets calculate the odds you have the flu by inference, Simple Version: click to enlarge.

Ok Got that? Those are baby numbers to make the calculations easy. Now lets calculate the odds you have the flu by inference with real world data. Advanced version, click to enlarge.

Text from the above pictures:
F = Probability a person has the flu.
H = Probability a person has a headache.
A = Those with the flu and no headache.
C = Those with headache but no flu.

A = 6
B = 3
C = 35
F = (A + B) = 9
H = (B + C) = 38

P = Probability function.

P(H | F) = If you have a flu, how likely is it you have a headache?
P(F | H) = If you have a headache, how likely is it you have the flu?

P(H | F) = B / (A+B) = 3 / 9 = 33.33% chance.
P(F | H) = B / (B+C) = 3 / 38 = 7.89% chance.

1. Data Input
One out of 90 people have the flu.
One out of 40 people have a headache.
Of the people who have headaches, 1 in 60 had the flu.

2. Draw this graph

3. Link Graph to Data.
F = (A + B) = 1/90 = .01111
H = (B + C) = 1/40 = .025
B = H * (1/60) = .025*.016667 = .000416

4. Do highschool algebra to get missing values.
Find A:
F = (A + B)
.01111 = A + .0004167
.01111 - .0004167 = A
.01096 = A

5. Gather up the values for each box.

A = .01096
B = .0004167
F = .01111
H = .025
C = H - B
C = .025 - .0004167 = .0245833

6. Apply the probabilistic Inference Equation:
P(H | F) = B / (A+B) = B / F = .0004167 / .01111 = .03750
This means if you have the flue, there is a 3.75% chance you have a headache.

P(F | H) = B / (B+C) = B / H = .0004167 / .025 = .01667
This means if you have a headache there is a 1.667% chance you have the flu.

You might be wondering "you could get there a lot easier by just taking the "one in 60 had the flue" and then calculate 1 / 60 to get .01667.

But in doing out the probabilistic Inference Equation you are able to calculate what percentage of people who have flus get headaches when all you have is data on how many people with headaches get flus.

To code machine intelligence, we will have to get a thorough understanding of how to get computers to "get it" like humans get this intuitively.

With this skill, you can find out the probability that you have the flu based on the knowledge you have a headache when all you know for certain is what percentage of flu sufferers had headaches. Humans have algorithms inside our heads that do this automatically, and here is the mathematical representation of the software in your head.

L10 solving games with AI.

2009-08-30T08:43:00.000-07:00

In this lesson we will review what has been done and is going on in the AI community.

So there is this java based video game called "Infinite mario bros". It has an infinite amount of levels and scenes to play with varying difficulty. If you want to just play it, here it is. http://www.mojang.com/notch/mario/

If the above link is unavailable you might find another with a google search "Play Infinite Mario Bros java".

Infinite Mario Bros controlled by AI:

Sergey Karakovskiy and Julian Togelius setup this competition to optimize playing this video game for time to completion. The details are here: http://julian.togelius.com/mariocompetition2009

There is this Google group discussing the details of the competition:
http://groups.google.com/group/mariocompetition

I saw this java application built by Robin Baumgarten and I was humbled:

http://www.acceleratingfuture.com/michael/blog/2009/08/friendly-ai-supporter-solves-super-mario

Robin Baumgarten, author of http://aipanic.com seems to have written a successful script or program capable of navigating complex dangerous scenes with ease.

His Mario makes a number of mistakes where it seems not to choose the best movement. This leads me to believe that it's short sighted and works itself into corners or else it is a true learning machine and is just making mistakes trying out new things. I wish I could get his source so I can dissect.

Another contestant:
http://www.youtube.com/watch?v=BD4_6ZRrDFk
and
http://www.youtube.com/watch?v=NmpIEbiRyCU&fmt=22

I'll be watching this contest and trying to snag some source code if it presents itself so we can see what strategies they are using.

L09 Whence cometh a sequence java app.

2009-08-25T09:16:00.001-07:00

In this lesson we analyze my attempt at creating a facet of scalable machine sentience.

Look at this java code.

http://mainecode.com/sentientmachine/ProgrammingWork/machine_learning_pattern_guessing/Runner.java

I coded this up in about an hour, it's nothing too special. It's not that smart. It just implements what I discussed in the previous lesson L08.

L08 Whence cometh a sequence?

2009-08-07T17:04:00.000-07:00

In this lesson we look at a few patterns. A reasonably college educated human could figure out what mathematical formula caused these patterns. We explore what it might mean if software could get at the root of every kind of mathematically generated pattern. In the next lesson I'll show you a java program I whipped up to implement what I'm describing.

This idea comes from Douglas Hofstadter's book Fluid Concepts and Creative Analogies.
link: http://books.google.com/books?id=somvbmHCaOEC&lpg=PP1&ots=oiCRgrQN1L&dq=douglas%20hofstadter%20fluid%20analogies&pg=PP1#v=onepage&q=&f=false

Buy the book, he really conveys the depth of this strategy of building computer sentience in software.

In the first chapter: "To seek whence cometh a sequence" Douglas Hofstadter provides four sequences:

1,3,6,10,15,21,28,36,45,55,66,78,91, ...
1,4,9,16,25,36,49,64,81,100,121, ...
1,1,3,4,6,9,10,15,16,21,25,28,36, ...
2,1,2,1,1

The first pattern is the sum of all integers up to the index of the position, so position 5 = 1+2+3+4+5 = 15

The second pattern is the sum of all odd integers up to the index of the position, so position 5 = 1+3+5+7+9 = 25

The third pattern is patterns 1 and 2 spliced together, put into order.

The fourth pattern is the count of (pattern 1 objects) situated between the (pattern 2 objects).

He did this because the pattern 2,1,2,1,1 seems to have a chaotic progression to it when he calculated it out:

2,1,2,1,1,2,1,2,1,2,1,1,2,1,2,1,1,2,1,2,1,2,1,1,2,1,2,1,1,2

He wanted to find the simplest rule that governed the seemingly simple progression of 1's and 2's. The majority of the chapter is devoted to his strategies of how he went about trying to figure out whence cometh that sequence.

Later in the chapter, he provides 20 other complex sequences like this. Douglas said that if one could create an algorithm that would deduce where all those sequences came from as well as every conceivable pattern within the infinite set of mathematically generated patterns, then it would be sentient just as we regard college educated humans as sentient (in the area of mathematical pattern recognition).

One strategy he raised for building a program that would accomplish this is to simplify a pattern by applying modifiers to it. For example, take this mysterious pattern:

1,4,9,16,25,36,49,64,81,100,...

The more perceptive of you already know what this sequence is. For our purposes, all you need to know is that we have a list of numbers, and we want the next one in the sequence.

Step 1, apply a modifier to this sequence (Take the differences between each number) and assemble it into another child sequence:

3,5,7,9,11,13,15,17,19, ...

Humans and computers can simply look at this pattern and deduce what comes next. But suppose we still don't see it? Step 2, run the same modifier on it again!

2,2,2,2,2,2,2,2,...

The pattern is strong with this one, humans and computers can easily predict the next number in the sequence. It's "2".

So with this knowledge of the next number in the sequence, percolate that up to the original sequence, and thus, you have your next number. (It is the sum of all odd integers up to the index of the position position 5 = 1+3+5+7+9 = 25).

Douglass says this method sounds promising because each new learned sequence could be entered into the knowledge base of "known sequences". That would enable it to quickly get at the source of some very complex patterns. But the computer is not thinking as a human does. Humans attach ideas to individual numbers and groups/sets/oscillations of numbers. Humans notice that a '25' can be seen as a (5 * 5). This algorithm above does none of that.

The main problem with this strategy is that trying all the possibilities will require too much time and energy. If the software is to find the root of a complex pattern, it must have a massive amount of modifiers in it's library. It will also need a clever depth first strategy or else it will too long searching the infinite search space.

Thus machine is cursed with the same curse of man if it is to become sentient: You can't search infinity, so you better do the best you can with what you have.

In the next lesson I'll show you my best attempt to write this program.

L07 Java learns a perfect game of tic-tac-toe.

2009-07-28T06:45:00.000-07:00

In the previous lesson we talked about the principle of how to use statistics, memory and rules to create an algorithm that can learn to play a perfect game of tic-tac-toe. Lets code it in java.

I coded up a java application last night in 2-4 hours that illustrates two learning algorithms playing tic-tac-toe against each other thousands of times and learning to play a perfect game far faster than any child or adult human could.

See the java code here:
http://machinesentience.com/java_machine_learning_example.html

Board index positions:

 0 | 1 | 2     
-----------
 3 | 4 | 5 
-----------
 6 | 7 | 8

A normal boring state
Below is a state for player1. X is to move. See cupContents below, it's contents were determined after 4000 games. '2' represents board index position 2 seen above. X has learned that 2 is a win and 5 is a loss, thus there are more '2' than '5'.

 X | X |  
---|---|---
 O | O |  
---|---|---
 X | O | O
cupContents:  '2222222222522222222'

Another state:
Here is where the my learning algorithm surprised me, it understands it's own "guess and learn" mentality and chooses a situation that forces a board win over an immediate win. Consider the following state:

 X |   | O
---|---|---
   | X | X
---|---|---
 O |   | O
cupContents:  
'11333333333377777777773333333377
777777777777777777777777777777'

Above: X to move. To move to position 1 is dumb, 1 is small, that's as I expect. 7 is the most likely choice and 3 second most likely. Why is 7 a more desirable play? Position 3 is the immediate win! Is the learning algorithm broken? Not at all, position 7 creates the triangle formation which forces a win even when X's learning is sub-optimal. The learning algorithm is making provision for what it knows it might not know. Humans do the same thing, we choose a bird in the hand over 2 in the bush.

I'm putting extra emphasis on this because it is the secret sauce of learning algorithms. It learns its own weaknesses. We want to encourage our future algorithms to do the same kind of thing.

Another state:

 X |   |  
---|---|---
   |   | O
---|---|---
   | O |  
cupContents:  
'2344668822666666662222222288888888188888888
66666666888888881111111122222222666666662222
222211111111'

X to move. The above state looks dangerous for X because O is about to secure the deadly triangle formation which can guarantee a win. X notices that position 8 is pretty good because it blocks all that. But it also notices that '2' and '6' are pretty good too, X is trying to beat O by winning faster than O can form it's O triangle. It likes position '1' over '3' even though they are equivalent, that's just the way the game progressed. If it played even more maybe it would discover 1 is a bad move too.

Thoughts on learning that a loss < draw < win

This application is not perfect, a small change can greatly improve it, I'll let you do it if you want, consider this state:

      | O |  
   ---|---|---
    X | O | O
   ---|---|---
    O | X | X

X to move. The choices are position 2, Draw, and position 0, loss. This Java app algorithm punishes Player1 with varying intensities for draw and loss, so the beads in the cup are reduced to the minimum and the cupContents reach the minimum and essentially results in a 50/50 pick. That is not learning.

The problem is that this algorithm has no concept of "given a choice between loss and draw, choose draw". We see 3 choices to fix this, understand the pros and cons of each:

1. Descend down and teach it a hard and fast rule: "Given the choice between draw and loss, choose draw". But that's just normal rules based programming and has been done millions of times before so that's a waste of our time.

2. Don't punish the player at all for drawing. This would result in position 2 being much more likely than position 0. However it would not accumulate that wisdom by itself, it's only working that way because that's how the programmer coded it to work, no learning occurred with that state.

3. The best fix would to reward the player a small amount for a draw, and reward it a large amount for a win. This way, over time, the algorithm will accumulate the knowledge by itself that a draw is more desirable than a loss, and a win is more desirable than a draw.

Geek out.

L06 How to learn how to play tic-tac-toe.

2009-07-23T20:26:00.000-07:00

In this lesson we analyze a learning algorithm that is capable of learning how to play a perfect game of tic-tac-toe on its own.

I borrowed this idea from Bruce Frey's O'REILLY Book: "Statistics Hacks", Hack #52 page 216-220.

Books.google.com has a preview of the latter half of that chapter: http://books.google.com/books?id=HOPy...

I don't want to steal Bruce Frey's thunder (go buy the book). But to summarize, he explains that you don't need a computer to make a learning algorithm. The thought experiment shows that successful learning can be accomplished with statistics, memory and rules. What you'll need is 287 cups and a large supply of beads consisting of 9 different colors.

The nine colors represent each of the nine different spaces on the tic-tac-toe board. The 287 cups represent the different configurations of X's and O's on the board. There are far more than 287 configurations, but because the layout is a square, rotations of the board are summarized into one position. I assume further compression could be done based on board configurations that would never occur (like a board with 5 X's and only 2 O's).

So we begin teaching the learning algorithm by playing a game of tic-tac-toe. We are 'X', the algorithm is 'O'. The algorithm goes first, the initial state of the board is blank. Go to your cup corresponding to that state and pull out a random bead. Mark an 'O' on the board representing the color. Save the bead by setting it down next to the cup it came from. Now make your move. Now the board will have a new state. Choose the cup representing that state, and repeat until the game is over.

If the learning algorithm wins, add more beads of the same color to the cups that lead to that victory. If it lost, or ended in a draw, throw away the beads you collected.

If you play this game thousands of times, the learning algorithm will learn to play a perfect game of tic-tac-toe and will make the move which most likely results in a win every time.

Bruce Frey does the description of the problem much more justice, I suggest you take a look at it in your local borders or barns and noble. It's in the math section.

Totally impressed with the chapter, I went ahead and coded it up in Java, in the next lesson we will examine the source code that proves that this learning algorithm works and examine it's limitations.

L05 Definitions

2009-07-17T16:59:00.000-07:00

Decision Trees - http://en.wikipedia.org/wiki/Decision_tree
A decision tree is very simple. Wikipedia uses big words for something easy. This picture should be worth a thousand words:

Suppose I have a piece of bread I want to sell you. It is moldy and 60% off. I instruct you to evaluate whether or not you want to buy my bread based on the decision tree in this image. If you correctly follow the instructions, you will buy the bread. We can improve this tree quite a bit by hand. But the fun part will be teaching the computer to improve this decision tree based on collected data and observation of probabilities.

Tractable and Intractable - http://knowledgerush.com/kr/encyclopedia/Intractable_problem/
An intractable problem is a problem that is not easily directed, managed or governed. A tracktable problem is a problem that is easily directed, managed or governed. An example of an intractable problem (to me) would be an algorithm that optimizes what to say to the opposite sex to cause a certain emotion. Exploring the entire solution tree of an intractable problem can be problamatic, and if we are not smart, we may miss the most important subtree altogether.

Cost Function - http://economics.about.com/od/termsbeginningwithc/g/cost_function.htm
A function which when calculated will tell us how much the solution costs based on parameters passed in. For example the traveling salesman problem cost function would be a sum of the distance between the cities traveled to.

Contingency Table - http://en.wikipedia.org/wiki/Contingency_table
Wikipedia says it best: "A contingency table is used to record and analyse the relationship between two or more variables, most usually categorical variables." The illustration used connects gender with handedness. If the proportions of individuals in the different columns varies between rows (and, therefore, vice versa) we say that the table shows contingency between the two variables. If there is no contingency, we say that the two variables are independent.

Data Mining - http://en.wikipedia.org/wiki/Data_mining
Finding patterns in data. For example the duration of a wire-tapped phone call measured against the average volume of the voice on the call. Would there be a correlation between volume and length?

Information gain - http://www.cs.cmu.edu/afs/cs/Web/People/awm/tutorials/infogain.html
Huge subject, saving this for another lesson, it measures how we are able to predict one variable by observing a different variable.

Overfitting - http://en.wikipedia.org/wiki/Overfitting
Overfitting in the field of Machine Learning is where an algorithm actively makes a connection between random data and predicted output. The observations and stats gleaned will most likely mislead it in future tests without random data in it. In order to avoid overfitting, it is necessary to use additional techniques (e.g. cross-validation, regularization, early stopping, Bayesian priors on parameters or model comparison), that can indicate when further training is not resulting in better generalization.

cross-validation - http://en.wikipedia.org/wiki/Cross-validation_(statistics)
A great way to eliminate invalid test hypothesis suggested by the data. What you do is take your original testing set and split it into multiple sub-test sets. Training the learning algorithm on each, then testing it on the others, doing it both ways and averaging the results.

Testing hypothesis suggested by the data - http://en.wikipedia.org/wiki/Testing_hypotheses_suggested_by_the_data
A set of data that implies a strong correlation between two variables. This does not automatically guarantee that there is a correlation between those two variables. Type I and Type II errors (false positives and false negatives) can be produced by always assuming that testing hypothesis suggested by the data are valid.

Type I and Type II errors - http://en.wikipedia.org/wiki/Type_I_error#Type_I_error
Fancy names for false positives and false negatives. These are caused by rejecting the null hypothesis when you shouldn't have and accepting it when you should have rejected it.

Bias - http://en.wikipedia.org/wiki/Bias http://en.wikipedia.org/wiki/Biased_sample
Meaning unjust, lacking integrity, Bias is where there is a preference for certain ideas or data over others when the preference is unjustified given the subject at hand. A biased sample of data can show a correlation between variables when in fact none exist. The correlation was caused by the bias itself.

Pedantic -
A pedant is a person who is overly concerned with formalism and precision, or who makes a show of his learning.

Binary categorical splits -
Allows a decision tree split of the form "attribute IS value" and "attribute is not value". See below image.

For more information on Binary Categorical Splits see http://www.autonlab.org/tutorials/dtree18.pdf

Regression Trees - http://en.wikipedia.org/wiki/Decision_tree
A regression tree is a kind of decision tree that has Real valued outputs meaning that the outputs can be a decimal or integer instead of a boolean or category.

L04 Understand crossover strategy.

2009-07-14T08:55:00.000-07:00

In the last lesson we discovered how the eaters link what they see to an action to perform. Though entertaining, this process alone will only produce randomly moving eaters. In this lesson we investigate exactly how the eaters evolve/learn.

Open up GACanvas.java, look at the crossWith function:

private static class Chromosome 
{
  .
  .
  .
  void crossWith(Chromosome c) {
    int crossPoint = (int)(Math.random()*128);
    byte temp;
    int ct = 0;
    for (int i = 0; i < 16; i++) {
      for (int j = 0; j < 4; j++) {
        if (ct > crossPoint) {
          temp  = newState[i][j];
          newState[i][j] = c.newState[i][j];
          c.newState[i][j] = temp;
        }
        ct++;
        if (ct > crossPoint) {
          temp  = whatToDo[i][j];
          whatToDo[i][j] = c.whatToDo[i][j];
          c.whatToDo[i][j] = temp;
        }
        ct++;
      }
    }
  }
}

Marked in red shows the genetic material mixing strategy. David Eck has chosen a 'Single Point Crossover' strategy. To get a visual representation of what's going on here, read all of this:
http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php

This 'Single Point Crossover' strategy can damage the discoveries of the parent eaters, so why does he use it? Why damage the potential discoveries? Why not just just make copies of the best eaters?

Good question. David Eck knows that combining parents will increase the chance that a child will get 2 smart ideas in it where each parent only had one smart idea each, the child will be much better at finding plants.

Let me illustrate with colors:

    Legend:
      row 0 = eater sees a wall.
      row 1 = eater sees an eater.
      row 2 = eater sees a space.
      row 3 = eater sees a plant.

      0 = turn left
      1 = turn right
      2 = move forward
      3 = move backward

      dash = Junk Data, random dumb movement.

Here is Mom's genetic code, she has figured out that when you see a plant, the best movement is to move forward into it. She also discovered that if you see a wall, the best movements are turn right, turn left, or go in reverse. Good job Mom. One problem, the right side of her genetic code is full of junk. When her state is set to 4 or higher, she starts doing dumb things.


   Mom's newState array:
   0  0313110---------
   1  -100------------
   2  -2--------------
   3  2222------------

Here is Dad's genetic code, like Mom, he figured out that seeing a plant means you should move into it. But his good ideas are only on the right, not the left. Just like mom, he does well when the state is 9 or higher, but when it is lower, he moves randomly.


   Dad's newState array:
   ---------100110-
   ---------1212122
   ----------------
   ---------22-2-2-

So here is our dilemma, how to we mate these two champions? Should we populate the world with new copies of Mom and Dad and let them duke it out? What if there was a way to keep the good idea of Mom, and keep the good idea of Dad and put both into ONE the child eaters? This eater would always do the smart thing.

So I'm hand picking a crossover point for the Single Point Crossover as position 6 so we can see the potential.

So here is our Child eater:

   0  031311---100110-
   1  -100-----1212122
   2  -2--------------
   3  2222-----22-2-2-

This child eater is much smarter then the individual parents. This situation happens once in a great while, the risk of damaging the genetic code to secure these gains are worth it.

We've exhausted the Genetic Algorithms part of this program. The rest is just rules to refine this process. The Mutation part introduces mistakes into the child genetic code. Suppose state 5 had '2'(move forward) for sight '3'(see plant). This is a wise thing to do. But the mutation flips this to 'turn right'. In most situations this is only going to hurt productivity. But once in a great while it will actually make the eater do the right thing instead of the wrong thing.

The magic of this program is that complexity emerges within it that I haven't described. Given enough CPU time, the eaters will discover strategies for circling the clumps of plants when it finds them. Also the eaters develop good search strategies, like circular motions or scanning patterns. Also, when the eaters approach lots of eaters, it's likely a good idea to go far away from there because the eaters likely already ate up the food. The eaters discover competition is bad if it wants a big clump for itself.

And thus, man became the architect of his own demise, though loyal and pure, the machines earned no respect from their masters, these curious, endlessly multiplying mammals.

L03 Understand the genetic material.

2009-07-11T18:48:00.000-07:00

In the last lesson you got David Eck's GA program to run in Eclipse. You should have the source code visible. Open up GACanvas.java, see the java class called Chromosome:


   private static final int turnLeft=0, 
                            turnRight=1, 
                            forward=2, 
                            back=3;
   private static final int seeWall=0, 
                            seeEater=1, 
                            seeSpace=2, 
                            seePlant=3;
   ...
   ...
   ...

   private static class Chromosome
   {
      byte[][] newState = new byte[16][4];
      byte[][] whatToDo = new byte[16][4];
      void randomize() {
         for (int i = 0; i < 16; i++) {
            for (int j = seeWall; j <= seePlant; j++) {
                newState[i][j] = (byte)(Math.random()*16);
                whatToDo[i][j] = (byte)(Math.random()*4);
            }
         }
      }
      .
      .
      .
   }

Highlighted in red are arrays named newState, and whatToDo. It might be useful for us to review what a Chromosome is:
http://en.wikipedia.org/wiki/Chromosome.

Biologists will note that this array David Eck has created is not exactly a Chromosome. Here is the primary difference:

A Biological Chromosome ...
Contains instructions to build every interdependent system and component of a life form.

David Eck's Chromosome Array ...
Contains instructions to link 1 of 4 observations to 1 of 4 defined movements.

So 'Chromosome' is a bit of a stretch. Moving right along, here is what the arrays look like, the genetic material is outlined in bold blue with explanations on the right:

newState array:


      0  1  2  3          Meaning of array data:
      -----------         ----------------------
                          The values in newState are 
0     12 9  4  8          assigned from 0 to 15.
1     11 12 8  3          
2     14 3  9  13         Each row in this array is called 
3     2  0  10 11         a 'state'.
4     3  7  15 9 
5     1  8  11 2 
.                         In each iteration, the eater 
.                         sees, then acts, then loads 
.                         the next state as defined 
15    12 10 9  15         in newState.

whatToDo array:


      0  1  2  3           Meaning of array data
      ----------           ---------------------
                           0 = turn left
0     0  3  0  1           1 = turn right
1     3  2  1  1           2 = move forward
2     2  1  0  3           3 = move backward
3     1  0  3  2
4     3  1  2  3
5     2  3  0  0
.                          
.                        
.
15    1  1  3  0

For both of the arrays, columns 0 through 3 represent what the eater sees directly in front of it:
column 0 = eater sees a wall.
column 1 = eater sees an eater.
column 2 = eater sees a space.
column 3 = eater sees a plant.

Here is how the eater links sight to action:

Eater starts on state 0

The Eater looks ahead.

Eater sees a plant!

plant is represented by column 3

whatToDo array is read [state index][see what]

Eater sees that we should do action 1

Action 1 = turn right

Eater turns right

newState array read [state index][see what]

Read newState as '8'.

Repeat step 1 with state 8.

This loop is done many times, and if the eater lands on a plant, the eater's score is incremented by one. At the end of a generation, all of the scores of all the eaters are reviewed, and only the eaters that got the most plants get to have their genetic codes passed onto the next generation.

In the next lesson we talk about how the eater parents make out and combine the two genetic codes to create several offspring with genetic codes that are likely to retain the discoveries of the parents. Also we'll talk about how errors in the genetic code copying (mutation) is absolutely necessary for the eaters to become diverse and speed the discovery of new food finding strategies.

L02 Compile a Genetic Algorithm in Java.

2009-07-10T11:27:00.000-07:00

The purpose of this lesson is to compile and run David Eck's GA program illustrated in "Lesson 01". This lesson assumes you have proficiency to install Eclipse and build a java application, if you don't, you might want to find some tutorials that walk you through creating an Eclipse Java 'Hello World' Application before following along.

If you already know how to compile a java application through Eclipse then you can skip this lesson after downloading, installing and running the java files HERE.

Step 1: Download Eclipse and run it
http://www.eclipse.org/downloads/download.php?file=/technology/epp/downloads/release/galileo/R/eclipse-java-galileo-win32.zip

Step 2: Create a new Java Project File -> New -> Java Project

Step 3: Name the project 'GeneticAlgorithmExample', press Finish.

Step 4: Download the java files HERE

Step 5: right click the 'src' directory and click New -> Class

Step 6: You will be creating 5 empty class files under the 'src' directory, the names of the class files is as follows:
GACanvas.java
GAFrame.java
Launcher.java
RadioGroupMenu.java
ReportWin.java

Step 7: Access the files you downloaded in step 4, paste the content of the downloaded files into your class files with the same name.

Step 8: Compile and run the program, if you don't have the right version of Java installed and accessible by Eclipse it may spit up errors. I use the latest version of java-1.7.0-icedtea but I assume most versions would work from java 1.4.0 or higher.

Step 9: Your Artificially Learning eaters should be on screen and doing their thing trying to locate food and getting better at it. Play around with it. You should notice the arrays holding the genetic material and the functions responsible for mutation and reproduction.

This is what you should have on screen at this point:

Click to Enlarge:

In the next Lesson we will examine the individual functions in detail.

L01 Preview a Genetic Algorithm.

2009-07-09T17:57:00.000-07:00

The purpose of this lesson is to demonstrate the power of the Genetic Algorithm in laymans terms. This lesson is not to teach you, but to impress you.

To prove that the long words I use are not just a waste of brain space, we'll look at an example proving that Genetic Algorithms are very useful.

Visit this website: http://math.hws.edu/xJava/GA/

On that website there is an applet embedded into the web page, if it does not show the button called: "Start the World" then try a different browser. Firefox worked for me.

This screen shot shows what David Eck has coded in Java:

The red lines are eaters, the green circles are food.

The eaters have one sensor to see what is ahead of them. They have effectors to rotate or move themselves. Each eater has a 2D array of instructional data that determines what the eater will do based on what it has seen.

If you observe the behavior over the first 20 generations and then choose the 'Speed' Menu and select "Highest" for a few minutes and then set it back to normal speed you will see that the eaters are getting more proficient at locating the food.

After hundreds of generations the eaters start to appear life like, they appear to move toward their intended destination which is the food.

David Eck did not write code to cause the eaters to efficiently find food, in the next lesson we will run the code through Eclipse ourselves to prove that.

In case David Eck takes down the site, here are the Java code files:
Backup of David Eck's Source code in Java

GACanvas.java, GAFrame.java, Launcher.java, RadioGroupMenu.java, ReportWin.java

Definitions

2009-07-08T19:47:00.000-07:00

The notion of Machine Intelligence and Machine Learning gets me up in the morning. I Love it. It can make you happy too.

Lets start with terminology.

1. Heuristic - http://en.wikipedia.org/wiki/Heuristic
An algorithm that gets us to an approximate solution very fast. The heuristic algorithm uses common sense, good judgment and educated guesses to arrive near the best solution.

2. Metaheuristic - http://en.wikipedia.org/wiki/Metaheuristic
A Heuristic finds the best solution value, a metaheuristic finds the best solution heuristic. Use Metaheuristics to solve how to best solve computational problems.

3. Simulated Annealing - http://en.wikipedia.org/wiki/Simulated_annealing
Annealing in metallurgy is where you harden a metal by cooling it slowly which allows the entire batch of metal to be more pure than if cooled quickly. Doing Simulated Annealing means a a Metaheuristic Algorithm is being used to produce a solution set by randomly changing properties within the state and evaluating if that change would lead to a better state.

4. Fitness Algorithm - http://en.wikipedia.org/wiki/Fitness_function
Is used to calculate which solution is better. Without a reliable fitness function, the Genetic Algorithm will not evolve toward the best solution.

5. Genetic Algorithms - http://en.wikipedia.org/wiki/Genetic_algorithms
Algorithms that use inheritance, mutation, selection and crossover to evolve the group toward better solutions. A fitness function is used to determine which solutions are selected, mutated, crossed over and passed down to create new offspring solutions.

6. Channel Routing - http://en.wikipedia.org/wiki/Routing
Describes a kind of problem where multiple routes to a destination exist. The route selected needs to be chosen and optimized for balance as well as speed. Channel Routing describes the solution selection process that chip designers use to pack as much functionality on a chip as possible. With the Travelling Salesman problem, channel routing describes how solutions are initially chosen.

7. Travelling Salesman problem - http://en.wikipedia.org/wiki/Travelling_salesman_problem
A kind of problem best solved with a heuristic, or Genetic Algorithm because it is NP-Complete. Brute force, or deterministic approaches to solving NP-Complete problems will never produce the best result for large problem sets.

8. NP-Complete - http://en.wikipedia.org/wiki/NP-complete
This means that the algorithm will take an unreasonable amount of time to solve exactly for medium to large problem sets. The time needed to solve the problem approaches infinity as the size of the input set increases. Heuristics and Genetic algorithms are required for NP-Complete problems.

9. “Million Queens” problem - http://en.wikipedia.org/wiki/N_queens
Put a million queens on a chessboard with a width of 1 million squares such that no queen is attacking another. It would be ridiculous to place them all on the same row and test that for fitness. Solving 8 Queens quickly illustrates understanding of algorithms. Solving the "million queens" requires knowledge of well built heuristics to vastly decrease the solution set.

10. Iterative Improvement
Starting at a random state, change something and evaluate if the situation improved. If yes, keep the change, if not go back. Store the best value and if your stuck, restart somewhere else.

11. Local Optimum - http://en.wikipedia.org/wiki/Local_optimum
A solution is the local optimum when the immediate neighboring solutions are all worse than the current one. To break out from local optimum, a breakout strategy must be used. Breakout strategies include increased mutations, randomness or restarting elsewhere.

If you understand and are interested in all of these terms, this PDF from Carnegie Mellon will interest you http://www.autonlab.org/tutorials/hillclimb02.pdf

I Found it through here: http://www.autonlab.org/tutorials/

Introduction.

2009-07-08T19:24:00.000-07:00

The objective of this blog includes educating myself and others about everything related to elite programming and machine learning.

I started it because I want to create a function to predict the future of the securities markets by writing software to find and rate positive divergence in the stock market. But in order to do that I'll have to expand my mental faculties by immersing myself in this stuff.