<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Giovanni Fernandez-Kincade on Medium]]></title>
        <description><![CDATA[Stories by Giovanni Fernandez-Kincade on Medium]]></description>
        <link>https://medium.com/@giokincade?source=rss-9199bc6998f5------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*20XxmafqAj3ikjJ-xq6Lsw.png</url>
            <title>Stories by Giovanni Fernandez-Kincade on Medium</title>
            <link>https://medium.com/@giokincade?source=rss-9199bc6998f5------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 16:26:03 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@giokincade/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Intro to Opportunity Sizing]]></title>
            <link>https://medium.com/related-works-inc/intro-to-opportunity-sizing-ce9d7e5a29c4?source=rss-9199bc6998f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/ce9d7e5a29c4</guid>
            <category><![CDATA[product-management]]></category>
            <category><![CDATA[business]]></category>
            <category><![CDATA[ux]]></category>
            <category><![CDATA[analytics]]></category>
            <category><![CDATA[data]]></category>
            <dc:creator><![CDATA[Giovanni Fernandez-Kincade]]></dc:creator>
            <pubDate>Wed, 04 Dec 2019 15:06:38 GMT</pubDate>
            <atom:updated>2019-12-04T15:06:38.330Z</atom:updated>
            <content:encoded><![CDATA[<p>Or how to have a rational conversation about impact.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*OlQJgssueR7dtMSx" /><figcaption>Shirley Chisholm, the first black woman elected to Congress, consulting the data. <a href="https://www.loc.gov/item/2005676944/">Source: LOC</a></figcaption></figure><p>Opportunity Sizing is the act of giving a numeric value or range of values to the potential impact of some course of action:</p><ol><li>“If we build feature X, we will make $ZZ MM more dollars in yearly revenue”.</li><li>“If we can lower the cost of this drug by $XX, we will save ZZ million lives.”</li><li>“If we can switch to electric vehicles, we will prevent ZZ million tons in carbon emissions”.</li></ol><p>We regularly do Opportunity Sizing with our clients to help them figure out a product roadmap. The aforementioned examples were purposefully broad to help you understand that you can apply the same principles to any domain. We’ll focus on digital product development, since that’s the domain we typically operate in, and use examples from e-commerce since it’s well understood and approachable.</p><p>In this blog post we’re going to cover the basics of opportunity sizing, talk about why it’s important, and address some important objections to the practice.</p><h3>Turtleneck Tyranny</h3><p>The funny thing is you are probably already opportunity sizing, albeit in an implicit or intuitive way. Every business or organization makes decisions. At some point, someone decided that option X was the most impactful choice. Most organizations have some process they follow around making these decisions, but rarely do they involve doing math. The best and most common we’ve seen is teams assigning “t-shirt sizes” to potential impact. Even these “quantifications” mostly come down to the intuitions of decision makers or the ability of stakeholders to evangelize theirs.</p><p>The trouble with intuition-driven decision making is that even the intuitions of trained experts are frequently wrong or under-perform compared to simple statistical models [1]. <a href="https://hbr.org/2003/05/dont-trust-your-gut">Intuitions can be easily swayed by a number of subtle biases</a>, like the order of information available, the tendency to disregard or downplay competing evidence, or our intrinsic desire to pattern-match a new decision to our prior experience. Different stakeholders often have competing or inconsistent intuitions, and even the perspective of a single stakeholder can be noisy or change irrationally over time [2]. Living under this sort of regime can feel arbitrary and often tumultuous as different perspectives gain or lose favor. Maybe it works if you’re Steve Jobs, but most of us aren’t, and he didn’t seem like a great deal of fun to work with anyway.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*gdJSGJLtPTPUiJS1" /><figcaption><em>Living in an intuition-driven culture doesn’t seem like a ton of fun.</em></figcaption></figure><h3>A New Hope</h3><p>So that whole scheme sounds like a bummer. What’s the alternative? Let’s look at an example.</p><p>One of our clients has an e-commerce site where they sell clothing. They have a neat page, which we’ll call the Reorder Page, where you can explore previously purchased products, and then mix and match them to buy something new:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*YntanKR-vA218eBl" /><figcaption><em>The Reorder Page lets users browse past purchases to mix-and-match something new. Should we work on it?</em></figcaption></figure><p>Think the <a href="https://www.youtube.com/watch?v=XNDubWJU0aU">“clueless closet”</a>, except not quite as sophisticated as peak 90s technology. Undoubtedly a fun project, but was this really the right thing for a small team to invest in?</p><p>First, let’s understand what impact this page has on the business. Here’s a simple model: traffic arrives on the page, some of it converts to purchasing, spending some average order value:</p><blockquote>Traffic * Conversion Rate * Average Order Value (AOV) = Revenue ($)</blockquote><p>This may seem overly simplistic but we’ve seen models like this come pretty close to accurately predicting the revenue for an entire company.</p><p>If this project is successful, either users are more likely to purchase (i.e <em>Conversion Rate</em> raises) or they are likely to spend more money (i.e. <em>AOV</em> goes up). Let’s focus on the first scenario. We can model this by saying that we’ll make conversion on this page X% better (we’ll call this the <em>Lift</em>):</p><blockquote>Traffic * (Conversion Rate + <strong>Conversion Rate*Lift</strong>) * AOV = Revenue ($)</blockquote><p>If we want to isolate the value of our improvements, after some simple algebra:</p><blockquote>Traffic * Conversion Rate * Lift * AOV = Incremental Revenue ($)</blockquote><p>We can apply this same formula to any page in our theoretical e-commerce experience to understand the potential impact of UX improvements. Let’s say there’s a separate proposal to make improvements to the Home Page. Should we work on the Home Page or the Reorder Page? Here are some numbers we can use to round out our example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*qjCwM2udKtoE4aF4" /><figcaption><em>A simple model of two potential projects shows the Reorder Page has very little potential.</em></figcaption></figure><p>These are fake numbers but they were engineered to reflect trends we might expect on a typical e-commerce site. Most users encounter the Home Page, while very few users ever visit the Reorder Page. Users visiting the Reorder Page are probably quite engaged (they have, after all, purchased before), so they will convert at a higher rate and spend more money. The 5% <em>Lift</em> is our best guess for how much we could improve the UX on these pages.</p><p>According to this simple exercise, working on the Home Page has 30X more potential than working on the Reorder Page.</p><h3>Lies, Damn Lies, and Opportunity Sizing</h3><p>Just because we’re using numbers doesn’t mean this analysis is objectively true. There will always be uncertainty, interpretation and judgement. The difference is now we can be explicit about it:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*BnKsccAxMKv0AHWw" /><figcaption><em>As we share and discuss Opportunity Sizes, we can highlight the pieces we are uncertain about.</em></figcaption></figure><p>Most of the figures we used were ostensibly facts, but the <em>Lift</em> figures were a guess. As we share and discuss this analysis, we can highlight that this is a data point we’re not 100% certain about. In this way, Opp Sizing is more than just a tool for numerical reasoning. Opportunity Sizing is a framework we can use to have a principled conversation about impact.</p><p>If we feel particularly uncertain about a figure, we could prioritize getting more data. For instance, if this <em>Lift</em> figure is contentious, we could try reviewing the results of previous experiments. Have we ever shipped a 5% win? If not, perhaps this figure is a bit ambitious. If we’ve shipped 10–15% wins with some regularity, in similar circumstances, perhaps it’s too low.</p><p>Depending on the figure you have questions about, you could find more data by consulting your logs, data warehouse, industry research, surveying users, asking colleagues in the field, etc. The degree to which you want to spend effort getting better data depends on how uncertain you are, or how much the figure impacts your final opportunity size.</p><p>One of the great things about making a simple model is that you can easily play with the figures in a spreadsheet, or even model a range of options. For instance, here are two different scenarios for the Reorder Page:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Pq6mAoknKIntcXrh" /><figcaption><em>We can also model a range of outcomes for a project.</em></figcaption></figure><h3>The Good, the Bad, and the Average</h3><p>On that note, let’s say you really love the Reorder Page idea, and you think the 5%, and even the 10%, were really uncharitable. What if we made it 2X (100%) better?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*JURCzssQtokeelgu" /><figcaption><em>Even a HUGE lift isn’t enough to make the Reorder Page worthwhile.</em></figcaption></figure><p>This is a really striking conclusion. Even if we make a HUGE improvement to the Reorder Page, it still wouldn’t amount to comparably marginal improvements on the Home Page.</p><p>If you do this sort of analysis across all your ideas, you will likely find that some ideas simply have no hope, no matter how much you futz with the numbers, some look really promising, and the vast majority sit somewhere in between:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*-KoxpBFGGa08u7Uq" /><figcaption><em>Most opportunities will look average, a few will look pointless, and a handful will look massive.</em></figcaption></figure><p>Opportunity Sizing isn’t so much about making a precise forecast. It’s an estimate, usually done quickly, so it’s destined to be off by some margin. It’s really about creating this separation so it’s easier to make decisions. Ideally you should focus on the great ideas, and if you have extra bandwidth, take a gamble with some average projects.</p><h3>Recipe for Success</h3><p>Let’s think about <em>why</em> the Reorder Page doesn’t have much potential. Imagine for a moment if more users visited this page [3]:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*6lAFUkJ-pnfnXfXX" /><figcaption><em>The Reorder Page is bottlenecked by the lack of traffic.</em></figcaption></figure><p>Suddenly, this opportunity looks much more promising. Our bottleneck is traffic — no matter how much better we make the experience, there simply isn’t a big-enough audience to make it worthwhile.</p><p>Maybe instead of focusing on UX improvements, we can experiment with driving more traffic there (this is tricky, see [3]), or better yet, take this idea of driving repeat purchases and embed it throughout the mainline commerce experience so it has a bigger audience. We could, for instance:</p><ol><li>Make it easy to re-order from the Order History Page.</li><li>Email users that purchased something a while ago, ideally including products they may want to re-order.</li><li>Feature previously purchased items on the Home Page, Cart, or Product Details Pages.</li><li>Remind users they purchased an item on the Product Details Page.</li><li>Etc.</li></ol><p>In this way, Opportunity Sizing helps us understand the key ingredients to success, and potentially re-engineer ideas for impact. Often we’ll see teams focused on very specific, tactical ideas like “let’s fix the Reorder Page”. Going through this exercise helps them to zoom out and think about the bigger picture.</p><h3>Objections</h3><p>If you’re going to do this sort of thing it’s important to get everyone on the same page and supportive of the process. To that end, let’s discuss some possible objections to Opportunity Sizing.</p><p>The first, and most common, objection is this idea that <strong>you can’t quantify everything</strong>, or <strong>you can’t distill everything down to a single number.</strong> First, we should say, you would be surprised at the number of complex and philosophical ideas that people, especially governments and insurance companies, have quantified:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*FqeBYzfBnwiXT2er" /><figcaption><em>You’d be surprised by the things that people have found ways to quantify.</em></figcaption></figure><p>That being said, we agree. To re-frame the conversation a bit, we would say <strong>not everything you do should be about numbers. Some things you should do just because you believe in them.</strong> For instance, we are huge believers that the details matter, especially when it comes to a clear, smooth, and professional UX. Most of this “polish” would never show up on the map in terms of an opportunity sizing analysis, but over time, and across an experience, the little bits start adding up.</p><p>Every organization has goals, be it selling more clothing or saving more children from malnutrition. If your organization wants to actually affect that outcome, it’s probably measuring it in some way. We’re not suggesting every single initiative on your roadmap should be tied to that singular number. We’re suggesting that you spend enough time on the things that <em>do</em> affect that number, so you can confidently make space on your roadmap for the things you want to do for other reasons. In other words, maybe spend 80% of your time on the high-impact, numbers-driven projects, and spend 20% of your time on polish.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*wMgI-THc6x3I0JMM" /><figcaption><em>It’s ok to work on polish, let’s just make sure we’re spending most of our time on impact.</em></figcaption></figure><p>A related objection is that <strong>being driven by numbers can often have unintended consequences that are actively harmful to users or society at large</strong>. As the world becomes increasingly skeptical of the data-driven tech platforms that dominate our daily lives, it’s hard to argue with this perspective. This is a complex subject that we hope to write about more deeply some day, but for starters, we think the problem here isn’t necessarily the use of numbers, so much as the near-singular focus on one number (i.e. money) or a small set of myopic numbers (e.g. time-on-site, retweets, likes, replies, etc). If we’re concerned about our impact on users’ lives, and we should be, then we should try to measure it, gauge the potential impact of new projects on it, and take that potential impact into account in our decision-making process. Nothing is stopping us from using data for <em>good </em>(except maybe capitalism).</p><p>The last objection people usually have is “<strong>I’m bad at math!”</strong>.<strong> </strong>We’ve seen all sorts of folks do Opportunity Sizing, be it Sales, Marketing, Support, Design, Engineering, etc. If you can do simple math with two numbers, and you’ve ever written a formula in a spreadsheet, you can do this. It’s easier to do as a group, which can be a fun and educational way for a team to create a shared roadmap. There are obviously more complex modelling choices that require more advanced skills. But you’d be surprised by how far you can get with simple techniques.</p><h3>Coming Up</h3><p>We hope that was fun and approachable. In future posts, we’ll go over more complex examples, talk about rules of thumb, and share lessons learned after doing this across a number of companies. If you want help with Opportunity Sizing, or just want to learn more about <a href="https://www.relatedworks.io/">Related Works</a>, say <a href="/service/mailto:hello@relatedworks.io">hello@relatedworks.io</a>.</p><h3>Acknowledgements &amp; Further Reading</h3><p>This blog post and our perspective on Opportunity Sizing is deeply indebted to the work of <a href="https://mcfunley.com/">Dan Mckinley</a>. <a href="http://datadriven.club/">Datadriven.club</a> is Dan’s seminal take on the same subject matter. I had the good fortune of working with Dan and a lot of his good ideas rubbed off on me. Thankfully, flannel wasn’t one of them.</p><p>It’s also partially inspired by the book <a href="https://www.amazon.com/How-Measure-Anything-Intangibles-Business-ebook/dp/B00INUYS2U">How to Measure Anything</a> by Douglas Hubbard, which is akin to a crash course in quantitative <a href="https://en.wikipedia.org/wiki/Decision_analysis">decision analysis</a>. We love Hubbard’s work and methodology, but we’re trying to take some of these ideas and make them a bit more approachable for the average human. If most folks are operating in an intuition-driven culture, introducing even the simplest modeling is a giant leap forward.</p><h3>End Notes</h3><p>[1] — Meehl, P. E. (1954). Clinical vs. statistical prediction: A theoretical analysis and a review of the evidence. Minneapolis: University of Minnesota Press.</p><p>[2] — Goldberg, L. R. (1970). Man versus model of man: A rationale, plus some evidence, for a method of improving on clinical inferences. Psycholog- ical Bulletin, 73, 422–432.</p><p>[3] — We’re talking about driving traffic to highlight the bottleneck in this opportunity. If you were to actually drive more traffic to the Reorder Page, it would almost certainly convert at a lower rate. The visitors that are currently finding the page are fairly determined, since they found an odd corner in the experience, and thus probably have a great deal more engagement and purchase intent. The incremental visitors you would receive from increased exposure are likely to have less intent. This is a form of <em>Selection Bias</em>, which we’ll delve into more deeply in future posts.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ce9d7e5a29c4" width="1" height="1" alt=""><hr><p><a href="https://medium.com/related-works-inc/intro-to-opportunity-sizing-ce9d7e5a29c4">Intro to Opportunity Sizing</a> was originally published in <a href="https://medium.com/related-works-inc">Related Works</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Using Simple Arithmetic to Fill Gaps in Categorical Data]]></title>
            <link>https://medium.com/related-works-inc/using-simple-arithmetic-to-fill-gaps-in-categorical-data-9418e5c0b91b?source=rss-9199bc6998f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/9418e5c0b91b</guid>
            <category><![CDATA[data]]></category>
            <category><![CDATA[open-data]]></category>
            <category><![CDATA[privacy]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Giovanni Fernandez-Kincade]]></dc:creator>
            <pubDate>Wed, 25 Jul 2018 20:13:34 GMT</pubDate>
            <atom:updated>2018-07-25T20:14:15.634Z</atom:updated>
            <content:encoded><![CDATA[<h3>And potentially circumventing privacy protections in the process.</h3><p>One of our clients is using employment figures from the <a href="https://www.bls.gov/">Bureau of Labor Statistics</a> (BLS) in a machine learning model we’re helping them build. We recently noticed that there are frequently gaps in the data:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*IdS-aG6ti37ctuZB" /><figcaption><em>BLS Employment Data for Phoenix, Arizona is missing data for Oilseed and Corn Farming, among other industries.</em></figcaption></figure><p>It turns out that if a particular combination of Industry and Geography, like Corn Farming in Phoenix, has a small number of establishments (places of employment), the <a href="https://www.bls.gov/qcew/cewover.htm#Confidentiality">BLS will suppress data for that Industry+Geography</a>, in order to protect the confidential data about the firms there. Otherwise you could do things like figure out how many employees a private competitor has and how much they are paying them on average.</p><p>While this makes sense in the abstract, it makes the data tremendously difficult to use. Imagine a small town that has a single large employer, like a private hospital or university. They are a critical part of the local economy, but the BLS can tell you nothing about them! What if you want to calculate year-over-year growth rates to see which industries are up-and-coming in a particular geography? If healthcare jobs were suppressed last year, there’s no way for you to know how much they’ve grown even if the figures are published this year!</p><p>Suppressed categorical data is a common problem with public datasets. <a href="https://en.wikipedia.org/wiki/Iterative_proportional_fitting">Iterative proportional fitting</a> (IPF) is a dead-simple numeric technique you can use to fill gaps like these.</p><h3>Walk-through</h3><p>We can use IPF if we have data we can organize in a matrix or table, and we have row totals and column totals. In the BLS example, this might look like (this is a fictional example, and the missing value is 8):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Ox6J820Ub35Tu5Ba" /><figcaption><em>To perform IPF we need a two-dimensional table of data with row and column totals.</em></figcaption></figure><p>The column totals in this toy example would be the total number of jobs in a given industry in the state of New York, and the row totals would be the total number of jobs in each city.</p><p>We start by taking a guess for the value in each gap. You can try to leverage other data sources to take an informed guess, or just select one randomly. We’ll call these guesses <em>seeds.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*dvSZiE3c5h4zhuvw" /><figcaption><em>Seed each gap with a random guess.</em></figcaption></figure><p>For each row, we’ll calculate the current total. Then we’ll divide each seed by the current row total to turn it into a proportion:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*DEF8qbTYZuodLpue" /><figcaption><em>Divide the seed by the current row total to turn it into a proportion.</em></figcaption></figure><p>Then we’ll multiply each proportion by the true row total:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*PlfDYZ9PSVH0WEUd" /><figcaption><em>Now we multiply proportion with the true row total.</em></figcaption></figure><p>Congrats! We’ve successfully nudged our initial guess closer towards the missing value (8). Now perform the same operation for each column:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*vT28ErpEVCPql3ip" /><figcaption><em>Then we’ll perform the same operation for each column.</em></figcaption></figure><p>That completes one iteration. Just repeat the process until it converges (i.e. the seeds stop changing). To summarize:</p><ol><li>Seed each missing value with a guess.</li><li>For each row, adjust the seeds to be proportions of the current row total.</li><li>Multiply each proportion by the true row total.</li><li>For each column, perform #2 and #3.</li><li>Go to #2 until you converge.</li></ol><p>If you need whole numbers (like in the case of jobs), you’ll need to do a little rounding once you’re all done.</p><h3>Let’s try it!</h3><p>First let’s generate some fake data:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c492126d67f2691459fbd2b866054c2b/href">https://medium.com/media/c492126d67f2691459fbd2b866054c2b/href</a></iframe><p>To simulate confidentiality policies like the BLS’, we’ll remove any data that is less than 10.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3e637a9c692848a87784fc6c8be29149/href">https://medium.com/media/3e637a9c692848a87784fc6c8be29149/href</a></iframe><p>Now we’ll initialize each gap with a random seed between 1 and 10:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c6c1ddae31f77004c7ddbaff09ce4d02/href">https://medium.com/media/c6c1ddae31f77004c7ddbaff09ce4d02/href</a></iframe><p>To see how well IPF works, we can compare our final result for each gap to the original values we removed. Here’s a graph of the absolute errors (i.e. abs(actual — random_seed)):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/890/0*bOUTip2jxDgZZ1Bh" /><figcaption><em>The distribution of errors of our random seeds.</em></figcaption></figure><p>On average, our random guesses are off by 2.5, though you can see some outliers that are much worse. How much closer can IPF get us?</p><p>Here’s what the whole thing looks like:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/74775d392b5cc279252676ec2a2f0402/href">https://medium.com/media/74775d392b5cc279252676ec2a2f0402/href</a></iframe><p>After ~30k iterations, our error looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/890/0*m4s4FkHmqG57B08-" /></figure><p>The average seed is within 0.4 of its actual value. Pretty rad for 25 lines of code and ~30k iterations.</p><h3>Intuitions</h3><p>You can think of this process as solving <a href="https://en.wikipedia.org/wiki/System_of_equations">a system of equations</a>. The row and column totals are giving you constraints you can use to solve for the missing values. If there are too many missing values, it’s possible you won’t be able to converge [2].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/911/0*vNn9ELSjSDvGSKf1" /><figcaption><em>The number of iterations needed increases with the number of missing values. This experiment was capped at 50K max iterations. Generally we were able to converge on up to 1% missing values in a 100x100 matrix.</em></figcaption></figure><p>You can also do this in more than two dimensions, assuming you have totals along those additional dimensions. For instance, imagine having employment figures broken down by a combination of industry, geography, and race. Each additional dimension gives you another constraint to triangulate against, and thus potentially improves your fit.</p><h3>Ethical Ruminations</h3><p>In 2007, <a href="https://en.wikipedia.org/wiki/Netflix_Prize#Privacy_concerns">researchers were able to de-anonymize individual users in the Netflix Prize dataset by linking movie ratings on Netflix to public data on IMDB</a>. This is yet another reminder that even if you take pains to protect the privacy of your users, there is potential for sufficiently motivated parties to break your privacy protections in new and interesting ways. In this case, it’s not even particularly difficult. <a href="http://www.economicmodeling.com/2008/05/27/data-qa-emsi-data-and-public-lmi/">There are companies that have been selling de-suppressed versions of BLS data on the market for years</a> (presumably leveraging techniques like IPF) [3].</p><p>There is undeniably tension between protecting the privacy of users (or in this case, companies) and making data usable for statistics, machine learning, and transparency. As it stands, leveraging BLS data to do anything interesting is remarkably difficult (ironic for an organization whose <em>raison d’etre</em> is publishing data for people to analyze).</p><p>As we enter the GDPR Era and try to recover from the jaw-dropping disclosures of how tech companies like Facebook have grossly abused our trust, navigating this tension has never been more important. But I don’t think the solution is to stop disclosing information, either publically, or within our organizations. Doing so would be akin to deciding in 1900 that the whole “industrial revolution” thing really isn’t for us and and turning back to horse-drawn carriages.</p><p><a href="https://en.wikipedia.org/wiki/Differential_Privacy">Differential Privacy</a> is a field focused on the idea that you can introduce noise into a dataset, such that it’s provably impossible to know anything about a particular individual or data point, but you can still leverage the dataset in aggregate. I can imagine a scheme where rather than suppressing figures, noise is introduced to BLS data such that the confidentiality of individual firms is protected, but the data is still usable for time-series analysis. <a href="https://www.wired.com/2016/06/apples-differential-privacy-collecting-data/">Apple’s embrace of this approach</a> [4] gives me hope, but it’s still early days, and it’s not clear that their techniques will be directly applicable to data at the BLS’ much smaller scale, and fairly different set of analytic requirements.</p><p>Ultimately, I think we’ll need to pour way more resources into these sorts of problems if we hope to live in a just <strong>and</strong> data-empowered world.</p><h3>End Notes &amp; Thanks</h3><p>Many thanks to <a href="https://medium.com/u/ceeb00afdff0">Nishan Subedi</a> for careful reading and feedback.</p><p>[1] — IPF is typically concerned with adjusting <em>all</em> the cells in the matrix wrt to column/row totals, and there are many different strategies for seeding cells. This blog post presents a variant where we hold known/true values constant, and only adjust unknown values.</p><p>[2] — Because we’re doing a weird variant of IPF, it’s not clear that <a href="https://en.wikipedia.org/wiki/Iterative_proportional_fitting#Existence_and_uniqueness_of_MLEs">typical assertions about convergence apply</a>.</p><p>[3] — In the BLS’ defense, they have <a href="https://www.bls.gov/osmr/pdf/st040100.pdf">used software to audit the feasibility of re-generating suppressed data</a>, and in those tests found that no suppressed cells could be regenerated within 20% of their true values. In all likelihood, the feasibility of using IPF-like techniques for BLS data depends highly on your choice of seeds, your ability to leverage other datasets for seeds, or your level of error tolerance.</p><p>[4] — Great nuts and bolts blog post <a href="https://machinelearning.apple.com/2017/12/06/learning-with-privacy-at-scale.html">here</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9418e5c0b91b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/related-works-inc/using-simple-arithmetic-to-fill-gaps-in-categorical-data-9418e5c0b91b">Using Simple Arithmetic to Fill Gaps in Categorical Data</a> was originally published in <a href="https://medium.com/related-works-inc">Related Works</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Autosuggest Ranking]]></title>
            <link>https://medium.com/related-works-inc/autosuggest-ranking-d8a3242c2837?source=rss-9199bc6998f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/d8a3242c2837</guid>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[information-retrieval]]></category>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Giovanni Fernandez-Kincade]]></dc:creator>
            <pubDate>Wed, 18 Apr 2018 13:39:28 GMT</pubDate>
            <atom:updated>2018-04-18T13:39:28.614Z</atom:updated>
            <content:encoded><![CDATA[<h4>Supercharge your search box with Statistics, Supervised Learning, Bayesian Inference, PCA, Clustering, Word Embeddings, and more! Oh my!</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6phD8sgoNHMTwidfmKbMCA.jpeg" /><figcaption>Ebisu, Japanese god of luck, hard at work ranking your fortune. <a href="https://www.loc.gov/resource/jpd.00274/">Source</a>.</figcaption></figure><p>In the <a href="https://medium.com/related-works-inc/autosuggest-retrieval-data-structures-algorithms-3a902c74ffc8">last post </a>we talked about retrieval: given a prefix, producing a list of candidate suggestions that we can offer to users in a search box. In this post, we’ll talk about ordering this list of candidates.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*l-wA6tJQPI-BJe3L." /><figcaption>After the retrieval phase returns a set of candidate suggestions, we apply a ranking algorithm to resort them.</figcaption></figure><p>In practice, most production systems rank in two phases. The first phase is usually very cheap and may be based on a single static score or a handful of factors. It’s often part of the retrieval pass. A second phase of ranking is then performed on the top N, usually leveraging more complex models and a larger set of features. Often this second phase is when personalization is incorporated.</p><p>Where the line is drawn between the two is a function of performance and technology. It’s usually too expensive to perform complex ranking on a large set of candidates, e.g. the full set of suggestions that start with a short prefix like “b”. That first phase of ranking is usually happening inside a generalized search engine like Solr or Elasticsearch, and it’s difficult to run arbitrary code in those contexts. Further, if you are performing retrieval using a system that supports <em>early termination</em>, like the <a href="https://en.wikipedia.org/wiki/Finite-state_transducer">Finite State Transducers</a> (FSTs) we discussed in the <a href="https://medium.com/related-works-inc/autosuggest-retrieval-data-structures-algorithms-3a902c74ffc8">previous post</a>, it’s tremendously advantageous to leverage a static score during the first pass.</p><h3>Goals</h3><p>As we discussed in the <a href="https://medium.com/related-works-inc/bootstrapping-autosuggest-c1ca3edaf1eb">first post</a> from this series, the goals of an autosuggest system are usually a mixture of prediction and performance. We want to suggest queries that users are likely to accept, but we should make sure users are going to have an engaging experience if they issue those queries. Suggesting a very probable query that has no results, for instance, is a tremendous bummer.</p><p>As we talk about optimizing ranking, you can conceptualize the task as finding some ordering that maximizes the right blend of prediction and performance for you. Or you can simply try to enforce some minimum threshold of performance (e.g. filter out any queries that yielded no results), and focus on prediction. There’s a lot of ground to cover on the prediction side, so we’ll assume that strategy and focus on prediction for the sake of this conversation.</p><h3>Two Paths</h3><p>Practically speaking we’re talking about designing a <strong>ranking function</strong>, which takes a prefix, a suggestion, and provides a numeric score we can sort by (usually descending):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5f7004d3cdeaa498392324ac9085aec0/href">https://medium.com/media/5f7004d3cdeaa498392324ac9085aec0/href</a></iframe><p>There are other ways to design the problem, but this framing is common. From a prediction perspective, you can think of the objective as estimating the probability P(suggestion|prefix). A simple estimate of that probability might look like:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*ykNxP2jziO8qHfrZ." /><figcaption>A simple calculation of the probability of a query given a prefix.</figcaption></figure><p>Every candidate suggestion will have the same denominator, so essentially we’re sorting by popularity, which turns out to be a surprisingly effective baseline, and a good choice for static scores used in first-pass ranking. If you don’t have query logs you can start by measuring popularity in your corpus of documents [1].</p><p>Of course, popularity isn’t everything. We’re not considering, for instance, how probable a query is for a given <em>user</em>. What if everyone is into “high waisted shorts” but you typed “h” because you really wanted a “hootie and the blowfish t-shirt”? If we really want to get you that Hootie, our job is to come up with a richer estimate of this probability.</p><p>A <strong>probabilistic </strong>approach to the ranking problem tries to calculate these probabilities directly based on observed data, or often leverages a <a href="https://en.wikipedia.org/wiki/Statistical_model">statistical model</a> to estimate them. The popularity approach described above falls into this category.</p><p>You can also formulate this as a <strong>supervised learning</strong> problem. This might take the form of training a binary classifier with (prefix + suggestion, label) pairs, like (“h” + “harry potter”, 1) or (“h” + “hella cool”, 0). The implication is that “harry potter” is a good suggestion for the prefix “h” , and “hella cool” isn’t. After showing the model a ton of these examples, it will learn to separate one class from the other, and given a new prefix + suggestion, it will generate a numeric value for how good or bad it is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fpmIpjFZIo3PC-7UKdYDZg.jpeg" /><figcaption>An example LTR model takes as input a prefix, a suggestion, and produces a numeric score we can use to rank.</figcaption></figure><p>The application of supervised learning to ranking is often called <a href="https://en.wikipedia.org/wiki/Learning_to_rank"><strong>Learning to Rank (LTR)</strong></a>.</p><p>Usually training data is harvested from user behavior. Say a user issued the query “hella”. For each prefix of “hella” we would create a positive example associated with that query, so [(“h” + “hella”, 1), (“he” + “hella”, 1), (“hel” + “hella”, 1), …]. For each prefix, we might retrieve the set of candidates from our first-pass system and use them as negative examples. So for instance, if “hello” was a candidate for “h”, we would generate the training instance (“h” + “hello”, 0)[2].</p><p>Typically you don’t literally give the model the prefix and suggestion — you show the model a vector of <em>features</em> about the two. You can include features about the prefix (how long was it?), about the suggestion (how popular is it?), about their intersection (what’s the edit distance between the two?), and about the context within which the suggestion was shown (what time of year is it? What was the user’s geographic location?). A feature vector might look like this: {prefix_length: 2, suggestion_volume: 200, edit_distance: 10, ….}.</p><p>Both the probabilistic and LTR approaches end up utilizing a lot of the same factors, and contextual features are the most popular, so that’s what we’ll focus on for the remainder of this post.</p><p>Generally a probabilistic approach is easier to get started with, has intuitive explanations, and requires less data. LTR may ultimately yield better performance at the cost of complexity and possibly opacity. The other big advantage of LTR is that it’s straightforward to incorporate many factors in a principled way — just add them to your feature vector.</p><h3>Query Logs, User Data, &amp; Privacy</h3><p>In a <a href="https://medium.com/related-works-inc/building-an-autosuggest-corpus-part-1-3acd26056708">previous post</a>, we discussed the decision between using query logs or documents as the source for your corpus of suggestions. Even if you chose documents, you can still leverage query logs to inform suggestion ranking.</p><p>A lot of the research and techniques we’ll discuss today depend on query logs. It’s hard to predict when you have nothing to predict against. But as the world learns about the crimes of Cambridge Analytica and the tech industry braces for the impact of GDPR, it would behoove us to address the responsibility we have while leveraging user data for a project like this. You should give users <strong>transparency</strong> (i.e. inform them how their data is being used) and <strong>control</strong> (i.e. give them the ability to decide how or whether or not their data is used). You need to make sure their data is securely stored with access restrictions, auditing, and you should offer them the <strong>right to be forgotten</strong>. Addressing this in a comprehensive way is beyond the scope of this post, but suffice to say it’s something you should be thinking about.</p><h3>Time Features</h3><p>When we talked about sorting by popularity, there was implicitly some notion of <em>time.</em> Are we talking about popularity across all time? The last month? Some other time-frame?</p><p>We’re trying to predict the probability P(suggestion|prefix), ideally at the moment the user is typing the prefix, which will be at some point in the future after we’ve designed/trained our ranking function. Essentially, we’re trying to <a href="https://en.wikipedia.org/wiki/Forecasting"><strong>forecast</strong></a> the future volume of a given suggestion, and there’s a large body of statistical techniques we can draw from to accomplish this.</p><h4>Recency</h4><p><strong><em>Recency</em> </strong>refers to the idea that recent events are more important than the distant past, or that they are better indicators of the future. A year ago “Colin Powell”, “Colin Kaepernick”, and “Card B”, had virtually indistinguishable query volumes, but these days Cardi B is reigning queen:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*b_xTm8VeBKSnSH35." /><figcaption><em>Plotting the Google query volume of “Cardi B”, “Colin Kaepernick”, and “Colin Powell”. You can tell who’s making money moves.</em></figcaption></figure><p>How quickly things turnover depends highly on the nature of your product. Twitter trends change on the order of minutes or hours, but even slower-paced products tend to have recency-effects. You can think of Twitter’s original feed algorithm of sorting by time-descending as wholeheartedly embracing recency as a signal.</p><p>An easy way to incorporate recency is to only consider the popularity of queries in the recent past (say the last month or two). But by doing so, we would be throwing away all of the valuable data we have about long-term trends. How do we find a balance between recent events and the past?</p><p>A common approach is to use an <a href="https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average">exponential moving average</a> or exponential smoothing[3]. The idea is pretty simple:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/652/0*z8_SLAJlwsQiTQeK." /><figcaption>The formula for computing an exponential moving average. It’s recursive!</figcaption></figure><p><em>St</em> is the smoothed (people also use the term estimated or forecasted) query volume at time <em>t </em>. Time is defined as equal-sized steps, say days, months, or years. So if our steps were months, <em>t=5</em> would mean the fifth month since the beginning of our history. <em>Yt </em>is the observed query volume at a given time step. Notice that <em>St</em> is recursive, i.e. it depends on <em>St-1</em>, so our current estimate depends on the previous estimate, which depends on the penultimate estimate, and so on until the start of time. We’re essentially encoding the idea of <em>recency</em> by giving every step backwards in time exponentially less impact on the current estimate, by a factor of <em>(1-α)</em>. <em>α</em> is a parameter between 0 and 1 that lets us trade off between recent trends and the past. The higher the <em>α</em>, the more important recent events are.</p><p>How do you choose an <em>α</em>? You can try out a few values and see which one yields an <em>St</em> that’s close to the observed values <em>Yt</em>. This can be quantified using a number of metrics including the <a href="https://en.wikipedia.org/wiki/Residual_sum_of_squares"><strong>Sum of Squared Errors (SSE)</strong></a><strong>. </strong>There are also <a href="https://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm">optimization techniques</a> you can use rather than manually trying a bunch of <em>α</em>’s.</p><p>Once you’ve tuned <em>α</em>, you can use <em>St</em> in place of query volume to calculate your probabilities:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ypHA9DZQ-QdHbj47kqDVCw.jpeg" /><figcaption>Using predicted query volume to compute suggestion probabilities.</figcaption></figure><h4>Seasonality</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*TUNXWxda26DXIkEl." /><figcaption><em>Plotting the Google search volume of “mothers day” against “mugs”.</em></figcaption></figure><p><strong><em>Seasonality</em></strong> is another important temporal feature that is often useful in ranking functions. If you’re running an e-commerce shop, and it’s almost Mother’s Day, you might want to show folks more Mom stuff. Seasonality can operate on many time scales — holidays occur on yearly cycles, but you could just as easily observe monthly trends (people tend to move on the first of the month), weekly trends (<a href="https://blog.mozilla.org/metrics/2007/10/10/firefox-usage-%E2%80%93-does-the-day-of-week-have-an-effect/">people browse on desktop less on weekends</a>), etc. Again what’s important really depends on your users.</p><p>To model this you could use <a href="https://en.wikipedia.org/wiki/Exponential_smoothing#Triple_exponential_smoothing">triple-exponential smoothing</a>[3], which really just builds on vanilla exponential smoothing to incorporate an estimate for the seasonality on a predetermined time-scale (yearly, monthly, etc). Going over that in detail is beyond the scope of this blog post, but <a href="https://grisha.org/blog/2016/01/29/triple-exponential-smoothing-forecasting/">here’s</a> an AMAZING walk-through.</p><p>Again you can use these smoothed volumes directly to estimate your suggestion probabilities.</p><h4>LTR</h4><p>If you’re taking an LTR approach, it’s easy to just incorporate raw volume figures for different time scales as model features, e.g. {volume_last_month:200, volume_last_year:150, volume_this_month_last_year: 300, …}. But if you take the time to model recency or seasonality effects, it’s often effective to incorporate the predicted volume as a feature[4]. Probably because you’ve gone through the trouble of modeling the temporal aspects directly and finding good parameters, so the model doesn’t have to do that while juggling a ton of other factors.</p><h3>User Features</h3><p>As we alluded to earlier, which query a user is likely to issue is widely different for different types of users. So it shouldn’t be surprising that user-based features are some of the most effective you can leverage in an autosuggest ranking function.</p><h4>Demographics</h4><p>Folks will often start on user-features by looking at <strong>demographics</strong> — coarser level criteria that group together lots of users like location, gender, device-type, etc.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/932/1*xOxQg6S7JbmcDOZTHzuZiA.png" /><figcaption>The probabilities of issuing the queries “imdb” versus “instagram” on Yahoo, broken down by age and gender. [2]</figcaption></figure><p><a href="https://en.wikipedia.org/wiki/Thanksgiving_(Canada)">Canadian Thanksgiving</a> (eh!) is in October, while <a href="https://en.wikipedia.org/wiki/Thanksgiving_(United_States)">American Thanksgiving</a> is in November. It’s particularly popular to use coarse location (city, country, etc) as a feature because it can be extracted from <a href="https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/Accept-Language">HTTP headers </a>or <a href="https://en.wikipedia.org/wiki/Geolocation_software">inferred from IP addresses</a> (<a href="https://www.conversionworks.co.uk/blog/2017/05/19/anonymize-ip-geo-impact-test/">while still being privacy-friendly</a>), so you don’t need rich user profiles, and it’s a signal that can help you separate local tastes, trends, and seasonal effects like when to show that Thanksgiving stuff.</p><p>If you’re taking a probabilistic approach you can simply segment your probabilities or forecasts by demographic. So if the user is in the US, only look at US query volume. Or you can combine this segmented probability with global trends using <a href="https://en.wikipedia.org/wiki/Bayes%27_theorem">Bayes rule</a>. We can treat our previously estimated probability (perhaps using temporal modeling) for the query “foo” as our <em>prior </em>probability P(“foo”), and we will now compute a <em>posterior</em> probability of the query “foo” given the user’s location is the USA, P(“foo”|USA):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Ykb1pUywcbDGjhe0." /><figcaption>Combining global suggestion probabilities with location-specific probabilities using Bayes Rule.</figcaption></figure><p>In this manner you can incrementally incorporate new factors in a principled way. Simply take your previous estimate for a query, treat it as the prior, and then apply Bayes rule using the new evidence. This is often called performing a <a href="http://www.statisticalengineering.com/bayesian.htm">Bayesian Update</a>.</p><p>You will almost certainly run into situations where you get probabilities of zero — e.g. the query “foo” was never issued in Estonia. Zeros are a bad trip because they unreasonably discard the information in your prior. It’s not that a user in Estonia would never issue the query “foo”, you probably just don’t have enough traffic from Estonia to know. Realistically, the probability isn’t zero, it’s probably some small number we don’t have enough information to accurately estimate. Instead, you can use <a href="https://en.wikipedia.org/wiki/Additive_smoothing">probability smoothing</a>, which just turns those zeros into really small numbers.</p><p>On the LTR side of the equation, the most straightforward way of including user demographics is to make demographic-specific versions of existing features. So for instance if a query was issued globally 500 times, and was issued 200 times in the user’s location, you might up with something like {global_query_volume: 500, local_query_volume: 200…}.</p><h4>Behavior</h4><p>The next step in sophistication is considering how users behave in your product and using those signals to inflect your ranking function. This family of signals is naturally the most privacy antagonistic, so you should proceed with caution.</p><p>I would start by clustering users based on behavior — i.e. creating behavior-based demographics. For instance, you could create a giant matrix where the rows are users, and the columns are the terms from your inventory. Initially the matrix is all zeros. For each item a user interacted with, set the terms from that item to 1 for that user’s row:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*BHE_vvD6VPRMzcA1." /><figcaption><em>A user-term matrix, which we’ll decompose and use to create user-clusters. Ara is apparently the only user into “camo”.</em></figcaption></figure><p>This is similar to a typical setup <a href="https://en.wikipedia.org/wiki/Collaborative_filtering">for collaborative filtering</a>. If you have <em>V</em> terms in your vocabulary, you have a <em>V</em>-dimensional representation of a user. That’s probably very large and very sparse. You can use dimensionality-reduction techniques, like <a href="https://en.wikipedia.org/wiki/Principal_component_analysis">Principal Component Analysis (PCA)</a> to project this representation down to a smaller space with say few hundred dimensions. Now with this much more compact representation of users, you can cluster them using something like <a href="https://en.wikipedia.org/wiki/K-means_clustering">K-Means Clustering</a>. The cluster a user belongs to can become a demographic that you segment by, use to update your probabilities, or use in cluster-specific model features , e.g. { user_cluster_query_volume: 500 }. These clusters should end up representing broad interests like separating folks that like “boho chic” from the people into “athleisure”.</p><p>You can just as easily look at query-terms instead of looking at item-terms (and a number of other dimensions). Both might be useful but the later, not surprisingly, tends to have more data you can leverage.</p><p>A more direct and personalized approach is to compute some measure of the similarity between a query and a user’s past behavior. A simple place to start is computing the ratio of query terms that were present in the user’s past queries:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*-mzUB6IbK7JYaBeO." /><figcaption>A simple similarity measure is the ratio of terms in a suggestion that were present in a user’s history.</figcaption></figure><p>So for the query “harry potter tshirt”, if the user has searched for “harry potter” before but never “t-shirt”, the ratio would be ⅔. You can also compute a similar ratio using <a href="https://en.wikipedia.org/wiki/N-gram">n-grams</a> instead.</p><p>You can use this measure directly as your ranking function, which would be more of a heuristic approach, or incorporate it into your LTR model, e.g. { user_history_n_gram_similarity: 0.082 }.</p><p>You can consider the user’s history across a number of time frames — across all history, recent behavior, within the same <a href="https://en.wikipedia.org/wiki/Session_(web_analytics)">session</a>, etc. Often users will slowly evolve their query by looking at results and adding or removing terms from the query, a process called <a href="http://searchuserinterfaces.com/book/sui_ch6_reformulation.html">query reformulation</a>. Through this process the user is learning the language of what’s available, and is learning the ins and outs of your search engine. Looking at in-session behavior allows you to pick up on query reformulation, but carries the danger that you will put too much stock in recent behavior and not understand when a user is changing directions completely.</p><h3>Combining Queries</h3><p>We briefly mentioned the problem of data sparsity. This is particularly troublesome for autosuggest because search is a <a href="https://en.wikipedia.org/wiki/Long_tail">long-tail game</a>. While there is often a head of very popular queries, there is an enormous set of queries that are only ever issued a handful of times. For instance, on Etsy “harry potter” was a very popular query, but you can imagine that “harry potter t-shirt size small red” was very rare by comparison.</p><p>Rarity is difficult because it means our probabilities for that suggestion will be close to zero, or our LTR models will rarely see that suggestion. Yet those long-tail queries might be precisely what the user is looking for, especially in the midst of query reformulation.</p><p>Just as we clustered users, it can be useful to group together queries so we can share information about them, e.g. {query_cluster_volume_last_month: 1500}[6]. This can give long-tail queries an extra boost, and when combined with in-session personalization, can be powerful a mechanism to aid query reformulation.</p><p>If you can generate a vector representation or embedding for a query, you can simply run a clustering algorithm in that space to generate query clusters. The most obvious choices are:</p><ol><li><strong>PCA</strong> — You could perform a matrix decomposition (similar to what we did earlier with users and items) where the rows are queries and the columns are users that issued them, the terms in the queries, or the items that were shown or interacted with.</li><li><strong>Neural Query Embeddings </strong>— You could leverage word vectors from a neural network model like <a href="https://en.wikipedia.org/wiki/Word2vec">word2vec</a> or <a href="https://nlp.stanford.edu/projects/glove/">GLoVe</a>, pre-trained or trained on your own query corpus. If a query has multiple terms the most straightforward way to generate a query-level embedding is to sum or average the vectors for each term in the query, but there are more principled approaches (like <a href="https://github.com/facebookresearch/StarSpace">Facebook’s StarSpace</a>).</li></ol><p>You could also group queries by:</p><ol><li><strong>Term Co-Occurrence — </strong>You could treat any queries that share at least one term as a cluster. This is roughly equivalent to doing PCA with query terms as the columns.</li><li><strong>Query Classifications — </strong>It’s often useful to classify queries into broad classes of inventory that the user might be interested in like “Clothing” vs “Furniture”. Query classifiers are useful for ranking, disambiguation, etc. If you happen to have a query classifier, this might be a useful grouping mechanism to experiment with.</li></ol><h3>Coming Up</h3><p>Phew! That was a lot. I hope this whirlwind tour of autosuggest ranking was interesting, though I’m sure it can feel overwhelming. The best place to start is just using query popularity across a fixed time range. That’s more or less where everyone starts. I presented the factors/techniques roughly in order from coarsest/easiest to most-granular/sophisticated, so I would suggest slowly trying things in that order. You don’t have to go too crazy to get something decent.</p><p>In an upcoming post, we’ll talk about the autosuggest user experience.</p><p><em>Liked this post? </em><a href="https://medium.com/related-works-inc"><em>Follow us on Medium</em></a><em>. Need help with your autosuggest, search, or with data in general? That’s what we do! Get in touch (</em><a href="/service/mailto:gio@relatedworks.io"><em>gio@relatedworks.io</em></a><em>).</em></p><h3>Acknowledgements, Endnotes, and References</h3><p>A huge thanks to <a href="https://medium.com/u/14069aa7af95">Steve Mardenfeld</a> and <a href="https://medium.com/u/ceeb00afdff0">Nishan Subedi</a> for reading this unbelievably long post and giving thoughtful feedback. Y’all are the best.</p><p>Yet again, I would recommend Daniel Tunkelang’s <a href="https://queryunderstanding.com/autocomplete-69ed81bba245">work on the subject</a>, and<a href="https://staff.fnwi.uva.nl/m.derijke/wp-content/papercite-data/pdf/cai-survey-2016.pdf"> this survey</a> was a critical source for this post.</p><p>[1]<em> </em>— The danger with measuring document popularity is that you are mistaking supply for demand. Just because you have a ton of documents that mention buttresses doesn’t mean your users are actually interested in them.</p><p>[2] — Milad Shokouhi. 2013. Learning to personalize query auto-completion. In <em>Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval</em> (SIGIR ‘13). ACM, New York, NY, USA, 103–112. <a href="http://doi.acm.org/10.1145/2484028.2484076">http://doi.acm.org/10.1145/2484028.2484076</a></p><p>[3] — C. C. Holt. Forecasting seasonals and trends by exponentially weighted moving averages. International Journal of Forecasting, 2004.</p><p>[4] — Fei Cai and Maarten de Rijke (2016), “A Survey of Query Auto Completion in Information Retrieval”, Foundations and Trends® in Information Retrieval: Vol. 10: №4, pp 273–363. <a href="http://dx.doi.org/10.1561/1500000055">http://dx.doi.org/10.1561/1500000055</a></p><p>[5] — Cai, Fei &amp; de Rijke, Maarten. (2016). Learning from homologous queries and semantically related terms for query auto completion. Information Processing &amp; Management. 52. 10.1016/j.ipm.2015.12.008.</p><p>[6] — [5] demonstrates the impact of considering <em>homologous</em> queries, especially in combination with personalization. I’m generalizing this concept to any set of query groupings or relations that we can utilize to share information across queries.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d8a3242c2837" width="1" height="1" alt=""><hr><p><a href="https://medium.com/related-works-inc/autosuggest-ranking-d8a3242c2837">Autosuggest Ranking</a> was originally published in <a href="https://medium.com/related-works-inc">Related Works</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Autosuggest Retrieval Data Structures & Algorithms]]></title>
            <link>https://medium.com/related-works-inc/autosuggest-retrieval-data-structures-algorithms-3a902c74ffc8?source=rss-9199bc6998f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/3a902c74ffc8</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[information-retrieval]]></category>
            <category><![CDATA[search]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Giovanni Fernandez-Kincade]]></dc:creator>
            <pubDate>Tue, 06 Mar 2018 16:31:49 GMT</pubDate>
            <atom:updated>2018-03-06T16:31:49.139Z</atom:updated>
            <content:encoded><![CDATA[<h4>From Brute Force to Tries, Automata, and beyond.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*eBs-jfHLSgOO_NN45cGizQ.jpeg" /><figcaption>Picture of the <a href="https://www.loc.gov/item/2004667708/">Coulee Dam construction</a>.</figcaption></figure><p>In the <a href="https://medium.com/related-works-inc/building-an-autosuggest-corpus-nlp-d21b0f25c31b">last post</a> we talked about constructing an autosuggest corpus — the list of search phrases we can offer to users when they start typing in the search box. In this post, we’ll talk about building a search engine to serve up those suggestions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Vc3d-C2bW3kNGUisbluTww.jpeg" /><figcaption>Given a prefix, an autosuggest engine produces a list of completions.</figcaption></figure><p>You can think of any search engine as working in two phases:</p><ol><li><strong>Retrieval </strong>— Given some input, find a suitable set of candidate results.</li><li><strong>Ranking </strong>— Given a set of candidates, order them.</li></ol><p>We’ll be focusing on the former. In the case of autosuggest, the input is a prefix, like someone typing “b” in the text box, and the candidates are the suggestions from our corpus that begin with that prefix, like “building”, “buttress”, and “buffalo bill”.</p><p>It’s estimated that 10–15% of web search traffic is misspelled¹ and misspellings are even more common on mobile. Although it’s not necessarily a requirement, it would be nice if our autosuggest system had built-in spell-checking or typo-tolerance. So if I searched for “bitt” it should still retrieve “buttress”.</p><h3>Preamble</h3><p>This blog post is heavy on code, algorithms, data structures, and asymptotic analysis. If that kind of thing excites you, carry on!</p><p>Accompanying code can be found <a href="https://github.com/giokincade/suggest-structures">here</a>.</p><p>Some of these techniques are simple enough that you may implement them yourself directly for production use. Others are more complex and chances are good you should be leveraging them through existing libraries like Elastic Search or Solr. This post will give you a glimpse into what those systems are doing underneath the hood.</p><h3>Brute Force</h3><p>The dumbest thing we could possibly do is keep a list of suggestions and manually check each one to see if the prefix matches:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/083d06db94cdfbe4b799e613ab174774/href">https://medium.com/media/083d06db94cdfbe4b799e613ab174774/href</a></iframe><p>The space complexity of this approach is O(N) where N is the size of the autosuggest corpus, and the run-time complexity of search is also O(N). We’re not terribly concerned with indexing complexity because typically this is done offline. As long as it’s not a total disaster, it’s not super important.</p><p>The Levenshtein distance, or <a href="https://en.wikipedia.org/wiki/Edit_distance">edit distance</a>, of two strings <em>x </em>and <em>y</em>, is the minimum number of changes (additions, substitutions, deletions) you would need to turn <em>x</em> into <em>y</em>. For instance, the edit distance between “bar” and “baz” is 1, a single character substitution. If we want to find suggestions with some degree of typo-tolerance we could frame the problem as “find suggestions that are within an edit distance of <em>n</em> from the user-provided prefix”.</p><p>The naive approach to achieving this is to just check the edit distance between the beginning of each suggestion and the prefix:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d2b985fec41c204f48d3076e9425df61/href">https://medium.com/media/d2b985fec41c204f48d3076e9425df61/href</a></iframe><p>The <a href="https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm">dynamic-programming approach </a>to edit-distance calculation would be O(P²) for a prefix of length P, which leaves us with a total complexity of O(NP²). Ouch.</p><h3>Binary Search</h3><p>The next obvious thing to try is keeping the list sorted and performing a <a href="https://en.wikipedia.org/wiki/Binary_search_algorithm">binary search</a> to find where in the list the prefix belongs. Anything that starts with the prefix should be to the right of that position.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PfJ5DQLV9KbXIKUfFxPaFA.jpeg" /><figcaption><em>We can perform a binary search to locate where in the list the prefix belongs.</em></figcaption></figure><p>First we make sure to sort the data after indexing:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9b22561e88263f89411b2796d7254779/href">https://medium.com/media/9b22561e88263f89411b2796d7254779/href</a></iframe><p>Then we binary search to find the insertion point, and check all the entries that come right afterwards. Conveniently, Python’s standard library has a <a href="https://docs.python.org/3/library/bisect.html#bisect.bisect_left">bisect_left</a> that does the heavy binary search lifting:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ad9d0d27e8b5a4a1945ba7bdb397bd41/href">https://medium.com/media/ad9d0d27e8b5a4a1945ba7bdb397bd41/href</a></iframe><p>Again our space complexity is O(N), but now our time complexity is O(log(N)).</p><p>At this point you may think this exercise is completely academic. As it turns out, Etsy’s autosuggest is actually powered by binary search (combined with edge n-gramming, which we’ll talk about in the next section) <a href="https://www.youtube.com/watch?v=oJTPcvRafYg">thanks to some pretty amazing work by Keyur Govande</a>.</p><p>Adding typo-tolerance here would require scanning the index again, which would bring us back to a brute force approach. No bueno.</p><h3>Edge N-Grams</h3><p>An n-gram is a sequence <em>n</em> characters that appears in a larger string. So all of the 2-grams (or bigrams) of “search” are [“se”, “ea”, “ar”, “rc”, “ch”]. Note: the term <em>n-gram</em> is sometimes used to denote sequences of other linguistic atoms like words, syllables, etc. In the context of this blog post (unlike the previous), we’re always talking about characters.</p><p>An edge n-gram is Elastic Search parlance for an n-gram that starts at the beginning of the string, i.e. a prefix. So all the edge n-grams of “search” are [“s”, “se”, “sea”, “sear”, “searc”, “search”].</p><p>For each suggestion in our corpus, we’ll produce all of the edge n-grams, and add them to a dictionary. The value in the dictionary is the set of words that begin with that prefix:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/24dc5cd78d35d3d34c1f1d1c3e53aa5d/href">https://medium.com/media/24dc5cd78d35d3d34c1f1d1c3e53aa5d/href</a></iframe><p>This is pretty close to what we call an <a href="https://en.wikipedia.org/wiki/Inverted_index">inverted index</a> in the field of Information Retrieval (IR). In that context we would call the keys in the dictionary the “term vocabulary”, and the list of suggestions or documents attached to each key the “postings list”.</p><p>Instead of a dictionary, you can imagine shoving these in a database, cache, etc. Prior to using Etseek (i.e. a binary-search-powered KV store), Etsy used Redis, and before that we used the same sharded MySQL databases that we used to serve the rest of the site.</p><p>When you search for a prefix, all we have to do is look it up in our dictionary.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ec5cb118fa96accc829c977fcb8a2d21/href">https://medium.com/media/ec5cb118fa96accc829c977fcb8a2d21/href</a></iframe><p>This technique trades space for time. For a string of length M, we’ll produce M prefixes — one ending on each character. So we end up with O(MN) entries in our dictionary, where M is the length of the longest suggestion.</p><p>For each entry, we have to keep the list of suggestions, which could be the entire corpus. So theoretically this is O(MN*N) or O(MN²) 😬</p><p>Realistically you won’t have every suggestion appearing for every prefix. But the length of the dictionary entries can be a problem for short prefixes. A single letter like “b” is likely to have a very long list of suggestions. This is expensive in terms of storage, but perhaps more importantly, if we have to do complex scoring with every suggestion for “b”, that will translate into more CPU and latency. Short prefixes are the first and most common interaction of your users with an autosuggest system. You don’t want that experience to be a bummer.</p><p>An easy solution to this problem is to only keep the top <em>z </em>suggestions, where <em>z</em> is the number you would ideally like to show the user. You’ll need a way to determine which suggestions are the best, which we’ll talk about more in depth in the next post. For now, assume we can assign a weight to each suggestion, and use that to sort and keep <em>z</em>. That will bring us back into O(MN) land, and ensure that we only have to rank precisely the number that the user is interested in seeing. In IR, this process of stopping as soon as you have <em>z</em> matches, rather than processing all of the potential matches, is called <em>early termination</em>, and we’ll see it come up again soon.</p><p>In return for all this space we get constant-time search. Neat.</p><p>Unfortunately, it’s difficult to add typo-tolerance to this scheme without a combinatorial explosion of dictionary entries or going back to scanning.</p><h3>N-grams (aka Fuzzy Search)</h3><p>Using a similar technique with normal n-grams, we can achieve a great deal of typo-tolerance. This is often how fuzzy search in IDEs works, and the same data structure powers <a href="https://github.com/etsy/hound">Hound</a>.</p><p>Remember that the n-grams of a string <em>x</em> are just a sliding window of all the n-sized substrings of <em>x</em>. So ngrams(“food”, 2) == [“fo”, “oo”, “od”]. We’re going to take these and index them just like we did with edge n-grams.</p><p>One hiccup with this style of n-gramming is the beginning and the end of the string. What happens if the user searches for “f”? We only know about “fo”! In order to allow matches at the beginning or the end of the string, people will often pad the string with a special character, e.g. ngrams(“food”, 2) == [<strong>“_f”</strong>, “fo”, “oo”, “od”, <strong>“d_”</strong>]. Since we’re using n-grams for autosuggest, and thus are searching for prefixes, we’ll only pad the beginning of the string (i.e. we’ll keep “_f” and ditch “d_”):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f2b309f8bf0303bab0be6dcdfbbbda2f/href">https://medium.com/media/f2b309f8bf0303bab0be6dcdfbbbda2f/href</a></iframe><p>Let’s try it out:</p><pre>&gt;&gt;&gt; ngrams(“food”, 2) <br>[‘_f’, ‘fo’, ‘oo’, ‘od’]</pre><p>Now for each suggestion in our index, let’s generate the n-grams, and for each n-gram we’ll store the list of documents that have that n-gram:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/af21661ee90a358925a68e9cacd7af7e/href">https://medium.com/media/af21661ee90a358925a68e9cacd7af7e/href</a></iframe><p>This is what our dictionary looks like after indexing a few words:</p><pre>&gt;&gt;&gt; suggester = NGramSuggester()<br>&gt;&gt;&gt; suggester.index([“foo”, “bar”, “baz”])<br>&gt;&gt;&gt; suggester.data<br>{‘_f’: [‘foo’], ‘fo’: [‘foo’], ‘oo’: [‘foo’], ‘_b’: [‘bar’, ‘baz’], ‘ba’: [‘bar’, ‘baz’], ‘ar’: [‘bar’], ‘az’: [‘baz’]}</pre><p>The search procedure for an input prefix <em>p</em> is as follows:</p><ol><li>Produce the set of n-grams of <em>p </em>(e.g. “foe” turns into [“_f”, “fo”, “oe”]).</li><li>For each n-gram, retrieve the list of matching suggestions (like “foo”).</li><li>For each suggestion, keep track of the number of matching n-grams.</li><li>Return any suggestions that have more than match_percentage matches. This parameter allows us to control how fuzzy the search is.</li></ol><p>In code:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/04ca64678c45d943297893ce7b74883d/href">https://medium.com/media/04ca64678c45d943297893ce7b74883d/href</a></iframe><p>Now let’s try it out:</p><pre>&gt;&gt;&gt; suggester.search(“foe”, match_percentage=0.6)<br>[‘foo’]</pre><p>This is similar to what’s happening underneath the hood in ElasticSearch when you use the <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/analysis-ngram-tokenfilter.html">NGram Token Filter</a> along with the minimum_should_match parameter at search time (<a href="https://www.elastic.co/guide/en/elasticsearch/guide/current/ngrams-compound-words.html">example</a>).</p><p>This percentage-based matching scheme is not the only way of doing things. Often folks will use the n-gram index to identify a set of candidate matches, and then perform more expensive filtering on these candidates.</p><h3>Details</h3><p>There are a number of details to consider and knobs to tune with this strategy.</p><p>First, obviously, there is the question of how large your n-grams should be. It’s a classic memory/storage vs CPU trade-off. Larger n-grams will take up more space, but in turn you will have to evaluate fewer candidates at search-time. Smaller n-grams will take up less space, but require evaluating more candidates. N-gram size will also affect fuzziness — larger n-grams mean more precision and smaller n-grams mean more fuzziness. In practice, trigrams are a common sweet-spot.</p><p>The padding at the beginning of our n-grams allow us to match short-prefixes and gives some extra match weight to the beginning of a suggestion. But a suggestions doesn’t <em>have</em> to match the beginning of the word. You could, for instance, search for “fo” and find “tinfoil”, which is a little strange for autosuggest.</p><p>Ideally we should incorporate some notion of <em>position</em>: where in the query string or the suggestion string a particular n-gram appears. You could incorporate position information into the postings list, you could partition your n-gram index by position, or you could simply do some additional search-time processing. For instance, you could go back to checking the edit distance between the prefix and the start of the suggestion:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d023cf1cd5543a2deaa4cb074bf6a797/href">https://medium.com/media/d023cf1cd5543a2deaa4cb074bf6a797/href</a></iframe><p>Or you could do something as simple as enforcing that the first character always matches. This is a blunt approach so you’ll miss out on misspellings in the first position, but it’s cheap and offers a reasonable blend of prefix-searching and typo-tolerance.</p><h3>Complexity</h3><p>Setting aside some of these details, let’s think about complexity for a second.</p><p>How many n-grams could there possibly be? If we have an alphabet (or character set) of size A, for every position in an n-gram there are A possible characters. For bigrams, we have A choices in the first position, and A choices in the second, which means there are A² combinations. In general, for n-grams of size Z, we will end up with A^Z possible n-grams.</p><p>So we have A^Z possible entries in our n-gram index. In the worst-case, each of the N suggestions are attached to each n-gram. So that’s O(NA^Z).</p><p>There will be a large disparity between worst case and average case complexity because we’re not indexing random strings — we’re indexing natural language which has a non-random distribution of characters and thus a non-random distribution of n-grams. In fact, those patterns are so far from random that examining character/n-gram distributions is a good language detection strategy². This worst case is definitely unrealistic but it gives us some important directional information:</p><ol><li>N-Gram indexes can get big</li><li>Individual N-Gram index entries can be large, i.e. the short-prefixes problem</li></ol><p>When we talked about edge n-grams we dealt with #2 by only keeping the top suggestions for each dictionary entry. In this case, that strategy isn’t viable because if you search for a prefix <em>p</em> with a match_percentage <em>m</em>, and <em>p t</em>urns into n-grams <em>a</em> and <em>b</em>, we need to keep track of <em>each</em> suggestion attached to either <em>a</em> <strong><em>OR</em></strong> <em>b</em> in order to determine whether or not they satisfy <em>m.</em> It’s impossible to know at index-time, for a given n-gram, which suggestions to keep.</p><p>Which brings us to run-time. For a prefix of length P, and n-grams of size M, we will generate P-M+1 n-grams (remember in this implementation the ending is not padded). For each n-gram, we need to accumulate potentially N matches. Then we need to process each of the N potential matches and evaluate the match_percentage. So that’s O((P-M+1)N + N) which is just O(PN).</p><p>So we’re definitely paying a price for typo-tolerance on both the storage and the computation side of the equation, but there are many production systems that have successfully scaled these techniques.</p><h3>Tries</h3><p>You can’t talk about autocomplete without talking about <a href="https://en.wikipedia.org/wiki/Trie">Tries</a>. Etsy Search used to ask interviewees to implement an autocomplete system as a take-home assignment, and the most common implementation was using a Trie.</p><p>The idea is pretty simple. Rather than storing our suggestions in a sorted array, or a dictionary of prefixes/n-grams, let’s put them in a tree. The root of the tree is empty and represents the start of a suggestion. The leaves represent complete suggestions that exist in our corpus. The edges between nodes are labelled with characters. The path from root to leaf is the sequence of characters that make up that suggestion. The k-th level in the tree corresponds to the k-th character across all the suggestions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MI3rrTjtabYyZtNlK2HR4w.jpeg" /><figcaption>A Trie containing the words “foo”, “bar”, and “baz”.</figcaption></figure><p>Let’s try a recursive version for funzies. Each node has a dictionary of children, keyed on the subsequent character. When we insert a string, we pop the first character off, find or initialize a node for that child, and then ask the child node to insert the remaining characters:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3f5f2e4b12105d73f048575d1a74ad2a/href">https://medium.com/media/3f5f2e4b12105d73f048575d1a74ad2a/href</a></iframe><p>Indexing just amounts to inserting every suggestion on the root node:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b376c66b9905a554286a2a6446da7c24/href">https://medium.com/media/b376c66b9905a554286a2a6446da7c24/href</a></iframe><p>To perform a search, we find the node that corresponds to a prefix, and then find all the leaves we can reach from that node:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0cdec0e2c46819e61f55a9639ef4360b/href">https://medium.com/media/0cdec0e2c46819e61f55a9639ef4360b/href</a></iframe><p>To find the node for a prefix, we recursively pop off the characters from the prefix and retrieve the corresponding child node:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1239116b5f564ac8a7d329eb8a02ad8b/href">https://medium.com/media/1239116b5f564ac8a7d329eb8a02ad8b/href</a></iframe><p>To find the leaves, we traverse depth-first from that node to each leaf, accumulating characters along the way:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/831e87b12dc16186aa68135d89ba1196/href">https://medium.com/media/831e87b12dc16186aa68135d89ba1196/href</a></iframe><p>Lucene’s <a href="http://lucene.apache.org/core/4_4_0/suggest/org/apache/lucene/search/suggest/tst/TSTLookup.html">TSTLookup</a> is an implementation of a Trie variant, which is exposed for autosuggest in both ElasticSearch and Solr.</p><h3>Complexity</h3><p>The worst-case for a trie is that none of the words overlap, so you end up with one node for each character in every suggestion:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*adk8NEm0VA0_kqqKKqOaPw.jpeg" /><figcaption><em>In the worst-case for a Trie, your terms share no prefixes.</em></figcaption></figure><p>If M is the length of the longest suggestion, your space complexity is O(MN). Trie’s exploit the fact that words often start with the same prefix to save on storage, e.g. if you already have “category” in your Trie, adding “cat” costs you nothing. So in practice they can be much more compact than other representations, and large indexes are easily stored in memory.</p><p>The run-time complexity for finding the node corresponding to a prefix of length P is O(P), which is fantastic. But the expensive part is finding all the leaves. This can be O(MN) — this is effectively the complexity of finding all the leaves from the root, and hints at the recurring problem of dealing with short-prefixes that can have a disproportionate number of suggestions.</p><p>To improve on the performance and storage overhead of Tries, and find some way to mitigate the pain of short-prefixes, we need to talk about DFAs.</p><h3>Deterministic Finite Automata (DFAs) and Finite State Transducers (FSTs)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4uOb92f_7NAo85cmUVxy2Q.jpeg" /><figcaption><em>A simple DFA that accepts the strings “foo” and “bar”. Look familiar?</em></figcaption></figure><p>It’s not a perfect metaphor, but I like to think of a Deterministic Finite Automata (DFA) as a Set&lt;String&gt;. It takes a sequence of symbols (or characters) as input, and tells you whether or not the sequence belongs to the language (or set). Underneath the covers, a DFA is a state machine. There is a start state and an end state, states in a graph between the two, and there are labelled transitions between states. A DFA has a single current state (which is why it’s called deterministic). As it processes the input, it updates its state according to the transition graph. If at the end of the input we’ve reached the end-state, the input is valid, or belongs to the language/set.</p><p>This should look familiar. A Trie is pretty similar to a DFA, and in fact you can represent a Trie as a DFA. This is useful because DFAs are a well-studied phenomenon: there are tons of known algorithms for doing interesting things with them. For instance, there are algorithms for compressing the state-graph of a DFA to use the fewest states/edges necessary. This is called <a href="https://en.wikipedia.org/wiki/DFA_minimization">DFA minimization</a>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/728/0*orC2ApIj-EiWgRwW." /><figcaption><em>A minimal DFA uses the fewest possible states. Image taken from </em><a href="https://www.slideshare.net/LucidImagination/weiss-dawid-finite-state-automata-in-lucene"><em>“Finite State Automata in Lucene”</em></a></figcaption></figure><p>We know that Tries take advantage of shared prefixes to save space. But words also often have shared suffixes, e.g. “zoology” and “biology” share “ology”. We’re wasting a lot of space duplicating “ology” everywhere. By treating our Trie as a DFA and minimizing it, we can regain that space:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9przW_KmnNjxPzrDsRjETA.jpeg" /><figcaption><em>Minimizing a Trie/DFA allows us to save space for shared suffixes.</em></figcaption></figure><p>If a DFA is a Set&lt;String&gt; a Finite State Transducer (FST) is a Map&lt;String, Number&gt;. It’s a DFA that allows us to associate a numeric (or really just commutative) value with a valid input sequence. For autosuggest that’s useful because it allows us to associate a weight or score with a suggestion:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fBPo6L2HMlaT4or6rLroxg.jpeg" /><figcaption><em>An FST allows us to associate a weight to a path. In this example, “bar” has a weight of 5 and “baz” has a weight of 10.</em></figcaption></figure><p>There are many ways we could represent the path weights. Instead of placing them at the end, we could place them at beginning:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Trx8-98a3qJA7KGcqloPAg.jpeg" /><figcaption><em>Shifting path weights to the beginning allow us to perform early termination.</em></figcaption></figure><p>This allows us to do early termination again by doing a depth-first traversal in weighted order. In the example above, if the user searches for “b” we can first check the 10-weighted branch. If we only need a single suggestion, we’ll find “baz” and then we’re done. If you have a high-cardinality or real-numbered set of weights, you can just make weight buckets at the beginning of the FST.</p><p>Lucene’s <a href="https://lucene.apache.org/core/4_4_0/suggest/org/apache/lucene/search/suggest/fst/FSTCompletionLookup.html">FSTCompletionLookup</a> is based on FSTs and is exposed in Solr and ElasticSearch to power autosuggest. Dawid Weiss has <a href="https://www.slideshare.net/LucidImagination/weiss-dawid-finite-state-automata-in-lucene">a great presentation</a> on the subject of DFAs/FSTs in Lucene, which inspired some of my illustrations.</p><p>It turns out that given some string <em>s</em> and a maximum edit distance <em>d</em>, <a href="https://en.wikipedia.org/wiki/Levenshtein_automaton">you can construct a Levenshtein Automata that will only accept strings that are within <em>d</em> edits of <em>s</em></a><em>. </em>We can use this to produce typo-tolerant suggestions. As we depth-first traverse our FST, we can feed our steps into the Levenshtein Automata. If it accepts the input character, we proceed. If it doesn’t, we can ignore that whole branch, and then backtrack. There’s a amazing writeup of the process <a href="http://julesjacobs.github.io/2015/06/17/disqus-levenshtein-simple-and-fast.html">here</a>. Automata, talking to each other!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*B5q83JgEjXpSjoIT." /><figcaption><em>Portrait of Lucene developers trying to decipher automata papers.</em></figcaption></figure><p>Tangent: If you ever feel like you’re a dumb imposter, go read about how all of these ridiculously smart, veteran Lucene committers <a href="http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html">thrashed around desperately trying to translate a DFA paper into working code</a>.</p><p>I’ll leave the complexity analysis as an exercise to the user 😜 <a href="https://www.slideshare.net/LucidImagination/weiss-dawid-finite-state-automata-in-lucene">but benchmarks suggest FSTs yield better latency/throughput figures for short prefixes while using an order of magnitude less memory.</a></p><h3>Coming Up</h3><p>I hope that was a fun tour through some autosuggest datastructures and algorithms. Barring the obviously terrible brute force option, I’ve seen every approach utilized in production at scale. I would recommend the FST facilities offered by Solr and ElasticSearch, but don’t be afraid to start simple if you’d like to avoid adding a new system or just don’t have experience operating Solr/ES.</p><p>In the next post, we’ll talk about ranking.</p><p>You can find the reference implementations of these algorithms <a href="https://github.com/giokincade/suggest-structures">here</a>.</p><p>Thanks to <a href="https://twitter.com/stevemardenfeld?lang=en">Steve Mardenfeld</a>, <a href="https://medium.com/u/ceeb00afdff0">Nishan Subedi</a>, <a href="https://twitter.com/stanistan?lang=en">Stan Rozenraukh,</a> and <a href="https://twitter.com/keyurdg">Keyur Govande</a> for reading and giving feedback!</p><p>️❤️ Please feel free to reach out with any comments, questions, corrections, etc. ️❤️</p><p>[1] —S. Cucerzan and E. Brill. Spelling correction as an iterative process that exploits the collective knowledge of web users. In EMNLP, 2004</p><p>[2] — Dunning, T. (1994) “Statistical Identification of Language”. Technical Report MCCS 94–273, New Mexico State University, 1994.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3a902c74ffc8" width="1" height="1" alt=""><hr><p><a href="https://medium.com/related-works-inc/autosuggest-retrieval-data-structures-algorithms-3a902c74ffc8">Autosuggest Retrieval Data Structures &amp; Algorithms</a> was originally published in <a href="https://medium.com/related-works-inc">Related Works</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Building an Autosuggest Corpus, Part 2]]></title>
            <link>https://medium.com/related-works-inc/building-an-autosuggest-corpus-nlp-d21b0f25c31b?source=rss-9199bc6998f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/d21b0f25c31b</guid>
            <category><![CDATA[data]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[information-retrieval]]></category>
            <category><![CDATA[nlp]]></category>
            <dc:creator><![CDATA[Giovanni Fernandez-Kincade]]></dc:creator>
            <pubDate>Tue, 13 Feb 2018 16:26:13 GMT</pubDate>
            <atom:updated>2018-03-06T16:38:14.773Z</atom:updated>
            <content:encoded><![CDATA[<h4>Using NLP to extract key phrases from documents.</h4><p>In the <a href="https://medium.com/related-works-inc/building-an-autosuggest-corpus-part-1-3acd26056708">last post</a> we talked about how to decide between query logs and documents as your data source. For our product we settled on using our documents. In this post we’ll talk about how to turn documents into suggestions. This post will be longer, a bit more involved, but it should be a ton of fun. There will be code and math, but don’t worry, you should be able to follow along if you have some rudimentary programming skills and know how division works.</p><h3>When Life gives you Natural Language, just Process it.</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Cfl2kCXykg3o8QONhHOMng.png" /><figcaption>Our goal is to turn documents into autosuggestions.</figcaption></figure><p>Our goal is to produce a list of terms or short phrases that we can suggest to users as search queries. Our documents are composed of structured and unstructured fields. For instance, you might have a person field with a value like “Buffalo Bill”. It’s easy to imagine that with a little bit of normalization these structured fields might make decent suggestion candidates. But often the high value phrases are buried deep in unstructured fields like title. In the example above, if we only indexed structured fields we would miss out on “wild west”, which may be much more likely as a query to the uninitiated user.</p><p>The task of determining key phrases from text is called <a href="https://en.wikipedia.org/wiki/Terminology_extraction">terminology extraction</a>. Like most data sciencey problems, there are generally three ways to approach it:</p><ol><li><strong>Ad-Hoc Heuristics</strong> — You can hand-tune some rules about what phrases to keep and what phrases to discard.</li><li><strong>Supervised Learning</strong> — You can get some training data and train a model to extract phrases for you. For instance, you could represent this task as a binary classification problem where given a word or phrase, a model will give you a yes/no answer.</li><li><strong>Unsupervised Learning</strong> — You can use unsupervised techniques like <a href="https://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf">TextRank</a> that exploit patterns in the text to discover important phrases.</li></ol><p>In this post, we’ll focus on the the first. It’s a decent way to get started, and these basic NLP techniques will be useful to prepare your data should you choose to move on to more sophisticated strategies later on.</p><p>One important caveat is that unlike some terminology extraction tasks, our goal isn’t <em>only</em> to extract interesting terms/phrases, it’s to extract phrases that users are likely to search for, and that would yield a reasonable number of results. So the suggestion corpus should probably contain specialized terminology as well as more general terms that users are likely to use.</p><p>We’ll be using <a href="http://www.nltk.org/">NLTK</a>, a python library with a ton of utilities, corpora, and trained-models for common NLP tasks. It’s tremendously chill.</p><p>The code in this post will be edited for narrative purposes, but you can find fully functioning examples in the accompanying <a href="https://github.com/giokincade/suggest-extract-notebook/blob/master/notebooks/Extracting%20Suggestion%20from%20Text.ipynb">Jupyter notebook</a>.</p><p>We’ll be playing with a dataset of descriptions from the <a href="http://digital.denverlibrary.org/cdm/art/">Denver Public Library’s Western Art Collection</a>.</p><h3>Unigrams</h3><p>Another name for a sequence of words is an <a href="https://en.wikipedia.org/wiki/N-gram"><em>n-gram</em></a>. A sequence of a single word is a unigram, two words is a bigram, and so on. Note: the term <em>n-gram</em> is sometimes used to denote sequences of other linguistic atoms like characters, syllables, etc. In the context of this blog post, we’re always talking about words. Let’s start by looking at simple numeric approaches to gathering unigrams.</p><p>The gist of the techniques we’re going to talk about is to gather statistics about the appearance of terms in your corpus and use them to help you decipher which terms are important. Here’s a really dumb example:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5dd358ff6e43d350e38197445113fb5a/href">https://medium.com/media/5dd358ff6e43d350e38197445113fb5a/href</a></iframe><p>We stream through all of our documents and collect counts for how often each word appears. Easy peasy. This tiny program illustrates some of the pieces in a typical NLP pipeline:</p><ol><li><strong>Tokenization </strong>— the process of turning a long string into a sequence of words (or tokens). In this case, we’re breaking up the string whenever we encounter whitespace.</li><li><strong>Normalization </strong>— the process of mapping a token to a more canonical form, which allow us to treat variants of a token identically. In this case, we’re just making our analysis case-insensitive by lower-casing everything.</li></ol><p>A production pipeline will have more components and will be more sophisticated and resilient to the variance of human-produced text, but the idea is the same: you are building a pipeline of components that create, transform, and filter a stream of tokens. Lucene calls this <a href="https://lucene.apache.org/solr/guide/6_6/understanding-analyzers-tokenizers-and-filters.html">“Analysis”</a>, or the “Analysis Chain”. A lot of your blood, sweat, and tears will be spent here, and small changes in this pipeline will have out-sized effects on your output.</p><p>NLTK has a dictionary specifically designed for capturing token statistics. It defaults missing terms to 0 and has a common API of utility methods that other NLTK objects depend on, so let’s use that and abstract away the analysis:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/afca7abc2484178e5da7dc5bc6337331/href">https://medium.com/media/afca7abc2484178e5da7dc5bc6337331/href</a></iframe><p>Now we have a dictionary of words and their frequencies. What do we do with it? We have to decide which words to keep in our suggester. What are the top words?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RJamz8_3iupniE2dB724iA.png" /><figcaption>The most frequent words in our corpus are kind of a bad trip.</figcaption></figure><p>These aren’t terribly useful. A lot of them are <a href="https://en.wikipedia.org/wiki/Stop_words">stop words</a> — the glue words that we need to string sentences together but that don’t really add any meaningful information. NLTK has a <a href="http://www.nltk.org/book/ch02.html#wordlist-corpora">corpus of english stopwords</a> we can use, let’s try filtering them out:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qOmBUL5OEDXtQbR4F1DkGg.png" /><figcaption>The most frequent words in the corpus, excluding stopwords.</figcaption></figure><p>Getting somewhere, but we can do better. We’ve gotten rid of the glue, but there are still some low-value terms like “two”, “left”, “right”, “side”, etc. No one is going to search for these words in isolation.</p><h3>TF-IDF</h3><p>Let’s try a slightly different tack. Rather than considering all the terms across the entire corpus, perhaps we can get better results by only considering the best N terms from each document:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ca9501e21091c1d62acaf99c1b04c73e/href">https://medium.com/media/ca9501e21091c1d62acaf99c1b04c73e/href</a></iframe><p>How do we measure the importance of terms in a document? An easy way to get started is our good old friend <a href="https://en.wikipedia.org/wiki/Tf%E2%80%93idf">Term Frequency — Inverse Document Frequency (TF-IDF)</a>. In case you aren’t old friends, here’s a primer. Below is a sketch of the math for TF-IDF, ignoring a log, a constant, and the many variations you can choose from. It’s OK to ignore some of these details — we’re just trying to develop a mathematical intuition for how it works.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*3UrhlqALJOW7BRe5." /><figcaption>The TLDR on TF-IDF.</figcaption></figure><p>TF-IDF is a real number that estimates the importance of a term (or terms with a summation) in a document (which is implied above). The higher, the better.</p><p>There are two ideas here. First, as we observed earlier, extremely popular words tend to not be super useful. This idea is codified in the denominator, i.e. Inverse Document Frequency (IDF). The more frequent a word is in your corpus, the larger the denominator, and thus the smaller your TFIDF score. Second, if a document mentions a term like “wild” a ton of times, and that term isn’t particularly popular in the corpus, that term is probably important for the given document. The more a document mentions it, the higher the numerator, and the higher your TFIDF score.</p><p>Here’s an example of picking the top three unigrams for a tiny document:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/acc699895ee7da02dcdde750342689f4/href">https://medium.com/media/acc699895ee7da02dcdde750342689f4/href</a></iframe><pre>[‘fronting’, ‘snowbank’, ‘business’]</pre><p>If you have short documents, like we do in this case, the TF part of TF-IDF may be pretty low-signal, in which case you can try using IDF alone or set TF to 1.</p><p>Here’s what the top terms look like if we use IDF and limit to 10 terms per document:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3dnAvvq2pV-wWfy56YfNcw.png" /><figcaption>The most frequent words in the corpus, only considering the top 10 terms per document by IDF.</figcaption></figure><p>These are pretty good. There are still some low-value verbs and prepositions like “via”, “reached”, “near”, “towards”, etc. You’ll see the set change pretty dramatically if you fiddle with the number of terms to keep per document.</p><h3>What a POS</h3><p>It seems like we’re mostly interested in nouns. Can we use our knowledge of language to help filter down our candidates? Yes! We can use a Part-of-Speech (POS) tagger. Given a stream of natural language, a POS-tagger will output a stream annotated with syntactic information like “noun”, “adjective”, “preposition”, etc. NLTK comes with a bunch of pre-trained POS models you can leverage:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e5f47a472463b5bd29d1d3797cb84fb7/href">https://medium.com/media/e5f47a472463b5bd29d1d3797cb84fb7/href</a></iframe><pre>[(‘Several’, ‘JJ’), (‘men’, ‘NNS’), (‘stand,’, ‘VBD’), (‘and’, ‘CC’), (‘one’, ‘CD’), (‘sits,’, ‘NN’), (‘on’, ‘IN’), (‘the’, ‘DT’), (‘corner’, ‘NN’), (‘boardwalk’, ‘NN’), (‘opposite’, ‘IN’), (‘the’, ‘DT’), (‘hotel.’, ‘NN’)]</pre><p>You can find a list of tags <a href="https://www.ling.upenn.edu/courses/Fall_2003/ling001/penn_treebank_pos.html">here</a>. Underneath the hood, POS taggers are often supervised machine learning models trained on corpora painstakingly annotated by humans. They might depend on features like “is the current word capitalized?”, “was the previous word a preposition?”, etc.</p><p>Once you have a tagged sentence, you can filter the sequence down to only the tags you are interested in. Here’s what the most frequent unigrams look like after we’ve filtered to noun variants:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*tJExRnIFzcQLRgBv." /><figcaption>The most frequent unigrams after filtering to only nouns.</figcaption></figure><p>Neat. We succeeded in removing stuff like “via”, “reached”, etc. We can also try combining this technique with the IDF approach (i.e. only take the top N nouns per document):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7ZuAJWLqkU2x711yBGm6XQ.png" /><figcaption>Top unigrams looking at only the top 10 nouns in each document.</figcaption></figure><h3>Bigrams</h3><p>Now that we’ve got a decent list of unigrams, let’s turn our attention to longer sequences, like “wild west”. 2+-grams are sometimes called <a href="https://en.wikipedia.org/wiki/Collocation"><em>collocations</em></a>. NLTK has some built-in facilities for finding these. Let’s look at an example:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9a4020e27ea214e228267ee138a52055/href">https://medium.com/media/9a4020e27ea214e228267ee138a52055/href</a></iframe><p>The idea is that we collect statistics about how often two terms appear together, and in isolation. Then we use some statistical tests to figure out which pairs occur often enough to suggest that they are a meaningful concept together.</p><p>Note: You don’t have to collect your own FreqDists. The BigramCollocationFinder will take a sequence of tokens and do that for you. I did it to give you a glimpse of what’s happening under the hood, but it’s actually easy to screw up, which in fact, I did while writing this post.</p><h3>PMI</h3><p>NLTK offers a range of statistical tests you can use, but let’s look at the math behind <a href="https://en.wikipedia.org/wiki/Pointwise_mutual_information">Point-wise Mutual Information</a> because it’s easy and illustrative (again ignoring a log):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*H5DPRxsbM8RrwH87." /><figcaption>The PMI of “wild west”. There’s a Will Smith joke in here somewhere.</figcaption></figure><p>If you take any two contiguous words in a corpus chances are good they aren’t a meaningful concept as a phrase. You can think of PMI as encoding that idea in a hypothesis: the two words are independent. Whether or not they appear together is pure chance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*q_NWL8BzO-jg8QYQ." /><figcaption>You can think of PMI as the ratio between the real probability and the probability assuming independence.</figcaption></figure><p>The numerator is the probability that the two words actually occur together. The denominator is the probability that they would appear together if you assumed they were independent. Let’s make that real by doing the math for a simple example:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f0ecc79bb42994d79875753905997da6/href">https://medium.com/media/f0ecc79bb42994d79875753905997da6/href</a></iframe><p>As the numerator goes up, the terms appear together more often than you would expect if they were truly independent, and thus PMI goes up. High PMI bigrams are probably legit concepts. As the numerator goes down, the occurrence of the terms looks more and more like randomness.</p><p>Unfortunately PMI doesn’t have a fixed range. So the PMI values you will see will vary based on your corpus. To filter down to a decent set of bigrams, you’ll have to take a look at the results and come up with a reasonable threshold. You will probably also want to limit your results to only those bigrams that occurred a reasonable number of times — the probabilities will be unreliable for tokens that appear only a handful of times.</p><p>Now, here are some bigrams!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*b-EJhQ3MutNKHi4oE0Zfsg.png" /><figcaption>Best bigrams in our corpus based on PMI.</figcaption></figure><p>TIL about <a href="https://sgtarr.com/blog/125780/what-is-a-color-note-and-how-does-it-work">color notes</a> and <a href="https://study.com/academy/lesson/what-is-a-cornice-in-architecture-definition-styles.html#section---CorniceStyles">bracketed cornices</a>. Awesome! Again, we find some non-noun stuff like “made color”, “former tabor”, and “reached via”. We can try playing with POS tagging again to help with that.</p><h3>Piece of Chunks</h3><p>This time instead of filtering to noun unigrams, we’re interested in finding <a href="https://en.wikipedia.org/wiki/Noun_phrase">noun phrases</a> like “episcopal church” or “watercolor paintings”. Often these will contain adjectives, prepositions, etc. So we will need a mechanism to segment our text that allows us to capture this complexity. NLTK calls this “chunking” and provides a parser that will segment some text for you into labeled chunks according to a regex grammar you provide:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/08cc662b7735bc5a2af00b9231ea6775/href">https://medium.com/media/08cc662b7735bc5a2af00b9231ea6775/href</a></iframe><pre>(S<br> The/DT<br> (<strong>NounPhrase</strong> tops/NNS)<br> of/IN<br> (<strong>NounPhrase</strong> music/NN stands/NNS)<br> with/IN<br> (<strong>NounPhrase</strong> lamps/NNS)<br> and/CC<br> (<strong>NounPhrase</strong> chair/NN backs/NNS)<br> show/VBP<br> in/IN<br> the/DT<br> (<strong>NounPhrase</strong> foreground./NN))</pre><p>Once we have noun-phrase chunks, we can use these to filter the set of candidate bigrams and perform the same analysis:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*t5cKu6MPFikmkvAq." /><figcaption>Highest PMI bigrams after filtering to noun-phrases using a simple regex.</figcaption></figure><p>Mixed bag — we got rid of “reached via” but our first-pass grammar was too restrictive so we also killed “bracketed cornices”. We should go back and adjust it to allow for adjectives and other intervening tags. This is particularly important as you look at trigrams and longer phrases. The challenge with using POS annotations is the complexity of designing a grammar that will strike a reasonable balance between precision and recall.</p><p>Another note of caution about POS taggers is that they tend to work better on longer prose as opposed to short strings from structured form fields, and heavily processing the tokens before using them may reduce their effectiveness. For instance, if you lower-case and remove punctuation before you POS-tag, and the model depends heavily on capitalization and punctuation features, you may get poor results.</p><p>Trigrams and beyond are left as an exercise to the reader.</p><h3>Iterating and Evaluating</h3><p>There’s a lot of painstaking labor involved in any data science task and this is no exception. You’ll probably have to try a bunch of these strategies, and/or combine a few to get reasonable results. There are a ton of hyperparameters we can play with like minimum frequency thresholds, number of terms to keep per document (in the TF-IDF approach), minimum PMI, POS grammars, etc. How do we know if we’re getting anywhere?</p><p>First, I would recommend getting a visceral sense for how your corpus changes as you fiddle with the knobs. Looking at the top N in a notebook visualization is not bad, but it also helps to see a more comprehensive changeset. I will often generate a text file and then sort it and use diff:</p><pre>diff -u unigrams.csv pos_unigrams.csv</pre><pre>@@ -3941,30 +3048,20 @@<br> “workmen”<br> “works”<br> “world”<br>-”worn”<br>-”wrapped”<br> “wrecker”<br> “wrigleys”</pre><p>Even though we’re using heuristics, we can still leverage supervised techniques to tune our thresholds or evaluate our models. For instance, you could take a small sample of phrases and annotate them with yes/no labels, which indicate whether or not we want to keep the phrases in our final list of suggestions. Then we can use any number of <a href="https://en.wikipedia.org/wiki/Evaluation_of_binary_classifiers">binary classifier metrics</a> to evaluate how we’re doing:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/61d97f692e0fd56bb3d1c3aaf383d6b5/href">https://medium.com/media/61d97f692e0fd56bb3d1c3aaf383d6b5/href</a></iframe><pre>Baseline F1: 0.473684<br>POS Filtered F1: 0.800000</pre><p>In this example we’re measuring the <a href="https://en.wikipedia.org/wiki/F1_score">F1 score</a>, a metric which combines precision and recall into a single figure between [0, 1], the higher the better. Looks like POS filtering works better than just keeping any terms that appear more than 5 times. Sweet!</p><p>Remember if you are tuning hyperparameters, you’ll want to split your data <a href="https://en.wikipedia.org/wiki/Training,_test,_and_validation_sets">into validation and test sets</a> lest you bias your outcomes.</p><p>Of course, if you produce enough training data you could just train a classifier, perhaps using some of the techniques we’ve discussed to prepare your candidates or to generate features.</p><p>And naturally, the most effective way to evaluate your suggestions, if you have enough traffic, is to get them in front of users and run an AB experiment, probably measuring some of the metrics we talked about in <a href="https://medium.com/related-works-inc/bootstrapping-autosuggest-c1ca3edaf1eb">the first post</a>.</p><h3>Coming Up</h3><p>In the <a href="https://medium.com/related-works-inc/autosuggest-retrieval-data-structures-algorithms-3a902c74ffc8">next post</a> we’ll talk about building an autosuggest engine to serve up the corpus we just constructed.</p><p>If you’d like to read more, the <a href="http://www.nltk.org/book/">NLTK book</a> is a great resource. If you’re interested in state-of-the-art NLP techniques, <a href="http://cs224d.stanford.edu/">Standford’s CS224d</a> is super dope and the lectures are available online.</p><p>Many thanks to my people <a href="https://medium.com/u/1b7555451896">Fiona Condon</a>, <a href="https://medium.com/u/eed852b96053">Kelly Norton</a> and <a href="https://medium.com/u/4a0b616810df">Jaime DeLanghe</a> for taking the time to read this post and give thoughtful feedback. ❤️</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d21b0f25c31b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/related-works-inc/building-an-autosuggest-corpus-nlp-d21b0f25c31b">Building an Autosuggest Corpus, Part 2</a> was originally published in <a href="https://medium.com/related-works-inc">Related Works</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Building an Autosuggest Corpus, Part 1]]></title>
            <link>https://medium.com/related-works-inc/building-an-autosuggest-corpus-part-1-3acd26056708?source=rss-9199bc6998f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/3acd26056708</guid>
            <category><![CDATA[search]]></category>
            <category><![CDATA[ux]]></category>
            <category><![CDATA[information-retrieval]]></category>
            <category><![CDATA[data-science]]></category>
            <dc:creator><![CDATA[Giovanni Fernandez-Kincade]]></dc:creator>
            <pubDate>Wed, 31 Jan 2018 16:23:32 GMT</pubDate>
            <atom:updated>2018-02-13T16:32:31.451Z</atom:updated>
            <content:encoded><![CDATA[<p>In the <a href="https://medium.com/related-works-inc/bootstrapping-autosuggest-c1ca3edaf1eb">last post</a> we covered the goals of our autosuggest product and different measurement strategies. In this post we’ll talk about what an autosuggest system looks like, and start talking about how to build an autosuggest corpus.</p><h3>Anatomy of Autosuggest</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8rRYXmVF5Ab0-KCqN4LsSQ.png" /></figure><p>Here are the components of our auto suggest system:</p><ol><li><strong>Autosuggest Corpus</strong> — A static dataset of suggestions that we can offer users. This is computed offline at a scheduled interval and loaded into the engine.</li><li><strong>Engine</strong> — A REST API responsible for <strong>Retrieval</strong> (getting the list of candidate suggestions for a given user input) and <strong>Ranking </strong>(ordering the retrieved suggestions).</li><li><strong>Client </strong>— The client application that runs in your browser, asks the engine for results, and displays them to the user.</li></ol><p>We’ll be focusing on the corpus for the next two posts.</p><h3>Finding Suggestions</h3><p>So where do we look to find the suggestions we can offer to users?</p><h3>Query Logs</h3><p>The first option is to harvest your query logs, i.e. your record of what queries users have issued in the past. In my experience and in most benchmarks, query logs are the most effective source of suggestions.</p><p>But this path is not without its difficulties. You will need to have query logs in the first place, and have reasonable means of programmatically accessing them. Further, anytime you are leveraging user-data, you should strongly consider the privacy and security implications of doing so. Is it ok if my search history is used to provide suggestions for someone else? Do users expect that information to be private? Even if they don’t, do they sometimes search for potentially sensitive information? Can an adversary maliciously pollute your logs in order to game your autosuggest? What about misspellings? Potentially offensive material? You may find yourself spending a ton of time trying to scrub this dataset of <a href="https://en.wikipedia.org/wiki/Personally_identifiable_information">PII</a>, or just deciding it’s not worth the trouble/risk.</p><h3>Documents</h3><p>The second option is to harvest your documents, i.e. the content that users are ultimately searching for. On an e-commerce site this would be the items for sale. On our digital collections product, it’s the maps, photographs, and other cultural artifacts that institutions are making available for consumption.</p><p>The reason this source typically underperforms compared to query logs is that your users and your documents are usually speaking different languages. My favorite example from my time at Etsy was a shop that was selling beautiful handmade <a href="https://en.wikipedia.org/wiki/Cloche_hat">cloches</a> (a type of hat). This tremendously talented seller was so deep in the world of millinery (hat making), that it didn’t occur to them to tag their items with the term “hat”. We did a poor job of handling this discrepancy at the time so it was hard for them to get found. The people or processes that produce content are usually subject-matter experts compared to the average consumer. If you build your autosuggest corpus from your documents, you may find that it’s filled with words your users aren’t likely to type, and it may be missing some important terms that they are.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/620/0*QPhMk6cjlO88NMws." /><figcaption><em>Ceci n’est pas une hat</em></figcaption></figure><p>Now the astute reader will probably ask, what do you mean it underperforms? Underperforms on what metric? This brings us back to the whole <em>prediction</em> vs <em>performance</em> dichotomy. You can probably expect that a document-based autosuggest will have a lower <em>Acceptance Rate</em>, but users that accept suggestions may ultimately be more successful (i.e. higher CTR, fewer searches with empty results, etc). After all, if suggestions are coming from the documents themselves, the search results are likely to have plenty of stuff to look at. Although I’ve historically been biased towards query logs as a source, I’ve spoken to organizations that have run successful experiments showing that document-based suggestions are better for their bottom line.</p><h3>It’s a choice.</h3><p>There’s no right answer here. What makes sense for you will depend on your content, the goals of your system, the types of users you have and their expectations, your privacy policy, etc. You’ll have to weigh the trade offs of each approach and if both are viable you may want to compare their outputs or even their performance using live AB experiments.</p><p>In our case, we used our documents. Patron privacy is a critical requirement for cultural institutions, a fact that we deeply cherish and respect. Often these institutions don’t have query logs or getting access to them is tremendously painful. So query logs were, by default, not an option.</p><h3>Coming Up</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4BexzkCAwjU3qn7N-QVCdg.png" /></figure><p>The nice thing about query logs is they are already split out into bite-sized queries users might type. One of the challenges with using your documents is turning a blob of data into a small set of discrete suggestions. In <a href="https://medium.com/related-works-inc/building-an-autosuggest-corpus-nlp-d21b0f25c31b">the next post,</a> we’ll talk about some simple techniques to extract suggestions from your data.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3acd26056708" width="1" height="1" alt=""><hr><p><a href="https://medium.com/related-works-inc/building-an-autosuggest-corpus-part-1-3acd26056708">Building an Autosuggest Corpus, Part 1</a> was originally published in <a href="https://medium.com/related-works-inc">Related Works</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Bootstrapping Autosuggest]]></title>
            <link>https://medium.com/related-works-inc/bootstrapping-autosuggest-c1ca3edaf1eb?source=rss-9199bc6998f5------2</link>
            <guid isPermaLink="false">https://medium.com/p/c1ca3edaf1eb</guid>
            <category><![CDATA[auto-suggest]]></category>
            <category><![CDATA[data]]></category>
            <category><![CDATA[autocomplete]]></category>
            <category><![CDATA[search]]></category>
            <dc:creator><![CDATA[Giovanni Fernandez-Kincade]]></dc:creator>
            <pubDate>Wed, 24 Jan 2018 15:15:51 GMT</pubDate>
            <atom:updated>2018-02-16T15:47:21.316Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ga5LQvndGrU_q7p2JFei_w.jpeg" /></figure><p>Autosuggest is critical to the modern search experience. Users expect it, depend on it, and it’s particularly important on mobile devices where typing is cumbersome and error-prone. It’s also a ton of fun to work on because it’s a complex product that blends a bunch of different disciplines: interaction design, data structures, front-end engineering, information retrieval, natural language processing, AI, etc.</p><p>This is the first post in a series describing the work that I did to add autosuggest to one of our products. I’ll talk about the techniques we employed, but along the way I will also spend some time speaking more broadly about the challenges involved and the spectrum of approaches people use to solve them.</p><h3>Goals</h3><p>Before you write a single line of code I think it’s important to establish what your goals are for the product. Who is your target audience? What are they trying to do?</p><p>At Related Works we’re currently working on a platform to host digital collections for libraries, museums, archives, and other cultural institutions. You will find all sorts of treasures in these collections: historical maps, photograph of the famous and even the mundane, digitized manuscripts and documents, audio and video from important events, etc.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Ic2fNwK6Q7Dljne2qRJoHw.jpeg" /><figcaption>Items you may find in Digital Collections</figcaption></figure><p>For this iteration of autosuggest our target audience is the public: <a href="http://www.nytimes.com/1998/03/15/nyregion/students-pursue-past-in-oral-history-project.html">a high-school student doing a history project about the Croton Dam</a>, <a href="https://99percentinvisible.org/episode/remembering-stonewall/">a podcast producer working on an episode about the LGBTQ community in NYC in the 60s</a>, <a href="https://www.amazon.com/dp/B0156ZH9CK/ref=dp-kindle-redirect?_encoding=UTF8&amp;btkr=1">a researcher writing a book about the Syrian colony in lower Manhattan at the turn of the century</a>, etc. Searches are usually oriented around a particular theme like “Worlds Fair”, “Gay Pride 60s”, etc, but these collections are filled with unique and unimaginable things, so users aren’t quite sure what they might find.</p><p>You could describe these as <a href="https://en.wikipedia.org/wiki/Exploratory_search">exploratory searches</a>: the user doesn’t have a particular objective and is using search to get a sense for what’s available and browse. This is as opposed to <em>known-item searches</em> where the user knows exactly the document or object they are looking for. Our goal, then, is to make it easy for users to dive into fairly broad searches that will offer them a ton of material to look at. If you were designing autosuggest for a power-user tool, like say Asana, your goal may be to direct users to individual items/objects/tasks, or even to suggest some advanced query syntax. I can imagine at some point we will offer a more specialized autosuggest on the internal version of our platform that institutions use to manage their content.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*m6bxKhUQhoaq_2xDN4w_8g.jpeg" /><figcaption>Sentry is a good example of autosuggest as a power-user tool</figcaption></figure><p>The other thing to bear in mind is that latency and UX is especially important for our target audience. We may be only a single-stop on a very long research journey for these folks. If our experience is slow or janky, they will probably move on. Users of internal/power-tools are usually more patient as long as you can point them in precisely the direction they need/want to go in.</p><h3>Measurement</h3><h4>Basics</h4><p>You can’t talk about goals without talking about metrics. How do we know if we’re actually getting anywhere? Not all goals are easily measurable, and even if they are, measurement is often a subtle and troublesome art. But that shouldn’t dissuade us from trying to understand how we’re doing.</p><p>Academic research tends to benchmark autosuggest engines using <a href="https://en.wikipedia.org/wiki/Mean_reciprocal_rank">Mean Reciprocal Rank</a> (MRR). MRR is a score between 0 and 1 that measures how high in the results the ultimately selected query was, on average. The higher the MRR, the better. Let’s look at an example:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YlGL1x9wgekcvaW1IZqo7Q.jpeg" /><figcaption>Calculating Reciprocal Rank</figcaption></figure><p>Let’s say the user typed the letter “c”, and selected “cats”, the third result. The reciprocal rank for the query would be ⅓. If they had selected “caterpillar” instead, the reciprocal rank would have been 1. The higher the rank, the higher the reciprocal rank. To understand how you are performing across many queries, you take an average of the reciprocal rank across that population.</p><p>I think MRR is useful and I would recommend measuring it, but it’s not the first metric I would look at because it’s a bit opaque. It’s useful for comparing different autosuggest strategies, which makes it useful for benchmarking and offline evaluation, but it doesn’t really give you a visceral sense for what’s happening on your website/app. And if you are adding autosuggest to your site for the first time it’s not really an option.</p><p>The first thing I would look at is what I call <em>Acceptance Rate: </em>the percentage of searches that come from autosuggest. If 60% of searches are coming from autosuggest, your autosuggest is probably pretty useful.</p><p>Another useful measure is <em>Average Keystrokes </em>(or <em>Average Prefix Length</em>)<em>. </em>Let’s say a user typed “so” and then selected the query “solange”. The prefix length would be 2. Averaging this figure across many searches lets us understand how many characters users typically have to type before finding something useful. The fewer characters, the better.</p><h4>Beyond the Search Threshold</h4><p>All of the metrics we’ve talked about so far are focused on <em>prediction:</em> how quickly can we figure out the query you want to type, and how high in the rankings can we get it? But what if the query you want to issue is actually a dead-end?</p><p><strong>As designers, product owners, cultural stewards, etc our ultimate goal isn’t for users to select precisely the query they had in mind, it’s to help them find something useful.</strong> So I like to think about autosuggest as part <em>prediction, </em>and part <em>recommendation</em>. It’s also why I prefer the term auto<em>suggest</em> rather than auto<em>complete</em>. It’s a short-cut, but it’s also an opportunity to steer users in a good direction and even to help them learn what you have to offer.</p><p>To that end, I think it’s useful to think about the outcomes <em>after</em> a user makes an autosuggest selection. If your endgame is easily measurable (like say, purchases on an e-commerce website), you can try measuring how often people that accept autosuggest selections make it to that success stage. Measuring <em>any</em> engagement in search (i.e. clicks or CTR) is not a terrible option, but clicks can be notoriously misleading (a topic for another blog post). If measuring engagement/success is hard, you can try measuring the inverse: how often are users that use autosuggest ending up on a page with little or no results? How often do they just abandon the site without doing anything else? In our case success isn’t as obvious, so we’ll be leaning heavily in this direction.</p><h4>Asking Humans</h4><p>We are big believers in UX research at Related Works. For autosuggest I think these studies would be useful for honing in on the interactions, which can be surprisingly tricky, especially if you are working on the super-user, precise, advanced-operator style of autosuggest.</p><p>I wouldn’t suggest UX research for understanding the effectiveness of one autosuggest algorithm over another (or at least not in isolation). Most search experiences have a long-tail of unique or infrequently issued queries so it’s remarkably hard to get a sense for your performance from just a handful of cases.</p><h3>Coming Up</h3><p>In the <a href="https://medium.com/related-works-inc/building-an-autosuggest-corpus-part-1-3acd26056708">next blog post</a> we’ll break-down all the technical components in an autosuggest product and start talking about building a suggestion corpus.</p><p>Feel free to reach out with suggestions, questions, corrections, insults, accusations, etc. We are, after all, tiny meaningless specks in a vast and incomprehensible cosmos.</p><p>If you’re interested in reading more I would recommend Daniel Tunkelang’s <a href="https://queryunderstanding.com/autocomplete-69ed81bba245">work on the subject</a>, and <a href="https://staff.fnwi.uva.nl/m.derijke/wp-content/papercite-data/pdf/cai-survey-2016.pdf">this survey</a> as good jumping-off points.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c1ca3edaf1eb" width="1" height="1" alt=""><hr><p><a href="https://medium.com/related-works-inc/bootstrapping-autosuggest-c1ca3edaf1eb">Bootstrapping Autosuggest</a> was originally published in <a href="https://medium.com/related-works-inc">Related Works</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>