<?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 Sharan Srinivasan on Medium]]></title>
        <description><![CDATA[Stories by Sharan Srinivasan on Medium]]></description>
        <link>https://medium.com/@sharanms?source=rss-3990aa7c5979------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*g3IuX35iqr3mj1gBXfSsyQ.jpeg</url>
            <title>Stories by Sharan Srinivasan on Medium</title>
            <link>https://medium.com/@sharanms?source=rss-3990aa7c5979------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 14:36:09 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@sharanms/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[Hardware Accelerated Inference on Edge Devices at Samsara]]></title>
            <link>https://medium.com/samsara-engineering/hardware-accelerated-inference-on-edge-devices-at-samsara-1bad5f406128?source=rss-3990aa7c5979------2</link>
            <guid isPermaLink="false">https://medium.com/p/1bad5f406128</guid>
            <category><![CDATA[data]]></category>
            <category><![CDATA[iot]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[platform]]></category>
            <dc:creator><![CDATA[Sharan Srinivasan]]></dc:creator>
            <pubDate>Thu, 03 Jun 2021 15:41:03 GMT</pubDate>
            <atom:updated>2021-06-03T17:07:07.295Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8zstPfRCD44T6wQbc4BfCA.jpeg" /></figure><p>By: <a href="https://medium.com/u/3990aa7c5979">Sharan Srinivasan</a>, <a href="https://medium.com/u/8c32033c0e37">Brian Tuan</a></p><p>On the Samsara machine learning and computer vision team, we build models and develop algorithms that help our customers improve the safety, efficiency, and sustainability of their operations. Depending on the particular product, the underlying models may reside in the cloud, be deployed to the edge, or even straddle both; in this post, we’ll discuss the models that run at the edge. Our <a href="https://www.samsara.com/products/models/cm32">CM31/CM32</a> series of dashcams, for example, run machine learning (ML) models in real-time — detecting potential hazards on the road and in the cab — to alert drivers and <a href="https://www.samsara.com/products/safety/dash-cam">prevent accidents before they happen</a>. These models are deployed in hundreds of thousands of vehicles today and help make the road a safer place for our customers and everyone else on the road.</p><p>From an engineering perspective, the safety-critical aspect of this product demands low latency ML inference on-device. Round-trip network latency and spotty cellular coverage eliminate the possibility of implementing these features in the cloud entirely. Thus, in addition to guaranteeing model accuracy, our team must also ensure that our models run within the stricter compute, memory, and latency bounds afforded by our edge hardware platforms.</p><p>In this blog post, we discuss the constraints posed by the environments our products are deployed in, analyze the tradeoffs that are considered when choosing models suitable for edge deployment, and deep-dive into some challenges that we’ve encountered in the process.</p><h3><strong>Hardware, Constraints, and Acceleration</strong></h3><p>Our journey begins with the hardware platform. Federal regulation <a href="http://www.ecfr.gov/cgi-bin/text-idx?SID=d17ab714955facfaca7da5e3818ed5fe&amp;mc=true&amp;node=se49.6.393_160&amp;rgn=div8">49 CFR 393.60</a> stipulates that certain areas of a vehicle’s windshield may not be obstructed, so we cannot just fit a beefy desktop GPU into our dashcam to run state-of-the-art models. Correspondingly, our hardware team opted for a more compact (but compute-constrained) smartphone-based platform.</p><p>With this platform, we want to squeeze out every last drop of ML compute we can. Our firmware and embedded systems engineers help us do so by delegating certain tasks to specialized modules on our SoC — hardware video encoders/decoders, the ISP (image signal processor), etc. This leaves plenty of headroom on the CPU, GPU, and DSP (digital signal processor) for our models to run.</p><p>In general, CPUs are the least suited for our work (they tend to be power-intensive and slow), GPUs offer a good tradeoff of flexibility and parallel-computation throughput (but are power-intensive), and DSPs are extremely power-efficient and fast (but limited in flexibility). Each of these processor families bears implications on what kinds of models we can run on the device and the tradeoffs we need to make in order to do so.</p><h3><strong>Model Selection and Tradeoffs</strong></h3><p>As ML engineers, we’d love for nothing but to simply take the latest state-of-the-art model from CVPR and drop it into our devices: deep learning literature is rife with benchmarks set using heavy model backbones like VGG19 and ResNet152. However, these architectures can be orders-of-magnitude off from our latency requirements. Instead, we must principally consider the accuracy-latency tradeoff when selecting a model architecture as a starting point.</p><p>We turn to mobile-friendly architectures that are built with hardware acceleration and limited compute in mind. Among these, we’ve experimented with a few variants, including SqueezeNet, CaffeNet, and MobileNet. The depthwise-separable convolution introduced by the MobileNet paper, for example, factors the convolution operation to be more parallelizable and memory-efficient. This, along with other architectural innovations help reduce the model size, memory footprint, and execution latency while minimizing the impact on model accuracy.</p><p>Critically, we also have to understand how these architectures interplay with the on-device execution environment. While we train our models in many different autograd frameworks (mostly Tensorflow and PyTorch), we often have to translate the trained model artifacts to a format that the platform-level neural network execution engines can leverage.</p><p>This translation process is oftentimes beset with further challenges. Notably, many network layers (i.e. graph operations) are not supported by every deployment environment. Other layers, while supported, may not have corresponding hardware-accelerated implementations and thus force a subgraph to run on the CPU (consuming additional memory bandwidth and creating a CPU bottleneck). Each deployment environment has its own set of these idiosyncrasies: <a href="https://www.tensorflow.org/lite/guide/ops_compatibility">tflite supported ops</a>, <a href="https://docs.nvidia.com/deeplearning/tensorrt/support-matrix/index.html">TensorRT supported ops</a>, and <a href="https://developer.qualcomm.com/docs/snpe/network_layers.html">SNPE supported ops</a> all differ slightly. Some of these layer incompatibilities must be addressed during the training process by modifying the model architecture, and others must be addressed at the translation stage. We outline one approach for doing so below.</p><h3><strong>Graph Surgery</strong></h3><p>Let’s say that we have a graph with an incompatible layer, and for some reason, we don’t want to — or can’t — modify the graph definition at train time. How can we still translate this model to be executed in our target deployment environment? Graph surgery based helps in this regard, by excising and stitching operations in a neural net computation graph to replace an incompatible operation with a set of supported ones (look ma, I’m a neurosurgeon!)</p><p>For this example, consider Keras’s <a href="https://keras.io/api/layers/pooling_layers/global_average_pooling2d/">GlobalAveragePooling2D</a> layer. This layer is commonly used in image classifiers to pool the feature map of a convolutional feature extractor before those features are fed into the dense layers of a classification head. However, in the Tensorflow backend, this Keras layer is implemented as a <em>tf.reduce_mean</em> op, which is not supported by some of the aforementioned execution engines and not hardware-accelerated by others.</p><p>We can leverage the <a href="https://chromium.googlesource.com/external/github.com/tensorflow/tensorflow/+/r0.10/tensorflow/g3doc/how_tos/tool_developers/index.md#GraphDef">proto</a> representation of the graph to excise the subgraph corresponding to the offending op and replace that subgraph with another single-input, single-output subgraph that has the same mathematical semantics but with different ops. Remember, in the end, a graph op is just a representation of a math operation! Let’s walk through these steps:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*cwr8y6bIo69pMKKY.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*lIotixhFtpaK0xSb.png" /><figcaption>(1a) original graph, incompatible op (2c) subgraph with replacement op</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*jHwEmMU4WfVLG0O8.png" /><figcaption>(3c) reconnected graph with replaced op</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*50Q7WMinvBXTTp7K.png" /></figure><ol><li>Identifying the subgraphs that need to be excised</li></ol><ul><li>a) In this case, we need to excise the <em>tf.reduce_mean</em> op and its associated metadata</li><li>b) Take note of the input and output names of this subgraph</li></ul><p>2. Coming up with an alternate implementation of that op with other ops</p><ul><li>a) This subgraph needs to take in the same input shape and output the same output shape as the <em>tf.reduce_mean</em> op, which means: input (1, 4, 4, 1280), output (1, 1280)</li><li>b) It looks like tflite supports average pooling (most frameworks should since it’s a very common CNN layer), so we can replace the reduce_mean with an average_pooling2d op having the same kernel size as the input (with no additional padding)</li><li>c) The shapes are not quite correct after the pool, so a call to reshape or flatten should make the output shape of this subgraph match the output shape of reduce_mean</li></ul><p>3. Replacing the unsupported op with the replacement connected subgraph</p><ul><li>a) Name the replacement subgraph nodes something sane, making sure there are no namespace collisions with the remaining graph, and insert it into the graph, connecting the input and output names to the remaining graph as necessary</li><li>b) Verify that the graph parses and is connected using a network visualization tool like <a href="https://github.com/lutzroeder/netron">Netron</a>.</li></ul><p>And there we have it! For most of the layer incompatibility issues we’ve encountered, we’ve been able to reimplement an unsupported op using the above trick. In some other cases, we’ve noticed that the graph conversion tools nominally support an op, but don’t necessarily the specific version of the op embedded in the graph. One example is the implementation of Tensorflow’s <em>tf.add</em> op was updated to <em>tf.addV2</em> , causing some graph conversion tools to fail on pattern-matching the op name against the tool’s “supported” op names (<a href="https://github.com/tensorflow/tensorflow/issues/42256">like this</a>). Yet, addition is still addition, so we can simply rename the op name in the graph proto to something that our converter can (AddV2 → Add).</p><p>Once we’ve completed the (sometimes arduous) task of exporting our trained model checkpoints to a platform-supported serialized graph representation and verified that the layers of the converted model are executed with hardware acceleration, we need to benchmark the model and compare the results with the latency requirements of the task. This part of the problem is well-explored by other literature: usually, the solution is some combination of removing or fusing operations, <a href="https://developer.nvidia.com/blog/transfer-learning-toolkit-pruning-intelligent-video-analytics/">graph pruning</a>, and <a href="https://www.tensorflow.org/model_optimization/guide/quantization/training">quantization</a>. We can remove all training nodes to slim down the graph size and fuse multiple operations (e.g. <a href="https://forums.fast.ai/t/faster-inference-batch-normalization-folding/69161">folding batch norm</a>) using a <a href="https://github.com/tensorflow/tensorflow/blob/master/tensorflow/tools/graph_transforms/README.md">graph transformation tool</a>. For quantization, we’ve found that certain model architectures or variants suffer less accuracy drift than others and that the insertion of quantization nodes at training time helps ensure that post-training quantization induces less additional error on our validation set.</p><p>At this point, we’ve picked a hardware platform for our product, trained a model that is sufficiently accurate for our product needs, converted our model, and slimmed it down to run within the latency envelope afforded by our embedded code. This is just the tip of the iceberg! In later posts, our team will share additional implications and challenges related to running models both at the edge and in our cloud backend.</p><p><em>Interested in working on projects like this? </em><a href="https://grnh.se/40ca09bf1"><em>Apply to our open positions!</em></a><em> We’re always looking for great people to join us as we learn and grow together, and if you love learning and building things in a highly collaborative environment, we’d love to hear from you! 👋</em></p><p><em>Special thanks to Edwin Zhang, Ali Akhtar, Asma Stephan, Etienne Dejoie and Kavya Joshi for helping us edit this post. Also a special shout-out to all the engineers in the ML and firmware team for enabling a lot of these features.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1bad5f406128" width="1" height="1" alt=""><hr><p><a href="https://medium.com/samsara-engineering/hardware-accelerated-inference-on-edge-devices-at-samsara-1bad5f406128">Hardware Accelerated Inference on Edge Devices at Samsara</a> was originally published in <a href="https://medium.com/samsara-engineering">Samsara R&amp;D</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Athen’s Marathon — being privy to a spirit bomb]]></title>
            <link>https://medium.com/@sharanms/marathoning-whats-in-a-race-7d8e7920ce36?source=rss-3990aa7c5979------2</link>
            <guid isPermaLink="false">https://medium.com/p/7d8e7920ce36</guid>
            <category><![CDATA[marathon]]></category>
            <category><![CDATA[athens]]></category>
            <dc:creator><![CDATA[Sharan Srinivasan]]></dc:creator>
            <pubDate>Thu, 15 Nov 2018 13:03:51 GMT</pubDate>
            <atom:updated>2018-11-24T20:00:11.335Z</atom:updated>
            <content:encoded><![CDATA[<h3>Athen’s Marathon — being privy to a spirit bomb</h3><p>“Run, run, keep running until you can run no more … then take another step”</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XDrR5_Rwp7KLrVRMEr8nNg.png" /></figure><p>It’s a warm summer evening, circa 500 BC. You’ve finished your shopping at the local market, (or agora) and you look up at the night sky… blood-red, filled with fatigue and the slightest glimmer of hope. Hope of defeating the Persians in what has already been a half-century long drawn Greco-Persian War.</p><p>As the well-worn legend goes, after the outnumbered Greeks miraculously managed to repel the Persians off the coastal plain of Marathon, an Athenian messenger — Pheidippides (our protagonist) was dispatched from the battlefields at Marathon to Athens to deliver the news of Greek victory. After running about 26 miles to the Acropolis, he burst into the chambers and gallantly hailed his countrymen with <em>“Nike! Nike! Nenikekiam”</em> (“Victory! Victory! Rejoice, we conquer!”) and then he promptly collapsed from exhaustion and died!!! My story treads along similar lines — except I did not run for glory, or war or peace, or for the glory. I <a href="https://www.imdb.com/title/tt1639426/">just ran.</a></p><p>I’m not a very good writer (my journalist mother would whole heartedly second that) and i’m not the first person to run a marathon by far and certainly wont be the last. But this is one experience is one that’s really moved me from within and I wanted to put it down on ink. Also a disclaimer that some of this might be a little more sentimental that what I’m used to.</p><h3>The cause</h3><p>A few months ago wildfires sprung up in Attica, Greece. I remember browsing through some twitter feed and noticed “The fire which is thought to have been the deadliest on record in Greece”.</p><p><a href="https://www.aljazeera.com/programmes/peopleandpower/2018/11/eye-fire-181108043136181.html">Greece: Eye of the Fire</a></p><p>Fires sprung up out of nowhere gobbling up forests and shelter, charring everything along the way. It was like an incendiary decided to spin up a twisted version of a fiery Tsunami. Videos surfaced of fleeting residents and tourists making a beeline for open ground as the flames simply running through houses…it was really sad.</p><p>The Athens Marathon this year decided to honor the victims of the fires and use the proceeds from the event to “spreads messages of strength and persistence”. <em>At this point I will fess up — I’m not some altruistic angel. I’ll be the first person to admit I did not decided to run because of this.</em></p><p>But even having it even at the back of your mind when running goes a long way towards building empathy and helping you take that extra step. I come from India — I love my country to bits. Tragedy and famine are far more common in that side of the world where. Things are definitely getting better, but I’ve learned that even the littlest of things can go a very very long way. <a href="http://www.youtube.com/watch?v=pMLa4IeFKHM&amp;t=1m40s">After all the very smallest things can cast a very large shadow.</a></p><h3>The Context</h3><p>This post is not really that long, so I’ll set some context.</p><p><strong>Health wise</strong> — I’m 26 years old, born and brought up in India — Madras. Physically while i’m not ultra fit, I can find way around the gym / dining table ;) .I enjoy playing — soccer, badminton, table tennis about once a week. Also living in the bay-area, with health conscious peers, eating avocado * food goes a long and unhappy way to keeping you somewhat in shape. Also, the longest I’ve every run in my life without stopping is like 4.5 km.</p><p><strong>Exercise: </strong><em>I hate running,</em> I really do. It’s mind numbingly monotonous and boring. Just hearing that “schwinn schwinn” of a treadmill belt makes me want to grab a TripleH sledge hammer. So why why from there → marathon?</p><p><strong>My concocted psychological reasoning: </strong><em>(Fee free to skip this part) </em>Behind all human decisions are implicit stimuli that serve as motivators, without any loss of generality I hope. These stimuli usually fall along one or more of the following dimensions.</p><ul><li>Inspiration</li><li>Love</li><li>Empathy</li><li>and Fear</li></ul><p>Looking back, any and all decisions I’ve taken run a thread through one or more of these nodes. For the marathon it was Inspiration and Fear!</p><p><strong>Fear:</strong> At 26 you don’t really expect to have a “mid-twenties crisis” or any crisis at all actually. there was this nagging feeling at the back my mind that I was doing things just on inertia. (I know it’s weird and seems a bit exaggerated, but bear with me). Days were routine ( home → work → friends → home), weeks were routine ( work → weekend chill and hang out → work) and the only thing I’d have to look forward to were my annual India trips to meet family. This started to trouble me. It’s the same weird sensation you have in your brain when you know that something is wrong. You don’t know what, you don’t know why — but you know it’s there. geez!</p><p><strong>Inspiration: (a) </strong>My roommate like me is in tech (surprise surprise). He ran the acclaimed SF marathon a couple of years ago and loved it. I’d watch him train every evening, running his 5,6,7 miles every day after work while I kicked back with a p̶u̶z̶z̶l̶e̶ cold beer. But it was awesome to see him battle it out there. <strong>(b)</strong>The other factor was a colleague of mine — let’s call him CHW. An extremely inconspicuous asian guy with thick half inch frames and a lanky hoodie that feels like a ghost gown. We hag out quite a bit, but mostly in a workplace setting. One fine day we’re walking back home and he tells me “Sharan, I’m going to Berlin to run the <a href="http://www.therunnerbeans.com/2016/12/run-world-marathon-majors-youre-not-elite.html">marathon major</a>”. All profiling aside, this guy did not look it. We had dinner that day and he told me about about his past marathon “conquests” as he calls it. I spent the following week (end of July) googling my brains on marathons.</p><p>Ok so, time to do something different. Let’s run this marathon! I was pumped, super motivated - but these bursts of motivation can been deceitfully ephemeral. ( I know!) The next SF marathon was a year away and… who am I kidding. My motivation wouldn’t last that long. So I needed to commit to it — that’s where Athens comes into the scene. I felt I was going to run once and I wanted it to be an “event” — a bookmark on my year’s timeline that I can look back at. Sign up!</p><p>Countdown : The Athens Marathon — 12 weeks away. (I later got reprimanded by a couple of my Greek co-workers for for calling it “The Athen’s Marathon”. They insisted I call it THE marathon” — symbolizing the originality of it i guess :D)</p><h3>Training</h3><p>My marathon training story is no different than anyone else, just compressed. The hardest part for me was the start 0–2 miles without stopping. It seems trivial now, but 4 months ago that for me was the real marathon. Anyway, thankfully it took me a couple of weeks to ramp up to that point and then it was all uphill here.</p><p>I started to run longer more consistently. I began slow as advised, stretched daily, breathed well, maintained discipline and took it one step at a time. Music was soo important to compensate the boredom of running. There were 2 parts of my 12 week training which were noteworthy.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/340/1*fVgbWzx5sYfjynzieB-p5Q.png" /></figure><p><em>The diet : </em>Low risk, (s)low reward. Diet as you can imagine is important to keep in check. Being veggie this was a little harder cos of all the protein you need to take it. I wasn’t pedantic about this but I did resolve myself to 0 sugar + ~ 0 fat and + 0 carbs. It’s all good — here’s some Greek yogurt!</p><p><em>The pace: </em>High risk, high reward. Pacing my distances was really important. The minute I realized I could go 3 miles without getting tired, I got all hasty and ramped up too fast. I went from 3mi → 5 mi → 7mi → 10 mi all in one week and … got injured. This set me back 2 weeks! Don’t try this at home!</p><h3><strong>The Marathon — Let’s do this!</strong></h3><p>11/11/18: The morning of …</p><p>Fine… admittedly no-one wants to listen to me talk about the 56,430 steps ordeal. This race was not about that — it was about the 5 stages of a first time runner’s grief. (ok I totally made that up, but I need to keep y’all reading)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/856/1*G69PSUMiUTXV-kV6lFQ90A.png" /></figure><h4><strong>Soaking it in!</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/360/1*3IuXfFeI31dkDcLqvztyCA.gif" /></figure><p>At first glance this doesn’t look like the fiery historic battleground that it’s made out to be. It’s more like a lush green field with cows as far as the eye can see. But! Fill it up with 18,000 people and this is how it looks like.</p><h4>Flag off!</h4><p>The scenes were amazing!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tsbenWEcIHNfKodmVXozdQ.png" /></figure><p><strong>Comfort: </strong>The first 15 kms went off smooth. Legs are working fine, the heel is holding up, mind feels light, the engine is cranking smooth. My tactic of thinking about Chandler’s legs is totally paying off. Wah! I can do this all day…</p><p><strong>The Mental pull: </strong>It turns all day = 5 more kms! :/. 19 km in and it’s all uphill. I’ve never felt my body burn so much before. The blaze from Apollo is not doing anything to help either. I get reminded of <a href="https://www.youtube.com/watch?v=5_l2TY-tCj4">kenshin Himura in the Shisho fight</a>. (The kind of things that pop into your head god!) Thankfully the left brain kicks in reminding me that it’s a 100 times harder to resume if I stop. ok I need something to distract me — so nice song. pull out my phone …Tap tap… Dhoommm! Crap!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*89kz-n5VRHG0zGcAotKXJQ.jpeg" /><figcaption>Spartans just popping outa nowhere! :D +10 for motivation.</figcaption></figure><p><strong>Spirit Bomb:</strong> 25 kms in and the streets are packed with Athenians. Women, children, the elders, and even the pets are flocking the streets to cheer us on. It was INCREDIBLE. I have never seen such a long stretch of bystanders cheering on as this before. That was when it really sunk into me that this marathon for them was more than a race — it was more of a symbolic event meant to recreate the victory. The passion and vigor with which they were cheering runner along was fantastic!! Showering the trail with flowers, olive branches, floral headbands and energy gels (quite anachronistically).</p><p><strong>Bargaining:</strong> 32 km in and half way up the incline on Nea Makri. Legs are burning. Thighs are throbbing. Knees are on the verge of explosion. Heels are being very adamant and my calves are refusing to flex any more — the longest 1km stretch I have ever traced. I think it was a question time as to what would break first — <a href="https://www.youtube.com/watch?v=EAPViUrsl9U">the mind or the body</a>. I was chatting with a friend I was running trying to laugh about what was going on in my brain, just to cover the pain.</p><p>I started to personify the aching muscles and began running a mental auction them to determine which one would give in first. The unit of bid was a “2 street poles length” — very victorian! Lampposts came and lampposts went the next one…. the next one… the next one.</p><p>34 kms in we Paused.</p><p><strong>The Athenian Grandma:</strong> They are mythical figures who have descended from Mt.Olympus emerging from nowhere just in time to pep you up. I squatted as a few others did too just stretching and about to wave the white flag. “Ok enough, 16 km uphill. I’m done”.</p><p>Grandma: (Reading my bib) “Ella re Saran. 10 more to go”. I couldnt really. None of my friends could either. Then she said something that I felt was sheer genius.</p><p>Grandma:“Ogay, Englisss? Listen You don’t finish marathon. You dont. You run”. I was like whaat!? “</p><p>Grandma:” You run and run till you cant run any more. Then take one more step”!</p><p>Waw! I stood there mind numbed, just processing that recursion. It was inspiring. #LessonForLifeHuh. It worked. I gobbled my chocolate bar and took off.</p><p><strong>Nirvana: </strong>I carried those words of wisdom with me as a trotted through a few more kms just walking and jogging and sometimes both. There was a stretch when Rob, actually ran with his eyes closed. haha. Finally The <a href="https://en.wikipedia.org/wiki/Panathenaic_Stadium">Panathenaic stadium</a>! The finish line.</p><p>I slowed down just to soak it all in. Energy just rushed back into me. Truly a feeling I will never forget. It was so inspiring to see.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XDrR5_Rwp7KLrVRMEr8nNg.png" /></figure><p>Men and women grinning from ear to ear, some shedding tears of joy and others just staring up at the sky. There was one moment when the stadium exploded when a father ran past the finish line with his child on a wheelchair ( Yeah! He ran 43 km with her). If you thought watching Usain Bolt blitz past that finish line was captivating — this was at a whole another level!</p><h3>Lessons learnt</h3><ol><li>Respect your challenges— they don’t come easy. No matter how talented you are the process deserves its respect.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/354/1*LarGZCnjvC-8If-tefXREA.png" /></figure><p>2. The Athenian Grandma : Run, Run and keep running till you can run no more. Then take another step</p><p>3. Spirit — It’s not about finishing the race (metaphorically). As wise Rob said, Nike!(victory) is only if you enjoy the ride.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7d8e7920ce36" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Learning Market Dynamics for Optimal Pricing]]></title>
            <link>https://medium.com/airbnb-engineering/learning-market-dynamics-for-optimal-pricing-97cffbcc53e3?source=rss-3990aa7c5979------2</link>
            <guid isPermaLink="false">https://medium.com/p/97cffbcc53e3</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <dc:creator><![CDATA[Sharan Srinivasan]]></dc:creator>
            <pubDate>Fri, 10 Aug 2018 15:01:01 GMT</pubDate>
            <atom:updated>2018-09-12T22:21:55.849Z</atom:updated>
            <content:encoded><![CDATA[<h4>Combining elements of machine learning with structural modeling</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9qPQ_U7hyqaAPEJBvkZOiw.png" /><figcaption>How do you think market dynamics influences this beautiful home in Cape Town?</figcaption></figure><p>Market dynamics plays a key role in matching guests with hosts in two-sided marketplaces such as Airbnb. Supply and demand vary drastically across different locations, different check in dates and different lead times until check-in. It is important for us to understand and forecast these spatial and temporal trends in order to find better matches for our community of hosts and guests.</p><p>In this post, we describe a framework used to model lead time dynamics in order to help hosts price their homes more competitively and improve their earnings potential. We embrace both machine learning (ML) and structural modeling to achieve improved predictive performance and model interpretability.</p><h3>A Primer on Lead Time Dynamics</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/850/1*oGd2Q_gx8UNHnKUpbyp7wg.png" /></figure><p>The lead time for a booking refers to the time between the date of booking and the trip check-in date. Taking a trip with a check-in date of New Year’s Eve (December 31) as an example, when a guest books 30 days in advance (on December 1), the booking lead time is 30 days. On the other hand, the booking lead time would be 0 for guests who make a last minute reservation on the day of check-in.</p><p>Guests will continue to make bookings for the New Year’s Eve as time progresses and the booking date gets closer and closer to the end of the year. This booking process reflects the inflow of demand and can be treated as a stochastic <strong><em>arrival process</em></strong>. The corresponding distribution of bookings over lead time is the booking <strong><em>lead time distribution</em></strong>.</p><h4>Why Model the Lead Time Distribution?</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_8FqWVJDL3kfL_GWjKe4OA.png" /><figcaption>Nightly prices for each check-in date on the calendar as set by Smart Pricing</figcaption></figure><p>Learning the booking lead time distribution helps power our pricing system. Airbnb launched Smart Pricing to help hosts set optimal prices and maximize earnings. These tools take into account factors like demand, supply and individual listing properties in order to make price suggestions for all check-in dates on the calendar. However, market conditions typically change as booking dates get closer to check-in dates, and, as a result, it is critical for us to account for these changes and help hosts keep their prices optimized for market conditions.</p><p>As an example, on a high demand night like New Year’s Eve, guests tend to book more in advance (i.e. at long lead times) than at other times of the year. This information helps set the right prices for New Year’s Eve. Similarly, locations play a big part in this too. A supply-constrained market gets bookings well ahead of check-ins compared to a holiday market like South Beach, Miami. By learning the arrival process for every check-in date and location, Smart Pricing accounts for this “early demand” and generates a pricing policy that allows hosts to optimally update their prices as we approach check-in.</p><h4>What Does the Arrival Process Look Like?</h4><p>To make the problem more concrete, let’s start by introducing some notation. Let <em>X_T(t) = P( Xijt=1 | Bij = 1)</em> represent the lead time distribution of guest bookings, where</p><ul><li><em>T </em>is a random variable representing lead time</li><li><em>i </em>be check-in date</li><li><em>j</em> be a listing of interest</li><li><em>Bij</em> be 1 if the check-in day ended up getting booked</li><li><em>Xijt</em> be 1 if the check-in day was booked at lead time</li></ul><p>The figure below is an example of the lead time distribution aggregated to a market level. As we can see, the booking mass density gradually increases as we approach check-in (right to left), since guests don’t always plan their trips well in advance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*laQ8afu4aUvB4Ogj" /></figure><p>Our goal is to learn and estimate <em>f </em>(the density of the distribution above), for each listing <em>i</em>, check-in date <em>j</em>, and every lead day <em>t </em>heading into check-in.</p><h3>Can We Use Machine Learning Directly?</h3><p>What would using a typical ML approach look like for this problem? Well, we would first build out training dataset with relevant features X and labels Y. In our case, the label would be the lead time for every guest booking. To predict this label, Airbnb has accumulated various predictor signals that capture market supply, market demand, as well as listing-level features. The model would then predict the average lead time for each check-in date. However, in the end, we concluded that an ML approach would have several complications:</p><ul><li><strong>Accounting for probabilistic outcomes</strong>: The arrival process is stochastic. For the purposes of optimal pricing, we need to know the distribution of bookings over lead time and not just the average lead time to book.</li><li><strong>Sparsity</strong>: Every listing gets booked at most once for a check-in date, leading to a highly sparse data set that would be challenging to handle without adding significant model complexity We will have to architect the model in a way that pools listing information together, enabling transfer learning across listings.</li><li><strong>High dimensionality</strong>: At Airbnb, we have millions of unique listings — each with its own defining characteristics and features that govern the arrival process. This makes every listing a very high dimensional data point and inefficient to use in a classic ML framework.</li><li><strong>Scale</strong>: The model will need to make predictions along three dimensions, ie. the triplet of (listings x check-in x number of lead times). This comes at a <em>O(10⁶ x 10² x 10³)</em> complexity, requiring very large training and scoring data sets and risks poor latency.</li></ul><p>In addition to these challenges, close examination of the lead time distribution revealed a distinct structure of unimodal distribution with clear cyclical patterns (likely weekday/weekend movements) — in fact, taking a closer look, we noticed that the distributions resembled a generalized exponential family. Considering these strong parametric characteristics along with the complexities of an ML-only approach we were inspired to try a hybrid approach combining ML and structural modeling.</p><h3>Machine Learning vs Structural Modeling, or Both?</h3><p>Modern ML models fare very well in terms of predictive performance, but seldom model the underlying data generation mechanism. In contrast, structural models provide interpretability by allowing us to explicitly specify the relationships between the variables (features and responses) to reflect the process that gives rise to the data, but often fall short on predictive performance. Combining the two schools of thought allows us to exploit the strengths of each approach to better model the data generating process as well as achieve good model performance.</p><p>When we have good intuition for a modeling task, we can use our insights to reinforce an ML model with structural context. Imagine we are looking to predict a response <em>Y</em> based on features <em>(X₀,…,Xn). O</em>rdinarily, we would train our favorite ML model to predict. However, suppose we also know that <em>Y is </em>distributed over an input feature <em>X₀ </em>with a distribution <em>F</em> parameterized by 𝜃 i.e. <em>Y~ F(X₀; 𝜃 ), </em>we could leverage this information and decompose the task to learning 𝜃 using features <em>(X₀,…,Xn)</em>, and then simply plug our estimate of 𝜃 back into f to arrive at <em>Y </em>in the final step.</p><p>By employing this hybrid approach, we can leverage both the algorithmic powerhouse that ML provides and the informed intuition of statistical modeling. This is the approach we took to model lead time dynamics.</p><h3>The Modeling Methodology</h3><h4>1. Laying the Foundation — Generating Demand Aggregations</h4><p>As a first step, we start by pooling our supply to form listing clusters. The clustering is learned using guest search patterns on Airbnb, with each cluster mapped to a common set of guest preferences. As a result, the listings within a cluster share common demand profiles and tend to witness similar lead time distributions. This process helps overcome problems of dimensionality and scale.</p><p>Unlike commoditized accommodations in the hotel industry, every listing on Airbnb is unique. Airbnb homes span over a broad spectrum, from price, location, quality, to size, etc. This vast heterogeneity brings challenges for personalization. It’s challenging to estimate the arrival process for every listing and every check-in date separately. Clustering listings into “demand aggregations” addresses this challenge. A demand aggregation refers to a cluster of listings that share common demand profiles.</p><p>When guests come to Airbnb, they browse through multiple listings in our catalogue and potentially choose one to book. By tracing a guest’s <em>path to purchase,</em> we learn more about their considerations and preferences. When two listings frequently co-appear in the purchase path of several guests, they tend to mirror a common set of guest preferences. For example, listings in west lake Tahoe often co-appear in search sessions of ski enthusiasts looking to stay at Airbnb (picture below).</p><p>We can employ the notion above to generate low dimensional listing embeddings, similar to <a href="https://medium.com/airbnb-engineering/listing-embeddings-for-similar-listing-recommendations-and-real-time-personalization-in-search-601172f7603e">this embedding technique</a>. This work produces listing embeddings which semantically relate to their demand profiles. With the listing embeddings at hand, we then clustered them together hierarchically to form demand aggregations. Each demand aggregation represents a <em>consideration set</em> that guests browsed over when making a booking. Such a framework is quite common in discrete choice models for demand estimation, specially online marketplaces. Here are some visuals of how these clusters might looks like.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*etJhzm9TEs2lSYYM" /><figcaption>Listing clusters map to identifiable guest preferences</figcaption></figure><p>This supply pooling step effectively reduces the cardinality on the listing dimension and helps address some of the problems enumerated above.</p><h4>2. Adding Reinforcements — Using Structural Modeling</h4><p>With clusters serving as a foundation, we can build a structurally reinforced ML model by having the lead time distribution adhere to a parameterized functional form. This helps us bypass having to make predictions for each lead time <em>t </em>and instead we predict the distribution by simply predicting the parameters of the functional form. This reduces the dimension of the prediction to just a couple of parameters.</p><p>If we make a simple assumption that the number of bookings in a unit interval of time is Poisson, then the time to event can be approximated by a gamma distribution. In other words, we can explicitly model the relationship between booking density and lead time by assuming the lead time distribution per cluster to be Gamma with unknown parameters <em>⍺, β.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/691/0*uZn1NwrHqIy8GNR1" /></figure><p>This actually agrees with the observation we made earlier about the lead time distribution resembling the exponential family. This approach also has a nice Bayesian interpretation since the Gamma is the conjugate prior for the parameter in a Poisson process. The lead time distribution that results, will have the following probability density and cumulative distribution function:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/514/0*VcN1T3vqRQOPRCj5" /></figure><p>With this structure in place, It becomes sufficient to predict the two parameters <em>⍺, β </em>and use them in the distribution’s functional form to generate the density at each lead time.</p><p>Similarly, we alter the functional form to account for cyclical patterns too. We treat the arrival time series as an waveform and decompose it to extract the inherent components. This typically involves,</p><ol><li>De-trending the time series to work on the residuals</li><li>Applying a Fourier Transform to get the resonant frequency (⍵)</li><li>Determining the amplitude (𝜌) and the phase angle (<em>φ)</em></li></ol><p>As as result, we obtain the stationary oscillating waveform <em>f_c(t) = 𝜌.sin(⍵.t + φ) </em>that models the cyclic component. This can be extended to as many harmonics as needed based on the use case. Finally, we combine <em>f_c(t) </em>with <em>f_b(t) </em>to get the final functional form to characterize the arrival process</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/406/0*QoN50cr5qoey_9M0" /></figure><p>This form has 5 parameters <em>(⍺, β, ⍵, 𝜌, φ)</em>. To predict the lead time distribution for every future check-in date, we only need to predict these 5 values.</p><h4>3. The Final Piece of the Puzzle — Forecasting the Parameters</h4><p>We start by building the training data with available predictors (<em>X</em>) and the empirical lead time distribution as the label (plot below). We then train our ML model to find the best parameter set <em>(⍺, β, ⍵, 𝜌, φ) </em>that maximizes likelihood given the training set. The resulting parameter estimates will best approximate the functional form <em>f_T(t) </em>to the observed empirical distribution. The plots below demonstrate this</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jZeNNlogXt8ZIwsjgzhfDQ.png" /><figcaption>Predicting the empirical lead time distribution using the ML + Structural modeling framework (a) Mass Density (b) Cumulative Density</figcaption></figure><p>Using this framework of modeling has several advantages. Notably we</p><ul><li><strong>Reduce problem complexity:</strong> In our case, we do so by reducing the dimensions of listing and lead time.</li><li><strong>Add interpretability:</strong> The various parameters of the structural model informs us about different components of the arrival process.</li><li><strong>Prevent overfitting:</strong> In this example, enforcing a parametric form to the model output provides additional information during model training which in turn serves as a natural regularizer.</li></ul><p>This model is currently used in product, primarily to power Smart Pricing. The tool uses the predicted lead time distributions for each check-in to help hosts keep prices up to date. We also use it to inform hosts about booking lead times statistics to help them make informed decisions around calendar availability. For instance, letting hosts in Tahoe know that we expect guests to be booking well in advance due to an upcoming ski season can help them unblock dates on their calendars early enough to capture the demand.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*GoGa2VD-fKjHymzq" /><figcaption><strong>Product use cases:</strong> <strong>(a) Guest side:</strong> Information about average lead times for LA, helps guests time their booking. <strong>(b) Host side:</strong> Knowing the percentage of completed bookings can help drive pricing decisions.</figcaption></figure><h3>Final Thoughts</h3><p>Using the structural + ML framework in this project helped halve the error and generalized better than the conventional ML algorithms that we tried. It also helped us understand and systematically model lead time dynamics. The framework is applicable to many other modeling scenarios as well, specifically when</p><ul><li>Imposing an explicit relationship between a predictor(s) and the response</li><li>Isolating effects of critical variables of interest, such as a treatment or a risk factor</li><li>Modeling the data generation mechanism for a stochastic process</li><li>Dealing with imperfect training data, e.g. dealing with censored or truncated data</li></ul><p>Today, machine learning has become a common tool of a data scientist’s toolkit. We often treat ML like a silver bullet - using off-the-shelf methods to build out data products. There are also a number of open source tools and that help automate various aspects of model development like feature generation, model selection, deployment etc. making model building much easier.</p><p>In such a world where the procedural details of model development have been abstracted away, sound problem formulation gains prominence. In particular, we can use domain knowledge to equip these ML models with the right structure and formulation using structural techniques. Utilizing human product intuition to architect, guide, and augment ML models in such a manner can truly push the boundaries of model performance and interpretability.</p><p>Want to learning more about market dynamics and build such frameworks? We’re always looking for <a href="https://www.airbnb.com/careers/departments/data-science-analytics">talented people to join our Data Science team</a>!</p><p>Special thanks to all my team members who contributed to this project and helped review this post. Milan Shen, Rubel Lobel, Minyong Lee, Chen-Hung Wu, Bar Ifrach, Robert Chang, Navin Sivanandam, Jeff Feng, Luca Beltrami, Paul Litvak and Clara Lam.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=97cffbcc53e3" width="1" height="1" alt=""><hr><p><a href="https://medium.com/airbnb-engineering/learning-market-dynamics-for-optimal-pricing-97cffbcc53e3">Learning Market Dynamics for Optimal Pricing</a> was originally published in <a href="https://medium.com/airbnb-engineering">The Airbnb Tech Blog</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>