<?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 Alex Liu Roc on Medium]]></title>
        <description><![CDATA[Stories by Alex Liu Roc on Medium]]></description>
        <link>https://medium.com/@alex.liu.roc?source=rss-e3f5232fa34------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*9H6Lrbu6VkB6fOSD</url>
            <title>Stories by Alex Liu Roc on Medium</title>
            <link>https://medium.com/@alex.liu.roc?source=rss-e3f5232fa34------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 19:38:37 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@alex.liu.roc/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[Understanding the Impossibility of Fairness]]></title>
            <link>https://medium.com/@alex.liu.roc/understanding-the-impossibility-of-fairness-199bba6c9072?source=rss-e3f5232fa34------2</link>
            <guid isPermaLink="false">https://medium.com/p/199bba6c9072</guid>
            <category><![CDATA[binary-classification]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[classification-metrics]]></category>
            <category><![CDATA[algorithmic-fairness]]></category>
            <category><![CDATA[diagrams]]></category>
            <dc:creator><![CDATA[Alex Liu Roc]]></dc:creator>
            <pubDate>Sat, 26 Aug 2023 16:35:38 GMT</pubDate>
            <atom:updated>2023-08-29T20:00:24.622Z</atom:updated>
            <content:encoded><![CDATA[<p>In the last <a href="https://medium.com/@alex.liu.roc/demystifying-algorithmic-fairness-definitions-551a72a438d0">article</a> we discussed common statistical definitions for algorithmic fairness, describing them with plain English and diagrams to aid intuition. In this article, we apply these definitions to the well-known theory, dubbed the Impossibility of Fairness.</p><p>The proof for this theorem, despite being a few lines, still does not draw out its intuition because it relies on mathematical jargon rather than visuals (<a href="https://doi.org/10.1089/big.2016.0047">Chouldechova, 2017</a>). On the other hand, I think that the intuition behind this theory can actually be explained quite easily. I’ll try to do so here with the help of some visuals and an example.</p><h3>Background</h3><p>One line of debate in algorithmic fairness has centered around the exclusivity between separation and sufficiency. The debate first appeared and developed with respect to COMPAS, a recidivism risk algorithm. The algorithm purported to predict the likelihood that a defendant would recidivate (i.e. commit a crime after being released on parole), and help a judge set bail.</p><p>After Angwin and colleagues discovered the violation of separation in the COMPAS algorithm (<a href="https://www.taylorfrancis.com/chapters/edit/10.1201/9781003278290-37/machine-bias-julia-angwin-jeff-larson-surya-mattu-lauren-kirchner">2022</a>), COMPAS rebutted by showing that their algorithm did not violate sufficiency, and thus was not discriminatory: Each risk score corresponded to the same rate of recidivism across groups (<a href="http://arxiv.org/abs/1808.00023">Corbett-Davies &amp; Goel, 2018</a>). Subsequent studies by Kleinberg et al. and Couldechova showed that both perspectives were correct: <strong>Under practical conditions, where distribution of outcomes is unequal, it could not be the case that an algorithm satisfies both sufficiency and separation</strong> (<a href="https://doi.org/10.1089/big.2016.0047">Chouldechova, 2017</a>; <a href="http://arxiv.org/abs/1609.05807">Kleinberg et al., 2016</a>). This conundrum was dubbed the “Impossibility of Fairness”.</p><h3>Visualizing the Impossibility of Fairness</h3><p>Recall in the last <a href="https://medium.com/@alex.liu.roc/demystifying-algorithmic-fairness-definitions-551a72a438d0">article</a> the definitions of sufficiency and separation. We used the following visuals. It shows the confusion matrix for two protected classes, and maintains the “numerator inside denominator” visual pattern used in the figures before. Similar colors represent the assertion that the two ratios are equal:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HVIZQHpj3cEL1Fxnuo_9KQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mkjvVAsyK1SVxCsDPp_JaA.png" /></figure><p>We’ll be using the same diagram style to understand the impossibility of fairness, particularly why sufficiency and separation can never be satisfied in practice. In particular, the following visual shows a situation where sufficiency is satisfied yet separation cannot be satisfied:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pYv4NQtX8ot6i_zK2SpNaQ.png" /></figure><h3>Example: COMPAS</h3><p>We will exemplify the impossibility of fairness through role play. Specifically, we will act as the designers of the COMPAS algorithm, which attempts to predict the likelihood that a defendant would recidivate if released from jail.</p><p>We will make a few simplifications to the problem space to ease understanding. First, we will simplify this problem to the binary: 1 if predicted to recidivate, 0 if not. Second, we analyze model performance along one protected class, race, using two classes, white and Black. The outcome variable, whether the defendant really recidivated or not, remains binary.</p><h4>Step 1: Problem Setup</h4><p>We are designing an algorithm that lives in the real world using real datasets. As such, our data takes on the biases that the world has to offer.</p><p>Concretely, our dataset has that Blacks recidivate (60:40) at a higher rate than whites (30:70). This occurs for a number of societal reasons such as discriminate policing and a historical unequal distribution of socio-economic resources that are critical to reintegration.</p><p>Our job is now to design our recidivism predictor. Here, we uptake the usual statistical fairness definitions that algorithm designers usually uptake, and the one the actual COMPAS designers chose to stand behind: <strong>Sufficiency. </strong>In other words, precision rates must be equal. Here we will set the precision rates to 75%: The system’s positive and negative predictions should both be correct about 3/4 of the time.</p><p>Altogether, our algorithm must allocate the set of black and white recidivators and non-recidivators below into their predicted category, while maintaining sufficiency. This algorithmic task is visualized below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EdAG-CF-NNhLyTRWzlYi1Q.png" /></figure><p>I encourage you to try to perform this allocation by hand yourself. In other words, how would you split up each outcome column’s population to each prediction so as to maintain the 75% precision in both negative and positive cases?</p><h4>Step 2: Prediction Allocation</h4><p>You can actually use a system of equations, separately for <a href="http://x/(x+y)=3/4;%20(70-y)/((30-x)+(70-y))=%203/4;">white</a> and <a href="https://www.wolframalpha.com/input?i=x%2F%28x%2By%29%3D3%2F4%3B+%2840-y%29%2F%28%2860-x%29%2B%2840-y%29%29%3D+3%2F4%3B+">Black</a>, to solve this problem.</p><p>Here is an allocation that satisfies sufficiency (with some slack given that some solutions are decimals so we round to the nearest integer):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RLU9QXTU9pgqRqEk6Y1efg.png" /></figure><h4>Realization and Implications</h4><p>Looking at the figure above we see that, while predictions for both positive and negative classes are ~75% correct (thus satisfying sufficiency), separation is not satisfied. In other words, the false positive rates are vastly different:</p><ul><li>For whites, the FPR is 3/70 = 4.3%</li><li>For Blacks, the FPR is 17/40 = 42.5%</li></ul><p>The implication from our algorithm, if designed this way, is that innocent Black defendants will be incorrectly labeled as recidivators at a much higher rate than their white counterparts. The root of this inconsistency is from the disproportionate distribution of outcomes in the first place.</p><p>This observation is exactly what Angwin and colleagues pointed out in the COMPAS algorithm (<a href="https://www.taylorfrancis.com/chapters/edit/10.1201/9781003278290-37/machine-bias-julia-angwin-jeff-larson-surya-mattu-lauren-kirchner">2022</a>). It was subsequently mathematically proven that, given an unequal distribution of outcomes, it <em>had</em> to be the case that sufficiency and separation could not be simultaneously satisfied (<a href="https://doi.org/10.1089/big.2016.0047">Chouldechova, 2017</a>; <a href="http://arxiv.org/abs/1609.05807">Kleinberg et al., 2016</a>).</p><p>The upshot of this dilemma is that any domain in which there is an already unequal distribution of outcomes among protected classes will never be able to have an algorithm that satisfies both requirements. In the US, one would be hard-pressed to find such a domain with equally distributed outcomes, especially with respect to race. This is true for housing (<a href="https://home.treasury.gov/news/featured-stories/racial-differences-in-economic-security-housing"><em>Racial Differences in Economic Security</em>, 2022</a>) and employment (<a href="https://www.bls.gov/opub/reports/race-and-ethnicity/2020/home.htm"><em>Labor Force Characteristics by Race and Ethnicity, 2020</em>, 2021</a>) as well.</p><h3>Interpretations</h3><p>Wallach and Jacobs argue that the impossibility was not a debate between two operationalizations of “fairness”, but rather different constructs altogether (<a href="https://dl.acm.org/doi/abs/10.1145/3442188.3445901">2021</a>). Barocas and colleagues echoed this line of argument by emphasizing the differences in values at play in sufficiency and separation in COMPAS: The former valued the algorithm design perspective, who is concerned with algorithmic accuracy, while the latter valued the defendant perspective, who was concerned with being falsely labeled at risk of recidivating.</p><p>When decisions are connected to consequential outcomes such as jail-time, taking the sufficiency route has the consequence of causing disproportionate experiences of jail-time by protected attributes (<a href="https://doi.org/10.1089/big.2016.0047">Chouldechova, 2017</a>), perpetuating historical inequality in the legal-prison system.</p><p>Ben Green goes a step further, offering that algorithms should be asked whether or not an algorithm should exist in the first place (<a href="https://link.springer.com/article/10.1007/s13347-022-00584-6">Green, 2022</a>). For instance, rather than designing a fairer college admission algorithm, one should consider the consequences of economic inequality that arise from the lack of college opportunity, and acknowledge that any decision-maker, whether algorithmic or not, will be contributing to to such economic opportunity gatekeeping, no matter how “fair” it is.</p><h3>Conclusion</h3><p>In this article we used an example algorithm design to draw out the Impossibility of Fairness. With some helpful visuals, we eventually gained intuition for why sufficiency and separation cannot be simultaneously satisfied by a classifier under unequal distribution of outcomes between classes.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=199bba6c9072" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Demystifying Algorithmic Fairness Definitions]]></title>
            <link>https://medium.com/@alex.liu.roc/demystifying-algorithmic-fairness-definitions-551a72a438d0?source=rss-e3f5232fa34------2</link>
            <guid isPermaLink="false">https://medium.com/p/551a72a438d0</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[algorithmic-fairness]]></category>
            <category><![CDATA[binary-classification]]></category>
            <category><![CDATA[diagrams]]></category>
            <dc:creator><![CDATA[Alex Liu Roc]]></dc:creator>
            <pubDate>Sat, 26 Aug 2023 15:03:11 GMT</pubDate>
            <atom:updated>2023-08-29T19:45:11.948Z</atom:updated>
            <content:encoded><![CDATA[<p>The motivation of this article comes from trying to understand various statistical definitions for algorithmic fairness. After reviewing some background, I’ll introduce a visual framework by explaining familiar binary classification metrics. Then, I’ll apply the same visual framework to the fairness definitions, making them easy to understand.</p><p>This article leads to the next <a href="https://medium.com/@alex.liu.roc/understanding-the-impossibility-of-fairness-199bba6c9072">article</a> on the Impossibility of Fairness.</p><h3>Background</h3><p>Recent decades have seen automated decision-making systems (i.e. algorithms) take hold in consequential domains protected by anti-discirmination law (<a href="https://www.google.com/books/edition/Automating_Inequality/pn4pDwAAQBAJ?hl=en&amp;gbpv=1&amp;dq=automating+inequality&amp;pg=PP10&amp;printsec=frontcover">Eubanks, 2018</a>). For instance, employment is mediated through digital advertising promoted by automated content recommendation engines, while employee screening and hiring can be aided or completely automated by softwares (<a href="https://journals.sagepub.com/doi/full/10.1177/2053951720938093">Ajunwa, 2020</a>). Housing has also taken a digital turn, with housing listings going online and advertising taking to social media <a href="https://www.zotero.org/google-docs/?90dGXM">(Asplund et al., 2020)</a>.</p><p>The conversation about algorithms and machine learning in consequential domains has been accompanied by a fervent call to the issue of fairness in these systems. Fairness in machine learning and algorithms has its roots in American anti-discrimination law. Because of its technical nature, statisticians have made a variety of attempts to translate legal doctrine to statistical definitions.</p><p>In this essay we examine the popular definitions of algorithmic fairness. For each we will give the statistical and “plain english” definitions. The next <a href="https://medium.com/@alex.liu.roc/understanding-the-impossibility-of-fairness-199bba6c9072">article</a> reviews the main theoretical obstacle to achieving fairness in algorithmic systems in a staticial sense, aptly dubbed the “impossibility of fairness”.</p><h3>Primer- Binary Prediction Metrics</h3><p>If you’ve ever done binary classification before (e.g. logistic regression models), then you’ve encountered terms such as accuracy, recall, and precision. These are terms associated with the behavior of the classifier with respect to prediction and outcome. Altogether, you can glean these metrics, and a host of other values, from the confusion matrix:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/488/1*tC8CIJ7iI1CG54q_o61uhQ.png" /></figure><p>The matrix is essentially a 2x2 cross-product of the two possible predictions (Y’=0 and Y’=1) and the two possible outcomes (Y=0 and Y=1).</p><p>We formalize common metrics for traditional binary classification here:</p><ul><li>Precision (positive) = TP/(TP+FP). How often our positive predictions are correct.</li><li>Precision (negative) = TN/(TN+FN). How often our negative predictions are correct.</li><li>Recall (positive) = TP/(TP+FN). How often the real positives get labeled correctly.</li><li>Recall (negative)= TN/(TN+FP). How often the real negatives get labeled correctly.</li><li>False Positive Rate = FP / (FP+TN). How often the real negatives are incorrectly labeled.</li></ul><p>While in practice the term “precision” and “recall” usually denotes the positive version, I’ve added the negative versions here too. You can visualize each of these metrics as circling the numerators and denominators as below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LpDn6MqB6Ni3Ri9NVkMabg.png" /></figure><h3>Algorithmic Fairness Metrics</h3><p>In the traditional, offline domain, definitions of fairness in legal literature have revolved around two types: disparate treatment and disparate impact. In the former, the decision-maker treats one person in a biased manner due to their protected attribute status, for example for being a Female. Disparate impact, on the other hand, focuses on groups. Instead of showing an individual case where bias took place, the plaintiff must show that a group of members of a given protected attribute are being mistreated as a whole, (for example over all receiving less job call-backs).</p><p>Because these decision-making algorithms tend not to treat individuals differentially based on the status of protected attribute status specifically, the body of statistical fairness definitions have focused on groups (i.e. disparate impact), such as for race and gender. Definitions of statistical fairness evolved from traditional notions of algorithm classification accuracy metrics, such as accuracy, recall, and precision (<a href="https://fairmlbook.org/pdf/fairmlbook.pdf">Barocas et al., 2017</a>). They involve comparing either real-life outcomes or algorithmic classification scores across groups, sometimes subject to people being of the same scores or outcomes, respectively.</p><p>Definitions of fairness, unlike binary classification systems, incorporate the notion of “protected class”, such as race and gender. If we are considering two protected classes, then this amounts to adding another confusion matrix, one for each class. We now have three binary variables to consider: prediction, outcome, and class, amounting to eight separate values.</p><p>We review some of the most common statistical definitions of algorithmic fairness below.</p><h4>Sufficiency</h4><p>Plain English</p><ul><li>“Risk scores should indicate the same real-life outcome, regardless of sensitive attribute membership”</li></ul><p>Statistical definition</p><ul><li>Precision should be equal across classes.</li><li>P(Y | Y’, Ai) = P(Y | Y’, Aj)</li><li>Y ⊥ A | Y’</li></ul><p>The visual below demonstrates sufficiency applied to the binary classification case. It shows the confusion matrix for two protected classes, and maintains the “numerator inside denominator” pattern used in the figure above. Similar colors represent the assertion that the two ratios are equal. In this figure, sufficiency is satisfied because precision is equal across the two classes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/1*WrJZNkzzN33L4X47-Pd6FQ.png" /><figcaption>Visualizing sufficiency. Identical colors represent equal ratios.</figcaption></figure><p>Sufficiency expresses the idea that the same score should mean the same real-life outcome for every group. One example might be that, for a recidivism risk score between 0 and 1, the value 0.6 should reflect some probability of recidivism, say 60%, for every race. If instead, Blacks who receive 0.6 recidivate 40% of the time while whites who receive 0.6 recidivate 70% of the time, such an algorithm would violate sufficiency.</p><p>While sufficiency violations are an important concern, they are rare in practice (<a href="https://fairmlbook.org/pdf/fairmlbook.pdf">Green, 2022</a>). This is because algorithmic models are often designed to give scores predictive of outcomes themselves, and are optimized (through loss functions) to give scores that best reflect these outcomes. Thus, the optimal scoring function will be one whose scores best match outcomes, regardless of sensitive attribute value.</p><p>One exception is the classic algorithm auditing example of Obermeyer et al. (<a href="https://www.science.org/doi/full/10.1126/science.aax2342?casa_token=K35zdXeJDswAAAAA%3AYpJVpjEbl0_IIMyvSPf8kafboKV0xSaxkxOF-ZI_rTKRapkBFBKzYInLXE2Kzu_AxVQDwnl481KklA">2019</a>). Examining a health risk score algorithm, the authors discover that it violates sufficiency because the variable used to train the risk scores was actually a proxy for the outcome, rather than the outcome itself. Specifically, the algorithm tries to predict people’s healthcare costs, whereas the outcome of interest was healthcare outcomes (as defined by the oft-used “comorbidity score” in the healthcare literature). Since historical inequities in healthcare access in the US across racial lines meant that Blacks, in general, pay less money for treatment at each comorbidity score, the risk scores trained on healthcare expenditures did not equate to the same outcomes for each racial group: At every risk score, Blacks had a higher comorbidity score. The substantive consequence of applying this algorithm is that Blacks would receive as much healthcare attention and resources as a white counterpart who was healthier than they were, maintaining historical health inequities.</p><h4>Separation</h4><p>Plain English</p><ul><li>“People of the same real-life outcome should get treated similarly by the algorithm, regardless of sensitive attribute membership”</li></ul><p>Statistical Definitions</p><ul><li>Recall should be equal across classes.</li><li>P(Y’ | Y, Ai) = P(Y’ | Y, Aj)</li><li>Y’ ⊥ A | Y</li></ul><p>The visual below demonstrates separation applied to the binary classification case. In this figure, separation is satisfied because precision is equal across the two classes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/1*8DoROyXh9u6RqPlTS0tQnQ.png" /><figcaption>Visualizing separation. Identical colors represent equal ratios.</figcaption></figure><p>Separation reflects the idea that people with similar outcomes should be treated similarly by the algorithm. Compared to sufficiency, this metric values the ground-truth outcome rather than the risk score as the locus of comparison, and is not immediately satisfied by training the algorithm optimally on the outcome of interest.</p><p>A classic example is Angwin and colleagues, who analyze the COMPAS recidivism risk assessment algorithm. This algorithm tried to predict the probability that a given defendant would recidivate- commit a crime after being released- in order to help judges determine whether or not to release someone from prison (<a href="https://www.taylorfrancis.com/chapters/edit/10.1201/9781003278290-37/machine-bias-julia-angwin-jeff-larson-surya-mattu-lauren-kirchner">Angwin et al., 2022</a>). The authors find that non-recidivating Black defendants received high risk scores at nearly double the rate of non-recidivating white defendants. In the language of classifiers, this finding translates to a much higher false positive rate for Blacks than for whites. Much like Obermeyer’s study, the algorithm that got implemented ended up maintaining historical inequalities in consequential domains of healthcare and criminal justice, rather than “debiasing” domains that are already bias-ridden.</p><h4>Independence/Demographic Parity</h4><p>Plain English</p><ul><li>“A given score should be equally likely for each group”</li><li>“The algorithm should render a given score to groups at the same rate as the group appears in the population”</li></ul><p>Statistical definitions</p><ul><li>P(Y’ | Ai) = P(Y’ | Aj)</li><li>#(Y’,Ai) / #(Y’) = #(Ai) / #(Population) (where # represents the count of people)</li><li>Y’ ⊥ A (The upside-down T means “independent”)</li></ul><p>Independence, or demographic parity, reflects the idea that no group should get disproportionately allocated a given algorithmic score. In practice, this form of discrimination is often operationalized by (1) soliciting the rate of groups within a population (i.e. demographic parity), (2) the rate of groups that receive a certain determination by the algorithm, and (3) comparing the two.</p><p>One example of demographic parity is Chang et al., who investigate the Google ad delivery system to see how advertisers target college scholarship ads across New York City (<a href="https://arxiv.org/abs/2109.15294">2021</a>). They find evidence that many advertisers, including universities, disproportionately allocate advertisements across zip codes in a way that violates demographic parity of racial tracts in the city. Specifically, while New York City has a racial makeup of (12% Asian, 19% Black, 45% White), some websites advertised in zip codes whose combined racial makeup was unaligned. For instance, schools from the City University of New York system were estimated to advertise to 42% Black people; Meanwhile, a different university was found to advertise to 33% Asian people.</p><p>While some of the more common statistical definitions of group fairness, we note that these are not comprehensive (e.g. <a href="https://dl.acm.org/doi/abs/10.1145/3442188.3445919">Kasey and Abebe, 2021</a>).</p><h3>Conclusion</h3><p>Here we discussed basic statistical defintiions of algorithmic fairness, with the help of some intuitive diagrams. In the next <a href="https://medium.com/@alex.liu.roc/understanding-the-impossibility-of-fairness-199bba6c9072">article</a>, we’ll apply what we learned to the famous algorithmic fairness theory, dubbed the Impossibility of Fairness.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=551a72a438d0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to Train Your YouTube Recommender]]></title>
            <link>https://medium.com/@alex.liu.roc/how-to-train-your-youtub-52db086365ab?source=rss-e3f5232fa34------2</link>
            <guid isPermaLink="false">https://medium.com/p/52db086365ab</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[algorithm-auditing]]></category>
            <category><![CDATA[recommender-systems]]></category>
            <category><![CDATA[social-science-research]]></category>
            <category><![CDATA[research-paper]]></category>
            <dc:creator><![CDATA[Alex Liu Roc]]></dc:creator>
            <pubDate>Fri, 25 Aug 2023 21:06:09 GMT</pubDate>
            <atom:updated>2023-08-26T15:04:07.928Z</atom:updated>
            <content:encoded><![CDATA[<p>This article describes a recent paper I published in the International Conference of Web and Social Media (ICWSM). The paper investigates the efficacy of several features that YouTube provides its users to remove unwanted recommendations. You can find the full paper <a href="https://arxiv.org/abs/2307.14551">here</a>, and corresponding code base <a href="https://github.com/avliu-um/youtube-disinterest">here</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/792/1*na-YNZjKvNKLRAXREwKZNQ.png" /><figcaption>Main descriptive diagram of my paper, Liu et al., 2024.</figcaption></figure><h3>Motivation</h3><p>YouTube can sometimes make unwanted recommendations. This content could be harmful to users in a variety of ways, such as Regretful content, societally-harmful content, and existing viewpoints [EXPAND].</p><p>In comes a string of recent features that platforms have developed, which purport to give users agency in desinging their own recommendations to better accommodate their tastes, identity, perspectives, and mental health. On YouTube, these include the Dislike button, “Not interested” button, and “Don’t recommend channel” button. Instead of having to “manipulate” the system by purposefully altering inputs designed for more background [FIX] interactions to get the desired output, the user is now given options designed specifically to receive the user’s constructive feedback on their recommendations. In essence, they’re infusing more user agency into their system.</p><p>While the positive prospect of increased user agency is enticing, we should be wary to accept these changes at face value. First, do they even work? Second, how do users know about and interact with them in the first place?</p><p>With these questions it becomes clear why the empirical efficacy of these buttons is important to understand. At a narrow layer, users should have tools at their disposal to avoid unwanted recommendations not only because they violate their personal ethos, but also because they are societally harmful in general. At a broader level, allowing these features to go about untested empirically by an independent party could lead to a situation where the platform can simultaneously tout the tools they’ve given users to avoid harmful information, whilst its underlying proliferation across the content remains unchanged. In essence, platforms could have their cake and eat it too by giving users the ineffective vaccines (user controls) to their own self-created disease (harmful YouTube content).</p><h3>Research Questions</h3><p>Relatively little is known about the efficacy of these buttons in practice, nor about users’ awareness of and confidence in them. To address these gaps, this work investigates how well simulated YouTube users (agents) can populate their recommendation feeds with content from a certain topic (the “stain” phase), as well as the ability for the recommendations of that topic to be removed by using a strategy to indicate disinterest (the “scrub” phase). Specifically:</p><h4>RQ1: how responsive are YouTube recommendations to watching many videos of the same topic (stain)?</h4><p>We selected four topics for stain: <strong>Alt-Right</strong>, <strong>Antitheism</strong>, <strong>Political Left</strong>, and <strong>Political Right</strong>. These topics are particularly interesting because they are well-studied for their consequential roles in political polarization and extemism.</p><h4>RQ2: how responsive are YouTube recommendations to repeatedly performing a variety of strategies to try to remove unwanted videos of a topic (scrub)?</h4><p>While plenty of literature exists on how to get <em>more</em> recommendations of our stain topics, little is known about removing them. We examined six scrub strategies for removal (<strong>Watch neutral</strong>, <strong>Dislike</strong>, <strong>Delete</strong>, <strong>Not interested</strong>, <strong>No channel</strong>, and <strong>Dislike recommended</strong>), as well as a <strong>None</strong> control strategy.</p><h4>RQ3: what are real users’ experiences with the platform features that we test in RQ2?</h4><p>Lastly, we conducted a complementary survey study to understand real users’ awareness of and experience with those scrubbing strategies on YouTube.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/726/1*p3spsMCA8nts4E242JVvdw.png" /><figcaption>Pictures of the buttons we investigated (Source: YouTube)</figcaption></figure><h3>Sock Puppet Study</h3><h4>Methodology</h4><p>We used code scripts to emulate YouTube users. These simulated users (also called “agents” or “sock puppets”) interacted with the system by watching videos and pressing relevant buttons. Doing so gives us the added advantage of interacting with the platform and receiving personalized recommendations like a real YouTube user, while simultaneously giving us as researchers the advantages of code, namely the ability to control every interactions to coordinate bots.</p><p>Broadly, our agents first purposely populate their feed with videos from this unwanted topic (“stain phase”); Then, they take on one of a variety of strategies to try to eliminate such videos from being recommended (“scrub phase”).</p><p>Our agents use web-scraping methods to collect the top 10 recommendations from the homepage and videopage at three strategic points:</p><ul><li>P1: The beginning of the stain phase.</li><li>P2: The end of the stain phase.</li><li>P3: The end of the scrub phase</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*udaiCZp_z5RSqqKNt6kfPg.png" /><figcaption>Flowchart for sock puppet run.</figcaption></figure><p>We used Selenium and undetected-chromedriver to simulate web interactions with YouTube while evading bot detection systems. For a given topic, we ran 5 bots for each of the 7 scrubbing strategies in parallel. This resulted in ~140 unique bots, ran 35 at a time in parallel with the help of some cloud computing on AWS.</p><p>Our agents collected data about many recommendations during their runs. We would like to label them for whether they belong to the topics that the agents were assigned to (what we call “stain”). After testing a few automatic methods, including deep-learning, we settled for manual annotation between myself and the second author (Siqi Wu). We were confident in our labels after digesting previous labelling codebooks of the same topics and achieving high Interrater Reliability (a measure for measuring the reliability and consistency of your labeling procedure).</p><h4>Results</h4><p>We cover a selection of interesting results. You can see all of them in the full paper. Here we cover the results gleaned from changes in recommendations between P1, P2, and P3. We used a Wilcoxon Ranked-Sum test to identify sginficant difference (as the data was non-normal and the comparison before and after the “stain phase” treatment was a paired test).</p><p><em>Stain phase-</em> Watching a topic increased its presence on the homepage (the landing page of YouTube.com), though the stain never covers more than half of the recommendations. Watching a topic had less effect on the recommendations shown on videopages (the page while watching a video).</p><p><em>Scrub phase- </em>For scrubbing a topic from the homepage, the most effective action was clicking the “Not interested” button on a recommended video (reducing 88% of unwanted recommeendations on average). In contrast, none of the scrubbing significantly reduced the number of recommendations of videos on the topic shown on videopages.</p><p>These main results can be identified from the table below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*E30FFKNu8hcCMZXt1Ijy6A.png" /></figure><h3>Survey Study</h3><h4>Methodology</h4><p>In this section, we want to understand better the relationship between real users and the disinterest buttons we used in the sock puppet study. The buttons we consider are “Delete” (delete a video from watch history), “Dislike”, “Not interested”, and “Don’t recommend channel”. We ran a survey to determine this. Specifically, we asked for respondents’ experiences with our disinterest buttons, with respect to three constructs:</p><ul><li><em>Awareness</em>: Before taking this survey, were you aware this button existed?</li><li><em>Usage</em>: Have you used this button to remove unwanted recommendations?</li><li><em>Belief in efficacy</em>: Recall the times when you used this button to remove unwanted recommendations. How effective do you think it was? Please rate from 1 (not at all effective) to 5 (completely effective).</li></ul><p>We recruited 300 participants from the survey recruitment platform Prolific, and ran the survey on the survey delivery platform Qualtrics.</p><h4>Results</h4><p>We received 274 usable results. To better generalize our results to the target population (adult YouTube users in the US), we used post-stratification.</p><p>Our main result was nearly half of survey respondents (44%) were not aware of the most effective feature (pressing “Not interested”). Those who were aware of it used it often (82.8%), and perceived its efficacy (3.42/5) to be less than that of the “Don’t recommend channel” button, contrary to our findings from the audit study.</p><p>On the other hand, users do not use the “Dislike” button to remove unwanted recommendations, despite most knowing about its existence. Our survey respondents’ intuition to not use this button fit our findings of inefficacy in the sock puppet section.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HJ1F-3uGBVduIrzqYOUeUg.png" /><figcaption>Survey results, post-stratified to fit adult US YouTube using population, with 95% confidence interval. “not-int” and “no_chan” indicate the “Not interested” button and “Don’t recommend channel” button, respectively.</figcaption></figure><h3>Conclusion</h3><p>Put together, our sock puppet and survey findings suggest that if YouTube wanted to allow users to more effectively remove unwanted recommendations, it should make its effective platform-features for doing so more broadly known to the general YouTube population.</p><p>Doing so would not only benefit users’ experience. It would also be in the best interest of the platform because allowing users to have more agency to tailor algorithmic decisions to their preferences can build and maintain their trust in the system (<a href="https://dl.acm.org/doi/abs/10.1145/2792838.2800195?casa_token=kwG70lyirjEAAAAA:mp3cafXMkJ7rKFfFOeRi3Do-KKeO9d6lSsYt89ziqM60WHggGBCqYiPUdXauJZHtehU-9Ezybzc">Ekstrand et al. 2015</a>), as well as increase overall satisfaction (<a href="https://www.sciencedirect.com/science/article/pii/S0747563220300984?casa_token=xNdY_SEQyVwAAAAA:y2izeOH-2Z5R7HPDJ31iq_-G4GrT_f4cR27sB63v6VkaAtWloHUYypy2KvWaxmOUgTsm_EQ">Shin, 2020</a>).</p><p>One implication for platform designers is that they should make buttons such as “Not interested” more widely known by increasing its discoverability on the website. To that end, Ricks and McCrosky provide a blueprint. In their experiment, they found that when their users were displayed “Don’t recommend this” buttons prominently and clearly on recommendation title cards, instead of being hidden behind a three-dots button or requiring the user to be led away from their current page, they were more than twice as likely to use it (<a href="https://foundation.mozilla.org/en/research/library/user-controls/report/">Ricks and McCrosky 2022</a>).</p><p>Thus, we join existing calls for YouTube to amplify more broadly the effective ways to remove unwanted recommendations on its platform.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=52db086365ab" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Demystifying Tensor Strassen’s Algorithm]]></title>
            <link>https://medium.com/@alex.liu.roc/demystifying-tensor-strassens-algorithm-c1eb5c9a972c?source=rss-e3f5232fa34------2</link>
            <guid isPermaLink="false">https://medium.com/p/c1eb5c9a972c</guid>
            <category><![CDATA[matrix-multiplication]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[diagramming]]></category>
            <dc:creator><![CDATA[Alex Liu Roc]]></dc:creator>
            <pubDate>Fri, 25 Aug 2023 14:39:37 GMT</pubDate>
            <atom:updated>2023-08-25T15:06:03.560Z</atom:updated>
            <content:encoded><![CDATA[<p>This article is my attempt at explaining a complicated algorithm that I came across as an undergraduate researcher at UB, one that took me a while to understand. To demystify this algorithm, I incorporated visuals, drew diagrams, and tried to interpret different components of the algorithm as intuitively as possible. I would like to share that demystification process here.</p><p>The algorithm is Tensor Implementation of Strassen’s Algorithm (Kumar et al., 1995). Put as simply as possible: It implements a fast matrix multiplication algorithm (Strassen’s Algorithm) using matrices well-designed matrices to represent the different operations performed in the algorithm.</p><p>Matrix multiplication is an important concept to understand if you’re interested in machine learning, because it undergirds all models and computations that allow your predictions and classifications to occur in the first place. In my research project, my collaborators and I were trying to understand whether we could perform this central operation faster and in a more structured way. The project eventually led to a <a href="https://proceedings.mlr.press/v162/dao22a.html">publication</a> at ICML 2022.</p><p>Back to the algorithm at hand, the central formula seemed completely unapproachable at first (Section 3.1 of Kumar et al., 1995):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0xMyJOl6R-suTxmRk8ep_Q.png" /><figcaption>Tensor Strassen’s Algorithm (complete).</figcaption></figure><p>Safe to say, when I first browsed through the paper, I was not sure whether or not I’d ever be able to comprehend it. Since my first task as a researcher was to understand this algorithm, I was not confident about my future on this project.</p><p>In the coming sections I’ll walk you through the steps that allowed me to slowly demystify this algorithm. We’ll begin with a quick background on Strassen’s algorithm and the generic matrix formulation that Kumar and co-authors used to implement it. Then, we’ll iteratively make observations about Strassen’s and matrix operations that allow us to slowly unravel the generic formulation into the detailed formulation you see above.</p><h3>Strassen’s Algorithm</h3><p>Matrix multiplication is a central operation in machine learning, neural networks and computer vision. From a computing perspective, naively multiplying together to matrices A and B, each of size n x n, takes O(n³) time. This is accomplished by implementing the formula for matrix multiplication directly on the matrices (for the rest of this article, we will call this algorithm the “Naive” algorithm). For many years, it was assumed that no algorithm could do better than that worst case time.</p><p>In 1969, Strassen shocked the world when he invented an algorithm that ran faster than naive. By leveraging recursion, he created an algorithm that ran in time O(n^{2.81})!</p><p>You can find thorough descriptions of Strassen’s Algorithm <a href="https://www.topcoder.com/thrive/articles/strassenss-algorithm-for-matrix-multiplication">here</a>; Here, we will only report the algorithm (multiplying arbitrary square matrices, A and B) and point out a few important observations:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GhrdaOHdGe9EcgE5Td2bdA.png" /><figcaption>Strassen’s Algorithm. Note that subscripts 11, 12, 21, and 22 represent NW, SW, NE, SE quadrants, respectively.</figcaption></figure><p>What Strassen realized was that, by splitting up the matrix into quadrants, and then cleverly recursively multiplying and combining them, he could arrive at a formula with a recursive runtime of T(n) = 7T(n/2) + cn², which yields an overall runtime of O(n ^ log_7(2)), listed above.</p><h3>General Formula</h3><p>Observe that the elements of A and B only interact (i.e. multiply) when we<br>reach the base case. In all other recursive calls, we are adding and subtracting elements purely within A, and purely within B. Since this is the case, we can view Strassen’s as an algorithm that deals with the elements of A and B completely separately, then combines them only after the base case is reached.</p><p>This observation motivates the general formula for Kumar et al.’s implementation of Strassen’s Algorithm:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/858/1*8dLQUuiSDq8mGkT3sAqNWw.png" /></figure><p>In the coming sections we will introduce more detail into this formula, each motivated by an observation about the form of Strassen’s algorithm. We’ll focus on preparing A, but note that definitions for preparing B and combining are analagous and covered in detail in the original paper.</p><h3>Detail 1: Quadrants and Z-order Vectorization</h3><p>Next, observe that at each recursive call, we are adding and subtracting quadrants of A and B. Even after recursive calls are completed, we are still adding and subtracting resultant quadrants (see the t’s).</p><p>It follows that an ideal matrix operation formula that captures Strassen’s algorithm should be able to add and subtract quadrants of A and B (separately) at any recursive level.</p><h4>Z-Order Vectorization</h4><p>Introduce the z-order vectorization function, a way to manipulate a matrix that is conducive to quadrant-level operations.</p><p>Vectorization functions are fancy term to denote ways of turning a matrix into a vector while preserving every element. A few simple vectorization functions are row-major and column-major. To acquire the row-major vectorization of a matrix, all you do is read the matrix row by row and write those values down the resultant vector. Column-major vectorization is defined analogously.</p><p>Since vectorization functions preserve every element in the matrix, you can visualize many vectorization functions as passing a long string through every element of a matrix, and then pulling that string until taut at both ends:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zUEgUTxBzlTeTwogChzlYw.png" /><figcaption>Row-major and column-major vectorization.</figcaption></figure><p>A z-order vectorization is defined as such:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/266/1*HdioXfS2J4ic_q9g6aalBg.png" /><figcaption>z-order of matrix. Note that subscripts 11, 12, 21, and 22 represent NW, SW, NE, SE quadrants, respectively.</figcaption></figure><p>The visual for z-order is quite beautiful:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/790/1*txAKz1OYhUlSufcsbbzATQ.png" /><figcaption>Vizualizing z-order vectorization.</figcaption></figure><p>From the recursive “subproblem” breakdown the algorithm takes up, it is clear that it’s friendly to quadrants. The most notable advantage of z-order is that the elements of a quadrant of <em>any size</em> are contiguous in its z-order form. This allows us to add and subtract them relatively easily, which is helpful when we start implementing these operations to emulate Strassen’s algorithm:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qrq1PSLqhLvvnoDoUG7Wfg.png" /><figcaption>Adding two quadrants in X is equivalent to adding the corresponding (contiguous) segments in z(X)</figcaption></figure><p>Thus, since Strassen’s algorithm relies heavily on quadrant-level operations, we choose to use the z-order function (denoted simply as “z(M)” for matrix M) to vectorize A and B, expanding our general formula in such a way:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/858/1*RHnn-W-tc7Z7D6aBq-JkxQ.png" /></figure><p>Where S*_A and S*_B, are special matrices representing the preparation of A and B, and S*_C representing the combination of results in the end (i.e. the “fix-up” section of the recursive algorithm).</p><h3>Detail 2: Recursion Tree</h3><p>You can draw a tree out of any recursive function. We will do that here with Strassen’s algorithm in order to motivate further our end formula. Specifically, we can visualize how A’s quadrants are manipulated recursively:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*luPPKOe027z2espo1blI3g.png" /><figcaption>Recursive tree representing how A is decomposed via recursion.</figcaption></figure><p>Now that we’ve selected how to best represent our matrices for quadrant-level operations (that is, with z-order vectorization), it’s time to start worrying about manipulating and interacting the quadrants themselves: Specifically, adding and subtracting them at all levels of recursion.</p><p>To that end, we design a series of operational matrices, T_i, each emulating a <em>specific layer</em> of the recursion tree i. Thus, our formula becomes:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lJuGKsNtuKBDKqkOJOq80g.png" /><figcaption>Tensor Strassen’s Algorithm (expand S* to a product of T_i matrices)</figcaption></figure><p>Each operational matrix is denoted as T_i. In the next section, we will design the contents of each T_i to emulate the operations performed at layer i of the recursive tree.</p><h3>Detail 3: Tensor Multiplication</h3><p>If the z-order function turns our input matrices, A and B, into vector form with convenient quadrant placements, then tensor multiplication helps us add and subtract these quadrants at all levels of recursion. This statement may seem quite abstract currently, but it will become concrete soon.</p><h4>Tensor Multiplication Primer</h4><p>The rule for tensor multiplication is the following:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/668/1*ncmtuJUM8S_5WnzpFkEeig.png" /><figcaption>Rule for tensor multiplication</figcaption></figure><p>Put simply, we multiply every element in X with the entire matrix Y. This operation is associative, which means that individual tensor multiplications in a string of tensor multiplications can be carried out in any order.</p><p>For the rest of the article we denote tensor multiplication between X and Y as “X (x) Y”.</p><p>Pertinent to our formula is the interaction between an arbitrary and an identity matrix. Specifically, (1) I (x) X and (2) X (x) I, for [1,-1,0] matrix X:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*G3_mag4uvpPD5u7UcPiO-w.png" /><figcaption>Tensor multiplication between a [1,-1,0] matrix and an identity matrix.</figcaption></figure><p>Visually, (1) and (2) uptake very specific forms: Whereas (1) repeats X down the diagonal, (2) expands every element of X to the size of I (we define “expands” here as turning an element of 1 or -1 into an entire identity submatrix). Both visual representations are helpful to intuit the final formula.</p><p>Notice that by manipulating the size of the I in (1), you can alter the number of repetitions. Additionally, changing the size of I in (2) lets you control the degree to which elements in X are expanded.</p><h4>Designing Tensor Operational Matrices</h4><p>To take these visual forms even further, we will be specifically leveraging the following form in the designing of T_i:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/230/1*Gt3qDeRM64Hg4B_b8lw-xw.png" /><figcaption>General form of T_i</figcaption></figure><p>Notice that we simultaneously leverage the capabilities of both (1) and (2) in this way, performing both <strong>expansion</strong> of elements (2) and <strong>repetitions</strong> of matrices (1). This form will be the basis of our T_i.</p><p>To finish, we will declare the general form of T_i. In plain English, it will be designed as such:</p><ul><li>S_a will be set to a 7*4 matrix with elements [0,1,-1], representing the seven quadrant operations performed at each recursive call.</li><li>I_r will be set according to the size of the quadrant, so that we can be adding and subtracting entire quadrants rather than single elements.</li><li>I_l will be set to the number of subproblems in the given layer of the recursive tree, so as to solve all of them rather than just one.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mIPB8HcD7lRFop2LP2yr8w.png" /><figcaption>S_a, S_b, and S_c representing the quadrant operations performed during Strassen’s recursive calls.</figcaption></figure><p>We finish by noting the current state of our formula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*x60tulCnM7VOZbYu9MeUpw.png" /><figcaption>Tensor Strassen’s Algorithm (expand T_i to tensor multiplication of identities and quadrant operation matrices)</figcaption></figure><p>All that’s left is to designate the sizes of I_r and I_l at each layer i, which we discuss in the upcoming section.</p><h3>Detailed Formula</h3><h4>Manipulating Tensor Sizes</h4><p>Remember the form for each T_i. We need to manipulate the two boundary identity matrices so that they can cover the right amount of subproblems and subproblem size. We’ve already done most of the intuitive legwork by associating the left identity with the number of subproblems, and the right identity with their size. Decoding the relationship between i (the layer) and these values is our last step, and is described here in the final form of the algorithm:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0xMyJOl6R-suTxmRk8ep_Q.png" /><figcaption>Tensor Strassen’s Algorithm (complete)</figcaption></figure><p>The left identity (subproblem count) increases by a factor of seven at each layer; The right identity (subproblem size) decreases by a factor of 4 at each layer.</p><h4>Extending T_i to S_B and S_C</h4><p>Extending our T_i to S*_B is pretty much completely parallel, except S*_B is encoded slightly differently based on the quadrant additions/subtractions done for the B matrix in Strassen’s algorithm.</p><p>Extending to S*_C is not completely parallel but is analogous. This is because S*_C’s job is to take the (z-order) resultant multiplication between A and B at the base layer of the recursion tree, and combine them, combining the results of seven recursive calls into four quadrants at each step.</p><p>As a result, its T_i is created slightly opposite of those for A and B: The number of subproblems (and thus size of the left identity) decrease, and the size of each subproblem (and thus size of right identity) increase, while the layer count i decreases (from base case to root case).</p><h3>Conclusion</h3><p>With a few observations and some diagrams, the initially scary algorithm in Kumar et al. is now much more approachable. What I took away most from this exercise in understanding this algorithm was the power of simple diagrams and plain English in capturing the essence of complicated ideas, which are usually initially presented to us in mathematical jargon.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c1eb5c9a972c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[My trick to understand dynamic programming problems]]></title>
            <link>https://medium.com/@alex.liu.roc/my-trick-to-understand-dynamic-programming-problems-2913cbf26a1e?source=rss-e3f5232fa34------2</link>
            <guid isPermaLink="false">https://medium.com/p/2913cbf26a1e</guid>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[diagramming]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[recursion-python]]></category>
            <dc:creator><![CDATA[Alex Liu Roc]]></dc:creator>
            <pubDate>Sun, 20 Aug 2023 04:43:48 GMT</pubDate>
            <atom:updated>2023-08-22T20:02:05.462Z</atom:updated>
            <content:encoded><![CDATA[<p>My relationship with DP began in Algorithms courses in undergrad. It continued as I TA’d the course. Now, as a fresh grad looking for jobs in the software space, it rears its ugly head again as the final boss of Leetcode concepts.</p><p>In short, dynamic programming is scary. But as scary as it is, I can’t escape it’s grip. It seems like the only way to advance in the software space is to power through this concept rather than dancing around it.</p><p>I’ve tried to tackle this concept many times. At first it was memorizing the common Data Structures used for DP. Then, it was ad-hoc solving Leetcode Problems. Now, with finally enough experience under my belt and a breath of fresh air and time to view these problems from above and identify patterns, I’m ready to share my approach!</p><h3>The Trick</h3><p>Split the problem into two dimensions:</p><ul><li>The “subproblem” dimension- This dimension indicates how the problem gets broken down into smaller problems. It’s how the problem gets broken down in recursion.</li><li>The “memory” dimension- This dimension describes all of the information you need from previous subproblems in order to generate the result for the current iteration/recursion.</li></ul><p>The purpose of one dimension is to keep track of subproblems. This means that, as long as the format in which you keep track of subproblems is in number format, you can use an array to store them (or, to be even more flexible, a dictionary that is integer-indexed).</p><p>The other dimension is to remember information about subproblems. This dimension is up to you to engineer! This is where you can get creative. You might need just a boolean for each subproblem (e.g. in “Word Break”). You might need a few well-named variables (e.g. in “Buy and Sell Stock III”). You might even need a list of pairs representing endpoints of a subsequence (e.g. in “Longest Palindromic Substring”).</p><h3>Examples</h3><p>Let’s look at some particular examples.</p><h4>Longest Palindromic Substring</h4><ul><li>Subproblem dimension: Palindromes of length n-2</li><li>Memory dimension: Start and stop indices of the palindromes</li></ul><p>Even by the wording of how we’ve written out our dimensions here, it is clear that every iteration (or recursive call) only depends on the memory from the previous iteration (or subproblem). In terms of recursion, this usually means that the solution to a problem of size n only depends on the results from a call to size n-2. I call these types of DP solutions “<strong>Layering</strong>”, because you can think of just maintaining a layer or slice at a time as it moves through an imaginary 2D cache in the subproblem dimension.</p><p>The diagram below shows the layer of palindromes of length i-2 as i evolves over time. You can see find the full solution video playlist <a href="https://www.youtube.com/playlist?list=PLCzCiGXExEplkme4vfoBavLRHtqQpIUqD">here</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*A64yMTa5jMtXt0MDwN8XiQ.png" /><figcaption>Evolution of the dynamic programming cache as i increases.</figcaption></figure><p>Similar problems that require a “layering” solution include “Jump Game IV”, “Unique Paths”, and “Best Time to Buy and Sell Stock III”.</p><h4>Word break</h4><ul><li>Subproblem dimension: Various substrings starting at index n+1 to end</li><li>Memory dimension: Whether the substring satisfies the Word Break problem</li></ul><p>Like Layering solutions, the solution to this problem also requires a 1D array. However, the purpose of this array is categorically different. Rather than maintaining memory of just one subproblem, the 1D array required to solve this DP maintains information of <em>all</em> subproblems. However, the information needed to be maintained for each subproblem can be represented by just one number.</p><p>I call this problem “<strong>Long-tailed</strong>”. You can think of a “tail” of subproblems from the one closest to the current iteration (n-1) to the farthest (0).</p><p>The diagram below shows the DP cache as it is in the middle of being filled in from right to left. You can see the full solution video <a href="https://www.youtube.com/playlist?list=PLCzCiGXExEpmMBnHzymyRYr1n1prNeeR-">here</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zRv1ABw2OSmZXbfyr15ZTA.png" /><figcaption>Dynamic programming cache (labeled “mem”) and an intuition of what each cell in the cache represents (below), along with the direction of execution and input string s (above).</figcaption></figure><p>Similar problems are “Longest Increasing Subsequence”, “Longest Arithmetic Subsequence of Given Difference”, and “Coin change”.</p><h3>Why it works for me</h3><p>The reason I see this breakdown as better than other approaches to teaching DP is that we can not only quickly generate an intuitive solution; We can also quickly iterate on our solution to save as much space as possible. This breakdown makes it clear what parts of the cache we must keep and which parts we can cut down.</p><p>Many solutions don’t make it clear why a 1-dimensional DP solution suffices as opposed to 2D. Sometimes a 1D solution suffices automatically; other times, it is only after creating the 2D solution that we realize the 1D solution suffices. With a subproblem/memory dimension understanding, it becomes clear not only how to set up an intuitive DP solution, but also how to improve on the space complexity if the problem allows.</p><p>Complicated DPs that use a two-dimensional matrix are also confusing to understand, because solutions often don’t describe the purpose of the dimensions during execution. This keeps learners siloed in their creativity about how to engineer the DP cache. Your memory dimension doesn’t need to be an array. It can be whatever you want!</p><p>Deconstructing the DP cache into the above dimensions has given me freedom to let my mind run wild in designing its form. It’s given me an edge when I’m analyzing DP problems and allowed me to solve many LeetCode hard questions too!</p><h3>More examples for practice!</h3><p>I’ve broken down 20+ more DP problems <a href="https://docs.google.com/spreadsheets/d/1v3ONoUFNkD7UQLpibVcdJB-umHxRBX35643a22yLeec/edit?usp=sharing">here</a>, check them out!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2913cbf26a1e" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>