SBTB 2023: Louis Brandy, Challenges at the intersection of ML.

SBTB 2023: Louis Brandy, Challenges at the intersection of ML.

Recording: SBTB 2023: Louis Brandy, Challenges at the intersection of ML.

um you can go read about some of the work we did in spam fighting if anyone's interested I'm not here really to talk about spam fighting necessarily it's it it it it's emblematic of the things I want to talk about and nothing here will be specific to spam fighting but we'll just use it because it's fun and it motivates a bunch of these examples um one of my rules here is you got to get in trouble like in the first three minutes so let's try quickly uh I spent a lot of time in infra and I watched a lot of teams working on different things um data sort of infra people and teams and ml infra and teams uh have done a bad job communicating with one another I'll just say it I've seen a lot of data infro that's really good at being data tools really bad for serving ml for various reasons we could talk about it to some degree I've also seen ml teams really underappreciate how much infro they need to run an ml app in production and pretty much the worst mistake you can make is to sort of not realize you're building a database as an ml team like oh whoops I'm accidentally building a database I thought it was a feature store turns out it's an entire database I need to build for example this conversation is actually really happening emerging as we speak um I don't want to make it sound like it's just happening last few years at least so you you see it in at least three predominant places feature stores have started to become a grownup piece of infrastructure kind of in the open source World Vector databases a very hot topic which we will spend a decent amount of time on here in a bit and these kind of orchestration layers right so things that treat for example the life cycle of a feature as a first class citizen um all of these are places where the data tools and the data world and the ml tools in the ml world are actually collaborating in a good healthy way so okay ostensibly this talk is about the intersection of domains let's just talk about these domains so we're all on the same page super briefly first is this real-time data world of search and analytics uh this is where rocket lives this is our bubble I will take just a second to explain to you what I mean by real time real time is one of these words that people use buzzword that may or may not have a meaning depending on what room we're in effectively it means usually both of these things are necessary for your app you care about the query latency for your data and you care about the data latency of your data queries I think most people understand I want fast queries right uh but data latency may be a little bit I was warned there might be flickering so I can only do so much though um data latency might be the one that's a little more subtle uh basically the idea is as soon as a piece of data is created how long until it's ingested and queriable right that is that is the fundamental of data latency and it often determines how real time an application is right if you need if you need last seconds data versus last minutes data versus last maybe milliseconds data these are all different generations of real ESS um I will give you guys some super important Trade Secrets if you don't happen to work in the database World um if you need query latency in a database it means you need indexes on your data top secret don't tell anyone don't record this and put it on the internet um data latency is a little trickier right so data Laten is really about having these indexes be updatable in a streaming and sort of incremental fashion right you can't rebuild your database from scratch excuse me your index from scratch constantly if you want it to be real time and if you know anything about vectors this this will come back soon um there is this other giant bubble uh the AI and ml infro World um a AI people want to train models they want to serve models they want to do all the other things asso associated with the with managing the life cycle of these models um not all of that is real time so for example training in the ml world is typically not a realtime operation and typically more of a batch style operation but a lot of the serving stack within Ai and ml apps is a real-time application so this are these are the two domains I want to collide this is what I want to talk about today I'm going to use Spam fighting as my motivating set of examples like I said before for fun nothing here is specifically spam fighting talking this could be anything realistically we could talk about product recommendations on Amazon we could talk about um you know twitch streams that you want to go watch instead of this talk anyway okay so yes what we're going to do is observations from the middle and I had this original agenda like if you actually read the abstract this is roughly kind of what it what it said um I made a realization while I was working on these slides this is too much this is too much content this would take two hours no one would sit here for two hours um and so I actually wanted to focus on one thing thing which is super topical is very much in this intersection and uh is emblematic of effectively everything so I'm actually going to talk today specifically about one set of really important topical challenges which is about Vector search in this intersection specifically real-time Vector search when there's a real-time component to your to your vector search applications so again it it it's emblematic right so it touches on most of the things I was going to talk about anyway so we're going to talk about vectors for the most of today's talk um but first let's talk about spam fighting infra just to give you a sense of like you just to make sure we're on the same page about what spam fighting infra is why it's a machine learning app and so forth um spam fighting is a pathologically realtime problem it is an adversarial situation right users are uploading things all the time um and so I need data as fresh as possible all the time so if I if I want to answer the question you know how many comments have you made in the last minute it it shouldn't take me like three minutes to know that you sent a thousand messages in the last minute that's catastrophic from a Spam fighting situation right I guarantee you will get spam in exactly those bursts if you can't detect it quick enough so data latency is Paramount in spam fighting so that's the first checkbox in the in the in the realtime thing query latency is also really important in spam fighting some people naively might think that you can sort of asynchronously clean up spam in other words let let the user post their comments I I'll classify and clean it up later this turns out to not work very well it's actually quite bad and it's for two reasons one is that the first reason is that uh spam does most of its damage soon so you actually don't want it there at all even if you're going to clean it up eventually second I don't want to write amplify spammers I don't want to give them two wrs to my database right once to write once to clean up that's the wrong cohort of users to write amplify is are spammers so fundamentally you want your spam protection synchronous you don't get to write to the database until I think it's not spam that means that my latency of my queries my classifications is part of the product experience it's in the critical path of my product my site will not feel Snappy if it takes me 10 seconds to decide if it's spam or not so I've just given you the two pillars of real time um that is you know spam fighting infra is deeply real-time problem certainly not the only one um there is one other really interesting thing in spam fighting uh that approxim is okay in spam fighting if you if you're going to give me a 99% correct accurate answer but 10 times faster I will take it every single time in spam fighting this is true of almost all kind of ml recommendation style systems um and if you know anything about vectors this will come back with vengeance approximation is crucial in in the vector world as well and so this little bit of foreshadowing here so all right let's talk about vectors and spam fighting so vectors were very powerful in spam fighting and they have been for a really long time they we were doing vector before they were cool they're cool now but even before they were cool they were they very they were popular in the in the spam world there's this classic question is this photo that you're uploading me spam this is a very hard question historically to answer um traditionally uh people would try to solve this with like a point classification I'm giving you an image I know who uploaded that image I know some metadata about the upload I know the pixels in the image can you look at that and tell me if it's spam or not can you train a classifier to tell me if that image is Spam or not historically speaking the answer is absolutely no that classifier cannot be built it will not work um it's possible that that's changing literally as we speak I've heard rumors that some of this AI Revolution might actually have made progress on this question I am skeptical but I would be happy to be wrong I would love to be wrong if we if we've made non-trivial progress here so vectors enter the equation I'm going to I don't actually know how much background to assume for people about how much you know about this whole Vector thing that's going on I'm going to do really quick 101 just in case uh the basic idea is you take really unstructured data in our our example it's an image you're going to embed it into a vector space via machine learning AI right so the you train this big old AI it it it it projects this into a vector space and the idea being that distance in this Vector space preserves some semantic you care about okay so your ml model is trained to preserve this semantic so distance measurements is a sort of a precise notion of of of some notion of likeness okay and in our case photos being aike that's a basic idea so going back now our our image problem becomes very different when I use this when I introduce this Vector concept what I tend to do is find and Link photos based on their similarity which is to say their nearness in this Vector space and as soon as I have that little bit of fan out things change radically and this actually Powers a significant fraction or at least one time powered a significant fraction of like image-based spam fighting for example how many photos look like this photo if the answer is very few it's almost certainly not spam if this is the first time I've seen a photo it's almost certainly not spam maybe even more powerfully is to start to Fan out Beyond just the photos so of all the users who uploaded photos that look like this how organic is that set if if a thousand people uploaded a photo and they all thousand of them were registered during the same one hour period in September that's not probably kosher right and once you have this idea you start to think in terms of clusters of data not in terms of any particular Point uh of data right so what does this cluster look good or not right that's the that's that's the transformation that gets made as soon as you have vectors in this notion of nearness in an image space and so we we could talk about this all at Great length um but it's basically this idea of clustering on once I have clusters of photos I can start building classifiers on clusters of photos I can also just have humans annotating that actually becomes a scalable thing to say this entire cluster of photos is no good don't allow them on the site for example and the important thing is the real time component of this has now been reduced to exactly Two Steps step one is to is to embed this in a vector space so create a vector from your image step two is figure out what cluster if any does it belong to and what have I labeled that cluster right is it good or bad so my online realtime component is exactly Vector generation Vector search right so I can power a lot of spam fighting with Vector search right so hopefully that motivates uh where where we've headed which is to say Vector search in real time can power a wide range of ml apps and again not to belabor the point this isn't just Spam fighting um I want to make a comment here really quickly since there's been a lot of talks about llms and and all these other things um Vector search is a feature of vector databases it would be a grave error to confuse these two things so a vector database is a database and databases are a non-trivial category of pieces of software obviously Vector databases store vectors and they can do Vector search but they do a lot more than Vector search and I will make a controversial claim I've actually been making variations of this claim with different people and I don't think it's actually as controversial as I thought originally but a good Vector database is more Vector excuse me is more database than Vector it's going to have Vector stuff in it there's going to be Vector Technology there but the database part is non-trivial like everybody remembers like that senior level class maybe grad level class you had there was literally a database textbook that was like this thick um that database textbook hasn't gone anywhere if you want to build a vector database you still have that entire textbook and all the problems it's it's laid out to deal with um and so it's not to say that Vector search is an easy problem in fact we're going to describe why it's hard that's literally all the rest of the slides but it it joins a whole host of well-known hard database problems and so my one takeaway if anything is to be wary of the enterprising engineer that wants to download a vector search library and productionize it um that is the very first step on inventing your own database accidentally you can do that if you want you can build your own database if you want just do it consciously don't do it accidentally that's my only that's my only plea um let's talk about indexing Vector data so in a traditional database sense you need indexes uh vectors are a really hard thing to index um as a general rule you can't index vectors uh to be more precise low dimensional vectors are indexable in a traditional sense this has been done for a long time lots of databases have them so for example things like geospatial or uh uh latitude longitude are low dimensional vectors you can use these kinds of space partitioning algorithms that's what's over here on the right by the way space partitioning type of algorithm to build an index that lets you quickly look up nearest neighbors uh in a traditional sense in high dimensionality data there's a thing called The Curse of dimensionality which essentially means you can't do better than linear scan you basically have to look at every point if you take a 1500 dimensional Vector you throw it in a KD tree to try to try to search it quickly it will still scan all 1500 excuse me all it will scan all the vectors in the in the database this is what the idea of the uh of high of excuse me the cursive dimensionality is and just to underline the point this whole Vector AI thing that's going on out in the world right now is all in high Dimensions right so open ai's text model is 1500 Dimensions it is very much in the high-dimensional category which basically means these indexes excuse me these vectors are not indexable that's what it means at least in a traditional sense so this enters into these approx Pro imate indexes so hopefully some of you have some some background here but if not we we we have to give up the idea of having exact nearest neighbors we have to give up the idea of an exact index in the traditional database sense and we have to kind of bring approximate indexes into the equation approximate indexes are not a thing in a traditional database typically like that's not all that's not really a thing we've done very often um but it is it's it's a necessary it's necessary for Vector search uh this is a Super Active area of research um you've probably heard some of these things you know hnsw is is a popular thing nowadays I'm not going to cover this stuff right here this is literally like conf conferences are happening papers are being written phds are being given on this topic of how to more efficiently find vectors in a vector space in an approximate fashion but I will say that Ann is not a silver bullet so even if I grant you you've built the world's greatest Vector lookup algorithm it's super efficient with minimal accuracy tradeoffs it preserves a sort of logarithmic style lookup instead of a linear scan you've only solved the first hard problem even if I grant it to you it's and it's a hard problem in and of itself you've only solved the first hard problem and there are a whole lot of really hard problems on its tail that you probably didn't think about when you were thinking about building a vector application and this is what I actually want to talk about so even if I grant you the first really hard problem the one that gives phds uh I still you still have lots of Hard problems in your future and that's the rest that's the rest of the today's talk so the hard problems in Vector search not including the first one which is actually building a good Vector search algorithm I want to stress something here these are hard hard problems I don't I don't exactly know what hard hard means but in this case um these are not solved to be clear we haven't solved them we're working on solving them um but do not trust anyone who's told you anything I'm about to tell you is a solved problem um many more papers will be written many more phds will be given on everything involving all of the next slides so if you're you know if you want a PhD I have some ideas so hard number problem number one in Vector search is incremental indexing so great you've built the world's greatest graph-based hierarchical navigable small worlds data structure it has all the vectors in it everything is awesome you can find vectors instantly the problem is can c can I add new vectors to this thing how do I add new vectors to this thing um this is fundamental to the data latency question right if if if if your use case requires that new things be added and findable in your search data latency is the thing you care about you have ran into a very hard problem in Vector databases um an enterprising engineer might say hey I I can imagine naively inserting um you know things into this data structure and that that that'll work probably maybe um as a general rule this doesn't work well and the mental model for most of these algorithms is like a balanced binary search tree right you do a lot of work to make your search tree balanced and then if you start inserting random things into it it becomes unbalanced and as a general rule these kinds ofn algorithms deteriorate even faster then a balanced binary search tree would deteriorate in terms of speed and accuracy tradeoffs so as a general rule naive insertion doesn't work very well these are they're hostile to some degree to to incrementally updating these these Vector search things now again lots of people have ideas lots of things are happening in this space lots of people are trying to solve this problem uh some of the options include one you can just Embrace this suboptimal incremental indexing you say look I'm going to insert randomly I'm Excuse me naively into this thing I know my my index is going to get worse I'm just going to rebuild it periodically perod ially rebuild my index from scratch swap it in that's how I'll build the system and productionize it a database person gets instantly very very uncomfortable with this idea because this idea of like rebuilding my index from scratch periodically immediately is horrifying like where are you going to do that are you going to do that on my database like while I'm serving queries you're going to kick off like a three-hour CPU bound job of reorganizing all the vectors that seems horrible um maybe you'll put it somewhere else and now I have consistency questions like what's the consistency model of of of of this how is that how is that going to work how are you going to Shard this thing like I don't I don't understand how you're going to do any of this of this work but you can you can go down this road it's just not an easy one you can Embrace a more batch index style so the idea is you acrw new vectors as they come in and when there's enough of them you build an index of just those and you sort of keep a history so to speak going backwards of of snapshots of of things you could occasionally even compact them so again if you know anything about databases and how databases have been built over time this is an extremely common strategy called a log structured merge um it's actually the basis of software like rock TB and other things this is one of the probably ways most people will be will be doing it in some form um it also has its problems though because it's not the most real time setup in the world there there there there's problems with kind of more recent vectors being fundamentally inefficient to Surge there is a third option of course is you can just improve these algorithms right like if if you come up with a better algorithm that is that does really great Vector search but also is elegantly incrementally updatable like congratulations like you can have your PhD and write your papers and publish it and I will happily implement it um lots of people are working on this of course I I think we'll make incremental progress on this but I don't know that I don't know that we'll have like a revolution here I think this is going to be a hard problem that we're going to have to solve one way or the other um yeah going forward so yeah hard problem number two this is called U metadata filtering this is one of these problems that depending on what world you live in has different names so if you're in the AI or ml world this is often called metadata filtering sometimes it's called hybrid search but hybrid is a bit of an overloaded term here as well if you're in the data world this is like the wear Clause of your query like literally it's the wear Clause um here's my example using spam fighting motivation like show me all the images like this one which is a vector lookup that's a vector search that were uploaded in the last 10 minutes that is a metadata filter and in this case it would be like a SQL query right like you know where the upload time was less than 10 minutes etc etc um this is a super hard problem in in Vector search and I would go one step farther uh maybe make a slightly controversial claim again it's also not optional um I would argue that just about any good Vector use case any good app will be made better by having some fraction of metadata filtering like some boundaries under which you're removing this the set of data you're looking at to make the user experience better um it might not be obvious why this is hard if you haven't spent time thinking about this um so I'll do is I'll try to do that that problem Justice here I mean the basic idea is this index is this like typically this graph-based hierarchical thing that's pre-computed on all the data so if your filter slices that data weirdly there's you don't have an index of the filter data you only have a filter of the the index of the unfiltered data so the the index and the filter might really compete with each other at at how to best sort of find data in this space again our enterprising Engineers have many solutions to this problem the most obvious solution is what was typically called post filtering which is to just over fetch essentially like hey Vector index give me the Thousand close vectors I'll filter after the fact and hope I end up with the the the amount I wanted to start with like let's say I want 100 I'll fetch a th I'll apply my filter and with any luck I'll end up with 100 this works obviously pretty well if it's not too selective but if it is it won't work very well prefiltering is this idea of filter first and then just scan your results so this actually is this essentially throws out the index the index doesn't do any good here so so if you you just apply your filter see how many vectors meet your filter and then just scan them all that works that totally work but your index has not participated in this process and then the final option is you can somehow build Ann search algorithm that includes some form of metadata filtering in the uh in the in the process of doing it this is again another area where papers can get written and it's a pretty active area of research so again if you want to write more papers down here help me um and and this leads finally to hard problem number three which is hidden in hard problem number two um if you understood this idea of pre-filtering and postfiltering sometimes pre-filtering is a good idea and sometimes postfiltering is a good idea and the choice of when those are good has to do with the selectivity of your filter okay so what does that mean so in the database world this is a very common and long-standing problem if I say give me the five nearest neighbors we x x is a filter the correct way to evaluate this often depends on how selective X is as a filter so if X is not that selective meaning let's say it only wipes out half the candidates then post filtering Works super great so post filtering remember is this idea of over fetch if I want to find five nearest neighbors that that meet this filter I'll fetch 20 I'll apply my filter which on average wipes out half and almost always I'll get the five that I want at the end no problem on the other hand if x is extremely selective this doesn't work at all I the pre-filter technique actually works much better so pre-filter is like hey I have this really stringent metadata filter where you know it's the color is red and it's over $200 and it was built on a Tuesday it turns out there's only five rows in my database that meet this criteria in which case I can just pull all five rows and you know rank those by distance I don't need an index to do that lookup so the idea of how best to execute the same query is a function of how how selective the filter is this is one of those problems that if if you've taken all the database classes you you you there's just like a whole thing you learn about and there's like mountains of Technology built into all your favorite databases to to to track predicate selectivities and use that and what's called a cost base Optimizer um if you don't know that and you wander into this space by trying to bolt on like metadata filter uh onto like a vector database this is one of these pie giant pieces of technology that you end up accidentally Reinventing and you'll spend a decade probably realizing it so anyway going back to the database perspective uh cost Bas Optimizer is the thing we have we've had for a long time it's not actually that hard to plug a vector search into it to to optimize it based on this selectivity to kind of do this pre-filter versus post filter thing automatically in your database but of course the the hard part here was having the cost base Optimizer in the first place that's actually the hard part here all right so I've given you three hard problems in Vector search when Vector search needs to be done online and in real time so they were just to recap incremental indexing so adding new vectors to this thing oh by the way we didn't talk about mutating or erasing vectors that that's even harder so just just adding vectors is itself a hard enough problem uh metadata filtering which I consider to be non optional and super important and then optimizing these metadata queries becomes really important this whole idea of selectivity optimization optimizations becomes really hard um so anyway that's my talk for today [Music] um I have a couple things that I kind of could wax philosophically about maybe if you find me outside I will I I think at the heart of it it's like watching these two groups of people slowly work together I just don't want you to build your own database by accident you you can build it on purpose by all means build your own database do it on purpose um but on the flip side if you're a if you're a data person don't underestimate how hard your data tools are to use for ML use cases um if you go talk to ml people about how they want their data tools to work um there's a lot of gaps so for example the idea of an approximate index in a database is like crazy idea for data people like what what are you talking about turns out it's super valuable uh for an ml style workload like in this case and there are really really hard problems like I granted you an entire database I granted you the vector search problem and I still can come up with three or four ways that this becomes a nightmare for your application so there are a lot of hard problems in this space so it's a fairly exciting space a lot of problems to be solved and that is my talk so thank you