O Simples e Elegante Algoritmo Que Torna o Google Maps Possível


“Algoritmos são uma ciência baseada em engenhosidade. Uma manifestação natural do raciocínio lógico – indução matemática, em especial – um bom algoritmo é como um retrato passageiro e condenatório da alma de um problema. Uma selva de propriedades e relações torna-se uma simples relação de recorrência, um passo recursivo de linha única produzindo caos e complexidade sem limites. E para ver através desta complexidade, é necessário engenhosidade.

Foi o pioneiro da programação Edsger W. Dijkstra quem realmente sacou isso, e o algoritmo que leva seu nome segue como uma das coisas mais engenhosas na informática. Um defensor ferrenho da simplicidade e elegância na matemática, ele meio que acreditava que todo problema complicado tinha uma parte acessível, uma entrada, e a matemática era uma ferramenta a ser usada para encontrá-la e explorá-la…”


Why Racket? Why Lisp?


, ,

“In prac­ti­cal pro­gram­ming projects, Lisps are rare, and Racket es­pe­cially so. Thus, be­fore I em­barked on my Lisp ad­ven­ture, I wanted to un­der­stand the costs & ben­e­fits of us­ing a Lisp. Why do Lisps have such a great rep­u­ta­tion, but so few users? Was I see­ing some­thing every­one else missed? Or did they know some­thing I didn’t? To find out, I read what­ever I could find about Lisps, in­clud­ing Paul Gra­ham’s Hack­ers & Painters and Pe­ter Seibel’s Prac­ti­cal Com­mon Lisp. (OK, parts. It’s a big book.)

What I found was plenty of Lisp flat­tery from ex­pert Lisp pro­gram­mers. (Also plenty of Lisp kvetch­ery from its de­trac­tors.) What I didn’t find were sim­ple, per­sua­sive ar­gu­ments in its fa­vor. So here’s why Racket was the right tool for this project, and what I see as the prac­ti­cal virtues of Lisps in general...”


Deep Learning, NLP, and Representations



“In the last few years, deep neural networks have dominated pattern recognition. They blew the previous state of the art out of the water for many computer vision tasks. Voice recognition is also moving that way.

But despite the results, we have to wonder… why do they work so well?

This post reviews some extremely remarkable results in applying deep neural networks to natural language processing (NLP). In doing so, I hope to make accessible one promising answer as to why deep neural networks work. I think it’s a very elegant perspective…”


Ideal Hash Trees



“Hash Trees with nearly ideal characteristics are described. These Hash Trees require no initial root hash table yet are faster and use significantly less space than chained or double hash trees. Insert, search and delete times are small and constant, independent of key set size, operations are O(1). Small worst-case times for insert, search and removal operations can be guaranteed and misses cost less than successful searches. Array Mapped Tries(AMT), first described in Fast and Space Efficient Trie Searches, Bagwell [2000], form the underlying data structure. The concept is then applied to external disk or distributed storage to obtain an algorithm that achieves single access searches, close to single access inserts and greater than 80 percent disk block load factors. Comparisons are made with Linear Hashing, Litwin, Neimat, and Schneider [1993] and B-Trees, R.Bayer and E.M.McCreight [1972]. In addition two further applications of AMTs are briefly described, namely, Class/Selector dispatch tables and IP Routing tables. Each of the algorithms has a performance and space usage that is comparable to contemporary implementations but simpler…”


How to write Lua modules in a post-module() world


“Our beloved function module() is really going away. As of Lua 5.2 it’s only available with compatibility flags on, and the writing’s on the wall: it is going away for good in Lua 5.3. So, in a new Lua project I wrote this past semester, I decided to write it without using module(), while making sure my code runs on both Lua 5.1 and 5.2 (as a side result, I started the compat52 project, which allows you to write code in a well-behaved Lua 5.2 style and make it run on both 5.1 and 5.2)…”


Machine Learning: Full-Text Search in Javascript (Part 1: Relevance Scoring)


, ,

“Full-text search, unlike most of the topics in this machine learning series, is a problem that most web developers have encountered at some point in their daily work. A client asks you to put a search field somewhere, and you write some SQL along the lines of 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…”


Deep Learning vs Machine Learning vs Pattern Recognition



” Lets take a close look at three related terms (Deep Learning vs Machine Learning vs Pattern Recognition), and see how they relate to some of the hottest tech-themes in 2015 (namely Robotics and Artificial Intelligence). In our short journey through jargon, you should acquire a better understanding of how computer vision fits in, as well as gain an intuitive feel for how the machine learning zeitgeist has slowly evolved over time…”



Get every new post delivered to your Inbox.

Join 685 other followers