July 25, 2010
K-Means Clustering

  • Since I had a temporary lapse in journal access, I had to put a hold on victorant.tumblr.com. That kind of meant a hold on this too!
  • Never worry though, I’m still here. We’re about to do K-Means clustering. Ready —- GO!
  • K-means is an algorithm for grouping data into clusters. You don’t have to know anything about the clusters, just about how many there are.
  • K-means falls under “unsupervised learning”: http://drfiveminutes.tumblr.com/post/462273941/types-of-learning
  • Remember that your data set can be seen as a collection of points in d-dimensional space. Example: a point can be (age, weight, height).
  • The algorithm is as follows: 1. for each cluster you think you’ll have (k of them), pick a random point. That’ll be your mean.
  • 2. Associate every point with the closest one of those means. Regular old straight-line distance works for this. These are now clusters.
  • 3. The centroid of the clusters (basically center point of that cluster) becomes the new mean.
  • 4. Repeat steps 2 and 3 until the algorithm converges and nothing changes anymore. Or until you get tired.
  • It works best when you know roughly how many clusters you need. Always be sure to visualize your data. And now a demo in R. Copy/Paste.
  • x <- matrix(rnorm(100, sd = 0.1, mean = 1), ncol=2) # make some 2 dimensional points with normal distribution around 1
  • y <- matrix(rnorm(100, sd = 0.1, mean = 0.7), ncol=2)
  • z <- matrix(rnorm(100, sd = 0.1, mean = 0.4), ncol=2)
  • mat <- rbind(x,y,z) # stick all our points together into one matrix
  • kcluster <- kmeans(mat, 3, 25) # R has a builtin kmeans function. we are calling it with our points, 3 clusters, and 25 iterations
  • plot(mat, col=kcluster$cluster) # plot our points, coloring them by the cluster they are in
  • If you run this more than once, you’ll find that your cluster may change. That is because the initial means are randomly selected.

    • 7:53pm  |   URL: http://tmblr.co/Z_gONypByuJ
    (Notes: 1)
      
    Filed under: k-means clustering machine learning 
    April 9, 2010
    Monte Carlo Integration

    A Haiku

    Need an integral?
    Sample the important parts.
    (finding dist. is hard)

    3:37pm  |   URL: http://tmblr.co/Z_gONyUL5eT
    March 20, 2010
    Types of Learning

  • Types of learning overview, starting now!
  • There are three types of learning: supervised, unsupervised, and reinforcement learning.
  • In supervised learning, all of the data is associated with tags. The tags say what the data is.
  • Example: if you wanted a neural net to learn handwritten digits, you would point it at the pixels of an image and say tell it number it was.
  • Labels are great, but most of the data in our wonderful world is unlabeled. That is where unsupervised learning comes in.
  • In unsupervised learning, you let the machine figure out which things are similar and which are different.
  • Hopefully it will see that a ‘3’ doesn’t look like a ‘7’, and there are about 10 different groups it can make.
  • Sometimes you have to give it a little help by telling it how many groups it should make. You don’t have to say what is in them, however.
  • In reinforcement learning, you don’t give anything labels, you just say whether or not it got its guesses right.
  • Here is a video of a neural net training with reinforcement learning: http://www.youtube.com/watch?v=Zybl598sK24

    • 10:59pm  |   URL: http://tmblr.co/Z_gONyRZRsL
    March 20, 2010
    Neural Nets

  • Neural nets, starting now!
  • First, a picture: http://www.ejbi.cz/media/full-138.jpg
  • Neural nets are used for recognizing patterns. They are simplifications of brains.
  • A neural net is made up of nodes (neurons) and connections between them (synapses).
  • They generally come in layers of neurons: one visible layer, a number of hidden layers, and an sometimes an output layer.
  • The visible layer matches features that you want to learn. Features can be pixels, temperatures, squares on a game board…
  • The hidden layers are magic. Long ago somebody proved that you can’t learn certain stuff (e.g. xor) without them, so now we have them.
  • A neuron can be on or off. The state it is in is dependent on the weights of the connections to it.
  • To train a neural net, you set those weights. There are lots of ways to do this, including simulated annealing and genetic algorithms.
  • To see if it recognizes a pattern, look for the state of the nodes in the output layer. That’s pretty much it!

    • 10:42pm  |   URL: http://tmblr.co/Z_gONyRZJhy
    March 13, 2010
    Hopfield Nets / Boltzmann Machines

  • Hopfield Networks, starting now!
  • Pretend are a student at a large midwestern university, watching out your window as the snow falls on the quad.
  • You don’t have a snow day today, so there are people still milling about.
  • You notice that the paths people walk on the most get carved deepest into the snow, while the the others remain shallow or fill up.
  • (I think these are called “opportunity paths”, but I can’t find a link saying this. Can somebody refresh my memory?)
  • A Hopfield network is a recurrent neural net works pretty much the same way.
  • (Neural net being something I will discuss later, and ‘recurrent’ meaning there are cycles in it.)
  • Things it sees more often get “carved deeper,” leaving you with with little valleys and channels.
  • Training it would be akin to walking around on your quad.
  • Testng to see if it recognizes a value would be like freezing all that snow in to ice, and then tossing a beach ball out your window.
  • The ball will want to come to rest at the bottom of the a valley.
  • For this reason, we say that it will always converge to a local minima.
  • The ball won’t necessarily fall into the deepest valley.
  • It will also get a little confused if there are two valleys that cross each other.
  • But more-or-less you can get an idea of where people have been walking in your quad.
  • Here is an applet you can try out: http://lcn.epfl.ch/tutorial/english/hopfield/html/index.html
  • ——- Bonus Round! Boltzmann machines! ——-
  • @lefavor, this is for you. Thanks for requesting it!
  • A Boltzmann machine is a lot like a hopfield net, but it is probabilistic.
  • Those valleys aren’t where people have walked, they are where people have _most likely_ walked.
  • A deeper valley translates to a higher probability.
  • If you toss a beach ball on to the same spot twice now, you may not get the same outcome twice.
  • You will, however, get responses matching that particular probability distribution.
  • This trait make it great for simulating creatitivity:
  • Take a little bit of what you learned here and there, and mix it all together to make something new.
  • Like, for example, jazz.
  • ( http://creative-systems.dei.uc.pt/icccx/programme/acceptedpapers )
  • I think that is enough tooting my own horn for now. I will go back and explain neural nets before I go any further.
  • Hopfield Nets / Boltzmann machines!

    • 1:31pm  |   URL: http://tmblr.co/Z_gONyQafE7
    March 13, 2010
    Bayes’ Theorem

  • Bayes’ Rule! Starting NOW.
  • Say you have two events. We’ll call them A and B.
  • They may depend on each other, or they may not.
  • For example, A could be storms in the gulf of Mexico, and B could be solar flares over the course of the year.
  • Just events.
  • There is a probability associated with those two, called P(A) and P(B).
  • The probabilities for the events by themselves are prior knowledge: we know them before hand.
  • We want to find the probability of those two events happening together, P(A,B).
  • Notational point: “The probability of B given A” is written as P(B|A).
  • So, we could assume that A happens, and find the probability of B given A.
  • That gives us P(A)P(B|A)
  • Or we could assume B happens, and find the probability of A given B
  • P(B)(A|B)
  • Those two things are equivalent.
  • P(A) P(B|A) = P(B) P(A|B)
  • Great! But what if we want to find the probability of just B given A?
  • Well, we have an equation, we just need to manipulate it a little.
  • P(B|A) = [ P(B) P(A|B) ] / P(A)
  • The probability of B given A is the same as the probability of A given B times the probability of B, divided by the probability of A
  • Bayes Theorem!
  • That was close! I should consider changing my name to Professor Ten Minutes.

    • 1:30pm  |   URL: http://tmblr.co/Z_gONyQaeeD
    March 13, 2010
    Garbuzov Zones

  • Yesterday somebody asked me about one of my current project, so I will try to explain it in five minutes.
  • Garbuzov Zones, starting now!
  • So a long time ago there was this guy sitting in his cave, shouting and throwing rocks and making all kinds of noise
  • Then Pythagoras was like, hey, stop that, let me show you how notes work
  • He had this single-stringed instrument that he used to show that you can make notes
  • The notes were related to each other through the rational numbers, through ratios p/q where p and q are both integers
  • For example, an octave is twice the frequency of the root, 2/1
  • and the perfect fourth was 4/3 times the frequency
  • All together, these make up the _overtone series_
  • ( I am going to skip ahead a little here, past tetrachords and the construction of basic scales)
  • Then a long time later (1940s), we had a lot more ways of making notes. Nobody really kept track of where they all came from.
  • Scientists (I am focusing specifically on those in Russia) wanted to 1. further music theory 2. get to the bottom of this, so they …
  • had a few theories.
  • Garbuzov tried to explain modern compositional technique in terms of the overtone series, or overlapping series.
  • That didn’t work for him.
  • He also considered contrapuntal origins for different harmonies, etc.
  • He didn’t like that either.
  • Another thing that bothered him: there are different cultures that didn’t even use the overtone series to make their scales.
  • So he thought really hard, and listened really hard, and using a 5-octave harmonium, he came up with a “zone-based theory of perception”
  • Basically different tuning systems have notes fall in different places, and human hearing isn’t too exact, so the intervals aren’t as well..
  • …defined as we would like. Instead, intervals are “fuzzy sets” with tolerances that vary.
  • Unisons and octaves are stricter than major seconds and minor sevenths.
  • Basically, I am using this theory to try to make an adaptive instrument, that sounds great in every key.
  • ( Equal temperament, what we use today, is a compromise. Every key sounds kind of bad.)
  • Pythagorean fifths sounds beautiful beautiful beautiful, but if you have your piano in pythagorean tuning you can’t really change keys.
  • I also explained them somewhere on reddit: http://www.reddit.com/r/Physics/comments/b7n1m/need_suggestions_for_semester_math_project/c0lhfk3
  • That’s mostly it for now! Garbuzov zones.

    • 1:28pm  |   URL: http://tmblr.co/Z_gONyQae9t
    March 13, 2010
    Simulated Annealing

  • Simulated Annealing, starting… now!
  • Congratulations! Today is your first day as a blacksmith.
  • Unlike other sub-par blacksmiths, you have vowed to never heat up the metal and then plunge it directly into cold water.
  • Heat is (basically) random movement at a molecular level.
  • Those molecules aren’t going to come to rest in a “tight fit” if you just stop them wherever. You get all sorts of tiny cracks and flaws.
  • Instead, you slowly lower the temperature of the metal, allowing the molecules to come to rest gradually.
  • This is annealing. Simulated Annealing is any process where, over time, you decrease the amount by which something is allowed to change.
  • For example:
  • Say that you want to find the shortest path from city to city around the country.
  • (This is the traveling salesman problem, for those of you playing along from home.)
  • You can’t try all possible paths: at only 25 cities if you tried one solution per nanosecond it would take 492 million years.
  • You can get a rough approximation using simulated annealing. Here is how:
  • 1. Start with one random connection between each city. This is akin to heating the metal.
  • 2. For each city, look at a neighboring city.
  • 2a. If that distance is shorter than the current connection it has to another city, drop that connection and make this one the new one.
  • Otherwise, with some probability P, make that the new connection anyways.
  • 3. Keep doing 2 until you are satisfied, but each time make that probability P a little smaller. This is akin to lowering the temperature.
  • That is it! Eventually the shortest (or short enough) path will “settle” out.

    • 1:27pm  |   URL: http://tmblr.co/Z_gONyQadb8
    March 12, 2010
    Genetic Algorithms

  • Genetic algorithms, starting now!
  • Pretend you just got a brand spanking new job as the official pastry chef of Queen Isabella II of Spain.
  • You don’t know how to make a cake. In retrospect, you shouldn’t have applied for this job.
  • You did take that machine learning class a few years back, and you are planning on solving this problem the way you solve all your problems:
  • With some sort of stochastic search.
  • You are vaguely aware of the ingredients in a cake - eggs, flour, milk, sugar, oven temperature, and oven time
  • And you have this wonderful older brother who will eat anything you make and tell you - comparatively - how good it was.
  • The queen is loaded, so you have unlimited resources. You decided to start by making 100,000 cakes with random amounts of each ingredient.
  • ( You write down the recipe for each one, in case that was unclear )
  • When the cakes are done, you feed each one to your brother. He ranks them from best to worst.
  • You take the recipe from the best cake, and combine it with the recipe for each other cake. Then you bake 100,000 new cakes.
  • ( You combine them by taking a few ingredients from one and a few from the other )
  • You keep feeding your brother and making new cakes until you decide that you have made the best cake you can.
  • The queen loves you, your brother loves you, and everyone lives happily ever after.
  • The recipe lists were chromosomes. Mixing them together was like making babies. The “best cake” was a local maximum.
  • When you really get into it, you can add things like mutations and different methods of combination.
  • Genetic algorithms are awesome, but you only want to use one when you can test partial solutions and you don’t have a better idea.

    • 3:08pm  |   URL: http://tmblr.co/Z_gONyQT1nH
    (Notes: 1)
      
    Liked posts on Tumblr: More liked posts »