tag:blogger.com,1999:blog-175983722024-03-13T02:54:46.199-07:00aicoderMusings about artificial intelligence, search engines, machine learning, computational advertising, intellectual property law, social media & widgets, and good beer.Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.comBlogger88125tag:blogger.com,1999:blog-17598372.post-62141456076235070452013-11-21T20:59:00.000-08:002013-11-21T20:59:01.929-08:00Break.com Case Study on ad serving.<br />
Guillaume Roels of the Anderson UCLA created a 2008 case study on ad serving used in his MBA courses.<br />
<br />
<a href="http://www.anderson.ucla.edu/documents/areas/fac/dotm/bio/pdf_GR07.pdf">pdf_GR07.pdf</a><br />
<br />
The case studies a 90 day period in the life of an adserver matching supply and demand. There are three associated data elements:<br />
<br />
<ul>
<li>Traffic data for the four inventory zones. This gives expected "supply" on a daily basis in the form of ad unit requests (impressions) per zone per day on average.</li>
<li>A set of booked orders with flight dates, budget and impression allocation limits per zone.</li>
<li>A set of proposed orders with the same data elements as orders.</li>
</ul>
<div>
For convenience I have put the data from the case study in an excel file as well as CSV files.</div>
<div>
<br /></div>
<div>
<a href="https://github.com/nealrichter/data/blob/master/break_data.xlsx?raw=true">break_data.xlsx</a></div>
<div>
<a href="https://raw.github.com/nealrichter/data/master/booked.csv">booked.csv</a></div>
<div>
<a href="https://raw.github.com/nealrichter/data/master/proposals.csv">proposals.csv</a></div>
<div>
<a href="https://raw.github.com/nealrichter/data/master/traffic.csv">traffic.csv</a></div>
<div>
<br /></div>
<div>
There are many interesting questions to ask with the case:</div>
<div>
<ol>
<li>How much daily or weekly surplus/unsold inventory is available per zone?</li>
<li>How many of the booked orders will be completed at a given level of supply?</li>
<li>How much total revenue results from fully completed orders?</li>
<li>How much total revenue results if partial credit is given for incomplete orders?</li>
<li>How many of the proposals should be accepted such that they will complete?</li>
<li>If the orders and proposals were treated equally which of the total set would complete?</li>
<li>How much revenue results given either completed and/or partially complete orders?</li>
<li>(advanced) Is there an optimal serving schedule (other than price order) that would result in more total revenue or more completed orders? </li>
</ol>
<div>
While the MBA student might approach this with a spreadsheet analysis, writing code is likely a better approach. When implementing the simulation in code one has to make a few assumptions:</div>
</div>
<div>
<ul>
<li>ASAP pacing of orders versus even pacing of volume per day across the flight dates.</li>
<li>Which traffic level to use per day (low/baseline/high).</li>
<li>The mechanism to decide the priority of orders to be served in a given day/zone.</li>
</ul>
<div>
This problem relates to both "matchmaking" and "mechanism design" in economics. It is also a simple example of the problems one might solve in software in "computational advertising". See below for a course with lecture slides touring the discipline.</div>
<div>
<br /></div>
<div>
<a href="http://www.stanford.edu/class/msande239/">Stanford MS&E 239: Introduction to Computational Advertising</a></div>
</div>
<div>
<br /></div>
Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-84391241351611970922012-12-13T09:47:00.001-08:002012-12-13T09:47:29.091-08:00Von Neumann on Empirics vs Hayek on Abstraction<div class='posterous_autopost'>Recently <a href="http://sciencehouse.wordpress.com/2012/12/11/von-neumanns-response/">Carson Chow</a> posted a short quote on the musings of Von Neumann on straying into pure mathematics when an idea originated in an empirical context. [Hat tip Daniel Lemarie for retweeting it around.]<p /><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204,204,204); border-left-style: solid; padding-left: 1ex;"><span style="color: rgb(119,119,119); font-family: Lucida Grande,Verdana,Arial,sans-serif; font-size: 13px; line-height: 16.78333282470703px; text-align: justify;">“[M]athematical ideas originate in empirics, although the genealogy is sometimes long and obscure. But, once they are so conceived, the subject begins to live a peculiar life of its own and is better compared to a creative one, governed by almost entirely aesthetic considerations, than to anything else, and, in particular, to an empirical science. There is, however, a further point which, I believe, needs stressing. As a mathematical discipline travels far from its empirical source, or still more, if it is a second and third generation only indirectly inspired by ideas coming from ‘reality’, it is beset with very grave dangers. It becomes more and more purely aestheticising, more and more purely l’art pour l’art. This need not be bad, if the field is surrounded by correlated subjects, which still have closer empirical connections, or if the discipline is under the influence of men with an exceptionally well-developed taste. But there is a grave danger that the subject will develop along the line of least resistance, that the stream, so far from its source, will separate into a multitude of insignificant branches, and that the discipline will become a disorganised mass of details and complexities. In other words, at a great distance from its empirical source, or after much ‘abstract’ inbreeding, a mathematical subject is in danger of degeneration.”</span></blockquote> <p /><div>The quote was unsourced in the post. It originally appeared in J.V.M.'s 1947 essay <i>The Mathematician</i> which is republished here:<br /><a href="http://www-history.mcs.st-and.ac.uk/Extras/Von_Neumann_Part_1.html">Part 1</a> and <a href="http://www-history.mcs.st-and.ac.uk/Extras/Von_Neumann_Part_2.html">Part 2</a></div> <p /><div>Recently I was reading Emanuel Derman's book Models.Behaving.Badly.: Why Confusing Illusion with Reality Can Lead to Disaster, on Wall Street and in Life</div><h3 class="r" style="font-size: medium; font-weight: normal; padding: 0px; margin: 0px; overflow: hidden; color: rgb(34,34,34); font-family: arial,sans-serif; background-color: rgb(255,255,255);"> <br /></h3><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204,204,204); border-left-style: solid; padding-left: 1ex;"><span style="background-color: rgb(255,255,255);"><span style="line-height: 14.545454025268555px;">Friedrich Hayek, the Austrian economist who received the 1947 Nobel Memorial Prize in Economics, pointed out that in the physical sciences we know the macroscopic through concrete experience and proceed from to the microscopic by abstraction. [...] In economics, </span></span><em style="font-style: normal; font-family: arial,sans-serif; line-height: 14.545454025268555px; background-color: rgb(255,255,255);">Hayek</em><span style="color: rgb(34,34,34); font-family: arial,sans-serif; line-height: 14.545454025268555px; background-color: rgb(255,255,255);"> argued, the </span><em style="font-style: normal; font-family: arial,sans-serif; line-height: 14.545454025268555px; background-color: rgb(255,255,255);">order of abstraction</em><span style="color: rgb(34,34,34); font-family: arial,sans-serif; line-height: 14.545454025268555px; background-color: rgb(255,255,255);"> should be </span><em style="font-style: normal; font-family: arial,sans-serif; line-height: 14.545454025268555px; background-color: rgb(255,255,255);">reversed</em><span style="color: rgb(34,34,34); font-family: arial,sans-serif; line-height: 14.545454025268555px; background-color: rgb(255,255,255);">: we know the individual agents and players from concrete personal experience, and the macroscopic "economy" is the abstraction. If the correct way to proceed is from the </span><span style="color: rgb(34,34,34); font-family: arial,sans-serif; line-height: 14.545454025268555px; background-color: rgb(255,255,255);">concrete to </span><em style="font-style: normal; font-family: arial,sans-serif; line-height: 14.545454025268555px; background-color: rgb(255,255,255);">abstract</em><span style="color: rgb(34,34,34); font-family: arial,sans-serif; line-height: 14.545454025268555px; background-color: rgb(255,255,255);">, he argued, in economics we should </span><em style="font-style: normal; font-family: arial,sans-serif; line-height: 14.545454025268555px; background-color: rgb(255,255,255);">begin with agents and proceed to economies and markets rather than vice versa.</em></blockquote> <p /><div>These are highly contrasting views! </div><p /><div>Hayek argued that the market economy was not designed, rather emerged from the fairly simple actions of actors within the economy (negotiating on price etc). Hayek is essentially saying that we should be able to reproduce the complexity of a given economy if only we can capture an accurate description of all of the 'rules' the actors are obeying.</div> <p /><div>Looking back on my own intellectual development I was first drawn to these emergent ideas within the 'bottom-up' branch of Artificial Intelligence. It was fascinating to set up a simple rule in cellular automata and watch it generate amazing complexity. Similarly the basic Darwinian model of evolution can be duplicated in a very short bit of code that given an objective function can solve problems indirectly via a massive number of randomized trials directed via the function. </div> <p /><div>Lately I'm a 'data scientist' which means that I'm attempting to extract models from data. Common methods attempt to wash out enough complexity in the data to derive a model that is inspect-able and understandable by a person. This is fundamentally grounded in empirics as the extracted model is tested for accurate prediction against other data. The inspected models are used mostly for 'story telling', helping users of the system to understand what is being learned from the data.. yet we leave specific predictions exclusively to the algorithms.</div> <p /><div>Of course one can't resolve these abstract differences in a blog post, that's a tall order. </div><p /><div>I would however assert that every learning algorithm should have two fundamentals. </div> <div><ol><li>It accurately predicts outcomes given input data</li><li>It emits a model that is inspectable and can inform the building of better 'toy models' of the system under study. </li></ol></div><div>No one disputes the first, yet many seem all to happy to ignore the second and are OK with building increasingly powerful black-boxes with 'big data' machinery.</div> <p style="font-size: 10px;"> <a href="http://posterous.com">Posted via email</a> from <a href="http://nealrichter.posterous.com/von-neumann-on-empirics-vs-hayek-on-abstracti">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-52842342279846409202012-01-07T09:13:00.001-08:002012-01-07T09:28:36.040-08:00Software pattern for proportional control of QPS in a webservice<div class="posterous_autopost"><h3 style="padding-left: 0px; padding-right: 0px; margin-right: 0px; padding-top: 0px; text-align: left; font-size: 15pt; margin-left: 0px; margin-bottom: 4px; font-family: Helvetica,Arial,sans-serif; margin-top: 28px; padding-bottom: 0px;"> Problem Statement</h3><p style="padding-right: 0px; padding-left: 0px; padding-top: 0px; text-align: left; margin-bottom: 10px; padding-bottom: 0px; line-height: 17px; margin-right: 0px; font-size: 13px; margin-left: 0px; font-family: Helvetica,Arial,sans-serif; margin-top: 10px;"> Imagine you are writing a webservice that must call a back-end service, such as a data store. Let's assume (with out loss of generality) that the data store (and your hardware supporting it) has some limit in QPS that it can handle. We'd like the client system (your web service) to impose a limit on the QPS to the back-end service. Also assume that this is a distributed webservice, lots of worker threads on lots of different machines.</p> <h3 style="padding-left: 0px; padding-right: 0px; margin-right: 0px; padding-top: 0px; text-align: left; font-size: 15pt; margin-left: 0px; margin-bottom: 4px; font-family: Helvetica,Arial,sans-serif; margin-top: 28px; padding-bottom: 0px;"> <a name="133c4f9fd80a0777_DesignPatternforaQPSController-Requirements"></a>Requirements</h3><ol style="line-height: 17px; text-align: left; font-size: 13px; font-family: Helvetica,Arial,sans-serif;"> <li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;">Given a goal in QPS manage the maximum outgoing requests per second to that goal.</li> <li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"><i>Be fast.</i> Maintain a fast controller settling time when the goal or queries change.</li> <li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"><i>Be adaptive.</i> Respond to swings of incomming requests that need to be queried against the service.</li> <li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"><i>Be distributed.</i> Locally active against global numbers without knowing the number of workers.</li> <li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"><i>Be robust.</i> Handle additions and subtractions of worker/clients to the system without coordination. Minimize overshoot.</li> </ol><p></p><div style="text-align: left;"><img src="https://wiki.rubiconproject.com/download/attachments/9654871/feedback_controller.jpg?version=1&modificationDate=1321489117000" border="1" style="font-family: Helvetica, Arial, sans-serif; font-size: 13px; line-height: 17px; background-color: rgb(255, 255, 255);" width="500" /></div> <div style="text-align: left;"> <p style="padding-left: 0px; padding-right: 0px; padding-top: 0px; margin-right: 0px; margin-left: 0px; margin-bottom: 10px; margin-top: 10px; padding-bottom: 0px;"></p><h3 style="font-family: Helvetica,Arial,sans-serif; line-height: normal; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 15pt; margin-top: 28px; margin-right: 0px; margin-bottom: 4px; margin-left: 0px;"> Design</h3><div><span style="line-height: 17px;">Assume that querying this backend service, while valuable and mostly needed, is optional under duress. It's far more important for your front-end service to be responsive and return some error or 'No Content' than hang on a busted back-end. As result we'll use a sampling rate 'r' to denote the % of time that the web service should query the back-end. Under normal conditions this rate is 1 (100%). Also assume that the goal in QPS to the back-end is set in some configuration area in your system. Under duress the rate r will be adaptively tuned to obey the QPS goal. Also assume you have smartly implemented some monitoring system like Ganglia/Nagios/Cacti and are emitting events to it when you call the back-end service.</span></div> <p></p><p style="padding-left: 0px; padding-right: 0px; padding-top: 0px; margin-right: 0px; line-height: 17px; font-size: 13px; margin-left: 0px; margin-bottom: 10px; font-family: Helvetica,Arial,sans-serif; margin-top: 10px; padding-bottom: 0px;"> <b>Inputs</b></p><ul style="line-height: 17px; font-size: 13px; font-family: Helvetica,Arial,sans-serif;"><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> G = Goal QPS</li><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;">M = Current measured QPS (from Ganglia).</li> <li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;">r = Current sampling rate [0,1]</li> </ul><p style="padding-left: 0px; padding-right: 0px; padding-top: 0px; margin-right: 0px; line-height: 17px; font-size: 13px; margin-left: 0px; margin-bottom: 10px; font-family: Helvetica,Arial,sans-serif; margin-top: 10px; padding-bottom: 0px;"> <b>Outputs</b></p><ul style="line-height: 17px; font-size: 13px; font-family: Helvetica,Arial,sans-serif;"><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> r_new = A sampling rate [0,1]</li></ul><p style="padding-left: 0px; padding-right: 0px; padding-top: 0px; margin-right: 0px; line-height: 17px; font-size: 13px; margin-left: 0px; margin-bottom: 10px; font-family: Helvetica,Arial,sans-serif; margin-top: 10px; padding-bottom: 0px;"> <b>Adaptive Mechanism</b></p><ul style="line-height: 17px; font-size: 13px; font-family: Helvetica,Arial,sans-serif;"><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> r_new = r * (G/M)</li><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> r_new = MAX(0,MIN(1,r_new)) //clamp r_new between [0,1]</li></ul><div><p style="padding-left: 0px; padding-right: 0px; padding-top: 0px; margin-right: 0px; line-height: 17px; font-size: 13px; margin-left: 0px; margin-bottom: 10px; font-family: Helvetica,Arial,sans-serif; margin-top: 10px; padding-bottom: 0px;"> <b>Benefits</b></p><ul style="line-height: 17px; font-size: 13px; font-family: Helvetica,Arial,sans-serif;"><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> Needs only global G and M as inputs.</li><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> No-coordination needed between workers/servers other than the globally observed M.</li><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> Adaptively moves the per-worker sampling rate independent of all other worker's rates. </li><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> Workers can have different incoming QPS rates from a load balancer, the controller will adapt.</li></ul><p style="padding-left: 0px; padding-right: 0px; padding-top: 0px; margin-right: 0px; line-height: 17px; font-size: 13px; margin-left: 0px; margin-bottom: 10px; font-family: Helvetica,Arial,sans-serif; margin-top: 10px; padding-bottom: 0px;"> <b>Failure Modes</b></p><ul style="line-height: 17px; font-size: 13px; font-family: Helvetica,Arial,sans-serif;"><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> If the sensor for M fails to be updated then the controller is blind</li><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> If the Goal is set or re-set to zero, then the controller will stop traffic</li><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> <em>Both of these can be addressed easily.</em></li></ul><div><b style="font-family: Helvetica,Arial,sans-serif; font-size: 13px; line-height: 17px; background-color: rgb(255,255,255);">Desired Response</b></div></div><div><ul style="font-size: 13px; line-height: 17px; font-family: Helvetica,Arial,sans-serif; background-color: rgb(255,255,255);"> <li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;">The overshoot/undershoot is called 'ringing'</li> <li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;">The time to approach the goal is called the 'settling time'</li> </ul><p style="font-size: 13px; line-height: 17px; margin-top: 10px; margin-right: 0px; margin-bottom: 10px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-family: Helvetica,Arial,sans-serif; background-color: rgb(255,255,255);"> <span class="image-wrap"><img src="https://wiki.rubiconproject.com/download/attachments/9654871/Adaptive_Response.png?version=1&modificationDate=1321548383000" border="1" /></span></p><h3 style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 15pt; margin-top: 28px; margin-right: 0px; margin-bottom: 4px; margin-left: 0px; font-family: Helvetica,Arial,sans-serif; background-color: rgb(255,255,255);"> <a name="DesignPatternforaQPSController-ImplementationNotes"></a>Implementation Notes</h3><ul style="background-color: rgb(255, 255, 255); "><li style="font-family: Helvetica, Arial, sans-serif; font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; "> Emit a ganglia/graphite/XXX counter for both requests sent and skipped</li><li style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; "><span class="Apple-style-span"><span class="Apple-style-span" style="line-height: 13pt;">Use a smoothed average of the measured QPS to </span><span class="Apple-style-span" style="line-height: 17px;">smooth out</span><span class="Apple-style-span" style="line-height: 13pt;"> controller jitter.</span></span></li><li style="font-family: Helvetica, Arial, sans-serif; font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; ">(Optional) Each worker should do a bit of randomization of when it performs its sampling-rate-update to smooth out any startup/restart ringing.</li></ul><h3 style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-size: 15pt; margin-top: 28px; margin-right: 0px; margin-bottom: 4px; margin-left: 0px; font-family: Helvetica,Arial,sans-serif; background-color: rgb(255,255,255);"> <a name="DesignPatternforaQPSController-Invertability"></a>Invertability</h3><p style="font-size: 13px; line-height: 17px; margin-top: 10px; margin-right: 0px; margin-bottom: 10px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; font-family: Helvetica,Arial,sans-serif; background-color: rgb(255,255,255);"> This design could be inverted for a server implementation. If your webservice has a set of APIs that are heavy to execute, then this controller could be used to control the incomming QPS that are delegated to the heavy work.</p> <ol style="font-size: 13px; line-height: 17px; font-family: Helvetica,Arial,sans-serif; background-color: rgb(255,255,255);"><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"> Receive request</li><li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;">Submit to sampling rate</li> <li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;">If Yes then delegate the request to the executor</li> <li style="font-size: 10pt; line-height: 13pt; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;">If No then respond to the client with 'HTTP 204 No Content' or equivalent empty reponse.</li></ol></div></div> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-76063945567950922352011-12-27T09:10:00.001-08:002011-12-27T09:10:44.040-08:00Standford's Introduction to Computational Advertising course<div class='posterous_autopost'><div><div><b style="font-size: 13px; font-family: verdana,arial,helvetica,sans-serif; background-color: rgb(255,255,255);"><a href="http://research.yahoo.com/Andrei_Broder">Andrei Broder</a> and </b><a href="http://research.yahoo.com/Vanja_Josifovski" style="font-size: 13px; font-family: verdana,arial,helvetica,sans-serif; background-color: rgb(255,255,255);"><b>Vanja Josifovski</b></a><span style="font-size: 13px; font-family: verdana,arial,helvetica,sans-serif; background-color: rgb(255,255,255);">, of Yahoo! Research, have wrapped up their Stanford course again this fall. As always the lecture slides are a great intro to the area.</span></div> </div><p /><div><a href="http://www.stanford.edu/class/msande239/">MS&E 239: Introduction to Computational Advertising</a><br /> <div><p /><div><div><span style="font-size: 14px;">Computational advertising is an emerging new scientific sub-discipline, at the intersection of large scale search and text analysis, information retrieval, statistical modeling, machine learning, classification, optimization, and microeconomics. The central problem of computational advertising is to find the "best match" between a given user in a given context and a suitable advertisement. The context could be a user entering a query in a search engine ("sponsored search"), a user reading a web page ("content match" and "display ads"), a user watching a movie on a portable device, and so on. The information about the user can vary from scarily detailed to practically nil. The number of potential advertisements might be in the billions. Thus, depending on the definition of "best match" this problem leads to a variety of massive optimization and search problems, with complicated constraints, and challenging data representation and access problems. The solution to these problems provides the scientific and technical foundations for the $20 billion online advertising industry.</span></div> <p /><div><span style="font-size: 14px;">This course aims to provide a good introduction to the main algorithmic issues and solutions in computational advertising, as currently applied to building platforms for various online advertising formats. At the same time we intend to briefly survey the economics and marketplace aspects of the industry, as well as some of the research frontiers. The intended audience are students interested in the practical and theoretical aspects of web advertising.</span></div> </div></div></div> <p style="font-size: 10px;"> <a href="http://posterous.com">Posted via email</a> from <a href="http://nealrichter.posterous.com/standfords-introduction-to-computational-adve">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-30917122825760908542011-12-27T09:04:00.001-08:002011-12-27T09:04:36.142-08:00Summer Program on Computational Advertising<div class='posterous_autopost'><div><a href="http://research.yahoo.com/Deepak_K_Agarwal">Deepak Agarwal of Yahoo Research</a> is organizing a summer program on Computational Advertising. It appears to be geared for grad students.</div><p /><a href="http://www.samsi.info/programs/summer-program-august-6-17-2012-computational-advertising">http://www.samsi.info/programs/summer-program-august-6-17-2012-computational-advertising</a><br /> <p /><div><span style="color: rgb(51,51,51); font-family: Arial,sans-serif; font-size: 13px; line-height: 18px; background-color: rgb(255,255,255);">This two-week program will run from August 6 to August 17, 2012. The first week will be at the </span><a href="http://www.radisson.com/samsi" target="_blank" style="color: rgb(0,51,102); font-family: Arial,sans-serif; font-size: 13px; line-height: 18px; background-color: rgb(255,255,255);">Radisson RTP</a><span style="color: rgb(51,51,51); font-family: Arial,sans-serif; font-size: 13px; line-height: 18px; background-color: rgb(255,255,255);"> in the Research Triangle Park, NC. The location is in close proximity to SAMSI. The first three days will be spent on technical presentations by leading researchers and industry experts, to bring everyone up to speed on the currently used methodology. On the fourth day, the participants will self-organize into working groups, each of which will address one of the key problem areas (it is permitted that people join more than one group, and the organizers will try to arrange the working group schedules to faciliate that). The second week will be spent at SAMSI headquarters in Research Triangle Park.</span></div> <p style="font-size: 10px;"> <a href="http://posterous.com">Posted via email</a> from <a href="http://nealrichter.posterous.com/summer-program-on-computational-advertising">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-16145801156581493922011-11-15T08:24:00.001-08:002011-11-15T08:35:18.033-08:00What Software Engineers should know about Control Theory<div class="posterous_autopost">Over the years I've noticed an interesting lack of specific domain knowledge among CS and software people. Other than the few co-workers that majored in Electrical Engineering, almost no one has heard of the field of 'Control Theory'.<p></p><div>From <a href="http://en.wikipedia.org/wiki/Control_theory" target="_blank">Wikipedia</a></div><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"> <span style="font-family: sans-serif; font-size: 13px; line-height: 19px;"><b>Control theory</b> is an interdisciplinary branch of <a href="http://wiki/Engineering" title="Engineering" target="_blank" style="text-decoration: none; color: rgb(6, 69, 173); background-color: initial;">engineering</a> and <a href="http://wiki/Mathematics" title="Mathematics" target="_blank" style="text-decoration: none; color: rgb(6, 69, 173); background-color: initial;">mathematics</a>, that deals with the behavior of <a href="http://wiki/Dynamical_system" title="Dynamical system" target="_blank" style="text-decoration: none; color: rgb(11, 0, 128); background-color: initial;">dynamical systems</a>. The desired output of a system is called the <i>reference</i>. When one or more output variables of a system need to follow a certain reference over time, a <a href="http://wiki/Controller_(control_theory)" title="Controller (control theory)" target="_blank" style="text-decoration: none; color: rgb(6, 69, 173); background-color: initial;">controller</a> manipulates the inputs to a system to obtain the desired effect on the output of the system.</span></blockquote> <div> </div><div> <div style="font-family: sans-serif; font-size: 12px; background-color: rgb(249, 249, 249); line-height: 19px;"><div style="border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-color: initial; text-align: left; line-height: 1.4em; padding-top: 3px !important; padding-right: 3px !important; padding-bottom: 3px !important; padding-left: 3px !important; font-size: 11px;"> <div style="float: right; border-top-style: none !important; border-right-style: none !important; border-bottom-style: none !important; border-left-style: none !important; border-color: initial !important; background-color: initial !important;"> <a href="http://wiki/File:Feedback_loop_with_descriptions.svg" title="Enlarge" target="_blank" style="text-decoration: none; color: rgb(6, 69, 173); background-color: initial !important; display: block; border-top-style: none !important; border-right-style: none !important; border-bottom-style: none !important; border-left-style: none !important; border-color: initial !important;"><img src="http://bits.wikimedia.org/skins-1.5/common/images/magnify-clip.png" height="11" alt="" style="border-top-style: none !important; border-right-style: none !important; border-bottom-style: none !important; border-left-style: none !important; border-color: initial; vertical-align: middle; display: block; border-color: initial !important; background-color: initial !important;" width="15" /></a></div> </div></div></div><div>Let's imagine that you write internet web services for a living. Some Rest or SOAP APIs that take an input and give an output.</div><p></p><div>Your boss walks up to you one day and that asks for a system that does the following:</div> <div><ul><li>Create a webservice that calls another (or three) for data/inputs, then does X with them.</li><li>Meters the usage of the other web services.</li><li>Your webservice must respond within Y milliseconds with good output or a NULL output.</li><li>Support high concurrency, ie not use too many servers.</li></ul></div> <p></p><div>The problem is that these other third-party webservices are not your own. What is their response time? Will they give bad data? How should your webservice react to failures of the others?</div> <p></p><div>Does this sound familiar? It should to many. This is the replicated-and-shared-connector problem (MySQL, memcached), the partitioned-services problem (federated search, and large scale search engines) and the API-as-a-service problem (<a href="http://www.mashery.com/" target="_blank">Mashery</a>, etc).</div> <p></p><div>There are two basic types of controls relevant here:</div><div><ul><li>Open Loop, Feed-forward: Requires good model of system inputs and response of the system.</li></ul><div><div class="p_embed p_image_embed"> <img alt="Feedforward" height="77" src="http://getfile3.posterous.com/getfile/files.posterous.com/nealrichter/3Itl7WJfodA5QyGwJuvKCw2nMkKewpvpFxsa8CvfNjXvxVYrfgDEZ0d0cQHE/feedforward.png" width="450" /> </div><br /></div><ul><li>Closed Loop, Feed-back</li></ul><div><a href="http://wiki/File:Feedback_loop_with_descriptions.svg" target="_blank" style="text-decoration: underline; color: rgb(6, 69, 173); background-color: initial;"><img src="http://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Feedback_loop_with_descriptions.svg/400px-Feedback_loop_with_descriptions.svg.png" height="101" alt="" style="border-top-style: solid; border-right-style: solid; border-bottom-style: solid; border-left-style: solid; border-color: initial; vertical-align: middle; border-top-width: 1px; border-right-width: 1px; border-bottom-width: 1px; border-left-width: 1px; border-top-color: rgb(204, 204, 204); border-right-color: rgb(204, 204, 204); border-bottom-color: rgb(204, 204, 204); border-left-color: rgb(204, 204, 204); background-color: rgb(255, 255, 255);" width="400" /></a></div> </div><p></p><div>Types of adaptive control are as follows:</div><div><ul><li>Linear Feedback</li><li>Stability Analysis</li><li>Frequency response</li><li>response time</li> </ul><div>Adaptive Schemes</div></div><div><ul><li>Gain Scheduling</li><li>Model Reference Adaptive Systems</li><li>Self-tuning regulators</li><li>Dual Control</li></ul></div> <p></p><div>Here's one <a href="http://www.igi.tugraz.at/helmut/Presentations/Hauser_2004_AdaptiveControl.pdf">survey deck from a lecture</a>. Unfortunately for software engineers, most of the presentations of the above are in linear system form rather than an algorithmic form.</div> <p></p><div>Dr. Joe L Hellerstein of Google and co-workers taught a course at U of Washington in 2008 that was more software focused. He's also written a textbook on it and a few papers.</div><div><ul><li><a href="http://research.microsoft.com/en-us/um/people/liuj/cse590k2008winter/" target="_blank">http://research.microsoft.com/en-us/um/people/liuj/cse590k2008winter/</a></li> <li>Joseph L Hellerstein et al "Feedback control of computing systems" 2004 Wiley <a href="http://books.google.com/books?id=J9aMWtoELWYC&printsec=frontcover&dq=Feedback-Control-Computing-Systems-Hellerstein&source=bl&ots=JwL91gojs8&sig=Mq3e1BFwVP0mDmfw5n1om7KuUnU&hl=en&ei=j_crTc7VJ4KosQPJg4GGBg&sa=X&oi=book_result&ct=result&resnum=2&ved=0CB4Q6AEwAQ#v=onepage&q&f=false" target="_blank">Google Books</a> <a href="http://www.amazon.com/Feedback-Control-Computing-Systems-Hellerstein/dp/047126637X" target="_blank">Amazon</a></li> <li><a href="http://www.research.ibm.com/PM/RC23159.pdf" target="_blank">Hellerstein 2003 IBM Tech Report "Challenges in Control Engineering of Computing Systems"</a></li><li><a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5374029" target="_blank">Hellerstein et al "Research challenges in control engineering of computing systems" Volume: 6 Issue: 4, 2010 IEEE Trans on Network and Service Management</a></li> </ul><div>The course page has a collection of great links to applications papers on controllers for software systems.</div></div><p></p><div>I'd like to see a 'software patterns' set created for easier use by software engineers. I'll attempt to present a couple common forms as patterns in a future blog post.</div> <p style="font-size: 10px;"><br /></p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-5399249062091328472011-11-10T10:23:00.000-08:002011-11-11T10:54:41.353-08:00Open RTB panel - IAB Ad Ops Summit 2011Monday November 7th I was on an <a href="http://www.iab.net/events_training/2011/adops/overview">IAB Ops</a> panel on OpenRTB.<br /><br /><iframe width="420" height="315" src="http://www.youtube.com/embed/K02hD023g-Y" frameborder="0" allowfullscreen=""></iframe><br /><br />The clip shows an exchange after Steve from the IAB asked a question about how webpage inventory is described in RTB. I described an example of differentiating a simple commodity, barley.<br /><br />Two of the major uses of barley in the US are animal feed and malting for making beer. Malting barley has specific requirements in terms of moisture content, protein percentage and other factors. Farmers don't always know what quality their crop will finish at. They count on having two general markets, if the tested quality meets malting standards then the premium over feed prices can be healthy. A 2011 report noted that malting barley provided a 70% premium over feedstock barley. Growing specific varieties and/or using organic farming methods can provide additional premiums over generic feed barley. The curious can follow the links below.<br /><ul><li> <a href="http://msuextension.org/publications/AgandNaturalResources/EB0186.pdf">Montana Barley Production Guide</a><br /></li><li> <a href="http://www.agmrc.org/commodities__products/grains__oilseeds/barley_profile.cfm">Agricultural Marketing Resource Center - Barley Profile</a></li></ul>How does this relate to publishers and advertising and OpenRTB? In my opinion we need several things standardized:<div><br /></div><div>1) Inventory registration and description API. Allows publishers influence on how their inventory is exposed in various demand-side and trading-desk platforms. Publishers should fully describe their inventory in a common format. Buy-side GUIs and algorithms will benefit from increased annotation and categorization. This can also harmonize the brand-safety ratings that are not connected between the sell and buy sides.</div><div><br /></div><div>2) Standardization of the emerging 'Private Marketplace' models in RTB. A set of best practices and trading procedures for PM needs to be defined such that the market can grow properly.</div><div><br /></div><div>While the main bid request/response API of OpenRTB has been criticized as being 'too late' given the large implementations in production, it is not too late to define standards for the above. These things will help the buy-side better differentiate quality inventory.</div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-40760188341101721912011-07-12T22:49:00.001-07:002011-07-13T08:28:26.688-07:00SchemaMgr - MySQL schema management tool<div class="posterous_autopost">SchemaMgr is a simple perl tool to manage schema change in MySQL DBs. I wrote this in 2007/2008 and it has been used in production for many years.<p></p><div><a href="https://github.com/nealrichter/schemamgr" target="_blank">https://github.com/nealrichter/schemamgr</a><p> Each change is assigned a version number and placed in a file. When the SQL in the file is executed successfully, a special table is set with that version number. Subsequent runs install only the higher versioned files.</p><div><p>It can also be used to reinstall views and stored procedures.</p><p> The best practice is to copy the file and change X in the filename and in the $DB_NAME variable.</p><div><div class="CodeRay"><div class="code"><pre>$ ./bin/schemamgr_X.pl<br />Usage: either create or upgrade X database<br />schemamgr_X.pl -i -uUSERNAME -pPASSWORD [-vVERSION] [-b]<br /> updates DB of to current (default) or requested version<br />schemamgr_X.pl -s -uUSERNAME -pPASSWORD<br /> reinstalls all stored procedures<br />schemamgr_X.pl -w -uUSERNAME -pPASSWORD<br /> reinstalls all views<br />schemamgr_X.pl -q -uUSERNAME -pPASSWORD<br /> Requests and prints current version<br />Optional Params<br /> -vXX -- upgrades upto a specific version number XX<br /> -b -- backs up the database (with data) before upgrades<br /> -nYY -- runs the upgrades against database YY - default is X<br /></pre></div></div></div><div>By convention you create ONE create_X_objects_v1 file with a date.<br />All other files are update files with greater than v1 numbers.<br /><pre>build/<br />|-- create_X_objects_v1_20110615.sql<br />|-- update_X_objects_v2_20110701.sql<br />`-- update_X_objects_v3_20110702.sql<br /></pre><br /></div> </div></div> <p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/schemamgr-mysql-schema-management-tool">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com1tag:blogger.com,1999:blog-17598372.post-39300124624738762632011-06-28T09:02:00.001-07:002011-06-28T12:45:32.592-07:00Managing yourself to tasks and finishing them.<div class="posterous_autopost">I saw these two short articles from HBR come across my twitter stream and read them. They stuck with me for more than a week as they triggered some connections with proof methods.<p></p><div><a href="http://web.hbr.org/email/archive/managementtip.php?date=060811">Treat Every Task as Three Steps, Not One</a></div> <p></p><div>The essence of the advice is "Prep-Do-Review". For each task you do make and review a plan for it before starting. Once the task completed review the plan. Did you finish? What did you learn? What would you do differently next time?</div> <p></p><div><a href="http://blogs.hbr.org/cs/2011/06/how_to_become_a_great_finisher.html">How to Become a Great Finisher</a></div><p> </p><div> The essence of this advice is to think in terms of "to-go" versus "to-date" performance on a task. When you entertain to-date thinking it's very easy to see how much you have accomplished so far. This can lead to a lowering of ongoing effort or allow yourself to become distracted and work on other tasks.</div> <p></p><div>So the optimal algorithm that combines the two is:</div><p></p><div><span class="Apple-style-span">PrepForWork();</span></div><div><span class="Apple-style-span">Do {</span></div> <div><span class="Apple-style-span"> IncrementalWork();</span></div><div><span class="Apple-style-span"> X = DistanceToFinish();</span></div> <div><span class="Apple-style-span">} Until (X == 0)</span></div><div><span class="Apple-style-span">ReviewResults();</span></div><p></p><div>Don't look back until you are done!</div><div><br /></div><div>Note that there is a formal method of proof in mathematics and CS that goes something like this:</div><div><div style="font-family: arial, sans-serif; border-collapse: collapse; color: rgb(80, 0, 80); font-size: 13px; "><br /></div><div style="border-collapse: collapse; "><span class="Apple-style-span"><span class="Apple-style-span">1) Define an integral metric </span><span class="Apple-style-span" style="font-size: small; ">f(x) </span><span class="Apple-style-span" style="font-size: small; ">measuring the distance to the goal</span></span></div><div style="border-collapse: collapse; "><span class="Apple-style-span">2) Define the starting distance</span></div><div style="border-collapse: collapse; "><span class="Apple-style-span">3) Show that your "algorithm/method" monotonically decreases f(x)</span></div><div style="border-collapse: collapse; "><span class="Apple-style-span">4) Infer that the goal will be reached </span></div><div style="border-collapse: collapse; "><span class="Apple-style-span">5) (Optional) Calculate the minimum number of steps required to reach the goal.</span></div></div><div style="border-collapse: collapse; font-size: 13px; "><span class="Apple-style-span"><br /></span></div><div>The important point is the rigor of the mathematical proof version. Your idea gets no partial credit for so-far progress, the algorithm either gets to the goal or it fails. The proof is either true or it is false. Thus you are either <i>Done</i> or you are <i>NOT Done.</i></div><p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/managing-yourself-to-tasks-and-finishing-them">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-43606426037400515252011-04-07T14:21:00.001-07:002011-04-08T11:27:07.190-07:00JSON parsing speed in various Node.JS versions<div class="posterous_autopost">We use <a href="http://nodejs.org/">Node.JS</a> for a very high capacity service at <a href="http://rubiconproject.com/">the Rubicon Project</a>. It often drives or handles in excess of 10B HTTP requests per day sending or receiving JSON data.<br />Out of curiosity I ran some tests on JSON parsing speed in different versions of Node.JS<p>node.js code:<br /></p><blockquote>var sys = require('sys');<br />var data = "{ \"item_uuid\": \"8ec56438-d3cf-442a-bbf7-7f076f229f35\", \"return_code\": 0, \"data\": [ { \"valid\": true, \"votes\": 2345, \"date\":\"Thu, 07 Apr 2011 15:17:17 EDT\", \"headline\": \"Senate Majority Leader Harry Reid indicates there likely will be a government shutdown on Friday. Lawmakers have been unable to agree on a new federal budget\", \"source\": \"Yahoo News\", \"published\":{\"hour\":\"19\",\"timezone\":\"UTC\",\"second\":\"17\",\"month\":\"4\",\"minute\":\"17\",\"utime\":\"1302203837\",\"day\":\"7\",\"day_of_week\":\"4\",\"year\":\"2011\"} } ] }";<p> try {<br /> for(var i = 0; i < 1000000; i++)<br /> {<br /> var tmp = JSON.parse(data);<br /> }<br />} catch(e) { sys.puts("ERROR: on parsing JSON with v8 parser"); }</p><p> sys.puts(data);<br />var tmp = JSON.parse(data);<br />sys.puts(JSON.stringify(tmp));<br />sys.puts("\n DONE \n");<br />process.exit();<br /></p></blockquote>Essentially this re-parses the same example JSON (I created a fake RSS like JSON pacakge) 1M times.<br /><p></p><div>Here are the results:</div><div><ul><li>Node 0.1.3x: real 0m30.050s</li><li>Node 0.2.6: real 0m30.050s</li><li>Node 0.3.8: real 0m9.915s</li> <li>Node 0.4.5: real 0m9.999s</li></ul><br /></div><div>For reference I ran the same test against a very fast tokening parser in C called <a href="http://zserge.bitbucket.org/jsmn.htm">jsmn</a>, and a C++ one called <a href="http://code.google.com/p/vjson/">vjson</a>.</div> <div><div><ul><li>jsmn: real 0m2.276s</li><li>vjson: real 0m7.465s <i>Note that vjson is a destructive parser, and I had to fix that first.</i></li></ul></div></div><p></p><div>Interestingly the JSON parser in node 0.4.5 and prior versions appears to be written in pure Javascript. See the file: node-v0.4.5/deps/v8/src/json.js</div> <p></p><div>It's unclear if the speed improvements are a result of improvements to the parser implementation or in some efficiency/speed leap in versions of V8 included in Node versions.</div><div><ul> <li>Node 0.1.33: v8: 2010-03-17: Version 2.1.5</li><li>Node 0.2.6: v8: 2010-08-16: Version 2.3.8</li><li>Node 0.3.8: v8: 2011-02-02: Version 3.1.1</li> <li>Node 0.4.5: v8: 2011-03-02: Version 3.1.8</li></ul></div> <p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/json-parsing-speed-in-various-nodejs-versions">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-37682368796486201682011-03-22T21:26:00.001-07:002011-03-22T21:26:26.331-07:00Pamela Samuelson on startups and software patents<div class='posterous_autopost'>Following up on my last post here is the view from Pamela Samuelson:<p /><a href="http://radar.oreilly.com/2010/07/why-software-startups-decide-t.html">Why software startups decide to patent ... or not</a><p /><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"> <span style="color: rgb(51, 51, 51); font-family: Arial, sans-serif; font-size: 14px; line-height: 18px;">Two-thirds of the approximately 700 software entrepreneurs who participated in the 2008 Berkeley Patent Survey report that they neither have nor are seeking patents for innovations embodied in their products and services. These entrepreneurs rate patents as the least important mechanism among seven options for attaining competitive advantage in the marketplace. Even software startups that hold patents regard them as providing only a slight incentive to invest in innovation.</span></blockquote> <p /><p /><div>She also lists a variety of reasons why these software entrepreneurs decided to forgo patenting their last invention. It's a very interesting write up. </div> <p style="font-size: 10px;"> <a href="http://posterous.com">Posted via email</a> from <a href="http://nealrichter.posterous.com/pamela-samuelson-on-startups-and-software-pat">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-48956514534282696032011-03-10T14:30:00.001-08:002011-03-10T14:30:42.596-08:00Comments re "The Noisy Channel: A Practical Rant About Software Patents"<div class='posterous_autopost'><div style="color: rgb(51, 51, 51); font-family: Georgia, Times New Roman, Times, serif; font-size: 14px; line-height: 23px;"><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;"> <a href="http://thenoisychannel.com/2011/03/07/a-practical-rant-about-software-patents/">The Noisy Channel: A Practical Rant About Software Patents</a> - [My comments cross-posted here]</p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;"> Daniel, nice writeup.</p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;">I worked for a BigCo and filed many patents. It was a mixed bag. The time horizon is so long that even after I’ve been gone for 3.5 years many of them are still lost in the USPTO. Average time for me to see granted patents was 5+ years.</p> <p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;">Here are my biased opinions:</p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;"> 1) Patents really matter for BigCos operating on a long time horizon. It’s a strategic investment.</p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;"> 2) Patents are nearly worthless for a Startup or SmallCo. The time horizon is way past your foreseeable future, and thus the whole effort is akin to planning for an alternate reality different than the current business context. Throwing coins in a fountain for good luck is about as relevant. You simply are better off getting a filing date on a provisional design writeup and hiring an engineer with the money you’d spend on Patent lawyers.</p> <p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;">3) As an Acquiring company looking at a company to acquire, Provisional or Pending Patents are a liability not an asset. They take time and resources to push to completion for a strategy of deterrence.</p> <p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;">4) Patents are mostly ignored in the professional literature. Take Sentiment Analysis as one example. Sentiment Analysis exploded in 2001 w.r.t. Academic publishing, yet there are more than a few older patents discussing good technical work on Sentiment Analysis. I’ve NEVER seen an algorithm in a patent cited in a paper as previous work. And I have seen academic papers with algorithms already 90% covered by an older patent… and the papers are cited as ‘novel work’.</p> <p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;">5) Finding relevant patents is ludicrously hard. It might be the most challenging problem in IR w.r.t. a corpus IMO. Different words mean the same thing and vise versa due to the pseudo-ability in a Patent to redefine a word away from the obvious meaning. With two different lawyers rendering the same technical design into a writeup and claims results in wildly different work product.</p> <p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;">6) I’ve seen some doosey granted Patents. Things that appear to either be implementations of very old CS ideas into new domains.. or worse stuff that would be a class project as an undergrad.</p> <p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;">It’s just plain ugly in this realm.</p><p style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 1em; margin-left: 0px;"> <br /></p></div> <p style="font-size: 10px;"> <a href="http://posterous.com">Posted via email</a> from <a href="http://nealrichter.posterous.com/comments-re-the-noisy-channel-a-practical-ran">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com2tag:blogger.com,1999:blog-17598372.post-44139024745665641482011-03-10T01:20:00.001-08:002011-03-10T01:20:37.891-08:00On Strategic Plans<div class='posterous_autopost'>This needs absolutely no comment.<p /><div> <span style="font-family: Lucida Grande, Lucida Sans Unicode, verdana, sans-serif; font-size: 12px; line-height: 22px;">“We have a ‘<em>strategic plan</em>.’ It’s called <strong><em>doing things</em></strong>.” ~ <em>Herb Kelleher</em></span><br /> <p /><div><div style="color: rgb(86, 60, 19); font-family: Helvetica, Arial, Verdana, sans-serif; font-size: 10px; line-height: 10px;"><img class="photo" src="http://distillery.s3.amazonaws.com/media/2011/03/09/ebe98db490154bbb9cd008f55ca5e0f8_7.jpg" style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; border-color: initial; font-family: inherit; font-size: 10px; font-style: inherit; font-weight: inherit; line-height: 1; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; text-align: left; vertical-align: baseline; height: 480px;" /><p /></div></div></div> <p style="font-size: 10px;"> <a href="http://posterous.com">Posted via email</a> from <a href="http://nealrichter.posterous.com/on-strategic-plans">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-50819329435406295382011-03-06T10:20:00.001-08:002011-03-06T10:20:05.657-08:00Hilarious system calls in the BeOS<div class='posterous_autopost'>These system calls in the BeOS still make me smile.<p /><div><span style="">int32<b><tt> is_computer_on(</tt></b>void<b><tt>)</tt></b></span></div> <blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><p style="font-family: Times New Roman; font-size: medium;">Returns 1 if the computer is on. If the computer isn't on, the value returned by this function is undefined.</p> </div></blockquote><div><div><span style="font-family: Times New Roman; font-size: medium;"><span style="">double<b><tt> is_computer_on_fire(</tt></b>void<b><tt>)</tt></b></span></span></div> </div><p /><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><div><span style="font-family: Times New Roman; font-size: medium;">Returns the temperature of the motherboard if the computer is currently on fire. If the computer isn't on fire, the function returns some other value.</span></div> </div></blockquote><div><p /><div><blockquote><span style="font-size: 15px;">#include <stdio.h> <br /> </span><span style="font-size: 15px;">#include <be/kernel/OS.h> </span><span style="font-size: 15px;"><br /> </span><span style="font-size: 15px;">int main() <br /></span><span style="font-size: 15px;">{ <br /> </span><span style="font-size: 15px;">printf("[%d] = </span><span style="font-size: 15px;">is_computer_on()</span><span style="font-size: 15px;">\n", is_computer_on()); <br /> </span><span style="font-size: 15px;">printf("[%f] = </span><span style="font-size: 15px;">is_computer_on_fire()</span><span style="font-size: 15px;">\n", is_computer_on_fire()); <br /> </span><span style="font-size: 15px;">} </span></blockquote></div><div> These functions serve a similar purpose to getpid() in Unix, essentially no-op calls that can be used to test the kernel's intrinsic response time under load.</div><p /><div>Write up of <a href="http://en.wikipedia.org/wiki/BeOS">BeOS history</a> is here, <a href="http://www.haiku-os.org/">Haiku</a> is an open source clone of the BeOS that is curiously under <a href="http://dev.haiku-os.org/changeset">active development</a>.</div> </div> <p style="font-size: 10px;"> <a href="http://posterous.com">Posted via email</a> from <a href="http://nealrichter.posterous.com/hilarious-system-calls-in-the-beos">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-34107081723217630122011-03-04T09:21:00.001-08:002011-03-04T09:21:43.852-08:00Contractor Needed: HTML/CSS/Javascript Ninja<div class='posterous_autopost'>The Rubicon Project is looking for an in-browser HTML/CSS/Javascript Ninja to restructure the workflow of an application GUI. The server side code is perl/mod_perl. Please contact me if you are interested and available. The contract is 4-6 weeks. <p style="font-size: 10px;"> <a href="http://posterous.com">Posted via email</a> from <a href="http://nealrichter.posterous.com/contractor-needed-htmlcssjavascript-ninja">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-20655462140911686042011-03-03T12:26:00.001-08:002011-03-03T12:41:31.353-08:00Job Post: Software Engineer/Scientist: Ad Serving, Optimization and Core Team<div class="posterous_autopost"><h1><span class="Apple-style-span" style="font-size: 16px; font-weight: normal; "><strong>LOCATION:</strong> <span style="font-weight: normal;">the Rubicon Project HQ in West Los Angeles or Salt Lake City</span></span></h1> <p><span style="font-weight: normal;">the Rubicon Project is on a mission to automate buying and selling for the $65 billion global online advertising industry. Backed by $42 million in funding, we are currently looking for the best engineers in the world to work with us.</span></p><p><strong>Team Description</strong></p> <p><br /><span style="font-weight: normal;">The mission of the Core Team is to build robust, scalable, maintainable and well documented systems for ad serving, audience analytics, and market analysis. Every day we serve billions of ads, process terabytes of data and provide valuable data and insights to our publishers. If building software that touches 500+ million people every month is interesting to you, you'll fit in well here.</span></p><p>Some of the custom software we've built to solve these problems include:</p><p>A patented custom ad engine delivering thousands of ad impressions per second with billions of real time auctions daily<br />A real time bid engine designed to scale out to billions of bid requests daily<br />Optimization Algorithms capable of scheduling and planning adserving opportunities to maximize revenue<br />Client side Javascript that performs real-time textual analysis of web pages to extract semantically meaningful data and structures<br />A web-scale key value store based on ideas from the Amazon Dynamo paper used to store 100s of millions of data points<br />Unique audience classification system using various technologies such as Solr and Javascript for rich, real-time targeting of web site visitors<br />Data Mining buying and selling strategies from a torrent of transactional data<br />Analytics systems capable of turning a trillion data points into real business insight<br /><br /><strong>Job Description</strong></p> <p><br /><span style="font-weight: normal;">Your job, should you accept it, is to build new systems, new features and extend the functionality of our existing systems. You will be expected to architect new systems from scratch, add incremental features on existing systems, fix bugs in other people's code and help manage production operations of the services you build. Sometimes you'll have to (or want to) do this work when you are not in the office, so working remote can't scare you off.</span></p><p>Most of our systems are written in Perl, Java, and C, but we have pieces of Python, Clojure and server-side Javascript as well. Hopefully you have deep expertise in at least one of these; you'll definitely need to have a desire to quickly learn and work on systems written in all of the above.</p><p>You should also have worked with and/or designed service oriented architectures, advanced db schemas, big data processing, highly scalable and available web services and are well aware of the issues surrounding the software development lifecycle. We expect that your resume will itemize your 3+ years experience, mention your BS or MS in Computer Science and be Big Data Buzzword Compliant.</p><p>Bonus points for experience with some of the technologies we work with:</p> <ul> <li><span style="font-weight: normal;">Hadoop</span></li> <li><span style="font-weight: normal;">NodeJS</span></li> <li><span style="font-weight: normal;">MySql</span></li> <li><span style="font-weight: normal;">Solr/Lucene</span></li> <li><span style="font-weight: normal;">RabbitMQ</span></li> <li><span style="font-weight: normal;">MongoDB</span></li> <li><span style="font-weight: normal;">Thrift</span></li> <li><span style="font-weight: normal;">Amazon EC2</span></li> <li><span style="font-weight: normal;">Memcached</span></li> <li><span style="font-weight: normal;">MemcacheQ</span></li> <li><span style="font-weight: normal;">Machine Learning</span></li> <li><span style="font-weight: normal;">Optimization Algorithms</span></li> <li><span style="font-weight: normal;">Economic Modeling</span></li></ul><div><span style="font-weight: normal;"><a href="http://www.rubiconproject.com/about/hiring/software-engineer-core-team/">Apply Now! Click the Apply button!</a></span></div> <p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/job-post-software-engineerscientist-ad-servin">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-54521041543343671042011-02-28T13:06:00.001-08:002011-02-28T13:17:16.717-08:00A note on software teams and individuals<div class="posterous_autopost">I'm currently running a loosely coupled team of people all working on a common initiative. While this is not my first time running a team, the same set of things seem to happen with all 'new' teams. Here's a quick set of observations.</div><div class="posterous_autopost"><p></p><div>The first major observation is that teams of engineers can quickly fall into operating like a "golf team" versus a "football team". In Golf, each team member generally competes against all other players (and their different teams) as an individual. A given team wins if it's individual players collectively do better than some other team's players. Football (or Soccer or Basketball) is very different. A team wins in the face of good opposition <i>only if it plays as a team.</i></div> <p></p><div>For software teams, done means one thing: the team is done with the milestone or project. Done means finished, tested and shipped code. Does does not mean "my part works", or "my tasks are done".</div> <p></p><div>IMO each team member should answer these questions to the group every day:</div><div><ol><li>What direction I am going relative to team goals.</li><li>What specific items I am working on today.</li><li> Does anyone need any help from me?</li><li>Do I need any help with my work?</li></ol></div><div>Team managers, both the overall and functional leads, should ask or answer these questions for the group every day:</div><div> <ol><li>Are we as a group going the right direction (towards the goal)?</li><li>Will we meet the timeline and/or functional goals?</li><li>Is there any functional or task ambiguity that needs working out?</li><li>Are any course corrections needed?</li> </ol></div><div>The second observation is that there are two major indicators of if a given individual is a good addition to the team:</div><div><ol><li>Does this person communicate well and often?</li><li>Does this person have the capability and desire to resolve ambiguity on their own when possible?</li> </ol><div>The second skill, resolving ambiguity, is in my opinion the primary question that a software hiring manager needs to answer in the affirmative about a given candidate... assuming of course the candidate has the needed skills.</div> </div><p></p><div>Much of this also circles back on a blog post that Jordan Mitchell wrote years ago when I was hip-deep in code at <a href="http://www.othersonline.com/">Others Online</a>.</div><p></p><div> <a href="http://kickstand.typepad.com/metamuse/2008/12/actual-vs-perceived-progress.html">Actual vs. Perceived Progress</a></div> <p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/a-note-on-software-teams-and-individuals">aicoder - nealrichter's blog</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-18951552042822419932011-02-07T15:13:00.000-08:002011-02-07T16:23:27.701-08:00RightNow - Our cowboys ride code<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbk1gAF1HWJuZhkAbs1cfjPeKLYXOQL3WmjmAod70nSowQ2veMCkgDCsU3jeLvHnkiYJ-LeQeR7iUyqqGwnezVx6yHX-R6y2c0iDk2aJguC7GFxi-MfwvnJiUMQ7sZg0aSLHz0/s1600/RightNowCodeCowboys.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 258px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbk1gAF1HWJuZhkAbs1cfjPeKLYXOQL3WmjmAod70nSowQ2veMCkgDCsU3jeLvHnkiYJ-LeQeR7iUyqqGwnezVx6yHX-R6y2c0iDk2aJguC7GFxi-MfwvnJiUMQ7sZg0aSLHz0/s400/RightNowCodeCowboys.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5571090459903667426" /></a><br /><div>This is a neat little ad in the <a href="http://msp.imirus.com//Mpowered/imirus.jsp?volume=ds11&issue=1&page=0">January Delta Sky Magazine</a> for RightNow Technologies, where I worked from 1999-2007.</div><div><div></div><blockquote><div>RightNow Technologies serves about 10 billion [customer interactions] a year through he companies and institutions it works with. “Every person in North America has used one of our solutions about 25 times,” says Gianforte.</div></blockquote><div></div></div><div><div>Why RightNow keeps its headquarters in Bozeman, MT</div><div></div><blockquote><div> The quality of life here is a huge advantage, but more importantly, says Gianforte, “there’s a ranch saying around here that goes,‘When something needs to get done, well then, we’re just gonna get ‘er done.’ In many environments, they have to form a committee, pull in consultants and such to make things happen, but our clients appreciate that when something needs to get done, we can easily make that hap pen because of the work ethic here.”</div></blockquote></div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-90258979046714498972011-01-30T23:45:00.001-08:002011-01-31T00:40:04.073-08:00The Provenance of Data, Data Branding and "Big Data" Hype<div class="posterous_autopost"><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"> The credibility of where data comes from in all these "big data" plays is absolutely crucial. Waving hands re "algorithms" won't cut it. @nealrichter Jan 27, 1010 Tweet</blockquote><p> </p><div>To expand on this tweet here's the argument: If one of your key products as a startup or business is to "crunch data" and derive or extract value from it then you should be concerned about data provenance. This is true whether you are crunching your own data or third-party data.</div> <p></p><div>Some examples:</div><div><ul><li>Web analytics - crunch web traffic and distill visitation and audience analytics reports for web site owners. Often they use these summaries to make decisions and sell their ad-space to advertisers.</li> <li>Semantic Web APIs - crunch webpages, tweets etc and return topical and semantic annotations of the content</li><li>Comparison shopping - gather up product catalogs and pricing to aggregate for visitors</li><li>Web publishers - companies who run websites</li> <li>Prediction services - companies that use data to predict something</li></ul></div><div>In each of the above categories the provenance of the input data and brand of the output data is key. For each of the above one could name a company with either solid-gold data OR a powerful brand-name and good-enough data. Conversely we can find examples of companies with great tech but crappy data or a weak brand. </div> <p></p><div>For web publishers, those that host user-generated content have poor provenance in general compared to news sites (for example). A notable exception is Wikipedia who has a pure "UGC" model but a solid community process and standards to improve provenance of their articles (those without references are targeted for improvement).</div> <p></p><div>In comparison shopping Kayak.com has good data (directly from the airlines) and has built a good brand. The same is true of PriceGrabber and Nextag. TheFind.com on the other hand appears to have great data and tech, but no well known brand.</div><div><br /></div><div><i>(I'm refraining from going into specific examples or opinions on big data companies to avoid poking friends in the eye.)</i></div> <p></p><div>The issue of Provenance and Branding is especially important in sales situations where you are providing a tool (analytics) that helps your customer (a sales person) sell something to a third-party (their customer). If the input data you are using either has a demonstrable provenance or a good brand you'll have an easier time convincing people that the output of your product is worth having (and reselling).</div> <p></p><div>The old saying for this in computer science is <a href="http://en.wikipedia.org/wiki/Garbage_In,_Garbage_Out" target="_blank">Garbage In, Garbage Out</a>. </div><p></p><div>In "big data" world of startups that is blowing by Web 2.0 as the new hotness there is a startling lack of concern about data provenance. The essentially ethos is that if we (the Data Scientists) accumulate enough data and crunch it with magical algorithms then solid-gold data will come out... or at least that's what the hype machine says.</div> <p></p><div>The lesson from the financial melt down is that magical algorithms making CDOs, CMOs and other derivatives should be viewed with a lens of mistrust. The GIGO principle was forgotten and no one even cared about the provenance (read credit quality) of the base financial instruments making up the derivatives. The credit rating agencies were just selling their brand and cared little about quality.</div> <p></p><div>In my opinion, there is a clear parallel here to "big data". Trust must be part of the platform and not just tons of CPUs and disk-space. A Brand is a brittle object that is easily broken, so concentrate on quality.</div> <div> </div> <p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/the-provenance-of-data-data-branding-and-big">nealrichter's posterous</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com1tag:blogger.com,1999:blog-17598372.post-12560276239605459372011-01-14T00:23:00.001-08:002011-01-14T00:59:20.557-08:00Finance for Engineers<div class="posterous_autopost"><div>Last summer I took a great mini-course at MIT Sloan on Finance. It's essentially a breadth-first review of the <a href="http://ocw.mit.edu/courses/sloan-school-of-management/15-402-finance-theory-ii-spring-2003/" target="_blank">MBA course</a> complete with three case studies and a review of project evaluation methods via <a href="http://en.wikipedia.org/wiki/Net_present_value" target="_blank">net present value analysis</a>. Approximately 80% of the attendees were engineers/techies with 10+ years experience.. and maybe 25% w/ PhDs.</div> <p></p><div><a href="http://mitsloan.mit.edu/execed/coursedetails.php?id=779" target="_blank">Fundamentals of Finance for the Technical Executive</a></div><p></p><div>TextBook was: <a href="http://www.amazon.com/Analysis-Financial-Management-Mcgraw-Hill-Insurance/dp/0077297652/ref=dp_ob_title_bk">Higgins - Analysis for Financial Management</a></div><p></p><div>The first case study is <a href="http://hbr.org/product/wilson-lumber-co/an/286122-PDF-ENG" target="_blank">Wilson Lumber from Harvard</a>. The material is copyrighted, yet these links look like accurate distillations by business students. </div> <div><ul><li><a href="http://www.detobey.com/work/Clarkson.pdf" target="_blank">Clarkson Lumber Overview PPT</a></li><li><span style="font-family: arial, sans-serif; color: rgb(14, 119, 74); line-height: 15px;"><a href="http://elvis.sob.tulane.edu/Documents/Assignments/Butler.xls" target="_blank">Butler Lumber Spreadsheet</a></span></li> </ul></div> <div>The initial position is that Wilson Lumber growing small business with good suppliers and loyal customers. Volume and revenue are all up period over period. Question is should the bank increase is line of credit to fund the business. Once you break down the financial statements and model the business, the answer is No. Essentially Mr Wilson is over extended by many measures and is growing at the expense of his balance sheet, loaning him money will only make the problem bigger down the road. His basic options are to take in a partner as co-owner for cash, go broke or raise prices to lower volume and improve margins and slowly rebuild the balance sheet.</div> <p></p><div>We then went through two NPV exercises. The first was a basic analysis of go/no-go on an engineering project with a bottom up analysis via putting all cost/benefit assumptions in a model and iterating though possibilities. The second was an analysis of a joint-venture between two biotech companies. Everything from external capital, deal structure to market penetration projections were worked in. Very informative and pretty interesting work for engineers to do once the terminology and methods were explained.</div> <p></p><div><a href="http://www.stanford.edu/~djenter/index.html">Professor Jenter</a> shared two amusing anecdotes:</div><div><ul><li>His MIT and Stanford MBA students often run off to found start-ups and forget the basic Wilson Lumber case. By the time they approach him for help it's too late and they are in Mr Wilson's position: shut-down, take in $$ and lots of equity dilution (and loss of control) or slow growth dramatically.</li> <li>Also a quote along the lines of "Startups founded by MIT PhDs fail at a rate above far average".</li></ul></div><div>This certainly hammered home the lesson that strategic planning for growth is very important, even for what look like non hyper-growth (software) companies. I'd recommend this course to any engineer wanting a quick structured intro to basic financial management.</div> <p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/finance-for-engineers">nealrichter's posterous</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-4750197763689688412010-12-30T09:34:00.001-08:002010-12-30T09:46:02.029-08:00List of Best Paper awards in CS/AI/ML conferences<div class="posterous_autopost"><div>The below is a great list of best paper awards for WWW, SIGIR, CIKM, AAAI, CHI, KDD, SIGMOD, ICML, VLDB, IJCAI, UIST since 1996</div><p><a href="http://jeffhuang.com/best_paper_awards.html">http://jeffhuang.com/best_paper_awards.html</a></p><p></p><div>Interesting thing to note: Google is ranked last in frequency, Microsoft first.</div><p></p><div>This needs NIPS and possibly UAI added to it.</div><div><a href="http://nips.cc/ConferenceInformation/PaperAwards">http://nips.cc/ConferenceInformation/PaperAwards</a></div> <p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/list-of-best-paper-awards-in-csaiml-conferenc">nealrichter's posterous</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-32656750313632189732010-12-29T11:18:00.001-08:002010-12-29T11:48:43.363-08:00Managing Open Source Licenses<div class="posterous_autopost"><div>From time to time I have helped companies do Open Source code audits in their own source code. Basically this consists of auditing their code to find open source code. </div> <p></p><div>These code audits are particularly important during software releases and M&A events. I've helped companies do this for releases and been on both sides of M&A event driven audits.</div><p></p><div>If the developers have kept the attributions with any open source code they have re-used then grep is a fine tool for auditing. However this is a big IF. If your developers are sloppy and do not keep the attributions (ie copyright and license notices) with code they lift from open source you have a problem. A software tool needs to be used to scan the corporate source for hits in open source repositories. </div> <p></p><div>There are at least three companies providing software to do this:</div><div><ul><li><a href="http://www.blackducksoftware.com/">BlackDuck Software</a></li><li><a href="http://www.palamida.com/">Palamida</a></li> <li><a href="http://protecode.com/">Protecode</a></li></ul></div><p></p><div>Ideally the outcome of this process is as follows:</div><div><ol><li>A clear company policy is set on what open source licenses are allowed and how developers can use open source come or components.</li><li>The corporate code is cleanly annotated with any third party attributions (see below).</li> <li>Open Source code that has bad licenses for commercial usage is identified and removed before release.</li><li>A Bill of Materials is created for each release listing third-party software in the release.</li><li>Necessary copyright or other notices appear in About dialogs, manuals or product websites.</li> </ol></div><p></p><div>Example comment block:</div><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"> <p style="margin-bottom: 0in; line-height: 100%;">/*</p> <p style="margin-bottom: 0in; line-height: 100%;"> * XYZ.com Third-party or Open Source Declaration</p> <p style="margin-bottom: 0in; line-height: 100%;"> * Name: Bart Simpson</p> <p style="margin-bottom: 0in; line-height: 100%;"> * Date of first commit: 04/25/2009</p> <p style="margin-bottom: 0in; line-height: 100%;"> * Release: 3.5 “The Summer Lager Release”</p> <p style="margin-bottom: 0in; line-height: 100%;"> * Component: tinyjson</p> <p style="margin-bottom: 0in; line-height: 100%;"> * Description: C++ JSON object serializer/deserializer </p> <p style="margin-bottom: 0in; line-height: 100%;"> * Homepage: <a href="http://blog.beef.de/projects/tinyjson/">http://blog.beef.de/projects/tinyjson/</a></p> <p style="margin-bottom: 0in; line-height: 100%;"> * License: MIT style license</p> <p style="margin-bottom: 0in; line-height: 100%;"> * Copyright: Copyright (c) 2008 Thomas Jansen (<a href="mailto:thomas@beef.de">thomas@beef.de</a>)</p> <p style="margin-bottom: 0in; line-height: 100%;"> * Note: See below for original declarations from the code</p> <p style="margin-bottom: 0in; line-height: 100%;"> */</p></blockquote><p></p><div>If the above were upgraded to be in a javadoc style comment then a tool could be built to auto-magically generate a Bill of Materials for each release.</div> <p></p><div>There is one grey area in all this: how to handle developers using code from discussion sites like PHP.net, CodeProject, StackOverflow and similar sites. Generally code put in these type of forums has no defined license. In this case the code is either copyrighted by the site or the author of the post... and developers should not use the code without getting an explicit license. However developers generally feel like people put the code up there to share. This conflict means the company policy on usage of this type of code must be clearly communicated to all developers.</div> <p></p><div>This is a nice review article of other considerations for open source auditing:</div><div><br /><a href="http://www.drdobbs.com/article/printableArticle.jhtml;jsessionid=JG1RLBQMN0ERNQE1GHOSKHWATMY32JVN?articleId=228000261&dept_url=/open-source/">Dr Dobbs: Managing Open Source Licensing by Kamal Hassin</a> </div><br /><br /><p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/managing-open-source-licenses">nealrichter's posterous</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-86092167175875978722010-12-17T09:11:00.001-08:002010-12-17T09:14:25.646-08:00Stochastic Universal Sampling/Selection<div class="posterous_autopost"><div>Stochastic Universal Sampling is a method of weighted random sampling exhibiting less bias and spread that classic roulette wheel sampling. The intuition is a roulette wheel with n equally spaced steel balls spinning in unison around the wheel. This method has better properties and is more efficient that doing repeated samples from the wheel with or without replacement of the selected items.</div> <p></p><div><p style="font-family: Times New Roman; font-size: medium;"><img src="http://docs.happycoders.org/unsorted/ai/genetic_algorithms/geatbx/selsus.gif" align="BOTTOM" alt="Stochastic universal sampling" width=400/></p> <dl style="font-family: Times New Roman; font-size: medium;"></dl></div><p></p><div><span style="font-family: sans-serif; font-size: 13px; line-height: 19px;">Baker, James E. (1987). "Reducing Bias and Inefficiency in the Selection Algorithm". <i>Proceedings of the Second International Conference on Genetic Algorithms and their Application</i> (Hillsdale, New Jersey: L. Erlbaum Associates): 14–21.</span></div> <p></p><div>Reference implementations on the web are scare, so here are a few:</div><p></p><div><a href="http://www.borgelt.net/">Christian Borgelt</a></div><div><a href="http://fuzzy.cs.uni-magdeburg.de/studium/ga/src/sus.c">http://fuzzy.cs.uni-magdeburg.de/studium/ga/src/sus.c</a></div> <p></p><div><a href="https://github.com/dwdyer">Dan Dyer</a></div><a href="https://github.com/dwdyer/watchmaker/blob/master/framework/src/java/main/org/uncommons/watchmaker/framework/selection/StochasticUniversalSampling.java">https://github.com/dwdyer/watchmaker/blob/master/framework/src/java/main/org/uncommons/watchmaker/framework/selection/StochasticUniversalSampling.java</a><p></p><div><a href="http://epr.adaptive.cs.unm.edu/asm/code.html">University of New Mexico</a></div><div><a href="http://epr.adaptive.cs.unm.edu/asm/code.html">http://epr.adaptive.cs.unm.edu/asm/code.html</a></div><p></p><div><a href="http://cs.gmu.edu/~eclab/projects/ecj/">GMU's ECJ</a></div><div><a href="http://cs.gmu.edu/~eclab/projects/ecj/docs/classdocs/ec/select/SUSSelection.html">http://cs.gmu.edu/~eclab/projects/ecj/docs/classdocs/ec/select/SUSSelection.html</a></div> <div>See the SUSSelection.java buried in the latest tarball.</div> <p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/stochastic-universal-samplingselection">nealrichter's posterous</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-58325060086167929552010-11-22T15:58:00.001-08:002010-11-22T16:00:11.164-08:00Computing, economics and the financial meltdown (a collection of links)<div class="posterous_autopost">This editor's letter from CACM last year is interesting: <a href="http://cacm.acm.org/magazines/2009/9/38884-the-financial-meltdown-and-computing/fulltext" target="_blank">The Financial Meltdown and Computing by Moshe Y. Vardi</a> <div><br /><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Information technology has enabled the development of a global financial system of incredible sophistication. At the same time, it has enabled the development of a global financial system of such complexity that our ability to comprehend it and assess risk, both localized and systemic, is severely limited. Financial-oversight reform is now a topic of great discussion. The focus of these talks is primarily over the structure and authority of regulatory agencies. Little attention has been given to what I consider a key issue—the opaqueness of our financial system—which is driven by its fantastic complexity. The problem is not a lack of models. To the contrary, the proliferation of models may have created an illusion of understanding and control, as is argued in a recent report titled "<a href="http://ideas.repec.org/p/kie/kieliw/1489.html" target="_blank">The Financial Crisis and the Systemic Failure of Academic Economics.</a>"<br /></blockquote><br />Krugman's essay at the time <a href="http://www.nytimes.com/2009/09/06/magazine/06Economic-t.html?_r=1&em=&pagewanted=all" target="_blank">How Did Economists Get It So Wrong?</a> gave a nice history of economic ideas, the models behind and his interpretations of their correctness.<p> </p><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">The theoretical model that finance economists developed by assuming that every investor rationally balances risk against reward — the so-called Capital Asset Pricing Model, or CAPM (pronounced cap-em) — is wonderfully elegant</blockquote><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">[snip]<br /></blockquote><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> Economics, as a field, got in trouble because economists were seduced by the vision of a perfect, frictionless market system.<br /></blockquote><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> [snip]<br /></blockquote><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">H. L. Mencken: “There is always an easy solution to every human problem — neat, plausible and wrong.”</blockquote> <div> </div>I read this months ago and it's been percolating in my thoughts since then. <a href="http://nymag.com/news/business/55687/" target="_blank">My Manhattan Project - How I helped build the bomb that blew up Wall Street by Michael Osinski.</a> Osinski wrote much of the software and models used to form <a href="http://en.wikipedia.org/wiki/Collateralized_mortgage_obligation" target="_blank">CMOs</a> and <a href="http://en.wikipedia.org/wiki/Collateralized_debt_obligation" target="_blank">CDOs</a>. Essentially the software aggregates debt instruments from mortgage and other debt markets and allowed a bond designer to issue tailor-made portfolio of debt while mitigating default risk of the debt via that aggregation. He called it his sausage grinder.<p> </p><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">“You put chicken into the grinder”—he laughed with that infectious Wall Street black humor—“and out comes sirloin.”</blockquote> <p></p><div>Here's a large collection of links from that period that are worth reading. My thought at the moment is this nugget from Twitter:</div><p></p><div><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"> <span style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;"><a href="http://twitter.com/Poormojo" class="tweet-url screen-name" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px;">Poormojo</a></span> <span class="Apple-style-span" style="font-family: 'Lucida Grande', sans-serif; font-size: 14px; line-height: 16px; ">"Any sufficiently advanced financial instrument is indistinguishable from fraud."</span></blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><span class="Apple-style-span" style="font-family: 'Lucida Grande', sans-serif; font-size: 14px; line-height: 16px; "><br /></span></blockquote><a href="http://www.wired.com/techbiz/it/magazine/17-03/wp_quant?currentPage=all" target="_blank">Recipe for Disaster: The Formula That Killed Wall Street</a><p><a href="http://www.nytimes.com/2009/09/13/business/13unboxed.html?em=&pagewanted=print" target="_blank">Wall Street’s Math Wizards Forgot a Few Variables </a></p><p> <a href="http://www.nytimes.com/2009/09/13/business/13lehman.html?_r=1&hp=&adxnnlx=1252814676-J4YWny4n5Bq8ehtgH1Fu3A&pagewanted=print" target="_blank">Tales From Lehman’s Crypt </a></p><p></p><div><a href="http://www.nytimes.com/2009/09/13/business/economy/13view.html?src=linkedin" target="_blank">Economic View: Flaw in Free Markets: Humans</a></div> <p><a href="http://freakonomics.blogs.nytimes.com/2009/01/09/this-is-your-brain-on-prosperity-andrew-lo-on-fear-greed-and-crisis-management/?pagemode=print" target="_blank">Andrew Low: This is your brain on prosperity</a><br /></p></div><p></p><div><a href="http://bit.ly/1PwZ5V" target="_blank">A crisis of politics, not economics: Complexity, Ignorance, and policy failure.</a></div><p></p><div> <a href="http://www.newsweek.com/id/200015" target="_blank">Revenge of the Nerd: Paul Wilmott is out to save Wall Street's soul—one dork at a time.</a></div><p></p><div><a href="http://cacm.acm.org/magazines/2009/10/42365-a-conversation-with-david-e-shaw/abstract" target="_blank">A Conversation with David E. Shaw</a></div> <p></p><div><a href="http://www.forbes.com/2008/10/07/securities-quants-models-oped-cx_ss_1008shreve.html" target="_blank">Don't Blame The Quants by Steven Shreve</a></div> <p></p><div><a href="http://www.nytimes.com/2009/10/14/opinion/14trillin.html?em=&adxnnl=1&adxnnlx=1255543552-DPpTSk3i4f5lEJZALsigRA" target="_blank">http://www.nytimes.com/2009/10/14/opinion/14trillin.html?em=&adxnnl=1&adxnnlx=1255543552-DPpTSk3i4f5lEJZALsigRA</a></div> <p></p><div><a>Sciam: Does Economics Violate the Laws of Physics?</a></div><p></p><div><a href="http://online.wsj.com/article/SB10001424052748704204304574543503520372002.html" target="_blank">Systemic Risk and Fannie Mae</a></div> <p></p><div><a href="http://www.reuters.com/article/marketsNews/idUSN1641435720091202?pageNumber=2&virtualBrandChannel=0&sp=true" target="_blank">Geeks trump alpha males as algos dominate Wall St</a></div> </div> <p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/computing-economics-and-the-financial-meltdow">nealrichter's posterous</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0tag:blogger.com,1999:blog-17598372.post-85622946029625868142010-10-27T00:02:00.001-07:002010-10-27T09:18:11.533-07:00Review of "Learning to Rank with Partially-Labeled Data"<div class="posterous_autopost"><br /><div>I've been attending the University of Utah <a href="http://www.cs.utah.edu/~suresh/mediawiki/index.php/MLRG/fall10">Machine Learning semina</a>r (when I can) this fall. PhD student <a href="http://www.cs.utah.edu/~piyush/">Piyush Kumar Rai</a> is organizing it.</div> <p></p><div>I volunteered to take the group though <span style=""><a href="https://ssli.ee.washington.edu/people/duh/papers/sigir.pdf" title="https://ssli.ee.washington.edu/people/duh/papers/sigir.pdf" class="external text" rel="nofollow" style="text-decoration: none; color: rgb(51, 102, 187); background-image: ; background-color: initial; padding-right: 16px; background-position: 100% 50%;">Learning to Rank with Partially-Labeled Data</a> by Duh & Kirchhoff. I have some experience researching and implementing LTR algorithms, mostly using reinforcement learning or ant-system type approaches. Some general intro <a href="http://en.wikipedia.org/wiki/Learning_to_rank">here</a>.</span></div> <p></p><div><span style="">The paper presents the main <a href="http://en.wikipedia.org/wiki/Transduction_(machine_learning)">Transductive Learning</a> algorithm as a framework, then fills in the blanks with <a href="http://en.wikipedia.org/wiki/Kernel_principal_component_analysis">Kernel PCA</a> and <a href="http://jmlr.csail.mit.edu/papers/volume4/freund03a/freund03a.pdf">RankBoost</a>. Several Kernels are used: Linear, polynomial, radial basis function and knn-diffusion. RankBoost learns a kind of ensemble of 'weak learners' with simple thresholds.</span></div> <p></p><div><span style="">The main reason to read the paper if you are already familiar with LTR is the use of the transductive algorithm.</span></div> <p></p><div><span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-size: 16px; "><img src="http://posterous.com/getfile/files.posterous.com/nealrichter/LfPNH6yZ7w2ku6Nkuw2V647tJK9XAtUCRaWKSncqzxRHWRqTum5gNmPREX2u/Transductive.png" width="400" height="300" /></span></span></div> <p></p><div><span style="">Note the DISCOVER() & LEARN() functions. These are the unsupervised and supervised algorithm blanks they fill with Kernel PCA and RankBoost. What the first actually does is learn a function we could call EXTRACT() that can extract or create features for later use. They do show that the basic idea of layering in unlabeled data with labeled data is a net gain.</span></div> <p></p><div><span style="">There are some issues with the paper. First the computational time performance, as they admit, is not good. The other is that their use of Kernel PCA in an information retrieval context is a bit naive IMO. The IR literature is full of hard-won knowledge of extracting decent features from documents. See <a href="http://nlp.stanford.edu/IR-book/information-retrieval-book.html">this book</a> for example. This is mostly ignored here.</span></div> <p></p><div><span style="">The more confusing thing is the use of K-Nearest Neighbor diffusion kernels. Basically they take the vector of documents, form a matrix by euclidean distance and then random-walk the matrix for a set number of time-steps. The PCA then takes this 'kernel' output and solves the eigenvalue problem, to get the eigenvectors. This all seems a round-about way of saying they approximated the Perron-Frobenius eigenvector (sometimes call PageRank) by iterating the matrix a set number of times and zeroed out low order cells. Or at least I see no effective difference between what they did and what I just described. Basically they just make the matrix sparse to solve it easier (ie this is the dual).</span></div> <p></p><div><span style="">Their use of various classic IR features like TFIDF, BM25 etc needed help. There's pleny of IR wisdom on how to use such features, why let the DISCOVER() wander about attempting to rediscover this? The results were also muddled with only one of the three data sets showing a significant improvement over a baseline technique.</span></div> <p></p><div><span style="">All that aside, it's worth a read for the intro to the</span><span style=""> transductive alg used with an IR centric task.</span></div> <p style="font-size: 10px;"> <a href="http://posterous.com/">Posted via email</a> from <a href="http://nealrichter.posterous.com/review-of-learning-to-rank-with-partially-lab">nealrichter's posterous</a> </p> </div>Nealhttp://www.blogger.com/profile/06306714297735275545noreply@blogger.com0