text:
The post Crafting Intuition with Language appeared first on Burak Kanber's Blog.]]>
It's the grapple – struggling to meet eye to eye with a student and molding your own understanding of the topic to their learning style.
But still: why is this so effective? I'm not an expert in developmental psychology or linguistics, but I propose a hypothesis.
Teaching is an effective learning tool because it forces us to shape and describe a concept with language in many different ways, because of that trial-and-error approach of figuring out a student's learning style.
Language is how we model thought, and using different approaches to model a concept will highlight different facets of the concept. A concept will become intuitive when all facets of the concept are ultimately brought into relief. That's what intuition is, after all: understanding all of the different ways a concept can take form and interact with other concepts.
One analogy is music. You may know how to play a C major chord, but you don't truly understand it until you know all of the voicings and all of the ways it can transit to other chords.
Language shapes concepts, and it's easy to use language to highlight only the parts of a concept that you want to highlight. Biased publications do this all the time. But when you want to learn, or teach, you need to use language to illuminate as much of the concept as possible. That's means saying the same thing in as many different ways as you can.
One way to test this hypothesis is to remove the student – or more accurately, to make yourself the student – and concentrate only on the verbal aspect of explaining concepts.
Take a topic that you have only a rote understanding of, and explain it – out loud – to yourself in as many ways as you can, from as many different angles as you can think of. Add analogies and metaphors, even if they're a bit of a stretch. Make sure to also move both higher and lower in abstraction ("programming languages are really just a grammar for a formal logical system, in that way programming is just like Law" vs "programming languages are just interfaces around hardware-driven bit manipulations").
Your goal, whether learning or teaching, is to shine light into all the nooks and crannies of a complex topic at all levels of abstraction. Imagine you're explaining the topic to an advanced coworker, and then imagine explaining it to a layman. Try this exercise for one hour, as you're showering and getting ready for the day, and you'll find yourself with a deeper intuition around a topic that you once had only a rote understanding of.
The post Crafting Intuition with Language appeared first on Burak Kanber's Blog.]]>
The post Machine Learning: Full-Text Search in Javascript (Part 1: Relevance Scoring) appeared first on Burak Kanber's Blog.]]>
WHERE title LIKE %:query%. It's convincing at first, but then a few days later the client calls you and claims that "search is broken!"
Of course, your search isn't broken, it's just not doing what the client wants. Regular web users don't really understand the concept of exact matches, so your search quality ends up being poor. You decide you need to use full-text search. With some MySQL fidgeting you're able to set up a FULLTEXT index and use a more evolved syntax, the "MATCH() … AGAINST()" query.
Great! Problem solved. For smallish databases.
As you hit the hundreds of thousands of records, you notice that your database is sluggish. MySQL just isn't great at full-text search. So you grab ElasticSearch, refactor your code a bit, and deploy a Lucene-driven full-text search cluster that works wonders. It's fast and the quality of results is great.
Which leads you to ask: what the heck is Lucene doing so right?
This article (on TF-IDF, Okapi BM-25, and relevance scoring in general) and the next one (on inverted indices) describe the basic concepts behind full-text search.
It would be convenient to be able to define a "relevance score" that relates a document to a search query. And then, when users search for things, we can sort by the relevance score instead of sorting chronologically. That way the most relevant documents come up on top, regardless (or maybe not) of how old they are.
There are many, many ways to relate one text to another, but let's start simple and use a statistics-based approach that doesn't need to understand language itself, but rather looks at the statistics of word usage and matches and weighs documents based on the prevalence of their unique words.
This algorithm doesn't care about verbs or nouns or even meaning. All it cares about is the simple fact that there are common words and there are rare words, and if your search phrase includes both common and rare words, you'd be better off to rank the documents that have that rare word in it higher, and put less weight on matched common words.
The algorithm we'll use is called Okapi BM25, but it builds on two basic concepts: term frequency ("TF") and inverse document frequency ("IDF"). Together, these concepts form "TF-IDF", which is a statistical measure that represents how important a term is to a document.
Term Frequency, abbreviated "TF", is a simple metric: it's the number of times a certain word appears in a document. You can also represent it as the fraction of the number of times a word appears over the total number of tokens (ie, total words) in a document. Term frequency says "I'm 100 words long and 'the' shows up 8 times, so the term frequency of 'the' is 8 or 8/100 or 8%" (depending on the representation you want).
Inverse Document Frequency, abbreviated "IDF", is more evolved: the rarer a word is, the higher this value. It's the log ratio of the number of total documents over the number of documents a term appears in. Rarer words, therefore, yield bigger "IDF"s.
If you multiply these two numbers together, (TF*IDF), you'll get the importance of a word to a document. "Importance" being defined as "how rare is this word and how often does it appear in this document?"
You can then use this concept to relate a document to a search query. For each term in a search query, calculate its TF-IDF score, add them all up, and whichever document has the highest score is your winner.
Cool? Cool.
The algorithm described above is okay but not wonderful. It does provide us with statistically-derived relevance scores, but it could be improved.
Okapi BM25 is considered a state-of-the-art ranking algorithm (so says ElasticSearch). The major improvements that Okapi BM25 bring over TF-IDF are two tunable parameters, called k1 and b, that modulate "term frequency saturation" and "field-length normalization". What?
To intuit term frequency saturation, imagine two documents of roughly the same length that both talk about baseball. Imagine that the overall corpus doesn't have much to do with baseball, so the term "baseball"s IDF is pretty high — it's a rare and important-ish word. These two documents both talk about baseball, and talk about it a lot, but one of them uses the term "baseball" way more. Should that document really show up that much higher in the rankings? Both the documents talk about baseball a hefty amount, and at a certain point it shouldn't really matter if you use the word "baseball" 40 times or 80 times. Anything above 30 is enough!
This is "term frequency saturation." The naive TF-IDF algorithm doesn't saturate, so the document that uses "baseball" 80 times will have twice the score as the one that uses it 40 times. Sometimes that's desired, sometimes it's not.
Okapi BM25, on the other hand, has a parameter called "k1″ that actually lets you tune how quickly term frequency will saturate. The parameter k1 is usually taken between 1.2 and 2.0. Lower values result in quicker saturation (meaning that those two documents above will have similar scores, because they both have a significant number of "baseball"s).
Field-length normalization considers the length of the document and normalizes against the average length of all documents. It's useful in single-field collections (like ours) to put documents of differing lengths on the same playing field. It's doubly useful in multiple-field collections (like "title" and "body") in putting the title and body fields on the same playing field as well. The term "b" is ranged from 0 to 1, with 1 giving full normalization and 0 giving no normalization.
You can see the formula for the Okapi BM25 algorithm on the Okapi BM25 Wikipedia page. Now that you know what each of the terms are, it should be pretty straight-forward to understand, so we won't dive into the equation here. Let's dive into code:
BM25.Tokenize = function(text) { text = text .toLowerCase() .replace(/\W/g, ' ') .replace(/\s+/g, ' ') .trim() .split(' ') .map(function(a) { return stemmer(a); }); // Filter out stopStems var out = []; for (var i = 0, len = text.length; i < len; i++) { if (stopStems.indexOf(text[i]) === -1) { out.push(text[i]); } } return out; };
We define a simple
Tokenize() static method whose purpose is to parse a string into an array of tokens. Along the way, we lower-case all the tokens (to reduce entropy), we run the Porter Stemmer Algorithm to reduce the entropy of the corpus and also to improve matching (so that "walking" and "walk" match the same), and we also filter out stop-words (very common words) to further reduce entropy. I've written about all these concepts in-depth previously, so please excuse me if I'm glossing over this section.
BM25.prototype.addDocument = function(doc) { if (typeof doc.id === 'undefined') { throw new Error(1000, 'ID is a required property of documents.'); }; if (typeof doc.body === 'undefined') { throw new Error(1001, 'Body is a required property of documents.'); }; // Raw tokenized list of words var tokens = BM25.Tokenize(doc.body); // Will hold unique terms and their counts and frequencies var _terms = {}; // docObj will eventually be added to the documents database var docObj = {id: doc.id, tokens: tokens, body: doc.body}; // Count number of terms docObj.termCount = tokens.length; // Increment totalDocuments this.totalDocuments++; // Readjust averageDocumentLength this.totalDocumentTermLength += docObj.termCount; this.averageDocumentLength = this.totalDocumentTermLength / this.totalDocuments; // Calculate term frequency // First get terms count for (var i = 0, len = tokens.length; i < len; i++) { var term = tokens[i]; if (!_terms[term]) { _terms[term] = { count: 0, freq: 0 }; }; _terms[term].count++; } // Then re-loop to calculate term frequency. // We'll also update inverse document frequencies here. var keys = Object.keys(_terms); for (var i = 0, len = keys.length; i < len; i++) { var term = keys[i]; // Term Frequency for this document. _terms[term].freq = _terms[term].count / docObj.termCount; // Inverse Document Frequency initialization if (!this.terms[term]) { this.terms[term] = { n: 0, // Number of docs this term appears in, uniquely idf: 0 }; } this.terms[term].n++; }; // Calculate inverse document frequencies // This is SLOWish so if you want to index a big batch of documents, // comment this out and run it once at the end of your addDocuments run // If you're only indexing a document or two at a time you can leave this in. // this.updateIdf(); // Add docObj to docs db docObj.terms = _terms; this.documents[docObj.id] = docObj; };
addDocument() method is where most of the magic happens. We're essentially building and maintaining two similar data structures:
this.documents, and
this.documents is our database of individual documents, but along with storing the full, original text of the document, we also store the document length and a list of all the tokens in the document along with their count and frequency. Using this data structure we can easily and quickly (with a super-fast, O(1) hash table lookup) answer the question "in document #3, how many times did the word 'walk' occur?"
We also build a second data structure called
this.terms. This represents all terms in the entire corpus. Through this O(1) data structure we can quickly answer the questions "how many documents does 'walk' appear in? And what's its idf score?".
Finally, we record the document length for each individual document, and also maintain an average document length for the whole corpus.
Of course, you see above that idf is initialized to zero, and I've even commented out the
updateIdf() call above. That's because it's quite slow, and only needs to be run once at the end of the indexing operation. No need to run this 50,000 times when once will suffice. Leaving this commented out and running it only once at the end of a bulk index operation really speeds things up. Here's the method:
BM25.prototype.updateIdf = function() { var keys = Object.keys(this.terms); for (var i = 0, len = keys.length; i < len; i++) { var term = keys[i]; var num = (this.totalDocuments - this.terms[term].n + 0.5); var denom = (this.terms[term].n + 0.5); this.terms[term].idf = Math.max(Math.log10(num / denom), 0.01); } };
It's a simple function, but since it loops over the entire corpus terms list, updating each one, it's a somewhat expensive operation. The implementation is the standard formula for inverse document frequency (which you can easily find on Wikipedia) — it's the log ratio of total documents to the number of documents a term appears in. I've also modified it to always be above zero.
BM25.prototype.search = function(query) { var queryTerms = BM25.Tokenize(query); var results = []; // Look at each document in turn. There are better ways to do this with inverted indices. var keys = Object.keys(this.documents); for (var j = 0, nDocs = keys.length; j < nDocs; j++) { var id = keys[j]; // The relevance score for a document is the sum of a tf-idf-like // calculation for each query term. this.documents[id]._score = 0; // Calculate the score for each query term for (var i = 0, len = queryTerms.length; i < len; i++) { var queryTerm = queryTerms[i]; // We've never seen this term before so IDF will be 0. // Means we can skip the whole term, it adds nothing to the score // and isn't in any document. if (typeof this.terms[queryTerm] === 'undefined') { continue; } // This term isn't in the document, so the TF portion is 0 and this // term contributes nothing to the search score. if (typeof this.documents[id].terms[queryTerm] === 'undefined') { continue; } // The term is in the document, let's go. // The whole term is : // IDF * (TF * (k1 + 1)) / (TF + k1 * (1 - b + b * docLength / avgDocLength)) // IDF is pre-calculated for the whole docset. var idf = this.terms[queryTerm].idf; // Numerator of the TF portion. var num = this.documents[id].terms[queryTerm].count * (this.k1 + 1); // Denomerator of the TF portion. var denom = this.documents[id].terms[queryTerm].count + (this.k1 * (1 - this.b + (this.b * this.documents[id].termCount / this.averageDocumentLength))); // Add this query term to the score this.documents[id]._score += idf * num / denom; } if (!isNaN(this.documents[id]._score) && this.documents[id]._score > 0) { results.push(this.documents[id]); } } results.sort(function(a, b) { return b._score - a._score; }); return results.slice(0, 10); };
Finally, the
search() method loops through all documents and assigns a BM25 relevance score to each, sorting the highest scores at the end. Of course, it's silly to loop through every document in the corpus when searching, but that's the subject of Part Two (inverted indices and performance).
The code above is documented inline, but the gist is as follows: for each document and for each query term, calculate the BM25 score. The idf score for each query term is globally pre-calculated and just a simple look-up, the term frequency is document-specific but was also pre-calculated, and the rest of the work is simply multiplication and division! We add a temporary variable called
_score to each document, and then sort the results by the score (descending) and return the top 10.
There are lots of ways the above can be improved, and we'll explore those in Part Two of "Full-Text Search"! Stay tuned. I hope to publish it in a few weeks. Some things we'll accomplish next time are:
For this demo, I built a little Wikipedia crawler that grabs the first paragraph of a decent number (85,000) of Wikipedia articles. Since indexing all 85k documents takes about 90 seconds on my computer I've cut the corpus in half for this demo. Don't want you guys to waste your laptop battery juice on indexing Wikipedia articles for a simple full-text demo.
Because the indexing is a CPU-heavy, blocking operation, I implemented it as a Web Worker. The indexing runs in a background thread — you can find the full source code here. You'll also find references to the stemmer algorithm and my stop-word list in the source code. The code license, as always, is free to use for educational purposes but not for any commercial purpose.
Finally, here's the demo. Once the indexing is complete, try searching for random things and phrases that Wikipedia might know about. Note that there's only 40,000 paragraphs indexed here, so you might have to try a few topics before you find one that the system knows about.
The post Machine Learning: Full-Text Search in Javascript (Part 1: Relevance Scoring) appeared first on Burak Kanber's Blog.]]>
The post HackCooper Hackathon! appeared first on Burak Kanber's Blog.]]>
You may know me as "that guy that gave a talk on physics-based games", or "that guy that taught you your first lines of CSS", or "that kind sponsor that provided our midnight surprise".
However you know me, my name's Burak and I'm glad to have made your acquaintance!
I love talking to smart, ambitious people about all sorts of topics — entrepreneurship, software, interactive art, physics, machine learning, music, video game design, anything. So if you're reading this, please feel free to reach out to me and strike up a conversation. We can talk about what it takes to build a company, or what it takes to build a car, or a video game. Or anything you want. Don't be shy!
You can easily email me at burak -at- burakkanber -dot- com, or reach out to @bkanber on Twitter.
Happy hacking!
PS: Here's the code for the Processing talk I gave:
int width = 400; int height = 400; float ballX = width / 2; float ballY = height / 2; float ballVy = -5; float ballVx = 10; float ballA = 0.2; int ballR = 20; float restitution = -0.8; float targetTheta = 0; float targetOmega = 0.017; float targetX; float targetY; int targetR = 40; int score = 0; void setup() { size(width, height); ellipseMode(RADIUS); textSize(24); } void draw() { background(255, 255, 255); // move the target targetTheta += targetOmega; targetX = (width/4)*cos(targetTheta) + width/2; targetY = (height/4)*sin(targetTheta) + height/2; // euler technique // runge-kutta // velocity verlet // move the ball ballVy += ballA; // integrating velocity to position ballY = ballY + ballVy; ballX = ballX + ballVx; // collide if (ballY + ballR > height) { ballVy = ballVy * restitution; ballY = height - ballR; } if (ballX + ballR > width) { ballVx = ballVx * restitution; ballX = width - ballR; } if (ballX - ballR < 0) { ballVx = ballVx * restitution; ballX = ballR; } // score the game if (dist(ballX, ballY, targetX, targetY) < targetR - ballR) { score++; } // draw the ball noStroke(); fill(#FF6600); ellipse(ballX, ballY, ballR, ballR); // draw the target stroke(#666666); noFill(); ellipse(targetX, targetY, targetR, targetR); // draw the score fill(#666666); text("Score: " + score, width - 140, 30); } void keyPressed() { float impulse = 7; if (key == CODED) { if (keyCode == UP) { ballVy -= impulse; } else if (keyCode == DOWN) { ballVy += impulse; } else if (keyCode == RIGHT) { ballVx += impulse; } else if (keyCode == LEFT) { ballVx -= impulse; } } }
The post HackCooper Hackathon! appeared first on Burak Kanber's Blog.]]>
The post On Learning: Expectations are Key appeared first on Burak Kanber's Blog.]]>
There's no single simple trick or hack. It turns out that learning is hard work. But we all want to be better at it, so we owe ourselves a little bit of hard work to get there.
From the outset, your expectations are a major factor in determining whether your educational venture will be successful or not. This may be surprising to many people. We're not used to the idea that we're actually in control of our ability to succeed in learning.
In my years of teaching — everything from physics to music to engineering to software to skiing — I've seen many students fail and many excel. I've seen many different failure modes at different stages of the learning process. Everything here is a generalization. There are always exceptions to the rule.
What I've never seen, however, is a student fail after dedicating 200 hours (for example) to learning something. The students that fail invariably fail in the early stages, before reaching some certain threshold. They fail before they reach their moment of clarity. That moment of clarity where it all "clicks"; we'll call it the "pass" threshold. A student is very likely to excel after reaching the pass threshold. The failure threshold, on the other hand, is generally when the frustration of learning outweighs the student's motivation to continue.
I've come to this conclusion after observing time and time again that when a student fails it's because they quit entirely somewhere in the early stages. They drop out. Give up. Leave the classroom and never return. Resign themselves to never trying that subject again. Other times a student performs a "soft quit"–they'll remain physically present in the lessons or the classroom but have mentally checked out. That's just as bad.
This quit-itude, I've found, stems from a misalignment in expectations. The student gets frustrated that they're not picking up the material as quickly as they hoped. Its almost as if they expect learning to be easy! (Check out the Dunning-Kruger effect.)
But learning is not easy. By definition, learning a new topic is the hardest part of that topic. Learning is the process of going from knowing nothing about a topic to knowing it intuitively. There is no greater mental challenge than learning!
Students that expect learning to be difficult and frustrating tend to succeed not because they're more mentally capable, but rather because the slow-going crawl of learning isn't frustrating to them. It's expected, and they manage their frustration and keep moving forward.
Many students have the mindset that certain things are simply inaccessible to them because they're not smart enough. "I just can't do math" or "I'm hopeless with computers". But that's not the case. Barring an actual learning disability, the odds are that you are mentally capable of picking up a subject. It's just like people claiming they're tone deaf; many people claim it, but very few people are actually tone deaf.
That mindset — the "I'm just not smart enough" mindset—is poisonous. You're likely smart enough, you just need to manage your frustration and make sure you don't quit before you reach your "a-ha!" moment.
I've seen it too many times: many students get excited about learning something, and when the first mere 20 or 30 hours of practice prove difficult or frustrating they'll invent an excuse to quit. "My fingers are too weak" when learning guitar or "I don't think I like the industry" when learning music production or "I can't even draw a straight line" when trying to draw (I'm guilty of that one!).
But what if I told you that you could learn a life changing skill, guaranteed, if you put 200 hours of tough, frustrating-at-times effort into it? How would that change your mindset? What if that skill could land you a job at three times the pay? Just imagine how much more willing you'll be to deal with the frustration of learning something new if you knew you'd get there and that the only enemy is frustration? All you have to do is keep pushing forward—even if you feel frustrated and demotivated at times—because you will get the subject to click.
That's what learning's really about: managing frustration. Learning will always be hard. But I believe–and I've seen, and I've done–that anyone is capable of learning anything with the right expectations at the outset. You just need to put in the hours–hours and hours of beautiful frustrating practice.
The right expectations, combined with an unrelenting drive and a good mechanism for dealing with frustration, is the first step in learning even the most difficult subject successfully.
The post On Learning: Expectations are Key appeared first on Burak Kanber's Blog.]]>
The post Learn to Embrace Dinkiness appeared first on Burak Kanber's Blog.]]>
While I was there, I met a guy who had O'Reillys Python for Big Data open on the desk next to him. He was practicing writing mathematical functions. I had a chat with him and he seemed passionate about learning Python, but really pretty unenthusiastic about the process. It was clear that learning Python was a career goal of his, not a personal goal, and he was going about learning it in a textbook way.
Watching him reminded me of an oft-ignored piece of advice: Learn by doing what you love. Obsession is key when it comes to mastering programming (or anything). While it's perfectly fine to choose this career path as just that—a career—it also takes a level of dedication and excitement that can't be generated without a natural spark.
Python for Big Data may be your goal, but that's not how you have to learn Python. There are plenty of ways to develop practical skills. Artists typically learn about art from a young age, crafting personal art projects, drawing what they love drawing, and then later refine those skills to be used towards a career. Writers learn to write by blogging or composing lyrics because they love it—and later figure out they can apply those skills to a profession, like grant writing. Learning quantitative finance is a smart career move, but unless quant really turns you on, why not develop your foundational skills by throwing yourself into something you love?
When in the learning stages, you should only work on projects that are so exciting and interesting to you that you voluntarily stay up until 4am coding. That's the best way to clock the 1,000 hours of experience you'll need before you can become a valued professional while also maintaining your enthusiasm and sanity. Why should you spend those 1,000 hours grinding though quantitative finance or big data (unless that's your thing!)? Learn to be a programmer first. Use projects you love to get there. Once you're comfortable, you can specialize in big data. And I promise, your excitement for your projects will make those 1,000 hours far more educational than if you're simply walking yourself through the steps.
Another thing to keep in mind—though we'd all like to think of each and every thing we do as deeply meaningful, your passion projects don't need to be world changing, life-altering attempts. Have fun with it. Embrace the Dinkiness. And through that, you actually will be making quite a difference.
Take on small projects, things that exercise certain skills one at a time, on topics that excite you. Jumping directly into big data is a quantum leap from where you need to be when you're just starting out. Instead, fill your plate with "dinky" projects: Build a dinky text based RPG. Build a dinky image processing app. Build a dinky dating site.
Dinky is great for a few reasons. First, it takes the pressure off the project; like I said earlier, coding should be fun. Let yourself explore an idea just for you. Sure, it'd be great if the weekend app you've created is professionally designed or technically robust, but really, there's no need for polish. You won't care if anyone uses it. This is just practice for you. Dinky projects are the blog posts and paintings that no one will likely read or see, but that the creator gains value from in personal satisfaction and knowledge. Maybe this dinky little project helped teach you how to work with 3D animation, or efficiently tell a story, or use WebRTC or something else new and exciting.
Plus, there is the off-chance that your dinky project hits it big. Every once in awhile that blog post turns into a novel. That painting gets purchased by a top hotel. Consumers aren't very predictable. If you work on one hundred dinky projects in a year, there's a good possibility that one or two of them will see moderate success, and that's a great morale boost and experience for someone who's simply trying to build their skills. I've had a few dinky projects accidentally go viral, and each one of those experiences taught me something new. But more importantly, they kept me excited—and routinely up until 4am, working because I couldn't tear myself away.
You can't get that experience by following a textbook plan. If the kid who was practicing Python only applied it to big data, chances are he'd either lose steam or flame out completely, and may never feel that personal satisfaction that keeps driving us forward. He also wouldn't push his limits; exploring the ideas you love with nothing to lose opens the door to new ideas that may never have arrived if simply plunking away on assigned projects. Finally, there's something powerful about harnessing your creativity and spark to fuel your skill set. But in order to do that best, you have to love what you're doing and do it for you. If other people think it's cool, that's just icing on the cake.
The post Learn to Embrace Dinkiness appeared first on Burak Kanber's Blog.]]>
The post Machine Learning: Sentiment Analysis appeared first on Burak Kanber's Blog.]]>
Compared to the other major machine learning tasks, sentiment analysis has surprisingly little written about it. This is in part because sentiment analysis (and natural language in general) is difficult, but I also suspect that many people opt to monetize their sentiment algorithms rather than publishing them.
Sentiment analysis is highly applicable to enterprise business ("alert me any time someone writes something negative about one of our products anywhere on the internet!"), and sentiment analysis is fresh enough that there's a lot of "secret sauce" still out there. And now that the world is run on social sites like Twitter, Facebook, Yelp, and Amazon (Reviews), there are literally billions of data points that can be analyzed every single day. So it's hard to blame anyone for trying to get a piece of that pie!
Today we'll discuss an "easy" but effective sentiment analysis algorithm. I put "easy" in quotes because our work today will build upon the Naive Bayes classifer we talked about last time; but this will only be "easy" if you're familiar with those concepts already–you may want to review that article before continuing.
There are better, more sophisticated algorithms than the one we'll develop today, but this is a great place to start. As always, I'll follow up with additional articles that cover more advanced topics in sentiment analysis in the future.
I found a nice, compact data set for this experiment. It consists of 10,662 sentences from movie reviews, labeled "positive" and "negative" (and split evenly). The primary goal today is to figure out how to tweak the Naive Bayes classifier so that it works well for sentiment analysis.
"Naive Bayes Classification" is termed such because it makes the assumption that each word is statistically independent from each other word. In language, however, that assumption doesn't hold true. "England" follows the word "Queen [of]" much more commonly than most other words ("Queen of Asparagus" just isn't something you see every day), so it's clear that words are not independent of one another. Still, it's been shown that the "naive" assumption is pretty good for the purposes of document classification.
And that's good news, because sentiment analysis feels quite a bit like classification: given a document, would you label it "positive" or "negative"? The main difference between classification and sentiment analysis is the idea that classification is objective but sentiment is subjective. But let's make another "naive" assumption and pretend that we don't care about that. Let's try applying Bayes to sentiment and see what happens.
For what it's worth, lots of scientific discoveries are made by people who are willing to "just try it and see what happens". If it fails, so what? Most experiments do. If it succceds though, that'd be great news!
Still, I don't think we should completely ignore the fact that sentiment is subjective and classification is objective. Subjective language is trickier than objective language because it's prone to idiom, turns of phrase, sarcasm, negation, and other artifacts of emotive language. Detecting what language a sentence is in, for instance, is straightforward because it's built on facts. Did you observe the word "allons-y"? If so, probably French. But consider Borat-ifying a movie review: "I loved this movie… not!" The naive approach may see the word "loved" and label the review positive, but that "not" changes the entire meaning of the sentence.
We should try to move just a little bit away from our assumption that words are independent. One nice way of doing this — if you have lots of training data — would be to use bigrams instead of unigrams. If you recall, the training portion of a Bayes classifer involves looking through your training set and counting the number of times a word appears in a class of documents. (Eg: "Clinton" appeared 9% of the time in "politics" articles, but only 0.1% of the time in "cooking" articles.)
Our Bayes classifier can easily be extended to use bigrams just by tokenizing our document two words at a time instead of one! Rather than treating the words "This" "movie" "was" "not" "great" separately — and risk getting confused by the negation — all we have to do is record them as pairs: "This movie" "movie was" "was not" "not great". Now our classifer knows the difference between "was great" and "not great"!
Sadly, using bigrams poses a real problem for us: it increases our entropy. Entropy is a concept used across lots of fields, but roughly speaking, it's a measure of the number of possible "states" a system can be in. If we use 7,000 different words in conversational English and build a unigram-based Bayes classifer for them, then we'll need to store data (word counts) for only 7,000 words. But if we start using bigrams, we could potentially need to store data for up to 49,000,000 different word pairs (that's our maximum possible value though; in practice we'd probably only encounter 30,000 unique word pairs or so).
But storage space and computational complexity is the least of our concerns (30,000 records is nothing!). The real problem is the lack of training data. Using bigrams and introducing more entropy into our system means that each word pair is going to be relatively rare! A unigram approach might encounter the word "great" 150 times in our training data, but how many times will it see "great movie"? Or "not great"? Or "was great"? Or "seriously great"? The bigram approach is nice, but unless you have a huge training corpus it's probably not the way to go.
Note that there are other ways to combat entropy, and that's a good thing to do even when you're using unigrams. I almost always stem words as part of the tokenization process. Stemming puts word variations like "great", "greatly", "greatest", and "greater" all into one bucket, effectively decreasing your entropy and giving you more data around the concept of "great".
It turns out that dealing with negations (like "not great") is a pretty important step in sentiment analysis. A negation word can affect the tone of all the words around it, and ignoring negations would be a pretty big oversight. Bigrams, unfortunately, require too much training data, so we've got to find a better way to consider negation terms.
Fortunately, the solution is "kick-yourself-for-not-thinking-of-it" easy. Here's how I do it: if I see a negation (like "not", "never", "no", etc), I just add an exclamation point to the beginning of every word after it!
The sentence "This movie was not great" turns into "This movie was not !great", and the token "!great" gets stored in our Bayes classifer as having appeared in a negative review. "Great" appears in positive reviews, and its negation, "!great" appears in negative ones. It's simple, it's clever, and it's effective. Best of all: you get to use a regular Naive Bayes classifer. The only modification you need to make is in your tokenizer (the code that goes through the text, pre-processes it, and splits it up in to words or "tokens"), but the Bayes classification algorithm stays the same.
I ran this experiment's data through a variety of different tokenizers, and in this case I found it's more effective to flag only the word immediately before and after the negation term, rather than all the words until the end of the sentence. My tokenizer takes the sentence "This movie was not good because of the plot" and turns it into "This movie !was not !good because of the plot".
Another effective trick you can use has nothing to do with the Bayes algorithm itself but rather with how you handle its results. A nice feature of a Bayes classifier is that it outright tells you its "confidence" in its ruling (confidence is in quotes here because this isn't the statistical definition of confidence, I'm just editorializing and calling probability "confidence").
Recall that the output of a Bayes classifier is "the probability that this document is 'negative'". If you have the luxury of not needing to label every single document you encounter, it may be best to only label documents that have over a certain percentage probability. This approach should make intuitive sense: if you read something and you're only 51% sure it's negative, maybe you shouldn't be labeling that document at all.
In this experiment, setting the "confidence threshold" to 75% or greater increased the classifier's accuracy from 78.5% to 85%, a 6.5 percentage-point difference!
You may not always have the luxury to abstain from guessing, but it makes sense in most cases. For example, if you need to alert a client about negative reviews, you could hit close to 90% accuracy if you only sent alerts out when the probability of being negative was greater than 80% or so.
I won't do a code walkthrough like I usually do, since the core of this project is just the Naive Bayes classifier we built last time. However, the cross-validation and test procedure is worth talking about.
Cross-validation is how you should be testing your algorithms. In short, here's what you do:
Remember that your algorithm will likely be highly specific to the type of training data you gave it. The program below gets 85% on movie reviews, but if you use it to judge the sentiment of a married couple's conversation it'll probably fall short.
This experiment's goal was simple: use a Naive Bayes classifier for sentiment analysis, and figure out what we can do to boost its accuracy.
I tried and tested 18 different variants of tokenizers and the Bayes classifier, both with and without adjustments for rare tokens, resulting in 36 total tests. Each test was run 30 times, for a total of 1,080 experiments. I found that the least effective tokenizer was the "stemmed, stopword-removed bigram" tokenizer (61.4% accuracy and slow as hell), and the most effective tokenizer had these properties:
The overall accuracy on that algorithm was 85.0%, which was pleasantly surprising to me. Most machine learning algorithms max out near 90%, so this turned out to be very successful for our "introduction to sentiment analysis"!
Wait for the system to train, and then write a movie-review-like sentence and see if it gets your sentiment right.
I'll be writing at least two more articles about sentiment analysis, so please be sure to ask any questions or make any suggestions you have in the comments below.
If you like this article, or thought it was helpful, please consider:
The post Machine Learning: Sentiment Analysis appeared first on Burak Kanber's Blog.]]>
The post Why I'm Learning Morse Code appeared first on Burak Kanber's Blog.]]>
In the very early days, we grunted. Then we developed the spoken word. Very fortunately for us, we have an organ (the vocal cord) that helps us encode language into audio and transmit it out of our throats, through the air, and into a listener's ear. So we did that for a while, but eventually (as it always happens), we figured there could be a different way to encode language such that we could store our thoughts for later. We developed drawings.
Drawing evolved into written language, and we started using paper so that our thoughts were mobile. The written word was a significant advancement in the evolution of human society. Scholars were able to share thoughts with future scholars that they would never meet. We could write plans for tools or machines. We could share ideas without ever needing to know who would read them.
We encode information for lots of different reasons. There are some forms of encoding that help us transmit data. Other forms help us store data. Other forms help us operate on data. And we're always improving the way we encode things.
Take recorded audio, for instance. At one point, someone discovered that you could capture pressure waves on a physical medium so that we could re-play them later. The first record was born. We discovered radio waves, and shortly after that we figured we could encode audio on top of a carrier wave. Thus was born AM radio. AM radio had its limitations in transmission and fidelity, however, so we figured out a better (albeit less intuitive) way to encode audio for radio: FM.
We encoded and recorded audio onto magnetic tape, hard discs, optical discs, and eventually dozens of popular binary formats. We encoded video in much the same fashion: first we used AM, then FM, and eventually landed on digital. Who knows what we'll have in the future. Maybe we'll encode things in quantum states, or in DNA.
This brings me to my fascination with Morse code. Granted, learning Morse code today may be a futile exercise. After all, I don't know a single person who speaks it! But Morse code was the first popular method of electronically encoding human language. What a huge step forward in history that was! What a fundamental breakthrough!
We used Morse code first over telegraph lines and eventually over radio. We used it as civilians and we used it in the military. Morse code was already mature before we could even transmit voice over radio. And even when we started transmitting voice, Morse was more reliable under poor conditions than voice was. The dashes and dots were easier to pick out from the static than spoken words were, so we continued to use Morse for quite some time.
Interestingly, Morse code was originally developed as a sort of written language. The receiving end of the early telegraphs had a roll of paper tape attached, and the dashes and dots would be drawn on the tape, ready for visual human transcription. But after a short while, telegraph operators were able to transcribe Morse simply by ear. In fact, they discovered that listening to Morse code was easier than visually transcribing it.
As you develop proficiency in receiving–or "copying"–Morse, you start hearing the characters rather than the dashes and dots. "Di-dah-dit" just comes across as "R", as passively and intuitively as the letter "R" itself. Eventually you begin to recognize full words, and if you have lots of experience, even common phrases require no active translation.
That's amazing to me. With some practice, we can learn to "natively" speak and translate an entire electronic encoding without active effort. It's even said that Morse operators, particularly during wartime, could identify the actual person they were listening to–because everyone has their own Morse "accent". You'd come to recognize Steve's "voice" without him having to identify himself.
That's why I'm learning Morse code. This simple form of communication, seen my many as antique, encapsulates so much about our world and technology. It shows us how we can use encoding to give information the properties we want it to have (in Morse code's case, ease of transmission, simple electronic components, and high fidelity even when the signal is weak). It teaches us about human language and adaptability (learning to "speak" Morse code). And, long before the internet and the digital age, Morse code revolutionized the way we communicate with one another.
While it may not be practical to learn Morse in this day and age, I feel I must pay homage to such a wonderful and revolutionary system. And who knows–it might come in handy some day. For some reason.
Do any of you speak Morse?
(If anybody is interested in learning, I've been using lcwo.net. There are downloadable programs out there as well, but I like LCWO because it's a webapp.)
(Update Oct 15 2013: I'm proud to say I can now copy Morse code at about 10WPM with 99% accuracy. I love it!)
The post Why I'm Learning Morse Code appeared first on Burak Kanber's Blog.]]>
The post Bash Scripting: Why didn't I start this earlier? appeared first on Burak Kanber's Blog.]]>
I had never seen myself as a "DevOps guy" or a "Systems Administrator", so I knew just enough to build good, sturdy, secure servers with little flash and lots of functionality. No flare. No grace. I concentrated on software.
But in the last year or so, I've come to embrace "Unix as an IDE". (Before that, I was a MacVim guy.) The tools are impressive and robust, and having a remotely hosted, SSH-driven development environment is just so convenient and enjoyable. As a result, I've logged nearly a thousand hours on my dev server via iTerm and an SSH connection in the last 6 months.
Despite my growing comfort with the command line, I never really concentrated too much on automating my sysadmin tasks. No premature optimization, I thought. I did everything by hand. All the server builds, the maintenance and upkeep, all done one line at a time. I've even tried Chef and other related tools; I just didn't like them.
But last week I ran into a problem: we had a huge increase in traffic and activity. We needed to scale significantly, and fast. I was used to building one server at a time, at my leisure, all by hand. (I've always felt a zen calm while building servers, so I enjoyed building them by hand.) But that wouldn't cut it now. I needed 8 new app servers in the next few hours.
I bit the bullet and wrote the first real (ie, longer than 10 lines) bash script I've ever written — to automate my app server builds. While I had the server build procedure committed to memory, it still took me about 90 minutes to write the script and work out all the kinks. (I had a few issues with accidentally calling the script from the wrong path, and made some other similar newbie mistakes.)
But the payoff was the most exciting part. This 90-minute investment of my time ended up transforming what used to be a 30 minute, manual, and error-prone server build process into a perfect lean, mean, server building machine. Now it only takes me 5 minutes to build a server, and they're all perfectly configured out of the box. All due to a crash course in bash scripting.
Part of me wishes it hadn't taken me 15 years to get to this point, but the other part of me recognizes that everyone learns their lessons in a different order. Either way, I'm happy to have finally added bash to my toolbelt.
What do you guys do? How do you manage your server builds and automation? I'd love to see what the full spectrum looks like.
The post Bash Scripting: Why didn't I start this earlier? appeared first on Burak Kanber's Blog.]]>
The post Machine Learning: Naive Bayes Document Classification Algorithm in Javascript appeared first on Burak Kanber's Blog.]]>
Are you just looking for the code example? Scroll down!
Document classification is one of my favorite tasks. "Document classification" is exactly what you think it is: given a document and a set of labels, apply the most appropriate label to that document. Labels (or "classes" or "categories") can be things like:
Today we're going to solve a simple problem: language detection. Put another way: "given a piece of text, determine if it's in Spanish, English, or French".
First, we'll have to change the way we think about "documents". At their most basic level, documents are just collections of arranged characters. Some characters may be letters, others are not. Letters make words, and words have meaning. Sometimes punctuation alters the meaning of words, other times it doesn't matter too much! (See what I did there?) We typically study documents by studying the individual words in them. Sometimes, if the situation calls for it, we'll look at more than one word at a time (word pairs are called "bigrams"), but since this is only "part 1″ of this Bayes series we'll only consider unigrams for now.
Because natural language itself is so quirky and complicated, we generally try to simplify things; we try to reduce the entropy of the system. If you consider both uppercase and lowercase letters, you can create 7.3 million different four-letter words. If you limit yourself to only lowercase letters, that figure drops down to only 450,000. Why is this important? You want your system to use as much data as it can, and treating "YOU'RE" and "you're" and "You're" separately only serves to keep what you learn about each in separate buckets. Converting all of those to a simple "you're" is best, because it'll allow you to study the concept of the word "you're" rather than the various syntaxes of the word.
Of course, more advanced data scientists will recognize that sometimes you do want these quirks in your system. When detecting spam emails, for instance, it turns out that "offer" and "OFFER" are two very different things. Often, spam detection algorithms will not normalize based on case because of this. Similarly, "money back" and "money back!!!!" have two very different meanings, so spam detection algorithms will generally also leave the punctuation intact.
You may also decide that you also want the meanings of the words "imagine", "imagination", and "imaginary" to be lumped together. To do so, you might chop off the ending of each, converting them to "imagin" — it's neither verb nor noun, neither singular nor plural, it's simply a concept. This is called "stemming", and it serves to treat different words with the same meaning as the same entity. These entropy-reduction techniques are very important in machine learning as a whole, since training sets for learning algorithms are usually limited.
The process of splitting a document up into discrete chunks that you can study is called "tokenization". For now, we'll keep our tokenization simple: we'll remove any punctuation, make everything lowercase, and split the document up by spaces to get our tokens.
I'm not going to talk about the math around Bayes' theorem, because interested readers can easily learn the basics of probability and Bayes' theorem on their own. Instead, we'll aim to develop an intuition about this important tool in probability.
We're trying to figure out which language a previously unseen document is in. We have a stack of pre-labeled documents in English, French, and Spanish. Since we decided above that we can learn about a document by inspecting the individual words in that document, let's start there.
If you look at a single word in a document, you can easily figure out how many times it appeared in your training data. Using that information, you can determine the probability that a certain language will use a given word. For example: "vous" is the first word in your document of unknown origin. "Vous" may show up in all of your French documents (100%), no Spanish documents, and a small number of English documents (5%). That's a great hint! The document is French!
But no, we can't stop there. Just because "vous" is clearly a French word doesn't mean the document itself is French. It may be an English novel quoting a French character. So we can't just simply look at the "probability that 'vous' is French", which is what we just tried. Instead, we need to determine the "probability that this document is French given that the word 'vous' is in it". Fortunately, Bayes' theorem does exactly that. If we apply Bayes' theorem to the fake numbers I gave above, we find that there's a 98% chance that a document is French if "vous" appears in it. The formula to calculate that is quite simple; see Bayes' theorem.
Of course, if the next phrase in the document is "said Jean Pierre, the French museum curator", we know there's a much smaller chance of the document being French. So we look at each word in turn and calculate the "probability that the document is (French|English|Spanish) given that this word is in it". We combine those individual probabilities and end up with an overall "probability that this document is French [given that all these words are in it]". If that probability is high enough, you can act upon it.
The Naive Bayes Classifier is so named because it assumes that each word in the document has nothing to do with the next word. That's a naive assumption. But it turns out that, while naive, it's actually a great simplifying assumption; studying words separately like this actually yields very good results. You could also study bigrams or trigrams (sets of two or three words at a time), at which point the classifier is no longer "naive" but it'll require a much larger amount of training data and storage space.
The reason the NB classifier works well for document classification is that it de-correlates the number of times a word is seen in a given language from its statistical importance. The word "a" is found in many languages. Perhaps it even appears in 100% of your English training set. But that doesn't mean that documents that have it are English. We use Bayes to convert the "probability that 'a' appears in an English document" (which is 100%) to the "probability that this document is English because it has 'a' in it" (maybe 50%).
Therefore, the common stuff that's found everywhere is given a very weak significance and the stuff that's found more uniquely across a category is given a much stronger weight. The end result is a very smart, simple algorithm that has low error rates ("low" being a relative term). It's not magic, there's no neural network, there's no "intelligence", it's just math and probability.
As usual, let's just dive in. The first thing our document classifier needs to be able to do is train itself given a piece of text and a label for that text. Since I decided to build this classifier as generalized as possible, we won't hard code the labels or even put a cap on the number of labels allowed. (Though naive Bayes classifiers with only two possible labels, like spam/ham, are a little bit easier to build.)
Bayes.train = function (text, label) { registerLabel(label); var words = tokenize(text); var length = words.length; for (var i = 0; i < length; i++) incrementStem(words[i], label); incrementDocCount(label); };
registerLabel function simply adds the label to the "database" (in this case, localStorage) so that we can retrieve a list of labels later.
tokenize function in this case is very simple. We'll look at more interesting tokenization techniques in another article (tokenization can be an important part of these classifiers), but this one is straight-forward:
var tokenize = function (text) { text = text.toLowerCase().replace(/\W/g, ' ').replace(/\s+/g, ' ').trim().split(' ').unique(); return text; };
In this case, we use
unique() because we're only interested in whether a word shows up in a document, and not the number of times it shows up. In certain situations, you may get better results by considering the number of times a word appears in a document.
We then loop through each word (or "token"), and call
incrementStem on it. This function is also very simple: it just records the number of times a word was seen for a given label.
Finally, we call
incrementDocCount, which records how many documents we've seen for a given label.
The end result of training is that we have a database that stores each label we've ever seen (in our example, it'll hold "english", "spanish", and "french"), stores the number of times a word has been seen for a label (eg, "le" was seen in French documents 30 times), and stores the total number of documents for each label (eg, we saw 40 French documents).
Training a naive Bayes classifier is dead simple and really fast, as demonstrated above. Guessing a label given a document is a little tougher, but writing the algorithm is easy to those who understand probability. If you don't understand probability, that's ok; you can spend some time reading up on naive Bayes classifiers and you'll always have this example to come back to and study.
The first thing we'll do in our guessing function (other than initializing variables; see the JSFiddle for the minutiae) is a little bit of bookkeeping:
for (var j = 0; j < labels.length; j++) { var label = labels[j]; docCounts[label] = docCount(label); docInverseCounts[label] = docInverseCount(label); totalDocCount += parseInt(docCounts[label]); }
Our goal here is to set ourselves up for calculating certain probabilities later. To do this, we need to know the number of documents we've seen for a given label (docCounts), but we also need to know the number of documents not in that label (docInverseCounts). Finally, we need to know the total number of documents we've ever seen.
You could flip this function upside down and get docInverseCount simply by subtracting a label's docCount from the totalDocCount -- in fact, that approach is better and faster, but I did it with an explicit docInverseCount function because it reads a little easier.
Given the above information we can determine, for example, the probability that any arbitrary document would be French. We also know the probability that any document is NOT French.
for (var j = 0; j < labels.length; j++) { var label = labels[j]; var logSum = 0; ...
Next, we look at each label. We set up a
logSum variable, which will store the probability that the document is in this label's category.
for (var i = 0; i < length; i++) { var word = words[i]; var _stemTotalCount = stemTotalCount(word); if (_stemTotalCount === 0) { continue; } else { var wordProbability = stemLabelCount(word, label) / docCounts[label]; var wordInverseProbability = stemInverseLabelCount(word, label) / docInverseCounts[label]; var wordicity = wordProbability / (wordProbability + wordInverseProbability); wordicity = ( (1 * 0.5) + (_stemTotalCount * wordicity) ) / ( 1 + _stemTotalCount ); if (wordicity === 0) wordicity = 0.01; else if (wordicity === 1) wordicity = 0.99; } logSum += (Math.log(1 - wordicity) - Math.log(wordicity)); } scores[label] = 1 / ( 1 + Math.exp(logSum) );
The above is the meat of the algorithm. For each label we're considering, we look at each word in the document. The _stemTotalCount variable holds the number of times we've seen that word in any document during training. If we've never seen this word before, just skip it! We don't have any information on it, so why use it?
wordProbability represents the "probability that this word shows up in a [French|English|Spanish] document". If you've seen 40 French documents, and 30 of them have the word "le" in them, this value is 0.75.
wordInverseProbability is the probability that the word shows up in any other category than the one we're considering.
The funny
wordicity variable is what happens when you apply Bayes' theorem to the two probabilities above. While the wordProbability variable represents "the probability that [le] shows up in a [French] document", the wordicity variable represents "the probability that this document is [French] given that [le] is in it". The distinction is subtle but very important. If you're having trouble understanding the distinction at this point, I strongly recommend saying those two phrases out loud and making sure you understand the difference before moving on.
The wordicity line above also makes the assumption that English, French, and Spanish documents are all equally common and starting off on the same footing. This assumption makes the calculation a little simpler, but you can consider the a priori probabilities of each language if you'd like. A note on that later.
The line below the wordicity definition is an optional adjustment for words that we've only seen in training a few times. If you've only seen a word once, for instance, you don't really have enough information about that word to determine if it's really French or Spanish. So we make a weighted adjustment: we bring the wordicity closer to 50% if we haven't seen it too many times. The "0.5" in that equation is the value we should try to adjust towards, and the "1"s in the equation are the weight -- if you increase this value, the wordicity will remain close to 0.5 longer. If you have a large training set, you can make the weight 5 or 10 or 20 or 50 (depending on how big your training set is). Since we have a very small training set, I made this value 1 but realistically I should have just omitted the line completely (my training set is only 15 paragraphs). I just wanted to show you that adjusting for rare words is something that you can do.
Below that, we avoid letting wordicity be either 0 or 1 since we're about to use a log function on our data, and either of those values would kind of mess up the results.
The logSum line isn't really a part of the mathematical equations, but is rather a practical consideration. After calculating the wordicity for each word, we need to combine those probabilities somehow. The normal mathematical way to do that would be to multiply each probability together and divide by the multiplication of all the inverses. Unfortunately, floating point math isn't perfect and you can run into "floating point underflow", where the number gets too small for floating point math to deal with. So instead, we take a log of the numerator and denominator (combined probabilities and their inverses), and add up the logs.
Finally, after we've combined all the individual word probabilities with the logSum line, we undo the log function we just used to get the probability back in the 0 to 1 range. Note that this happens outside of the "look at each word" loop but still inside the "look at each label" loop.
One thing I'd like to point out is that the above makes a big simplifying assumption: we've assumed that English, French, and Spanish documents are all equally likely to appear. In our example, this is a good assumption since you guys are probably going to test one of each later, but in the real world this isn't necessarily true.
The Bayes classification algorithm does actually let you consider the a priori probability of a document's language (meaning, the probability that a document is English just based on the number of English documents out there, before considering the actual contents of the document), but I've simply left this out. It's not too hard to put in; adding just a few more terms to the wordicity calculation can do this. The next Bayes article I write will use the full form of Bayes theorem.
Finally, please note that I was really lazy while training this algorithm. You can see from the JSFiddle that I've only used 5 paragraphs from each language to train the thing on. That's not nearly enough to go by, as the words seen during training are the only words it knows. I've found that this example does work well if you type in sentences or paragraphs (try just copy/pasting stuff from news sites), but simple nouns and phrases probably won't work. For example, you'll get the wrong result for "la tortuga" ("the turtle" in Spanish) simply because we never showed it the word "tortuga" before. The algorithm will guess French in this case because it's seen slightly more "la"s in French than it's seen in Spanish. A larger training set would fix this issue.
We're basically done. All we have to do now is either report all the labels' probabilities or just pluck out the highest one. Try pasting some English, French, or Spanish news text in the JSFiddle below -- you should see the guessed language and the probability that led us to guess that language. This example works better with sentences or paragraphs; the more words you give it to guess by, the better the chance that it has seen one of those words in its limited training set.
So far, I've had 100% accuracy when copying and pasting sentences from news sites. Try it below and see for yourself!
If you like this article, or thought it was helpful, please consider:
The post Machine Learning: Naive Bayes Document Classification Algorithm in Javascript appeared first on Burak Kanber's Blog.]]>
The post I was just tricked into learning another language appeared first on Burak Kanber's Blog.]]>
I just discovered Duolingo. If you're not familiar, Duolingo is a language learning web app. You sign up and decide to learn Spanish (or something else), and you're taken through a series of lessons that combine flash cards, translation, speaking, and listening. It's basically what Rosetta Stone would have evolved into if they didn't have so much culture inertia.
Here's what I noticed about Duolingo, and how it managed to suck me in:
Here's my point: I had no idea I wanted to learn Spanish (and German) until I played with this. It's fun and easy and the app's value made itself immediately apparent.
I was literally tricked into learning Spanish.
Hopefully other players in the education space will learn from Duolingo, but it's also hard to tell if this will work for other fields of study. Codecademy is pretty good at this kind of thing too, but there's something holding it back. Everybody already knows at least one spoken language, so everybody that uses Duolingo is familiar with the core concepts of communication. Codecademy's userbase is programming novices, however, and many of those core concepts (logic, program flow, functions) are foreign to new students. It's harder for someone to just dive in and stick around because the learning curve is steeper. Codecademy does a good job of shallowing the curve, but it's still steep.
This isn't Codecademy's fault. They're excellent. But it's obvious that there are fundamental differences in the course material that makes "gamified learning" a little tougher with programming than with language.
I'd also like to compare Duolingo to coursera. I'm sure we can all agree that coursera is amazing and wonderful all around, but their model has a limitation of its own: coursera is great at teaching people who want to learn (and have the discipline to do so), but that doesn't describe the general public. Coursera makes smart, driven people smarter. Duolingo, on the other hand, can take anyone and teach them a second language.
The obvious best-case scenario would be to somehow combine coursera's depth and breadth with the ease of use and stickiness of Duolingo. That doesn't seem possible. It probably isn't. But why the heck not? What is it about education that forces us to use so many different teaching and learning methods at so many different points in our learning journey?
I'm waiting for some player to come around and flip education on its head. Coursera et al are all amazing, but that head-flipping aspect isn't there. Duolingo is, in my mind, the best jump we've seen in language learning since Rosetta Stone came out, but their techniques aren't applicable globally. I wonder what education innovation will come next. I wonder if it'll ever come.
And the moral of this story, if you're a teacher: make sure you trick your students into learning.
PS: I have no affiliation with Duolingo. I just really love what they're doing and appreciate their approach. If you want to learn a language, please try them. I'd like to see them stick around for a while.
PPS: I have nothing against Rosetta Stone.
The post I was just tricked into learning another language appeared first on Burak Kanber's Blog.]]>
The post Big data doesn't need to be so big. appeared first on Burak Kanber's Blog.]]>
This article is me playing devil's advocate.
I think the big data hype is hurting our ability to think critically about our problems. Obviously this isn't the case everywhere. Many engineers are excellent and brilliant and do the right thing. But many others simply brute-force their problems into submission.
These days it's possible to cheaply collect and analyze billions of data points on commodity resources. On the surface that seems like a good thing, but we should keep in mind that many of the problems we solve today were solvable yesterday too. We went to the moon on a 2MHz processor and 4KB of RAM.
Think about what a feat that was! Think about the problem solving skills that took!
If we could that, why can't we just get by on a million data points instead of a billion? Have we already forgotten statistics? When was the last time you actually asked yourself if you need big data? Unless you actually need to record every single data point — if that's your core value proposition — I'm sure you can get by on a random sample.
I'd be willing to bet that any data source that can provide a billion data points will still be statistically significant if you were to sample only 1% or 0.1% of the source.
Big data doesn't need to be so big. Even Google analytics uses sampling for datasets larger than 100,000.
My suggestion to you, then, is to really evaluate your options before you spin up 50 new EC2 instances. If you're a startup and funds are slim, or if your data population is very dense, then brush up on your statistics and figure out if you can get away with sampled or aggregate data. Please don't think that you can avoid doing smarter work just because servers are getting cheap.
Like I said, this is a devil's advocate post. It's meant as food for thought. If you really do need all that data, then ignore this. I won't defend this article to the death. But if you've never thought about this sort of thing, it's time to start. Don't get caught up in the hype of big data, and just do what's best for the project!
The post Big data doesn't need to be so big. appeared first on Burak Kanber's Blog.]]>
The post Do we have a moral obligation to society? appeared first on Burak Kanber's Blog.]]>
I was sitting around in the dark thinking about whether ConEd would give us a pro-rated discount for the 48 hours we went without power. (I don't care if they do or not, I was just curious about the mundane.) Then I realized that 48 hours without power amounts to about $6 on my bill.
Six dollars? That's it? If I could have paid a premium to keep my power on during Hurricane Sandy I gladly would have paid maybe $50 or even $100 just for that $6 worth of electricity. Isn't that amazing? Electricity is so valuable to us and yet so cheap. And also so inaccessible to the undeveloped world.
Of course, I wouldn't be able to pay a sustained $1,500 a month for electricity, but the fact that I'd shell out $100 to keep my power on during a storm made me realize just how valuable it is. And that's not an easy feat. I used to be a hybrid car engineer, and I worked on several renewable energy projects in my grad school years. I always felt I had a grounded, solid understanding of how valuable electricity is.
But actually living without it gave me a new perspective. It made me think about places where power isn't a given, like my grandparents' house in the mountains in Turkey. Power comes and goes there and it's just a way of life. But if that were to happen here it wouldn't be acceptable.
Most people like to think that they're empathetic to poorer nations' way of life. But are we really? I always thought I maintained the appropriate level of gratefulness and empathy, but after just 48 hours with no power I started to go crazy. It was demoralizing, sitting in the dark, cold and helpless and cut off.
And now I have an existential crisis. I used to be a mechanical engineer. I have my master's degree in hybrid car design and I've also done quite a bit of work in renewable energy. And I left that behind to do what? Software engineering. I make websites and write code for the first world. I turned my back on my altruistic goals of helping the environment and designing clean tech because "it wasn't for me" and "I wanted to be my own boss".
Is that fair? Is that a decision I'm morally allowed to make? I have the skills to help other people out but instead I'm running a startup and writing on my blog. Should I feel guilty? Do I have a moral obligation to use my engineering skills to give back to the world in a bigger way? I don't know. I enjoy software more–which is why I switched. I have more experience in software than mechanical engineering, but that may be a moot point: having a couple of degrees and being published in hybrid vehicles engineering may have made me more valuable to the sustainable engineering world than the I am to the web startup world.
And if I'm more valuable to the sustainable world — if they need me more — than the startup world, am I supposed to be doing sustainable engineering with my life? Do I get to just recklessly choose which I pursue? Or am I supposed to go the way that needs me more?
Do what you love, or do what you're good at?
I think I'll stick to what I love for now (software and startups), but if anyone wants to buy my company for a few hundred million (it's worth it!) then I promise I'll follow in Elon Musk's footsteps and focus on the rest of the world.
The post Do we have a moral obligation to society? appeared first on Burak Kanber's Blog.]]>
The post SiteChat: a postmortem. Or, the rise and fall of a society. appeared first on Burak Kanber's Blog.]]>
I got bored one day and decided to learn how to build Chrome extensions. I also wanted to play with the nascent WebSockets protocol, so I figured I'd combine those two pieces into some kind of experiment.
As context, I'll mention that my tech friends often make fun of me because I write software entirely from scratch. Something about using a black box third party library makes me uneasy. And what's the point of "learning" WebSockets if you're not actually going to implement the protocol yourself? Otherwise, you're just learning somebody else's WebSockets library. My friends call it "overkill"; I call it learning!
So I wrote a WebSockets server daemon in PHP and threw together a Chrome extension called SiteChat. Pure laziness dictated that the app wouldn't require registration; all messages were passed through the WS server without being stored. That turned out to be very helpful; SiteChat was now essentially anonymous and registration-free. Chatters could enter a nickname, but since there was no registration that nickname could be used by anybody else in the system… which eventually lead to some amusing trolling in the system.
Version 1 of SiteChat took a day and a half to develop and release in the Chrome store. I posted a link to it on Hacker News and Reddit, took a nap or ate dinner or something, and woke up to thousands of new users.
Over the course of the next few days something like 100,000 people tried SiteChat. The night I released it, I had to scramble and write a new protocol on top of WebSockets to handle server bridging. I was committed to the anonymous, push-only aspect of SiteChat by this point, so bringing up a DB server as a message store was not possible–even though that would have easily solved my problem of quickly needing to bring up multiple WebSocket servers. Regardless, hacking together a bridging protocol wasn't too bad and I was able to keep SiteChat up in the face of tens of thousands of concurrent users all with permanently open TCP connections to my servers.
I'm actually very happy about the way my rushed, experimental, hacked-together-in-hours PHP WebSockets stack worked out. While I only have the one WS server running today, the system proved to be reliable and maintenance-free and has been going strong for over a year now. I think there was a period of downtime for a few days at some point, but that was because I switched DNS providers and forgot to update the SiteChat DNS entry. Oops! But the WS stuff never had any issues.
When I posted SiteChat on HN, I got a whole lot of "this will never stick, somebody tries it every year and it always fails." I expected that to be true, but I didn't really care either way. SiteChat was a side project that I had no emotional or financial investment in, so if it failed, whatever! I learned Chrome extensions and WebSockets, and it was fun to work on.
However, I became really excited when I saw the user stats. People were using this thing! The reddit.com, ycombinator.com, facebook.com, and gmail.com chatrooms were the most popular, with hundreds of people in each room and dozens of active chatters on at all hours of the day.
Over the next few weeks I remained very involved with SiteChat. I was online all day, chatting away. I also worked on some nice new features, my favorite being the Pop-Out/Mobile version of the app. Lots of FireFox users complained that they couldn't use SiteChat, and lots of people wanted to chat in a room while browsing other sites, so I made a standalone interface to SiteChat. It also (still) works on iOS and Android browsers, which is really cool.
(I'm getting excited just talking about SiteChat again. I really loved this app!)
But far more interesting than the technology was the community that formed. Each of the major chatrooms(/domains) on SiteChat had its own unique ecosystem. Reddit was for casual chatting. Hacker News was for techies. Facebook had people looking for cybersex. Long, deep conversations at a (generally) high level of discourse were held, and that lasted for a little over two months.
After a few weeks of coddling SiteChat, real life struck again and I no longer had hours a day free to chat online. So I stopped engaging with the app for a month(?… the timeline is fuzzy), but the little chat notification numbers in my browser told me that SiteChat was still alive and kicking.
A month or two went by and I'd all but forgotten about the app. One day I went back on, and it felt a little sad. While not quite a ghost town, SiteChat did resemble Detroit a few years back. It clearly had once been a great, booming society, but was also clearly on its way out. The regulars I used to know were no longer there–though there was a group of new regulars.
I hopped onto the reddit.com chatroom and said hi. Immediately, people asked me why my name was green! (I had the only reserved nickname, "bkanber" in green lettering). Even that was a bit of a shock to me. Everybody had known me in the past. Nobody knew me now, except for one guy who piped up "he's the creator of SiteChat". And then what happened was really strange.
It became clear to me that there was a lot of mythology floating around the SiteChat community. It seems that in the two-month hiatus I took, roughly three generations of users had gone by; just enough for stories to be handed down and distorted a bit. Some people thought I was some kind of rebel in an oppressed country, and I built SiteChat in order to exercise free speech (I'm from New York). Some people thought I was a basement-dwelling version of the comic book guy from The Simpsons (I'm social, and have decent genetics). Some people outright revered me. It was clear that SiteChat had alleviated social pain-points for a lot of people that lived in rural areas, and they thanked me profusely.
I realized at that point that online chatrooms weren't really popular anymore like they used to be in the past with AOL and IRC. But there was still a small market for it, and SiteChat filled that niche temporarily.
I then learned something very intriguing. SiteChat didn't have moderators of any kind, except for a simple rate-limiting system that prevented excessive abuse. While I never saw trolling become a huge problem, it was there. I then learned that, in my absence, a group of users formed a SiteChat vigilante group called something like "the Templar" or "the Agents" or something (I forget), with the sole purpose of bullying trolls into leaving SiteChat rooms. Now that's weird.
Given an open and free ecosystem, a group of users spontaneously decided to come together and protect their habitat. They defended the weak and innocent against bullies. Now, I think we all know that given an open ecosystem, bullies always appear. But other than some isolated "white-knighting", I never expected the ecosystem to regulate itself in such a manner. That really impressed me, and left me speechless for some time.
I did end up disengaging myself from SiteChat again. I knew that SiteChat would eventually disappear, but in the interim the community seemed like it could take care of itself without any intervention from me.
A month or two later, SiteChat usage was essentially down to zero and remained there for several weeks. Then the second wind came. About 10,000 new users joined up again, stabilized to 5,000 active users, and there was some good activity for a few months. I discovered that these users were primarily young people (13 and 14 year olds) whose parents didn't let them IM or use Facebook yet. SiteChat, freely available from the Chrome store, was their loophole. The level of discourse on SiteChat was at an all-time low. I quickly disengaged again, and haven't been back since.
Today the Chrome store shows 5,000 SiteChat users, but with only a hundred messages sent each day the once booming society is essentially extinct.
Could I revive it with a marketing campaign? Maybe. Will I? Probably not. Like Hacker News said from the very beginning, somebody tries this every year or so and fails. In fact, the reason I'm writing this is because I recently met with a young startup that wrote a very similar app. Will they have their moment in the sun? Maybe. I don't know.
I think what made SiteChat compelling for a while was its low barrier to entry. Thousands of people clicked on the Chrome store link when I first posted it, and a very high percentage of people converted. Installing a Chrome extension is really easy, and most users installed it and immediately saw people chatting. They were able to start chatting as "Anon 5032" or something as soon as they installed it. If they were interested in chatting more, it took just a second to type in a nickname. You didn't have to put in an email address, or click a confirmation link, or create a password.
SiteChat relies on the network effect, and so it falls victim to the chicken-and-egg problem. You wouldn't use SiteChat if no one else is using it, and if no one else is using it, it would attract no new users. The low barrier to entry was critical. Having, say, 1000 users online in the first hour created a society that lasted (in significant form) for roughly six months. Had only 250 users been online in the first hour, I can guarantee that SiteChat would have been dead in six days. So in this instance, that high conversion rate in the first hour was of the utmost importance. If you were to launch SiteChat in parallel universes, the "number of users in the first hour vs longevity" chart would certainly be exponential.
I had another major advantage: I didn't care about monetizing SiteChat. I can't tell you how many people asked me to turn it into a Live Support application (that supports file uploads and webcam!). I also received a weak offer to purchase SiteChat, which I didn't pursue. Had I tried to monetize SiteChat, I would have killed it. Using advertisements, requiring registration, or bloating it with features all could have made it monetizable, but would have immediately destroyed the userbase.
Fortunately, SiteChat only cost me about $200 over the past 14 months. And that price tag was well worth the experience of watching an app hit its stride, watching an entire society emerge, and subsequently experiencing the extinction of an entire species of SiteChat users.
The post SiteChat: a postmortem. Or, the rise and fall of a society. appeared first on Burak Kanber's Blog.]]>
The post Machine Learning: k-Means Clustering Algorithm in Javascript appeared first on Burak Kanber's Blog.]]>
Are you just looking for the code example? Scroll down!
Machine learning helps us navigate and process large volumes of data. We can ask all sorts of questions about our data, and hope that ML can answer them: what is this data point most similar to? Does the data come in patterns? Can we predict what will happen in the future, given past trends? These questions are applicable to all fields of study.
Today we're going to figure out how to find clusters of data points. Let's say you work at a medical imaging devices company. Imagine you already have a way to identify malignant cells from an image scan, but it would be great to automatically identify the centers of clusters of cells as well. Then a robot could go in with surgical precision and remove the problem!
What we're looking for is a clustering algorithm; today we're going to talk specifically about the k-means algorithm.
Clustering algorithms, in general, find groups of similar pieces of data. If you run an online store you might use a clustering algorithm to identify different shopper types. You may find that you have one type of visitor that just window shops through 3-5 pages of products and leaves. Another group might make meticulous purchasing decisions by looking through 15 pages of products and reviews and end up making only one, high-value purchase. And you may also identify the impulse buyer, who makes numerous small purchases without browsing too deeply. Once you've identified your e-shopper demographics, you're better able to optimize your site to increase sales. You can release features that appeal to your impulse buyers, because now you know that you have impulse buyers!
And while that's just one practical example of k-means, you'll find this algorithm used in multiple fields. Sometimes it's just image processing in 2 dimensions, other times it's processing huge data across dozens of dimensions and parameters. Like our k-nearest-neighbor algorithm, k-means is versatile, simple to understand and implement, and sneakily powerful.
Like k-nearest-neighbor, the "k" in k-means gives away that there's going to be some number that we're going to have to feed to our algorithm. Specifically, "k" is the number of clusters we're going to find in our data. Unfortunately, it's rarely possible to know the number of clusters before you solve the problem, so k-means is usually supplemented by another algorithm that first helps you find the best value of k.
The issue is this: the k-means algorithm will partition your data into "k" distinct clusters, but it does not tell you if that's the correct number of clusters. Your data might naturally have 5 different clusters in it, but if you feed k-means the number 3 you'll get 3 clusters back. Those clusters will be bigger, looser and more awkwardly shaped than if you had told it to find 5 clusters.
The long and short of it is this: in order to use k-means you either need to know how many clusters you're looking for at the outset, or you have to use a second algorithm to also guess the number of clusters. K-means just organizes your points into clusters; you need to do something else to figure out the right number of clusters.
For today we'll contrive a situation and use three clusters from the outset. Next time (in k-means part 2) we'll look at a technique you can use to automatically guess the value of "k". Most often, these algorithms rely on some kind of error analysis and multiple passes of the k-means algorithm in order to optimize for the solution with the smallest error value.
The k-means algorithm is simple but can become very powerful if you're using it on a dataset with many dimensions. Today we're going to work in 2 dimensions, but next time we'll do something more complicated. Here's what the algorithm looks like:
This algorithm, like many of the one we'll play with in this series, is susceptible to local optima. If you run the example below a few times you'll see that the clusters can end up in one of a few different configurations. These are various local optima that the solution gets stuck in. Algorithms that start with some sort of random seed state (like GAs or k-means) are particularly susceptible to local optima, because you never really know how the algorithm will start off and which path the solution will end up following. Will this seed state lead to a local or global optima? There's no way of knowing!
Like in genetic algorithms, one way to shake out of local optima is to give the solution a little bit of mutation. In our k-means example, we could add a rule that gives a centroid a nudge in a random direction if it doesn't move after an iteration. It might settle back into its last resting place, or it may find a new solution. The nudge shouldn't be big enough that it restarts the solution from the beginning, but just enough to kick a centroid out of a local valley, if it's in one.
Another technique we could use is called the "committee of machines", which works well if you're running an algorithm that finishes pretty quickly, or if you have parallel computing capabilities. It's simple: we run the k-means algorithm 3 or 5 or 51 or 10,000 times, and choose the solution that it returned the most often. The term "committee of machines" alludes to the fact that some people choose to actually run parallel algorithms on different pieces of hardware, and a literal committee of machines votes on the solution.
Let's dive in. Unlike my other examples thus far, I'm going to forego an object-oriented implementation and just go straight procedural. There are many ways to skin a cat. I love OOP but it's important not to get too comfortable in habits!
Additionally, while we're only working with 2 dimensional data in this example, I'd like to write this algorithm out to handle any number of dimensions (except for the canvas drawing functions).
Let's take a look at the data we're using — a simple array of "points", which are just represented by 2-element arrays (for X and Y values):
var data = [ [1, 2], [2, 1], [2, 4], [1, 3], [2, 2], [3, 1], [1, 1], [7, 3], [8, 2], [6, 4], [7, 4], [8, 1], [9, 2], [10, 8], [9, 10], [7, 8], [7, 9], [8, 11], [9, 9], ];
Next, we define two functions that are helpful to us, but not essential. Given a list of points, I'd like to know what the max and min values for each dimension are, and what the range of each dimension is. I want to know "X ranges from 1 to 11, and Y ranges from 3 to 7″. Knowing these figures helps us draw the graph on the canvas, and also helps when we initialize our random cluster centers (we'd like them to be within the range of the data points when we start them out).
Keeping in mind that we're writing this to be generic with regards to the number of dimensions they can handle:
function getDataRanges(extremes) { var ranges = []; for (var dimension in extremes) { ranges[dimension] = extremes[dimension].max - extremes[dimension].min; } return ranges; } function getDataExtremes(points) { var extremes = []; for (var i in data) { var point = data[i]; for (var dimension in point) { if ( ! extremes[dimension] ) { extremes[dimension] = {min: 1000, max: 0}; } if (point[dimension] < extremes[dimension].min) { extremes[dimension].min = point[dimension]; } if (point[dimension] > extremes[dimension].max) { extremes[dimension].max = point[dimension]; } } } return extremes; }
getDataExtremes() method loops through all the points and each dimension in each point and finds the min and max values (note there's a hard-coded "1000" in there, which you should change if you're using large numbers). The
getDataRanges() function is just a helper that takes that output and returns the range of each dimension (the maximum value minus the minimum value).
Next up, we define a function that initializes k random cluster centroids:
function initMeans(k) { if ( ! k ) { k = 3; } while (k--) { var mean = []; for (var dimension in dataExtremes) { mean[dimension] = dataExtremes[dimension].min + ( Math.random() * dataRange[dimension] ); } means.push(mean); } return means; };
We're just creating new points with random coordinates within the range and dimensions of our dataset.
Once we have our randomly seeded centroids, we need to enter our k-means loop. As a reminder, the loop consists of first assigning all our data points to the centroid closest to it, then moving the centroids to the average position of all the data points assigned to it. We repeat that until the centroids stop moving.
function makeAssignments() { for (var i in data) { var point = data[i]; var distances = []; for (var j in means) { var mean = means[j]; var sum = 0; for (var dimension in point) { var difference = point[dimension] - mean[dimension]; difference *= difference; sum += difference; } distances[j] = Math.sqrt(sum); } assignments[i] = distances.indexOf( Math.min.apply(null, distances) ); } }
The above function is called by our "loop" function and calculates the Euclidean distance between each point and the cluster center.
Note that the above algorithm loops through each point and then loops through each cluster centroid, making this an O(k*n) algorithm. It's not terrible, but it might be computationally intensive if you have a large number of data points or a large number of clusters or both. There are ways you can optimize this, which we'll perhaps discuss in a future article. For one, we can try to eliminate the expensive
Math.sqrt() call; we could also try not to iterate through every point.
Once we have our list of assignments — in this case, just an associative array of
point index => center index — we can go ahead and update the positions of the means (the cluster centers).
function moveMeans() { makeAssignments(); var sums = Array( means.length ); var counts = Array( means.length ); var moved = false; for (var j in means) { counts[j] = 0; sums[j] = Array( means[j].length ); for (var dimension in means[j]) { sums[j][dimension] = 0; } } for (var point_index in assignments) { var mean_index = assignments[point_index]; var point = data[point_index]; var mean = means[mean_index]; counts[mean_index]++; for (var dimension in mean) { sums[mean_index][dimension] += point[dimension]; } } for (var mean_index in sums) { console.log(counts[mean_index]); if ( 0 === counts[mean_index] ) { sums[mean_index] = means[mean_index]; console.log("Mean with no points"); console.log(sums[mean_index]); for (var dimension in dataExtremes) { sums[mean_index][dimension] = dataExtremes[dimension].min + ( Math.random() * dataRange[dimension] ); } continue; } for (var dimension in sums[mean_index]) { sums[mean_index][dimension] /= counts[mean_index]; } } if (means.toString() !== sums.toString()) { moved = true; } means = sums; return moved; }
moveMeans() starts by calling the
makeAssignments() function. Once we have our assignments, we initialize two arrays: one called "sums" and the other called "counts". Since we're calculating the arithmetic mean (or average), we'll need to know the sum of points' dimensions as well as the number of points whose dimensions we're averaging.
We then hit three loops:
First we loop through our means and prepare our sums and counts arrays. Our sums array will actually be multidimensional, because we're storing each dimension's sum of each point of each mean in this structure — so we have to zero-out the second-depth level of this 2 dimensional array.
Then we loop through our assignments and increment the counts counter for each cluster center we have points assigned to, and additionally loop through the point's dimensions to fill in the sums array. At this point we have all the data we need to calculate the new positions of the cluster centers.
The final loop loops through our results, calculates the mean position for each cluster center, and moves it. The final loop also checks to see if a cluster center had no points assigned to it. If it didn't have any points assigned to it, we give it a new random position. This is just us trying to kick that cluster center back into the solution.
Finally, we wrap up this function by checking to see if any one of our cluster centers has moved — and we return either true or false.
To get this algorithm started, we run the following setup functions:
function setup() { canvas = document.getElementById('canvas'); ctx = canvas.getContext('2d'); dataExtremes = getDataExtremes(data); dataRange = getDataRanges(dataExtremes); means = initMeans(3); makeAssignments(); draw(); setTimeout(run, drawDelay); } function run() { var moved = moveMeans(); draw(); if (moved) { setTimeout(run, drawDelay); } }
setup() initializes everything we need, and then our
run() function checks to see if the algorithm has stopped, and loops based on a timer so that we can watch the algorithm do its work in a reasonable timeframe.
One major issue with the k-means algorithm isn't a fault of the algorithm's, but rather of the concept of the arithmetic mean, or average. The average is a pretty bad metric when you have outlying data.
If you work at a company where 5 people make $50,000 a year but one person makes $1,000,000, the median salary is $50,000 (very representative of salary at that company), but the mean salary is $200,000 (not at all representative of salary at that company)!
This happens with all sorts of data, and can and will happen in the k-means algorithm too. If you have a dataset prone to outliers, you'll find that k-means gets "stuck" on the outlier and ends up yielding poor results. In that case, switch to k-medians! The algorithm is nearly the same; instead of calculating the mean for your cluster centers, use the median instead. I believe — but I'm not certain — that calculating the median also has a performance advantage over the mean.
As you can see from the example below, k-means works very well for our nice, neat data. Obviously it'll have more difficulty with messy data, like any other algorithm.
If you run the example below a number of times (click the play button on the JSFiddle) you'll eventually see it fall into a local optimum. This should also demonstrate the usefulness of the "committee of machines" solving method: while a bad solution does pop up from time to time, it should be clear that a committee of machines will produce the correct solution reliably.
Finally, if you like this series, please sign up for the mailing list below and tell your friends! I also appreciate discussion, so feel free to use the commenting tool below. And make sure to check out the other ML in JS articles!
The post Machine Learning: k-Means Clustering Algorithm in Javascript appeared first on Burak Kanber's Blog.]]>
The post Physics in Javascript: Rigid Bodies — Part 1 (Pendulum Clock) appeared first on Burak Kanber's Blog.]]>
Just looking for the cool JSFiddle code example?
So far, we've modeled everything in this series as particles. Particles are the simplest way to model something physically, because they only have a location in space and don't have a size or shape. Particles can only translate (move), and can't rotate.
And while you can do some amazing things just by modeling particles, particles aren't realistic in the real world. Real objects aren't just infinitely small dots. Real objects have a size and shape and most importantly, an orientation. Real objects can rotate. And since most of you are probably interested in game development: you can't get by on particles alone.
Today we're going to begin our discussion of rigid bodies. Rigid bodies have all of the properties of particles: they have a location, they have a linear velocity, and they have a linear acceleration. But because rigid bodies have a shape and size, they also have an orientation (a rotation angle), and are subject not just to forces but also to torques which cause them to rotate. Torques can either be applied to an object directly (in the case of a wheel on a motor, like in a car), or they can appear because a force is applied to an object off-center (like when a football is kicked and tumbles end-over-end).
While rigid bodies are more complicated to model than particles, we're still able to use familiar concepts and Newton's laws. We just need to extend them a little bit to deal with rotation and torque.
Let's start by comparing linear motion (translation) to angular motion (rotation). Translation has properties that we're pretty familiar with by now: position, velocity, acceleration, mass, and force. Rotation is similar, but the variables have been modified slightly to: angle, angular velocity, angular acceleration, moment of inertia, and torque. Let's introduce these concepts very briefly.
Analogous to "position" for translation, the angle describes the current orientation of a rigid body. If you're working in two dimensions — as we are here — you only need one angle to fully describe an object's rotation. Typically, angle is denoted by the Greek letter theta: θ. In three dimensions, three angles are required to describe the object's orientation, and in that case you should use Euler angles. Angle is a dimensionless quantity typically measured in radians or degrees. This is in contrast to the "position" in linear motion, whose dimension is "length".
Concretely: the angle θ is the number of radians or degrees something is rotated by.
Like linear velocity, angular velocity describes how much the object's angle changes in a given time-frame. While "degrees per hour" is an acceptable unit, angular velocity is almost always given in "radians per second". Since radians are dimensionless, angular velocity has a dimension of inverse time. Typically, the Greek letter omega is used for angular velocity: ω.
Similarly, angular acceleration is given in "radians per second squared" or "radians per second, per second", and is typically denoted by the Greek letter alpha: α.
Force, in the linear world, is directly responsible for an object's acceleration. Rotation is no different; in the angular world, torque is responsible for an object's angular acceleration.
What's more, a torque is just a force applied in a special manner: torque is what you get when you apply a force slightly offset from an object's center of mass. If you were to lay a block on a table and push on it dead-center with your finger, you'd push the block forward without rotating it. If, however, your finger were off to the side of the block, you'd end up both pushing and rotating the block. It's still the same block, it's still the same finger. The only thing that has changed is where you applied the force. Since you applied it in such a way that it didn't go "through" the block's center of mass, you created a torque and that's what caused the block to rotate.
A torque, therefore, is just a force multiplied by its (perpendicular) distance from the object's center of mass (or point of rotation, depending on your physical set-up). Think about using a wrench: the longer the wrench is, the easier it is to turn. That's because you're multiplying the force by a larger distance and getting a larger torque as a result (of course, you have to move your hand farther to get the same angle of motion with a longer wrench — so you end up doing the same amount of work!).
Torque is measured in units of force times distance: newton-meters or pound-feet, and is typically denoted by the Greek letter tau: τ.
The toughest piece of the rotational puzzle to calculate from scratch is the moment of inertia. In linear motion, mass (inertia) is a sort of resistance to changing the object's motion. A light object is easier to speed up or slow down than a heavy object. Similarly, moment of inertia is a resistance to a change in rotation. But moment of inertia is more complicated than mass, because both the object's mass and its shape and size need to be considered. A 5 pound hoop is harder to get spinning than a 5 pound disc of the same size, because the hoop has all its mass near the edge.
The moment of inertia is given in units of kg * m2 (kilogram times meters squared) and is typically denoted by the capital letter I or J. I like J.
Fortunately, you can just look up the moments of inertia of many common shapes and use those in your calculations. In school we were forced to do those calculations by hand with double or triple integrals. If you're interested in practicing your calculus, go that route. If not, just use the lookup table.
Newton's 2nd Law is Fnet = m*a. Modified for rotation, we can write it as τnet = J*α. Notice that, like the linear form of the equation, both τ and α are vectors. Since our example is in 2D — which means all our rotation happens around the "z" axis — we can just assume these are scalars for now.
Since you've certainly read the Gravity and Drag and Spring-Mass-Damper articles, you probably already know what to do with this equation. Figure out the total torque, use that to calculate the acceleration, and then integrate twice to get the angle. The trickiest part is the "figure out the net torque" step, especially if you're uncomfortable with trigonometry. Let's dive into an example.
I should now point out that — just like with linear motion — you can introduce springs and dampers into the mix. The equations are essentially the same as their linear counterparts. If you want a homework assignment, please try adding a damper to this pendulum!
I want to build a simple and elegant animated pendulum clock. Rather than just "fudging" the motion of the pendulum by using sine easing, I want to solve for the physics directly. (Though physics students will recognize that sine actually is the solution to this problem!)
The pendulum itself will be modeled as a point mass at the end of a weightless rod. Many physics problems are made with such assumptions: point mass, weightless rod, no friction, etc. It's a good way to make a first pass at what could become a very complicated problem.
Diving right into some code:
var pendulum = {mass: 1, length:500, theta: (Math.PI/2) - 0.05, omega: 0, alpha:0, J:0}; var setup = function() { pendulum.J = pendulum.mass * pendulum.length * pendulum.length; ... }
Right off the bat we set up initial conditions for our pendulum. In this case, we've defined θ = 0 to be when the pendulum is pointing horizontally to the right. Many people would choose to define θ = 0 as downwards. It doesn't really matter, as long as you're consistent.
Then we calculate the value of the pendulum's moment of inertia. Our Wikipedia list of moments of inertia tells us that a "point mass m at distance r from the axis of rotation" has a moment of inertia of m*r2, so that's what we use.
I've done a few things differently in this code example. First of all, I've used
requestAnimFrame() instead of
setInterval() (see the JSFiddle for the full code; I won't talk about it here). Secondly, instead of using Euler's method of numerical integration, I've used the velocity verlet method.
Euler's method is actually pretty inaccurate as far as numerical integration methods go. I've used it up until now because it's very simple to understand, but it's time to move onwards and upwards. You're ready for it!
The above graphic illustrates where the inaccuracy in Euler's method comes from. Numerical integration is all about calculating the area below a function's curve. Most basic numerical integration techniques draw rectangles underneath the curve and add up their areas (see Riemann sum); this is what we're doing with Euler's method. Unfortunately, this can grossly over- or under-estimate a function especially if that function changes quickly. Making those rectangles thinner (in our case, making the loop delay smaller/faster) can help greatly, but there's still the fact that we're putting the the corner of the rectangle on the curve.
One other integration technique improves accuracy by having the function run through the midpoint of the rectangle, instead of the left or right corner; this is called the midpoint method. There's also the trapezoidal method, which draws trapezoids instead of rectangles. There's also the very accurate Runge-Kutta method, which uses a weighted average of 4 points along the function to calculate the area below the curve.
Here's a nice demonstration of how much better the midpoint method (in green) works compared to Euler's method (blue).
To make a long story short, we'll use the velocity verlet method today. I encourage you to look up the details and try to understand what gives it an advantage over Euler's method!
Let's get back to code. In the loop (boring stuff omitted):
var loop = function() { ... /* Velocity Verlet */ /* Calculate current position from last frame's position, velocity, and acceleration */ pendulum.theta += pendulum.omega * deltaT + ( 0.5 * pendulum.alpha * deltaT * deltaT ); /* Calculate forces from current position. */ var T = pendulum.mass * 9.81 * Math.cos(pendulum.theta) * pendulum.length; /* Current acceleration */ var alpha = T / pendulum.J; /* Calculate current velocity from last frame's velocity and average of last frame's acceleration with this frame's acceleration. */ pendulum.omega += 0.5 * (alpha + pendulum.alpha) * deltaT; /* Update acceleration */ pendulum.alpha = alpha; var px = width/2 + pendulum.length*Math.cos(pendulum.theta); var py = 50 + pendulum.length*Math.sin(pendulum.theta); ... };
The velocity verlet method has us do things "out of order", so to speak. I'll describe the steps in the order I feel is natural, however, starting with torque:
First we calculate the torque on the pendulum. Since gravity pulls downwards at all times, we need to use some trigonometry to get the component of the pendulum's weight that's pulling the pendulum towards the center — the small portion of the weight pointed perpendicular to the pendulum itself. Because of the fact that we set up the θ = 0 point on the right horizontal, we get this by calculating m * g * cos(θ) — (where m is the pendulum's mass and g is 9.81 m/s2, the acceleration due to gravity on Earth).
Since we're looking for a torque, we have to multiply that perpendicular force by its distance from the center.
Once we have the torque the next few steps are easy. We calculate the angular acceleration α, and then we implement a piece of velocity verlet to get the angular velocity ω: we use the average of last frame's and this frame's acceleration in the calculation.
Finally, we calculate the angle θ. Notice this time I kept the 0.5 * α * Δt2 in the equation. Up until now I've left that term out — Δt is pretty small, and squaring it makes it so small it's almost negligible. But let's leave it in here now just as a demonstration!
And that's it for the physics. The next part is a little trigonometry: we have to convert our radius and angle to x- and y-coordinates for the canvas. This is achieved readily with sine and cosine.
As an added bonus, we draw a cute little clock. See the JSFiddle for details.
If you have a formal education in physics, you've probably done this very same pendulum problem by hand. You should notice that our numerical solution agrees very well with the analytical solution. For one, the mass of the pendulum has no effect on the pendulum's period. Only the length matters! Additionally — without any damping — the pendulum always returns to its highest points on either side. Feel free to fork the code below and play around.
If you like these articles please tell your friends, please sign up for the mailing list below, and consider following me on Twitter. Readers like you following the blog and subscribing to the mailing list gives me the motivation to write these articles — and potentially an e-book in the future!
You may also like my Machine Learning in Javascript series.
The post Physics in Javascript: Rigid Bodies — Part 1 (Pendulum Clock) appeared first on Burak Kanber's Blog.]]>
The post Machine Learning: Genetic Algorithms in Javascript Part 2 appeared first on Burak Kanber's Blog.]]>
Just looking for the example?
You're a scientist that has recently been framed for murder by an evil company. Before you flee the lab you have an opportunity to steal 1,000 pounds (or kilograms!) of pure elements from the chemical warehouse; your plan is to later sell them and survive off of the earnings.
Given the weight and value of each element, which combination should you take to maximize the total value without exceeding the weight limit?
This is called the knapsack problem. The one above is a one-dimensional problem, meaning the only constraint is weight. We could complicate matters by also considering volume, but we need to start somewhere. Note that in our version of the problem only one piece of each element is available, and each piece has a fixed weight. There are some knapsack problems where you can take unlimited platinum or up to 3 pieces of gold or something like that, but here we only have one of each available to us.
Why is this problem tough to solve? We'll be using 118 elements. The brute-force approach would require that we test 2118 or 3.3 * 1035 different combinations of elements.
A quick benchmark we'll use for our solution is called the "greedy" solution. The greedy algorithm grabs the most valued items and puts them into the knapsack until it can't fit any more.
Sometimes this works great. Sometimes it doesn't. Imagine that there's a piece of gold in the warehouse that's valued at $1,000 but weighs 600 pounds. And there's also a piece of cadmium that has a value of $950 but only weighs 300 pounds, and there are a bunch of other elements that have a pretty high value but reasonably light weights. The greedy algorithm still tosses gold in there, and all that precious available weight is taken up by something that's not really worth it.
The "naive" greedy algorithm for our dataset will give us a total value of $3649 with a total weight of 998 pounds.
You may at this point be thinking "why don't we just figure out value per pound for each element and use that?" Sure, that works too! It will, in fact, work way better than the above.
Using that approach, the "weighted" greedy algorithm gives us a total value of $4901 and a total weight of 969.
So those are our numbers to beat: we should expect to handily beat $3,649, and we'll be happy if we also beat $4,901.
Why does the greedy algorithm work well for this type of problem? Because the greedy algorithm is solving for the "highest value per unit weight" and that's very close to what we want to fill our knapsack with. However, the greedy algorithm will not perform well in instances where there's a large range of weights and values. That is, the greedy algorithm will perform better if the range of values (and/or weights) of the elements is between $1 – $100, but will perform worse if the range is $1 – $500.
Respond in the comments: why would the greedy algorithm perform worse with a larger range of weights and values?
Our GA might lose to the greedy algorithm from time to time, but that's ok. The GA will continue to perform well as complexity increases, but the greedy algorithm will not.
So we're still tackling a pretty simplified and contrived problem here, but it's certainly more complex and useful than our "Hello, World!" from the last article. Let's get started.
There are some major differences between our problem and the previous "Hello, World!":
The "Hello, World!" algorithm represented the chromosome as a string. Mutating involved randomly changing a letter. Mating (or crossover, as it's really called) involved splicing two strings together at the halfway point. We need to do things a little differently here.
It turns out that representing our solution requires a little more finesse than "Hello, World!". Since we don't know how many elements to choose, we can't use a fixed length string. (Just the first of our problems!)
Instead, I propose we use a "bitmask" of sorts. We don't have to use an actual bitmask, but my proposal is to use a representation of all of the available elements, and set each "present" or not.
Our chromosome could look like this:
Helium: present Hydrogen: not present Lithium: not present
And et cetera for all 118 elements. Or if you want to go the bitmask route:
Where each bit represents a single element and the value of the bit indicates whether that element is in the knapsack or not.
Additionally, if we were to allow more than one of each element, the representation could look like so:
Helium: 0 Hydrogen: 4 Lithium: 2
What would not work well is the following:
In Knapsack: Helium, Lithium, Lead, Tin
The above makes mating more difficult. You can make it work, but it feels like you'd be jumping through hoops to pull it off. Structure feels better for this problem.
We have a specific difficulty with mating: we need to make sure that even after mating and mutation we still only have at most one of each element in the list. Using the bitmask approach will help us to that end, but that's a common pitfall when trying the list approach above.
The difficulty of making sure something happens only once in a chromosome is a common one. If you're familiar with the traveling salesman problem, it's easy to imagine a scenario where you mate two solutions and end up visiting the same city twice. That city appeared in the first half of the first parent and the second half of the second parent — therefore appearing nowhere in one child but twice in the other child.
For this problem we're going to keep track of three properties of the population: weight, value, and score.
Score is the same thing as value, with one difference: score accounts for the population being overweight.
You may be tempted to throw out overweight populations completely. It's a natural instinct because overweight solutions are not acceptable solutions! But there's a good, practical reason we don't want to throw out overweight chromosomes: there will be some slightly overweight (1,001 pounds) chromosomes that have very high values and just need to be "tweaked" a little to bring them within the weight range.
There could be a lot of potential in some of the overweight chromosomes. Rather than killing them, we'll penalize them just enough that they still get to reproduce, but are unlikely to be the #1 pick. That's what we'll use "score" for. If you're underweight, then your score is just your total value. If you're overweight, however, we'll penalize you 50 points for every pound over weight. Feel free to play with this number.
Evolutionarily, this "encourages" promising chromosomes to drop some weight. All they need is a little tweaking. There's no use in throwing out a potentially strong candidate!
We'll cover the specifics of mating and mutation and the important of death (really called "elitism") as we're looking at the code.
First, let's take a look at the data set. I wrote a simple PHP script that generates random weights and values (ranged 1 – 500) for each element and outputs the set as JSON. It looks something like this:
"Hydrogen":{ "weight":389, "value":400}, "Helium":{ "weight":309, "value":380}, "Lithium":{ "weight":339, "value":424}, "Beryllium":{ "weight":405, "value":387}, "Boron":{ "weight":12, "value":174},
And so on.
We then define three quick and easy helper functions:
function length(obj) { var length = 0; for (var i in obj) length++; return length; } function clone(obj) { obj = JSON.parse(JSON.stringify(obj)); return obj; } function pickRandomProperty(obj) { var result; var count = 0; for (var prop in obj) if (Math.random() < 1 / ++count) result = prop; return result; }
The 'length' property only exists for javascript arrays, so we create a length() function that works for objects.
We create a clone function that ensures our element objects aren't passed by reference.
Finally, we create a function that picks a random property of an object. This is an analog to PHP's 'array_rand' function, which returns a random array key.
var Chromosome = function(members) { this.members = members; for (var element in this.members) { if (typeof this.members[element]['active'] == 'undefined') { this.members[element]['active'] = Math.round( Math.random() ); } } this.mutate(); this.calcScore(); }; Chromosome.prototype.weight = 0; Chromosome.prototype.value = 0; Chromosome.prototype.members = []; Chromosome.prototype.maxWeight = 1000; Chromosome.prototype.mutationRate = 0.7; Chromosome.prototype.score = 0;
The chromosome constructor takes an object of 'members'. In this case, we'll either be passing our original list of elements data when we're creating a brand new chromosome, or we'll be passing in the results of a mating operation.
The constructor randomly activates elements if the 'active' property isn't yet defined. The end result is that this will create a random chromosome if we're creating one from scratch, and it'll leave a pre-configured chromosome alone.
The prototype also specifies some defaults. The mutationRate property is the chance that a chromosome will mutate.
Chromosome.prototype.mutate = function() { if (Math.random() > this.mutationRate) return false; var element = pickRandomProperty(this.members); this.members[element]['active'] = Number(! this.members[element]['active']); };
The mutate method is most similar to the "Hello, World!" example. If the chromosome is to mutate then we simply pick an element at random and toggle its 'active' property. I cast to Number here. It would have been more semantic to cast the Math.random() in the constructor to Boolean. I'll ignore this, as I've already pasted all the code into this post.
Chromosome.prototype.calcScore = function() { if (this.score) return this.score; this.value = 0; this.weight = 0; this.score = 0; for (var element in this.members) { if (this.members[element]['active']) { this.value += this.members[element]['value']; this.weight += this.members[element]['weight']; } } this.score = this.value; if (this.weight > this.maxWeight) { this.score -= (this.weight - this.maxWeight) * 50; } return this.score; };
The calcScore method starts with a tiny performance optimization: if we've calculated the score already, just serve the cached score — it's just a nice way to not have to worry about at which point in the chromosome life cycle to calculate the score.
We then look through the elements and add up the value and weights for the active ones. We then apply a penalty of 50 points per overweight pound.
Chromosome.prototype.mateWith = function(other) { var child1 = {}; var child2 = {}; var pivot = Math.round( Math.random() * (length(this.members) - 1) ); var i = 0; for (var element in elements) { if (i < pivot) { child1[element] = clone(this.members[element]); child2[element] = clone(other.members[element]); } else { child2[element] = clone(this.members[element]); child1[element] = clone(other.members[element]); } i++; } child1 = new Chromosome(child1); child2 = new Chromosome(child2); return [child1, child2]; };
In the "Hello, World!" example we picked the center point as the pivot point when mating two chromosomes; in this example we pick a random point instead.
This adds a little more randomness to the system and can help avoid local optima.
Once we've picked our pivot point we create two children by splicing the parents at the pivot and combining. We then use our chromosome constructor to generate chromosome objects and return them.
var Population = function(elements, size) { if ( ! size ) size = 20; this.elements = elements; this.size = size; this.fill(); }; Population.prototype.elitism = 0.2; Population.prototype.chromosomes = []; Population.prototype.size = 100; Population.prototype.elements = false;
The population constructor is straightforward: we give it the master list of elements and the desired population size. We also define the 'elitism' parameter; this is the percentage of chromosomes that will survive from one generation to the next.
Population.prototype.fill = function() { while (this.chromosomes.length < this.size) { if (this.chromosomes.length < this.size / 3) { this.chromosomes.push( new Chromosome( clone(this.elements) ) ); } else { this.mate(); } } };
We use the fill method to initialize the population; we'll also use it to fill the population after killing the weakest chromosomes. A little bit of logic determines whether we should create random chromosomes or fill the population through mating instead. If our population size is 20, the first 6 chromosomes will be random and the remaining will be generated by mating. If the population size ever dips below 30% (perhaps due to death/elitism), new random chromosomes will be created until the population is diverse enough to create babies through mating.
Yes, 'this.chromosomes.length' in a while loop is bad form. If you expect to use a large population size — or want this to be highly optimized — do this the right way and cache the length.
Population.prototype.sort = function() { this.chromosomes.sort(function(a, b) { return b.calcScore() - a.calcScore(); }); }; Population.prototype.kill = function() { var target = Math.floor( this.elitism * this.chromosomes.length ); while (this.chromosomes.length > target) { this.chromosomes.pop(); } };
The sort function above is just a helper; note that we use the calcScore method instead of accessing the 'score' property directly. If the score hasn't been calculated by this point, it will be now; if the score was already calculated we just use calcScore as an accessor.
After sorting, the kill method removes the weakest chromosomes from the bottom of the list by popping them until we reach our elitism value.
Population.prototype.mate = function() { var key1 = pickRandomProperty(this.chromosomes); var key2 = key1; while (key2 == key1) { key2 = pickRandomProperty(this.chromosomes); } var children = this.chromosomes[key1].mateWith(this.chromosomes[key2]); this.chromosomes = this.chromosomes.concat(children); };
The mate method is always called after the kill method, so the only chromosomes allowed to reproduce are the elite ones in the population (in our example, the best 20%). Rather than mating only the best two chromosomes (like we did in "Hello, World!"), we pick any two random chromosomes to mate — with the exception that we won't mate a chromosome with itself.
Again, this serves to add a little more randomness to the system, and will avoid stasis if the top two chromosomes remain the same for many generations — we see that happen sometimes in the "Hello, World!" example and fix it here.
Population.prototype.generation = function(log) { this.sort(); this.kill(); this.mate(); this.fill(); this.sort(); };
Then we define a "generation". The generation starts by sorting the chromosomes in terms of score. We then kill the weakest members.
Then we do something a little intriguing: we call mate() once and then call fill(), which we know will also call mate(). The reason we call mate() explicitly is as a bit of insurance: if the elitism parameter is less than 0.3 we want to mate at least once before potentially "polluting" the population with random members. This really depends on the elitism value; if you keep it over 0.3 you don't have to call mate() explicitly, because fill() will do that for you. But if you have elitism = 0.2 like we do, then we want to run at least one mating routine that involves only the elite, and not the new random chromosomes we introduce with fill().
Finally, we sort once more at the end of the generation. We could just as easily leave this part out, but it's nice to see the chromosomes in order after every generation if you're debugging.
I briefly introduced this idea in the "Hello, World!" example: we don't know the best possible score in this problem, therefore we won't know when to stop.
The technique (one of many) that we'll use is to stop when you've had 100 (or 1,000 or 1,000,000) generations with no improvement. We'll just call this the "threshold" or the "stop threshold".
Population.prototype.run = function(threshold, noImprovement, lastScore, i) { if ( ! threshold ) threshold = 1000; if ( ! noImprovement ) noImprovement = 0; if ( ! lastScore ) lastScore = false; if ( ! i ) i = 0; if (noImprovement < threshold) { lastScore = this.chromosomes[0].calcScore(); this.generation(); if (lastScore >= this.chromosomes[0].calcScore()) { noImprovement++; } else { noImprovement = 0; } i++; if (i % 10 == 0) this.display(i, noImprovement); var scope = this; setTimeout(function() { scope.run(threshold, noImprovement, lastScore, i) }, 1); return false; } this.display(i, noImprovement); };
The run method is an iterative function. It doesn't need to be. The only reason it is in this example is because writing to the DOM in the middle of a fast-moving loop doesn't work — the DOM doesn't update until execution is done. It's just a javascript thing.
To get around the DOM limitation, we use a short setTimeout and have the run method call itself iteratively until we're done. In general, however, this function could just use a while loop instead of calling itself — but in that case you'd either need to use console.log or just wait until the loop is done to watch the results.
Other than that DOM messiness, the run method is straightforward. We compare last generation's best score to this generation's best. If there was improvement, then we reset the 'noImprovement' counter. If we have noImprovement equal to our stop threshold, we stop.
Not shown is a simple display method used to print the results to a table on the page. We only call it every 10 generations, and then once again when we're done.
Our JSFiddle is below. You're given a slider that lets you set the stop tolerance and a big "Go" button. You then get to watch the population's evolution.
Even with a 10-generation stop threshold, the GA consistently beats the naive greedy algorithm, though this is to be expected.
At a 50-generation stop threshold, the GA also consistently beats the weighted greedy algorithm. This is a happy result. There are some datasets where the GA will never beat the greedy algorithm, and other datasets where the greedy algorithm doesn't perform well at all. This seems like an in-between. We don't crush the greedy algorithm, but we do outperform it by a significant margin.
The best score I've observed so far is 5944, with a weight of 992. Please let me know in the comments below if you find a better score, and I'll post the updates here.
Update: Sylvain Zimmer below found a solution with a score of 5968 and weight 998.
As always, feel free to fork and play with this example. I would encourage you to experiment with different values of population size, elitism, and mutation rate and observe the results.
The post Machine Learning: Genetic Algorithms in Javascript Part 2 appeared first on Burak Kanber's Blog.]]>
The post Opinion: Preparing for the Future of Technology appeared first on Burak Kanber's Blog.]]>
We've made some crazy progress in technology, particularly in the last 20 years. What will the next 20 (or even 10) years bring? And most importantly, how do we prepare ourselves for it?
Right now there are engineers and scientists working on what we once thought were ridiculous technologies. E-textiles that have a cell phone embedded in the fabric and beam the audio straight into your ear. Google Glass and augmented reality. Siri and speed recognition. Machine learning everywhere.
I feel kind of left out in the face of all of this. The lowly web software engineer. The hardware engineers are doing all the cool stuff! At first I was a little disappointed that I didn't pursue a career in hardware, but then I realized: once the hardware guys do their job, it's on the web developers to make it useful. When AR glasses become popular, web designers and engineers will have to figure out how to create a real user experience. Sure, at first all the software will be proprietary, but eventually it'll move to the web. That's just the way it goes. And that brings up some interesting challenges: after all, how do you browse the web in a pair of glasses?
The web won't be the same as it is now. Ten years from now there won't be keyboards or mice. They'll eventually be replaced by a Javascript Speech Recognition API bundled with HTML7 or something. New cell phones will sit in your pocket and somehow understand gestures, and beam audio to your face through your clothes. Project Glass will have brain sensors that take thought commands — maybe. (Google would love to monetize our thoughts, I'm sure.) It sounds ridiculous, but I bet all of what I just mentioned will happen in the next decade (or two).
Siri can already understand you speak, and she'll only get better at it. Eventually she'll be able to browse Facebook for you, read your stream out loud, and take instructions. (I'm already calling Siri "she"!) But it would be silly to have to build technologies from scratch to do this. It'll all start with proprietary tech (the iOS Facebook app), but eventually the W3C will just have HTML specifications for how Siri should read your webpage out loud. There'll be a spec for taking speech commands and gestures.
What does this mean for designers and engineers? It means that if you don't want to be left behind, you need to start thinking about this stuff. Start by opening up your mind to the possibilities of interface-less human/computer interaction. Every once in a while, you should be doing a thought experiment: how will people interact with websites 5, 10, or 20 years from now? Maybe your webcam will have eyeball tracking built in, and all you have to do is look at a link to follow it. Maybe physical keyboards will be replaced by on-screen keyboards, and all you have to do is look at the right letters until it can auto-complete the word you want.
We don't know what the web is going to look like in the future, but we all know it's going to change. You can teach an old dog new tricks, but I think we need to start mentally and creatively preparing ourselves for some sort of paradigm shift in the upcoming years.
"Grandpa, how did you used to go on Facebook?"
"Well, Jimmy, we had this thing called a keyboard, and we had to type in 'facebook.com' and then put in our email address and password."
"It's something we used to type letters into a computer."
"You had to type letters?!"
Prepare yourselves.
The post Opinion: Preparing for the Future of Technology appeared first on Burak Kanber's Blog.]]>
The post Physics in Javascript: Car Suspension – Part 1 (Spring, Mass, Damper) appeared first on Burak Kanber's Blog.]]>
Today, we'll be talking about arguably the most important set of building blocks there is: the spring-mass-damper.
The spring-mass-damper is important to learn because it's everywhere in mechanics. Superficially, the system is just a block connected to a wall by a spring and a damper (we'll talk about what a damper is in a bit). But as you can imagine, physics is a can of worms — and there's a lot more to this simple system than meets the eye.
The humble spring is one of the three most important mechanical components to know how to model. Why is the spring so important? How often do you actually see a spring? Sure, they're in lots of mechanical devices, like your car and your door lock and your clicky pen, but it turns out that they're a lot more important than their use in mechanical devices.
The reason springs are so important is because there's nothing in the real universe that's "infinitely rigid". Every object in the universe is a little bit springy, even if you can't tell by eye.
Imagine you're holding a stick from one end and you rest the other end against a cup on a table. You want to push the cup across the table, so you start pushing the stick with your hand. As it turns out, the cup does not start moving the instant you start moving your hand. There's a tiny delay — a fraction of a second — before the cup starts moving.
That's because the stick isn't "infinitely rigid" — the molecules in the stick don't all move at once. The stick is actually a spring! If you now re-imagine that scenario with a big, floppy spring, you can immediately see why the cup doesn't start moving instantly: the spring has to compress a little bit first, and only when it compresses enough does the cup start moving. Additionally, the force from your end of the spring takes some time to travel down to the other end of the spring — think about wiggling a slinky back and forth. You're not moving the whole object instantaneously, but rather you're sending a little shockwave through the spring.
(By the way, the speed of that shockwave is called the "speed of sound", and every different material has a different speed of sound.)
Back to the stick: it's really a spring; a very, very stiff spring (the term "stiffness" actually refers to something slightly different, but for this article I'll use "stiffness" and "spring constant" interchangeably). A big floppy spring isn't very stiff, and so you can compress it quite a bit before it builds up enough force to move the cup. But imagine a stiffer spring: it needs less compression before the cup moves. Even a metal rod is a spring. You can't see it with your eyes or feel it with your hand, but the metal rod does compress a little bit before the other end moves. It's just so stiff that you can't see the compression with the naked eye.
So not only can actual springs be modeled as springs (mathematically) but so can sticks and rods! They're just really stiff springs. And you can even connect individual particles to each other by springs to make a realistic fluid or fabric particle simulator. So as I said: springs are everywhere.
Fortunately for us, the basic method of modeling springs is really easy. It's governed by Hooke's Law, which says this:
Fspring = -kΔx
The force that a spring pushes or pulls with is -k (called the "spring constant", measured in kg / s2) times the displacement. Let's look a little closer:
The displacement is how much the spring is being stretched or compressed. If a spring wants to be 10 inches long (we'll call this "equilibrium length" or "natural length"), but it's being crushed to 8 inches, the displacement is 2 inches.
The spring constant is a characteristic of the spring itself. We'll assume that it's a constant, but that's not true in the real world. The value of "k" changes due to things like temperature and if the spring is stretched to an extreme, but the assumption that "k" is a constant is usually a good one. There are also springs designed to have a non-constant "k", but we'll avoid those too.
The spring constant is also negative; that implies that the spring force fights the direction you're displacing the spring. If you stretch a spring, it tries to compress itself. If you compress a spring, it tries to stretch itself. The spring wants to be back to its equilibrium length, and the farther it is from its natural length, the harder it'll push back.
In short: a spring resists changes in displacement.
While a spring resists changes in displacement, a damper resists velocity. A spring wants to go back to position 0, while a damper wants to go back to velocity 0. Physically dampers can take many forms, but the one we typically talk about is called a dashpot. The dashpot is a cylinder filled with fluid with a piston that can move through the liquid. You can move the piston through the liquid, but you experience considerable resistance in doing so. Check out the Wikipedia article for a nice image.
Why are dampers so important? Just like springs, actual dampers are not used everywhere (in cars we call them "shock absorbers"), but the mathematic model is seen everywhere. Dampers often represent the internal frictional losses of a system.
Mathematically, if you had just a perfect mass and a perfect spring and "plucked" it in a vacuum, the mass would oscillate back and forth forever, always returning to the same exact two extreme points. But intuition and a lifetime of experience tells us that shouldn't happen, even in a vacuum! The spring itself is made of metal, and when the spring flexes the molecules rub up against each other — that causes friction, and friction takes away from the energy of the sprung mass. The result is that (even in a vacuum) the spring will warm up slightly and the mass will eventually stop moving.
But it's really difficult to model the internal material friction of the metal in the spring. So instead, we assume the spring is perfect ("ideal"), and add a damper to the system instead. The damper ends up representing the internal losses of the spring. The damper adds a dash of reality to the system, and will make the mass eventually stop moving just like in real life.
The viscous damping force equation is similar to the spring force equation:
Fdamping = -bv
Instead of using the displacement like we did with Hooke's law, we're using the velocity. Instead of the spring constant we have -b, called the "viscous damping coefficient", measured in kg / s. Again, we have the negative sign, which signifies that the force acts opposite the velocity. If you're moving one direction, damping will slow you down by pulling in the opposite direction.
Together, the spring, mass and damper elements form what's called a harmonic oscillator, and that system has some interesting properties: most notably, a "resonant frequency" (or natural frequency). If you've ever whacked a knife against a table, or tapped a wine glass with a fork and listened to it ring, you've listened to a resonant frequency. Because of the springiness of all materials, every object in the world has some frequency that it "likes". If you tap the object, it'll resonate at its so-called "natural frequency".
Additionally, if by some external means, you wiggle the object at that very frequency, you can cause it to vibrate wildly. That's what happens when an opera singer breaks a glass with her voice — she's singing that frequency and therefore "exciting" the glass at its natural frequency. More impressive is the Tacoma Narrows Bridge Collapse Disaster, caused by the wind exciting the bridge's natural frequency. Jump to 1 minute for the oscillation, 3 minutes for the collapse.
If you know the spring stiffness and mass of a spring-mass system, you can calculate the natural frequency. The natural frequency is
fn = ( 1 / 2 π ) * sqrt( k / m )
If there's a damper attached to the system, that changes the natural frequency slightly.
If you use external motion to excite a spring-mass-damper system (called forced vibration), the following effects occur:
Let's build the code and play with this, so we can finally see these effects in action!
/* Spring stiffness, in kg / s^2 */ var k = -20; var spring_length = 180; /* Damping constant, in kg / s */ var b = -0.5; /* Block position and velocity. */ var block = {x: 100, v: 0, mass: 0.5}; var wall = {x: 30, lx: 30, v: 0, t: 0, frequency: 0};
Some of the usual setup above. We create a block object and a wall object. We set a spring_length (for the spring's equilibrium length), and initialize the spring constant and the damping constant.
Inside our loop:
var loop = function() { /* Move the wall. */ wall.t += frameRate; wall.lx = wall.x; wall.x = 30 + 70 * Math.sin(2 * Math.PI * wall.frequency * wall.t); wall.v = (wall.x - wall.lx) / frameRate; /* Loop continues .... */
In our example, the spring and damper are connected to a moveable wall on one end and a block on the other end. The code above moves the wall according to the sine function.
/* ... continued from above . */ /* Move the block. */ if ( ! mouse.isDown ) { var F_spring = k * ( (block.x - wall.x) - spring_length ); var F_damper = b * ( block.v - wall.v ); var a = ( F_spring + F_damper ) / block.mass; block.v += a * frameRate; block.x += block.v * frameRate; }
There's not too much magic here. We learned how to use forces in the Gravity and Drag article before this one.
We first calculate the spring force by figuring out the spring displacement: the distance between the wall and block at this moment minus the equilibrium length of the spring. Then we multiply that by the spring constant, which is a negative number.
The damping force is calculated similarly, except using the velocities of the wall and block instead of position.
Not shown is a bunch of code to draw the wall and block. There's also some mouse handling: in this example, you can grab the block with the mouse.
In order to get a good feel for what goes on with spring-mass-damper systems, please try the following procedure:
What does this mean for a car suspension? Imagine the wall as the road and wheel, and the mass as the rest of the car. If you drive slowly over big, loping bumps, the whole car moves up and down. If you drive quickly over rapid bumps, the tire will bounce up and down a lot but the car will stay more or less in place.
Next week we'll be talking about different methods of solving our equations, and hopefully get something that feels a little smoother.
Here's the JSFiddle:
The post Physics in Javascript: Car Suspension – Part 1 (Spring, Mass, Damper) appeared first on Burak Kanber's Blog.]]>
The post Effective Teaching is a Long Con appeared first on Burak Kanber's Blog.]]>
If you wish to make an apple pie from scratch, you must first invent the universe.
– Carl Sagan
The above Carl Sagan quote is why most smart people are bad teachers. Smart, impassioned people know the whole story behind what they're teaching. Smart people like to think about the whole story; they run it through their heads over and over in the shower, while they're cooking, and on the subway. Smart people like to tell other people the whole story, and end up re-inventing the universe when all they set out to do was teach a lesson on a single topic.
(Of course, not all smart people are bad teachers. Being smart and being a good teacher are two separate skills. While being smart certainly can help a teacher's skills, one can not get by as a teacher on being smart alone.)
Telling the whole story is frustrating to students; it's too much to take in all at once. The smart person tends to forget that they learned the whole story over years of intense learning. It's hard for the smart person to let go of pieces of the story — to consciously omit them — even if they're not of immediate importance.
I wrote my first Physics in Javascript article on Gravity and Drag the other day. Part of the article talks briefly about calculus and the derivative. I love physics and I love calculus so it was very tempting to tell the whole story. I wish I could have gone in-depth about what integration really is, I wish I could have talked about numerical ODE solvers and how the solver I implemented is a first-order ODE solver called Euler's method… and what that all means. But it would have been the wrong thing to do.
If you try to tell the whole story you'll end up writing a whole damned textbook and lose your audience in the process. You'll alienate the people that matter the most: the students. Students are people trying to learn this stuff for the first time and it's easy for a teacher to lose sight of that.
Knowing what not to teach is just as important as knowing what to teach. If you need to introduce a concept to complete a lesson, then do so — but don't get pulled into the beauty of the deeper meaning that you understand, because your students don't understand that stuff yet.
Instead, I strive to have my students accidentally learn stuff. Your lessons or lectures or articles should omit the bits that aren't of immediate importance, but leave a little trail of breadcrumbs in the process. Drop little clues about those tangential topics you want your students to come to understand. Eventually your students will piece it all together.
"… this isn't the only way to do this; this is called Euler's method but there are some more sophisticated methods…"
"… electrons orbit the nucleus — well, almost… Heisenberg's uncertainty principle tells us we can't know exactly what they're doing …"
"… this is called a linked list — there's also a doubly-linked list, but we don't need that today …"
It's hard to accept that many of your students will simply ignore the breadcrumbs you drop, but it's still the right thing to do. Not going into too much detail keeps your lessons accessible. In future lessons you'll leave more breadcrumbs and eventually your students will discover a little puzzle you've left for them.
Why is this my favorite way to teach? The most engaged students will go and research that stuff on their own, and the least engaged students won't get bogged down by extraneous information. Worst-case scenario, a student ends up leaving with exactly what you taught them. Best-case, a student leaves the class with more than you gave them. And often enough, your students will subconsciously piece together the subplot you've laid out — without even doing the extracurricular research themselves.
The breadcrumb method works because we love solving problems and decoding patterns (see Raph Koster's "A Theory of Fun for Game Design" for some excellent discussion) — so when the student pieces it together they end up delighted by what they've learned. That's more effective than spoon-feeding them the information, and creates a generation of excited learners in the process.
It's a long con. After months of lessons, you've tricked your students into learning more than they've bargained for. Most students won't even know you conned them. The smart-alecs will even challenge you at times: "you left out ___ !" or "you forgot about friction!" But that's ok — you're not supposed to impress them. You're supposed to guide and teach the people who need you to keep their best interests in mind, and you need to do that by whatever means necessary.
It sounds strange, but the morally responsible thing to do is carefully and meticulously plan to con your students. With knowledge. Please don't actually con them.
The post Effective Teaching is a Long Con appeared first on Burak Kanber's Blog.]]>
The post Machine Learning in JS: k-nearest-neighbor Introduction appeared first on Burak Kanber's Blog.]]>
Just looking for the example code? The JSFiddle is at the bottom of the page.
Today we're going to look at the k-nearest-neighbor algorithm (we'll abbreviate it kNN throughout this article). I love this algorithm because it's dead simple, but can still solve some exciting problems. Its strength doesn't lie in mathematical or theoretical sophistication, but rather in the fact that it can elegantly handle lots of different input parameters ("dimensions").
k-nearest-neighbor also serves an ulterior motive of mine: it's a great way to introduce the concept of "supervised learning". So let's go ahead and build the k-nearest-neighbor algorithm. And we'll graph our results, because I love visuals!
There are two giant umbrella categories within Machine Learning: supervised and unsupervised learning. Briefly, unsupervised learning is like data mining — look through some data and see what you can pull out of it. Typically, you don't have much additional information before you start the process. We'll be looking at an unsupervised learning algorithm called k-means next week, so we can discuss that more in the next article.
Supervised learning, on the other hand, starts with "training data". Supervised learning is what we do as children as we learn about the world. We're in the kitchen with mom. Mom shows us an apple and says the word "apple". You see an object and your mother has labeled it for you.
The next day, she shows you a different apple. It's smaller, it's less red, and it has a slightly different shape. But your mother shows it to you and says the word "apple". This process repeats for a couple of weeks. Every day your mother shows you a slightly different apple, and tells you they're apples. Through this process you come to understand what an apple is.
Not every apple is exactly the same. Had you only ever seen one apple in your life, you might assume that every apple is identical. But instead, your mother has trained you to recognize the overall features of an apple. You're now able to create this category, or label, of objects in your mind. When you see an apple in the future you can recognize it as an apple because you've come to understand that while all apples share some features, they don't have to be identical to still be apples.
This is called "generalization" and is a very important concept in supervised learning algorithms. We would be useless if we couldn't recognize that an iPhone was an iPhone because it had a different case, or because it had a scratch across the screen.
When we build certain types of ML algorithms we therefore need to be aware of this idea of generalization. Our algorithms should be able to generalize but not over-generalize (easier said than done!). We want "this is red and kind of round and waxy, it must be an apple" and not "this is red and round, it must be a ball; this other thing is orange and round, it must be a ball." That's overgeneralization and can be a problem. Of course, under-generalization is a problem too. This is one of the main difficulties with ML: being able to find the generalization sweet spot. There are some tests you can run as you're training an algorithm to help you find the sweet spot, but we'll talk about those in the future when we get to more advanced algorithms.
Many supervised learning problems are "classification" problems. The classification problem goes like this: there's a bucket of apples, oranges, and pears. Each piece of fruit has a sticker that tells you which fruit it is — except one! Figure out which fruit the mystery fruit is by learning from the other fruits you're given.
The classification problem is usually very easy for humans, but tough for computers. kNN is one type of many different classification algorithms.
This is a great time to introduce another important aspect of ML: features. Features are what you break an object down into as you're processing it for ML. If you're looking to determine whether an object is an apple or an orange, for instance, you may want to look at the following features: shape, size, color, waxiness, surface texture, etc. It also turns out that sometimes an individual feature ends up not being helpful. Apples and oranges are roughly the same size, so that feature can probably be ignored and save you some computational overhead. In this case, size doesn't really add new information to the mix.
Knowing what features to look for is an important skill when designing for ML algorithms. Sometimes you can get by on intuition, but most of the time you'll want to use a separate algorithm to determine which are the most important features of a data set (we'll talk about that in a much more advanced article).
As you can imagine, features aren't always as straightforward as "color, size, shape". Processing documents is a tricky example. In some scenarios, each word in a document is an individual feature. Or maybe each pair of consecutive words ("bigrams") is a feature. We'll talk about document classification in a future article as well.
Given the number of rooms and area (in square feet) of a type of dwelling, figure out if it's an apartment, house, or flat.
As always, we're starting with the most contrived possible problem in order to learn the basics. The description of this problem has given us the features we need to look at: number of rooms, and square feet. We can also assume that, since this is a supervised learning problem, we'll be given a handful of example apartments, houses, and flats.
I think the best way to teach the kNN algorithm is to simply define what the phrase "k-nearest-neighbor" actually means.
Here's a table of the example data we're given for this problem:
We're going to plot the above as points on a graph in two dimensions, using number of rooms as the x-axis and the area as the y-axis.
When we inevitably run into a new, unlabeled data point ("mystery point"), we'll put that on the graph too. Then we'll pick a number (called "k") and just find the "k" closest points on the graph to our mystery point. If the majority of the points close to the new point are "flats", then we'll guess that our mystery point is a flat.
That's what k-nearest-neighbor means. "If the 3 (or 5 or 10, or 'k') nearest neighbors to the mystery point are two apartments and one house, then the mystery point is an apartment."
Here's the (simplified) procedure:
If you're having trouble visualizing this, please take a quick break to scroll down to the bottom of the page and run the JS fiddle. That should illustrate the concept. Then come back up here and continue reading!
Let's start building this thing. There are a few fine points that will come out as we're implementing the algorithm, so please read the following carefully. If you skim, you'll miss out on another important concept!
I'll build objects of two different classes for this algorithm: the "Node", and a "NodeList". A Node represents a single data point from the set, whether it's a pre-labeled (training) point, or an unknown point. The NodeList manages all the nodes and also does some canvas drawing to graph them all.
The Node constructor has nothing to it. It just expects an object with the properties "type", "area", and "rooms":
var Node = function(object) { for (var key in object) { this[key] = object[key]; } };
When I build these algorithms "for realsies" I usually abstract the features a little bit more. This example requires "area" and "rooms" to be hard-coded in certain places, but I usually build a generalized kNN algorithm that can work with arbitrary features rather than our pre-defined ones here. I'll leave that as an exercise for you!
Similarly, the NodeList constructor is simple:
var NodeList = function(k) { this.nodes = []; this.k = k; };
The NodeList constructor takes the "k" from k-nearest-neighbor as its sole argument. Please fork the JSFiddle code and experiment with different values of k. Don't forget to try the number 1 as well!
Not shown is a simple NodeList.prototype.add(node) function — that just takes a node and pushes it onto the this.nodes array.
At this point, we could dive right in to calculating distances, but I'd like to take a quick diversion.
Look at the data in the table above. The number of rooms varies from 1 to 10, and the area ranges from 250 to 1700. What would happen if we tried to graph this data onto a chart (without scaling anything)? For the most part, the data points would be lined up in a vertical column. That'll look pretty ugly, and hard to read.
Unfortunately, that's not just an aesthetic problem. This is an issue of a large discrepancy of scale of our data features. The difference between 1 room and 10 rooms is huge when you consider what it means for classifying a "flat" vs a "house"! But the same difference of 9, when you're talking about square feet, is nothing. If you were to measure distances between Nodes right now without adjusting for that discrepancy, you'd find that the number of rooms would have almost no effect on the results because those points are so close together on the x-axis (the "rooms" axis).
Consider the difference between a dwelling with 1 room and 700 square feet and 5 rooms and 700 square feet. Looking at the data table by eye, you'd recognize the first to be a flat and the second to be an apartment. But if you were to graph these and run kNN, it would consider them both to be flats.
So instead of looking at absolute values of number of rooms and area, we should normalize these values to be between 0 and 1. After normalization, the lowest number of rooms (1) becomes 0, and the largest number of rooms (10) becomes 1. Similarly, the smallest area (250) becomes 0 and the largest area (1700) becomes 1. That puts everything on the same playing field and will adjust for discrepancies of scale. It's a simple thing to do that makes all the difference in the world.
Pro-tip: you don't need to scale things evenly (into a square) like I described above. If area is more important to the problem than the number of rooms, you can scale those two features differently — this is called "weighting", and gives more importance to one feature or another. There are also algorithms that will determine the ideal feature weights for you. All in due time…
To start normalizing our data we should give NodeList a way of finding the minimum and maximum values of each feature:
NodeList.prototype.calculateRanges = function() { this.areas = {min: 1000000, max: 0}; this.rooms = {min: 1000000, max: 0}; for (var i in this.nodes) { if (this.nodes[i].rooms < this.rooms.min) { this.rooms.min = this.nodes[i].rooms; } if (this.nodes[i].rooms > this.rooms.max) { this.rooms.max = this.nodes[i].rooms; } if (this.nodes[i].area < this.areas.min) { this.areas.min = this.nodes[i].area; } if (this.nodes[i].area > this.areas.max) { this.areas.max = this.nodes[i].area; } } };
As I mentioned earlier, the best approach would be to abstract the features and not have areas or rooms hard-coded. But doing it this way reads a little more clearly to me.
Now that we have our minimum and maximum values, we can move along to the meat and berries of the algorithm. After we've added all our Nodes to the NodeList:
NodeList.prototype.determineUnknown = function() { this.calculateRanges(); /* * Loop through our nodes and look for unknown types. */ for (var i in this.nodes) { if ( ! this.nodes[i].type) { /* * If the node is an unknown type, clone the nodes list and then measure distances. */ /* Clone nodes */ this.nodes[i].neighbors = []; for (var j in this.nodes) { if ( ! this.nodes[j].type) continue; this.nodes[i].neighbors.push( new Node(this.nodes[j]) ); } /* Measure distances */ this.nodes[i].measureDistances(this.areas, this.rooms); /* Sort by distance */ this.nodes[i].sortByDistance(); /* Guess type */ console.log(this.nodes[i].guessType(this.k)); } } };
That's a mouthful. First off, we calculate the min and max ranges so that the NodeList is aware of it.
We then loop through the Nodes and look for any unknown nodes (yes, this can do more than one mystery node at a time).
When we find an unknown Node, we clone the Nodes in the NodeList and make the Node aware of them. The reason we do this is because each unknown Node will have to calculate its own distance to every other Node — so we can't use global state here.
Finally, we call three Node methods in succession on the unknown Node: measureDistances, sortByDistance, and guessType.
Node.prototype.measureDistances = function(area_range_obj, rooms_range_obj) { var rooms_range = rooms_range_obj.max - rooms_range_obj.min; var area_range = area_range_obj.max - area_range_obj.min; for (var i in this.neighbors) { /* Just shortcut syntax */ var neighbor = this.neighbors[i]; var delta_rooms = neighbor.rooms - this.rooms; delta_rooms = (delta_rooms ) / rooms_range; var delta_area = neighbor.area - this.area; delta_area = (delta_area ) / area_range; neighbor.distance = Math.sqrt( delta_rooms*delta_rooms + delta_area*delta_area ); } };
The measureDistances function takes the NodeList's set of ranges for min and max rooms and areas. If you've abstracted away from hard-coding features, the argument to this method would just be an array of ranges for features, but here we've hardcoded it.
We quickly calculate the rooms_range (here, it'll be 9) and area_range (here, it'll be 1450).
Then we loop through our Node's neighbors (we gave this Node the neighbors property above when we cloned the Nodes from NodeList). For each one of the neighbors we calculate the difference in number of rooms and area. After each of those calculations, we normalize by dividing each feature by its range.
If the difference between the number of rooms turns out to be 3 and the total range is 9 we end up for 0.333 for the value of that delta. This number should always be between -1 and +1, since we've normalized to a square for this problem.
Finally, we calculate the distance using the Pythagorean theorem. Note that if you have more than 2 features (dimensions), you still keep the Math.sqrt — you just add all the squared features like so:
Math.sqrt( a*a + b*b + c*c + d*d + ... + z*z );
It should be pretty clear now what the true strength of this algorithm is. While our feeble minds may only be able to figure out correlations involving 5 or 10 different features, this algorithm can do that for hundreds or thousands of dimensions.
Node.prototype.sortByDistance = function() { this.neighbors.sort(function (a, b) { return a.distance - b.distance; }); };
This above sortByDistance is just a helper function to sort the Node's neighbors by distance.
Node.prototype.guessType = function(k) { var types = {}; for (var i in this.neighbors.slice(0, k)) { var neighbor = this.neighbors[i]; if ( ! types[neighbor.type] ) { types[neighbor.type] = 0; } types[neighbor.type] += 1; } var guess = {type: false, count: 0}; for (var type in types) { if (types[type] > guess.count) { guess.type = type; guess.count = types[type]; } } this.guess = guess; return types; };
The final piece of the algorithm is the guessType method. This method accepts the value of "k" from NodeList and slices out the k closest neighbors. It then tallies up the types of the neighbors, picks the most common one, and returns the result.
Algorithm finished. Congratulations! Now let's figure out how to graph this thing.
Graphing our results is pretty straightforward, with a few exceptions:
NodeList.prototype.draw = function(canvas_id) { var rooms_range = this.rooms.max - this.rooms.min; var areas_range = this.areas.max - this.areas.min; var canvas = document.getElementById(canvas_id); var ctx = canvas.getContext("2d"); var width = 400; var height = 400; ctx.clearRect(0,0,width, height); for (var i in this.nodes) { ctx.save(); switch (this.nodes[i].type) { case 'apartment': ctx.fillStyle = 'red'; break; case 'house': ctx.fillStyle = 'green'; break; case 'flat': ctx.fillStyle = 'blue'; break; default: ctx.fillStyle = '#666666'; } var padding = 40; var x_shift_pct = (width - padding) / width; var y_shift_pct = (height - padding) / height; var x = (this.nodes[i].rooms - this.rooms.min) * (width / rooms_range) * x_shift_pct + (padding / 2); var y = (this.nodes[i].area - this.areas.min) * (height / areas_range) * y_shift_pct + (padding / 2); y = Math.abs(y - height); ctx.translate(x, y); ctx.beginPath(); ctx.arc(0, 0, 5, 0, Math.PI*2, true); ctx.fill(); ctx.closePath(); /* * Is this an unknown node? If so, draw the radius of influence */ if ( ! this.nodes[i].type ) { switch (this.nodes[i].guess.type) { case 'apartment': ctx.strokeStyle = 'red'; break; case 'house': ctx.strokeStyle = 'green'; break; case 'flat': ctx.strokeStyle = 'blue'; break; default: ctx.strokeStyle = '#666666'; } var radius = this.nodes[i].neighbors[this.k - 1].distance * width; radius *= x_shift_pct; ctx.beginPath(); ctx.arc(0, 0, radius, 0, Math.PI*2, true); ctx.stroke(); ctx.closePath(); } ctx.restore(); } };
I won't describe the above in detail, but rather point out two lines that I want you to look at and figure out on your own:
It's a good but potentially frustrating exercise to try and figure out what's going on in those two lines, but please don't give up until you understand them!
Finally, we'll throw some code together to create random mystery points and do that every 5 seconds:
var run = function() { nodes = new NodeList(3); for (var i in data) { nodes.add( new Node(data[i]) ); } var random_rooms = Math.round( Math.random() * 10 ); var random_area = Math.round( Math.random() * 2000 ); nodes.add( new Node({rooms: random_rooms, area: random_area, type: false}) ); nodes.determineUnknown(); nodes.draw("canvas"); }; window.onload = function() { setInterval(run, 5000); run(); };
If you want to play with the value of "k", do it in the run() function above.
The kNN algorithm isn't the most sophisticated classifier there is, but it has some excellent uses. What's even more exciting is that you don't have to use kNN as a classifier; the concepts behind kNN are very flexible and can be used for non-classification problems. Consider the following problems that kNN might be a good candidate for (list includes both classification problems and otherwise):
There are two issues with kNN I'd like to briefly point out. First of all, it should be pretty clear that if your training data is all over the place, this algorithm won't work well. The data needs to be "separable", or clustered somehow. Random speckles on the graph is no help, and very few ML algorithms can discern patterns from nearly-random data.
Secondly, you'll run into performance problems if you have thousands and thousands of Nodes. Calculating all those distances adds up! One way around this is to pre-filter out Nodes outside of a certain feature's range. For example, if our mystery point has # of rooms = 3, we might not even calculate distances for points with # of rooms > 6 at all.
Here's the JSFiddle. The known points are colored, the mystery point is grey, and the result of the kNN guess is signified by the colored radius around the mystery point. The radius encapsulates the 3 nearest neighbors. A new random mystery point is solved for every 5 seconds:
The post Machine Learning in JS: k-nearest-neighbor Introduction appeared first on Burak Kanber's Blog.]]>
The post Modeling Physics in Javascript: Gravity and Drag appeared first on Burak Kanber's Blog.]]>
This is the first post in the Modeling Physics in Javascript series. As such, we'll need to cover some introductory material. There are some of you who have real training in physics and calculus. You may be tempted to scream "that's not the whole story" at me when I explain some concepts, and my response to you is this: I wish I could cover all the amazing parts of physics and calculus in one blog post, but I can't. I'll therefore cover only the bits I need. Hopefully, the people reading this will accidentally learn physics while trying to pick up some cool JS tricks.
Model a bouncy ball, under the influence of gravity, which can bounce off of horizontal or vertical walls. Oh, and it experiences air drag.
Not too shabby for day 1! We'll first talk about Newton's 2nd Law, forces, gravity, and a touch of calculus before we can start coding.
Newton's 2nd Law of Motion basically is physics. It describes how forces interact with macroscopic objects. If you've ever seen a ball fly through the air, or a car moving, or something rolling down a hill, or if you've ever felt anything, you know (indirectly) about Newton's 2nd Law.
Newton's 2nd Law looks like this: F = ma.
Well, not quite. It looks more like this: Fnet = ma.
As you can imagine, physics has a manner of starting simple and then getting very complicated very quickly. The subscript "net" means that the "F" doesn't just refer to a single force, but the sum total of all forces on the object. The bold "F" and "a" mean that those variables (force and acceleration) are vectors — meaning that they exist separately in 3 different directions (X, Y, and Z).
But that's not too bad. If you don't want to do vector math, you can simply rewrite Fnet = ma as the following three separate equations:
You may think that having three equations to worry about makes things tougher, but trust me, it doesn't. Just remember that you have to do the F = ma equation for each direction. We'll very rarely use the Z direction, so all we really have to worry about stuff happening in the X and Y directions (left/right, and up/down).
Let's just jump into a simple example. You have a ball with a mass of 2 kg, and there are three forces acting on it:
We combine the left and right forces to get our overall Fx, net = -2 N. (4 to the left and 2 to the right leaves us with 2 left over pulling to the left. The number is negative because in general, we'll consider "right" to be positive and "left" to be negative.)
And since there's only one force acting in the Y direction, the Fy, net is just -1 N. (Let's say "up" is positive and "down" is negative — but only for now. We'll switch that up later. In general, you use positive and negative signs in a way that makes sense for your specific problem.)
Finally, since our ball weighs 2 kg, we can substitute our numbers into F = ma and get the following two equations:
So far, so good. Truth be told, we're really interested in the accelerations here, so we'll just rearrange:
And then I'll tell you that when you divide "Newtons" by "kilograms" you get "meters per second-squared":
So we had a situation where we know the mass of an object and the forces acting on it. We added up the forces (assigning negative signs to "left" and "down", causing those forces to subtract instead), and rearranged to solve for acceleration — and we did this for both the X and the Y directions separately. In this example, the ball is accelerating down and to the left, but it's accelerating more to the left than it is downwards.
(More advanced: sometimes you don't know the X and Y components of a force. It's possible that you only know about one force that's angled at, say, 30 degrees up from right. In that case, you can use cosine and sine to figure out the X and Y pieces of that force respectively. We'll do that in a future article.)
Gravity is one of the universal fundamental interactions, along with the electromagnetic, strong, and weak forces. Gravity causes a force to act on every single object from every other single object, but fortunately everything works out to simplify nicely if you're on the surface of a planet. On Earth, for instance, we don't even need to worry about the force that gravity causes, we can just look at the end result: every single object on Earth experiences an additional downward acceleration of 9.8 m / s2. That simple.
If our ball from above (that we already solved for) is on Earth and experiencing gravity, then we just need to modify the ay equation slightly. We'll take the downward acceleration that the force is causing and combine it with the downward acceleration that gravity causes:
ay = -0.5 m / s2 – 9.8 m / s2
That leaves us with an acceleration of
ay = -10.3 m / s2
As you can see, the downward force combined with the acceleration from gravity shoots the ball downward even faster than either gravity or the force alone could.
So, gravity is simple (if you're on a planet). All you do is modify the ay acceleration to factor in the downward pull of gravity.
In a future article we'll look at how to model gravity if you're not on a planet (perhaps you are a planet), but that doesn't come until later…
Our ball experiences gravity, but as I mentioned, we don't need to model that as a force; we just plug it directly into the acceleration result. Drag, however, is a force, and we'll have to model it.
The equation (one of the equations) for aerodynamic drag looks like this:
FD = -0.5 * CD * A * ρ * v2
It looks complicated, but when we break it down, it's pretty simple. First off, notice the bold characters. Like F = ma above, a bold variable means it's actually a vector — so right off the bat we can split this into two equations:
And then we look at each one of those terms above:
Calculus, like physics, is amazing and has a wonderful depth that I can't do justice in a blog post.
The "derivative" in calculus describes how something changes as something else is changing; often this will be called the "rate of change". When you drive a car at 30 MPH, your position is changing by 30 miles every hour. Your position changes as time changes. It can then be said that velocity is the "derivative of position with respect to time" or simply the "time derivative of position".
Then we can think about what happens when you speed up or slow down (accelerate). You might change your velocity by 5 MPH per hour (MPHPH?). In that sense, your velocity is changing with time, and you can say that acceleration is the time derivative of velocity.
So it starts with position. The derivative of position is velocity. And the derivative of velocity is acceleration. (The derivative of acceleration is called "jerk", and the derivative of jerk is called "jounce".)
Why is this relevant? Because if you know the acceleration of something (5 meters per second per second), and if you know how fast it's going when you start looking at it (let's say it's not moving at all), you can figure out where it will be at every moment in the future.
An example: your ball is accelerating at 2 m / s2 (meters per second per second). Let's say it's not moving at all when you start looking at it, and that the starting point is called x = 0;
|0 s
|2 m / s2
|0 m / s
|0 m
|1 s
|2 m / s2
|2 m / s
|0 m
|2 s
|2 m / s2
|4 m / s
|2 m
|3 s
|2 m / s2
|6 m / s
|6 m
|4 s
|2 m / s2
|8 m / s
|12 m
|5 s
|2 m / s2
|10 m / s
|20 m
|6 s
|2 m / s2
|12 m / s
|30 m
And so on. This is the approach we'll use when solving for the motion of our ball, except we'll do it not once per second but 40 times per second. All we're doing is using our knowledge of the forces to figure out the acceleration at every frame. Then we use the acceleration and current velocity to figure out the new velocity. And then we use the velocity and last position to find the current position.
Time to dive in. I won't reproduce all the code in snippets, because there's some stuff that has nothing to do with physics. You'll be able to see the full script at the bottom of the page in the JSFiddle.
var frameRate = 1/40; // Seconds var frameDelay = frameRate * 1000; // ms var loopTimer = false; var ball = { position: {x: width/2, y: 0}, velocity: {x: 10, y: 0}, mass: 0.1, //kg radius: 15, // 1px = 1cm restitution: -0.7 }; var Cd = 0.47; // Dimensionless var rho = 1.22; // kg / m^3 var A = Math.PI * ball.radius * ball.radius / (10000); var ag = 9.81;
We set up the frame rate and plug in some physics values. We also create a ball object that stores the ball's position, velocity, mass, radius, and a number called "restitution". You'll see later that this value determines how bouncy the ball is.
Notice here that we've set the ball to be moving at the start of the simulation.
The best part of programming real physics is the fact that you can look up the density of water and replace the value for rho, and the ball will actually behave as if it's in water! If you program the physics correctly, then all you have to do is change the constants and the rest follows. Want the ball to be on the moon? Just change the acceleration due to gravity. Want the ball to swim through water? Just change the density rho. Want a light, floaty beach ball? Lower the mass and increase the radius.
Please play with these values in the JSFiddle below. Change rho and the radius and the mass, and see how physics affects the simulation!
var setup = function() { canvas = document.getElementById("canvas"); ctx = canvas.getContext("2d"); canvas.onmousemove = getMousePosition; canvas.onmousedown = mouseDown; canvas.onmouseup = mouseUp; ctx.fillStyle = 'red'; ctx.strokeStyle = '#000000'; loopTimer = setInterval(loop, frameDelay); }
The setup function initializes the canvas and sets up a loop that executes every frameDelay milliseconds. We'll do all the physics and animation in the loop function.
In the loop:
// Do physics // Drag force: Fd = -1/2 * Cd * A * rho * v * v var Fx = -0.5 * Cd * A * rho * ball.velocity.x * ball.velocity.x * ball.velocity.x / Math.abs(ball.velocity.x); var Fy = -0.5 * Cd * A * rho * ball.velocity.y * ball.velocity.y * ball.velocity.y / Math.abs(ball.velocity.y); Fx = (isNaN(Fx) ? 0 : Fx); Fy = (isNaN(Fy) ? 0 : Fy); // Calculate acceleration ( F = ma ) var ax = Fx / ball.mass; var ay = ag + (Fy / ball.mass); // Integrate to get velocity ball.velocity.x += ax*frameRate; ball.velocity.y += ay*frameRate; // Integrate to get position ball.position.x += ball.velocity.x*frameRate*100; ball.position.y += ball.velocity.y*frameRate*100;
First off, we calculate the drag forces on the ball. There's a little trick I used to get the direction of the velocity. Instead of using "if" statements to see if the velocity is positive or negative, I just do:
ball.velocity.y / Math.abs(ball.velocity.y)
at the end of the drag force statements. Dividing a number by its absolute value just leaves the sign. Other than that, the drag force lines are pretty straightforward. We're just calculating the forces.
After that, we calculate acceleration. Notice that the statement for "ay" is different from "ax". Gravity only works in the Y direction, so we add that in here. Also notice that in this problem, "downwards" is positive, unlike the example at the top of the page.
After that, we update the ball velocities with the acceleration times the frame rate. The reason we multiply by the frame rate is so: the acceleration is given in "meters per second-squared". But we're calling this loop 40 times a second (not once a second), so we need to divide by 40 (or multiply by 1/40 in this case) to adjust for the frame rate.
Finally, update the ball positions in a similar fashion. In this case we're also multiplying by 100. If you look at the ball object definition way above you'll see I commented that "1px = 1cm", so this *100 is just an adjustment to make everything work out in meters.
Then we handle collisions with the walls:
// Handle collisions if (ball.position.y > height - ball.radius) { ball.velocity.y *= ball.restitution; ball.position.y = height - ball.radius; } if (ball.position.x > width - ball.radius) { ball.velocity.x *= ball.restitution; ball.position.x = width - ball.radius; } if (ball.position.x < ball.radius) { ball.velocity.x *= ball.restitution; ball.position.x = ball.radius; }
We're just checking to see if the ball has ended up past the wall in this frame. If it has, then we multiply the velocity in that direction by the restitution coefficient from above. Since that number is always negative, it'll make the ball reverse direction. If you set the restitution to -1, it'll be perfectly bouncy, meaning it'll bounce up as high as it started falling from. If you set the restitution to 0, it'll flop dead on the ground with no bounce whatsoever. And if you set it to something like -2, it'll bounce even higher than it started. Play with it!
We also modify the position of the ball to just kiss the wall -- this way the ball won't get stuck "in" the wall. Keep in mind that the ball is moving in discrete motions, and so when it collides with the wall it's actually overlapping slightly.
Finally, since we want to be able to control the ball with the mouse, we'll add some handlers (not all code shown here):
var mouseDown = function(e) { if (e.which == 1) { getMousePosition(e); mouse.isDown = true; ball.position.x = mouse.x; ball.position.y = mouse.y; } } var mouseUp = function(e) { if (e.which == 1) { mouse.isDown = false; ball.velocity.y = (ball.position.y - mouse.y) / 10; ball.velocity.x = (ball.position.x - mouse.x) / 10; } }
If you click and drag the mouse, and let go, you'll create a kind of slingshot effect. This is achieved not by applying a force to the ball (which you could do), but rather by overriding the velocity of the ball based on how far you pulled the mouse. I like this approach better because it's easier to apply than a force. If you were to use a force to move the ball with the mouse, you'd have to apply the force over a period of time. The "initial velocity" technique above just lets you un-naturally override the velocity in an instant and let physics figure everything out again.
I hope you learned something! Please fork and play with the code in the fiddle below. Click and drag the mouse to slingshot the ball.
Note that certain configurations of variables will cause the simulation to become unstable. Try setting rho = 1000 but leaving the mass at 0.1. The ball should spaz out and blink around the screen. This isn't a problem with the physics, it's just that we're not running at a high enough frame rate for the very large drag forces. To solve that problem we would have to increase the frame rate to make the simulation stable again. Or we could use a different solver (we're using Euler's method here, a first-degree ODE solver) -- but we won't talk about solvers for a few weeks.
The post Modeling Physics in Javascript: Gravity and Drag appeared first on Burak Kanber's Blog.]]>
The post Modeling Physics in Javascript: Introduction appeared first on Burak Kanber's Blog.]]>
Another post that starts with "I love":
I love physics. I really do. Once upon a time I was a real engineer (Master in Mechanical Engineering, hybrid car design, control systems, sustainable energy, etc etc etc) but decided to go back to the software world. Regardless, I still can't get physics out of my head. I read textbooks on quantum mechanics regularly. It's a sickness.
The great thing about physics is that it's not too hard. Well, maybe it is, but once you understand a handful of core concepts, you can do tons of problems. If you can figure out how a ball moves under the influence of gravity, you can also model the motion of a car's suspension. While that sounds like a big stretch, it's really not: it's all tied together by a few basic concepts.
I also enjoy Javascript. I'm not a graphics programmer, and have no knowledge of OpenGL or WebGL, but I like Javascript especially because it controls the fancy HTML5 canvas element.
And, if you can combine your rudimentary knowledge of physics with your rudimentary knowledge of Javascript, you can build really cool physics models and simulations.
With this series, I'm going to teach you how to model physics. We'll use Javascript to do the math and draw the animations to the canvas.
We'll start simple, with a bouncy ball and gravity, and we'll eventually move on to modeling full systems. It's going to be fun. While it'll start slow, I want to end up modeling things like bipedal robots within a couple dozen posts. And you'll be learning physics in the process.
Buckle up. Here's an example of a grandfather clock that actually simulates real physics for the swinging pendulum — just to whet your appetite:
(PS: the physics in the below example is a little bit fudged, because it was a code-debugging example I used for a class I used to teach; please wait for the full article on the pendulum clock before trying to follow the physics!)
The post Modeling Physics in Javascript: Introduction appeared first on Burak Kanber's Blog.]]>
The post Using Gmail and IMAP to create an incoming email system appeared first on Burak Kanber's Blog.]]>
Running your own email servers is pretty annoying. Outgoing email is a nightmare if you want to show up anywhere outside of the spam folder. Incoming email is a nightmare if you want a highly-available and reliable inbox.
Fortunately, the outbound email problem is solved by providers like SendGrid (my personal favorite). And incoming email: why not just use Gmail? I can't tell you the number of people I've interviewed with this very question, and none of them have ever suggested using IMAP to interface with Gmail to receive emails.
And my specific setup goes a step further. I don't want just grab incoming emails, I want to grab incoming emails that are intended for an infinite number of different people. I happen to be routing the emails to different dashboards, but that's not necessarily what you're doing. You may want to forward emails or do some algorithmic processing on them or something.
There are two aspects of Gmail you can leverage to use one account to handle multiple recipients. Choose which one works best for you.
Either technique will give you the desired result of being able to handle multiple destination addresses with one mailbox. Which is great, because we'll now use the PHP IMAP extension to grab those emails!
I should note here that you can always just make separate Gmail inboxes to handle your various accounts. I like the approaches above because you don't have to create a new inbox every time you get a new client, but if your client base is slow-growing or you can't use the methods above, making a separate inbox will certainly work.
The IMAP extension is stupidly simple to use, and I'm surprised I had never toyed with it before. I'm happy this project came up, because it was super fun to learn.
The one caveat is that the IMAP extension generally doesn't ship with PHP. On Linux systems you can use your package manager to install it pretty easily, and on Mac all you have to do is compile the IMAP module separately (no need to recompile all of PHP) and install it into your modules directory.
$imap = imap_open( IMAP_SERVER, IMAP_LOGIN, IMAP_PASSWORD );
Server strings are the trickiest part of the above, and they look something like this:
Check out the PHP imap_open documentation for details on the server string. It includes the server address, port, and options (the /ssl is not a path). You can also specify the default mailbox to connect to.
$emails = imap_search($imap, 'ALL', SE_UID);
The imap_search function is the best way to loop through emails in a mailbox. The function returns a simple array of email IDs. The third parameter above, SE_UID (part of a bitmask), specifies that I want the unique email ID — otherwise it'll return the regular mail ID. The distinction is this: every email in the account has a unique UID, but they also have a "mail ID" which is the same as "email # X of 1,200″ (where X is the mail ID). I feel safer using the UID, since you can store the ID value in your database and rest assured that it will always reference a single email.
The second parameter above is amazing! Values can be things like 'ALL', 'UNSEEN', 'UNANSWERED', 'UNSEEN FROM email@example.com', and all sorts of great, human-readable filters like that. Again, check out the imap_search documentation for details.
The $emails variable now holds an array of UIDs. Keep in mind that IMAP uses the plain-ol' ID by default, so if you decide you want to UIDs you need to specify that in every imap_* function call.
foreach ($emails as $uid) { $overview = imap_fetch_overview($imap, $uid, FT_UID); $headers = imap_fetchbody($imap, $uid, 0, FT_UID); $plaintext = imap_fetchbody($imap, $uid, 1, FT_UID); $html = imap_fetchbody($imap, $uid, 2, FT_UID); }
Some important things to note:
The overview function can actually take a comma-separated list of IDs for the second argument. If you give it a list, it will return the overviews for that entire list of emails. This is great if you just want to get a quick glimpse at the subjects and from fields for the whole inbox — no need to download the whole message. This is one of the core philosophies of IMAP.
Note that when you call imap_fetchbody, the message will be marked as seen (or "unread" in Gmail terminology). To avoid this, use the FT_PEEK constant in the bitmask:
$plaintext = imap_fetchbody($imap, $uid, 1, FT_UID | FT_PEEK);
Finally, $headers, $plaintext, and $html all use the imap_fetchbody function with the third parameter as either 0, 1, or 2. I don't believe that any of these are guaranteed to exist, but I'm not sure there so be safe and double check.
If your application should sort emails by "to" address, use the overview to check out the "to" field. If your application makes use of CCs, however, you'll need to look at the entire header section. The documentation says that the overview function is supposed to return multiple "to" and "cc" recipients, but my PHP 5.3.16 extension doesn't do that. It may be a bug, or it may just be a 5.4 feature — I haven't looked into it that deeply. While it's slightly annoying that the overview function isn't doing that properly, it's also not that hard to parse the headers.
I'm very glad I got to play with this, and I'm happy to say that this will be appearing in the next release of Tidal's dashboard in production. <3 IMAP.
The post Using Gmail and IMAP to create an incoming email system appeared first on Burak Kanber's Blog.]]>
The post Machine Learning: Introduction to Genetic Algorithms appeared first on Burak Kanber's Blog.]]>
I like starting my machine learning classes with genetic algorithms (which we'll abbreviate "GA" sometimes). Genetic algorithms are probably the least practical of the ML algorithms I cover, but I love starting with them because they're fascinating and they do a good job of introducing the "cost function" or "error function", and the idea of local and global optima — concepts both important and common to most other ML algorithms.
Genetic algorithms are inspired by nature and evolution, which is seriously cool to me. It's no surprise, either, that artificial neural networks ("NN") are also modeled from biology: evolution is the best general-purpose learning algorithm we've experienced, and the brain is the best general-purpose problem solver we know. These are two very important pieces of our biological existence, and also two rapidly growing fields of artificial intelligence and machine learning study. While I'm tempted to talk more about the distinction I make between the GA's "learning algorithm" and the NN's "problem solver" terminology, we'll drop the topic of NNs altogether and concentrate on GAs… for now.
One phrase I used above is profoundly important: "general-purpose". For almost any specific computational problem, you can probably find an algorithm that solves it more efficiently than a GA. But that's not the point of this exercise, and it's also not the point of GAs. You use the GA not when you have a complex problem, but when you have a complex problem of problems. Or you may use it when you have a complicated set of disparate parameters.
One application that comes to mind is bipedal robot walking. It's damn hard to make robots walk on two legs. Hand-coding a walking routine will almost certainly fail. Even if you succeed in making a robot walk, the next robot that comes off the line might have a slightly different center of balance, and that algorithm you slaved over no longer works. Instead of enduring the inevitable heartbreak, you might use a GA to "teach the robot to learn to walk" rather than simply "teaching the robot to walk".
Let's build a GA in Javascript.
Build a genetic algorithm in Javascript that reproduces the text "Hello, World!".
Naturally, everything starts with "Hello, World!" and so building a GA to reproduce that phrase is apropos. Note that this problem is highly contrived. At one point we're even going to type the phrase "Hello, World!" into the source code! Now that seems silly — if you know the desired result, why program the algorithm in the first place? The answer is simple: this is a learning exercise. The next GA exercise (which will be in PHP) will be a little less contrived, but we need to start somewhere.
The basic approach to GAs is to generate a bunch of "answer candidates" and use some sort of feedback to figure out how close the candidate is to optimal. Far-from-optimal candidates literally die and are never seen again. Close-to-optimal candidates combine with each other and maybe mutate slightly; this is an attempt to modify the candidates from time to time and see if they get closer to optimal or farther from optimal.
These "answer candidates" are called
genes chromosomes. (Note: my terminology here was incorrect. Genes are technically the individual characters of the solution candidate, while the whole thing is called a chromosome. Semantics are important!)
Chromosomes mate, produce offspring, and mutate. They either die due to survival of the fittest, or are allowed to produce offspring who may have more desirable traits and adhere to natural selection.
This may be a strange way to think about solving for "Hello, World!" but stick with it. This example isn't the only problem that can be solved with GAs!
The chromosome is a representation of a solution candidate. In our case, the chromosome itself is a string. Let's assume that all chromosomes have a length of 13 characters (the same as "Hello, World!"). Here are some possible chromosomes that could be solution candidates for our problem:
Obviously that last one is the "correct" (or globally-optimum) chromosome. But how do we measure the optimality of a chromosome?
The cost function (or error function, or fitness function as the inverse) is some sort of measure of the optimality of a chromosome. If we're calling it "fitness function" then we're shooting for higher scores, and if we're using "cost function" then we're looking for low scores.
In this case, we might define a cost function to be something like the following:
For each character in the string, figure out the difference in ASCII representation between the candidate character and the target character, and then square it so that the "cost" is always positive.
For example, if we have a capital "A" (ASCII 65) but it's supposed to be a capital "C" (ASCII 67), then our cost for that character is 4 (67 – 65 = 2, and 2^2 = 4).
Again, the reason we're using the square of the difference is so that we never end up with a negative cost. You could just use absolute value if you want, too. Please experiment with different approaches — that's how you learn!
Using that rule as a cost function, we can calculate the costs of the above 5 example chromosomes (in parentheses):
In this case, since this problem is easy and contrived, we know that we're shooting for a cost of 0 and that we can stop there. Sometimes that's not the case. Sometimes you're just looking for the lowest cost you can find, and need to figure out different ways to end the calculation. Other times you're looking for the highest "fitness score" you can find, and similarly need to figure out some other criteria to use to stop the calculation.
The cost function is a very important aspect of GAs, because if you're clever enough, you can use it to reconcile completely disparate parameters. In our case, we're just looking at letters. But what if you're building a driving directions app and need to weigh tolls vs distance vs speed vs traffic lights vs bad neighborhoods vs bridges? Those are completely disparate parameters that you can reduce into one, neat, tidy cost function for a route by applying different weights to each parameter.
Mating is a fact of life, and we use it tons in GAs. Mating is a magical moment that two chromosomes in love with each other share. The technical term for mating is "crossover", but I'll continue calling it "mating" here, because that paints a more intuitive picture.
We haven't talked about "populations" in GAs yet (we'll get to that a bit later) but for now I'll just say that when you run a GA, you don't just look at one chromosome at a time. You might have a population of 20 or 100 or 5,000 going all at once. Just like in evolution, you might be inclined to have the best and strongest chromosomes of the population mate with each other, with the hope that their offspring will be even healthier than either parent.
Mating strings, like in our "Hello, World!" example is pretty easy. You can pick two candidates (two strings; two chromosome) and pick a point in the middle of the string. This point can be dead-center if you want, or randomized if you prefer. Experiment with it! Take that middle point (called a "pivot" point), and make two new chromosomes by combining the first half of one with the second half of the other and vice versa.
Take these two strings for example:
As you can see, the offspring includes one bastard child that has the worst traits of both parents, but also an angel child that has the best traits of both.
Mating is how you get from one generation of genes to the next.
Mating alone has a problem: in-breeding. If all you do is mate your candidates to go from generation to generation, you'll get stuck near a "local optimum": an answer that's pretty good but not necessarily the "global optimum" (the best you can hope for).
(I was recently informed that the above paragraph is misleading. Some readers got the impression that the most important aspect of chromosome evolution is the mating, when in actuality a GA would achieve very little if not for the combined effects of both mating and mutation. The mating helps discover more optimal solutions from already-good solutions [many problems' solutions, like our Hello World problem, can be divided into optimal sub-solutions, like "Hello" and "world" separately], but it's the mutation that pushes the search for solutions in new directions.)
Think of the world that these genes are living in as a physical setting. It's really hilly with all sorts of weird peaks and valleys. There is one valley that's the lowest of all, but there are also tons of other little valleys — while these other valleys are lower than the land directly around them, they're still above sea-level overall. Searching for a solution is like starting a bunch of balls on the hills in random places. You let the balls go and they roll downhill. Eventually, the balls will get stuck in the valleys — but many of them will get stuck in the random mini-valleys that are stilly pretty high up the hill (the local optima). It's your job to make sure at least one of the balls ends up in the lowest point on the whole map: the global optimum. Since the balls all start in random places, it's hard to do this from the outset, and it's impossible to predict which ball will get stuck where. But what you can do is visit a bunch of the balls at random and give them a kick. Maybe the kick will help, maybe it'll hurt — but the idea here is to shake up the system a little bit to make sure things aren't getting stuck in local optima for too long.
This is called mutation. It's a completely random process by which you target an unsuspecting chromosome and blast it with just enough radiation to make one of its letters randomly change.
Here's an example to illustrate. Let's say you end up with these two chromosomes:
Again, a contrived example, but it happens. Your two chromosomes are exactly the same. That means that their children will be exactly the same as the parents, and no progress will ever be made. But if 1 in 100 chromosomes has one letter randomly mutated, it's only a matter of time before chromosome #2 above turns into "Ifllp, worlb!" — and then the evolution continues because the children will finally be different from the parents once again. Mutation pushes the evolution forward.
How and when you mutate is up to you. Again, experiment. The code I'll give you later has a very high mutation rate (50%), but that's really just for demonstration. You might make it low, like 1%. My code makes only one letter move by one ASCII code but you can have yours be more radical. Experiment, test, and learn. It's the only way.
Chromosomes are representations of candidate solutions to your problem. They consist of the representation itself (in our case, a 13-character string), a cost or fitness score and function, the ability to mate ("crossover"), and the ability to mutate.
I like thinking about these things in OOP terms. The "Chromosome" class therefore has the following properties:
We'll now look at how to have genes interact with each other in the final piece of the GA puzzle: the "Population".
The population is a group of chromosomes. The population generally remains the same size but will typically evolve to better average cost scores over time.
You get to choose your population size. I picked 20 for mine below, but you could choose 10 or 100 or 10,000 if you want. There are advantages and disadvantages, but as I've said a few times by now: experiment and learn for yourself!
The population experiences "generations". A typical generation may consist of:
Starting a population is easy. Just fill it with completely random chromosomes. In our case, the cost scores for completely random strings will be horrendous. My code starts at an average cost score of 30,000. But that's ok — that's what evolution is for. This is why we're here.
Knowing when to stop the population is a little trickier. Today's example is pretty simple: stop when you get a cost of 0. But this isn't always the case. Sometimes you don't know the minimum achievable cost. Or, if you're using fitness instead of cost, you may not know the maximum possible fitness.
In those cases you should specify a completeness criteria. This can be anything you want, but here's a starting suggestion to jump off from:
Stop the algorithm if the best score hasn't changed in 1,000 generations, and use that as your answer.
Criteria like that may mean that you never achieve the global optimum, but in many cases you don't need to achieve the global optimum. Sometimes "close enough" really is good enough.
I'll soon be writing another article on GAs (for PHP this time) with a slightly different problem, and that one will have a completeness rule similar to the above. It might be hard to swallow that "close enough is good enough" right now, but once you see the example in action hopefully you'll believe me.
Finally! I like OOP methods, but I also like rough and simple code, so I'll do this as straight-forwardly as possible though it may be a little rough around the edges.
(Note that while I changed the occurrences of the term "gene" to "chromosome" in the text above, the code below still uses the incorrect "gene" terminology. It's a semantic and pedantic difference, but where would we be without semantic pedantics?)
var Gene = function(code) { if (code) this.code = code; this.cost = 9999; }; Gene.prototype.code = ''; Gene.prototype.random = function(length) { while (length--) { this.code += String.fromCharCode(Math.floor(Math.random()*255)); } };
Simple. It's just a class that takes a string as a constructor, sets a cost, and has a helper function to create a new, random chromosome.
Gene.prototype.calcCost = function(compareTo) { var total = 0; for(i = 0; i < this.code.length; i++) { total += (this.code.charCodeAt(i) - compareTo.charCodeAt(i)) * (this.code.charCodeAt(i) - compareTo.charCodeAt(i)); } this.cost = total; };
The cost function takes the "model" string as an argument, finds the differences between ASCII codes, and squares them.
Gene.prototype.mate = function(gene) { var pivot = Math.round(this.code.length / 2) - 1; var child1 = this.code.substr(0, pivot) + gene.code.substr(pivot); var child2 = gene.code.substr(0, pivot) + this.code.substr(pivot); return [new Gene(child1), new Gene(child2)]; };
The mating function takes another chromosome as an argument, finds the center point, and returns an array of two new children.
Gene.prototype.mutate = function(chance) { if (Math.random() > chance) return; var index = Math.floor(Math.random()*this.code.length); var upOrDown = Math.random()
The mutate method takes a float as an argument — the percent chance that the chromosome will mutate. If the chromosome is to mutate we randomly decide if we're going to add or subtract one from the randomly-selected character code. I was going too fast to write a proper String.prototype.replaceAt method, so I just took an easy shortcut there.
var Population = function(goal, size) { this.members = []; this.goal = goal; this.generationNumber = 0; while (size--) { var gene = new Gene(); gene.random(this.goal.length); this.members.push(gene); } };
The Population class constructor takes the target string and population size as arguments, then fills the population with random chromosomes.
Population.prototype.sort = function() { this.members.sort(function(a, b) { return a.cost - b.cost; }); }
I define a Population.prototype.sort method as a helper function to sort the population by their cost score.
Population.prototype.generation = function() { for (var i = 0; i < this.members.length; i++) { this.members[i].calcCost(this.goal); } this.sort(); this.display(); var children = this.members[0].mate(this.members[1]); this.members.splice(this.members.length - 2, 2, children[0], children[1]); for (var i = 0; i < this.members.length; i++) { this.members[i].mutate(0.5); this.members[i].calcCost(this.goal); if (this.members[i].code == this.goal) { this.sort(); this.display(); return true; } } this.generationNumber++; var scope = this; setTimeout(function() { scope.generation(); } , 20); };
The meatiest population method is the generation method. There's no real magic here. The display() method (not shown on this page) just renders output to the page, and I set a timeout between generations so that things don't explode.
Note that in this example I'm only mating the top two chromosomes. This doesn't have to be your approach.
window.onload = function() { var population = new Population("Hello, world!", 20); population.generation(); };
That gets the ball rolling. See it in action:
It's slow — but it's not too difficult to figure out where the inefficiencies are. If you're clever enough you can certainly make it lightning fast. As always, I encourage you to fork and experiment and learn on your own.
Notice that there's nothing in the above that can't be done in any programming language. But you probably expected that, since this is "Machine Learning in All Languages", after all.
Happy learning! The next post in this series is ML in JS: k-nearest-neighbor.
There's also a Genetic Algorithms Part 2, which you should read if you want to get a little more advanced.
The post Machine Learning: Introduction to Genetic Algorithms appeared first on Burak Kanber's Blog.]]>
The post Machine Learning in Javascript: Introduction appeared first on Burak Kanber's Blog.]]>
I also happen to be a PHP and JavaScript developer. I've taught classes on both of these as well — but like any decent software engineer I have experience with Ruby, Python, Perl, and C. I just prefer PHP and JS. (Before you flame PHP, I'll just say that while it has its problems, I like it because it gets stuff done.)
Whenever I say that Tidal Labs' ML algorithms are in PHP, they look at me funny and ask me how it's possible. Simple: it's possible to write ML algorithms in just about any language. Most people just don't care to learn the fundamentals strongly enough that they can write an algorithm from scratch. Instead, they rely on Python libraries to do the work for them, and end up not truly grasping what's happening inside the black box. Other people only know ML academically, using Octave or Matlab.
Through this series of articles, I'll teach you the fundamental machine learning algorithms using Javascript — not Python or Octave — as the example language. Originally I intended to write these articles in a variety of languages (PHP, JS, Perl, C, Ruby), but decided to stick with Javascript for the following reasons:
While I'll be writing these articles with Javascript in mind, please re-write the examples in your language of choice as homework! Practice is how you get better, and writing the same algorithm several times in different languages really helps you understand the paradigms better.
It's possible to get excellent performance out of ML algorithms in languages like PHP and Javascript. I advocate writing ML algorithms in other languages because the practice of writing ML algorithms from scratch helps you learn them fundamentally, and it also helps you unify your backend by not requiring a Python script to do processing in the middle of a PHP application. You can do it in PHP, and cut out the (mental and computational) overhead of using another language.
Keep in mind that most of the algorithms we'll look at can be solved both with and without matrix math. We'll use iterative or functional approaches here, but most of these algorithms can be done with linear algebra as well. There's more than one way to skin a cat! I encourage you to also go and learn (or figure out) the linear algebra approaches, but since that's not my strong suit I'll use other approaches.
Here are some of the algorithms I intend to cover. I'll update this list with links to the relevant articles as they're published:
Happy learning!
The post Machine Learning in Javascript: Introduction appeared first on Burak Kanber's Blog.]]>