Fighting fraud: finding duplicates at scale

Speaker 1 [00:03]

Thank you for introducing me. So today I'm going to talk about fighting frauds, fighting fraud, finding duplicates at scale. First, a few words about me. Originally, I come from software engineering, like my original background in software engineering. I worked for a couple of years as a Java developer. Then I decided to switch into data science. I did a master's in business intelligence. last year was in Berlin and I decided to stay in Berlin and since 2015 I've been working as a data scientist full time first time I got into this problem of duplicates was a Kaggle competition a few years ago organized by Ivito Ivito is the largest classified website in Russia so they had this problem of duplicates and then they asked the community to help them to detect duplicates using machine learning. I did pretty well in that competition. Since then many people found me, many companies found me on the leaderboard, contacted me asking for help. I did help a couple of companies. So I want to summarize all this experience and present it here. And also the talk today will be not about how to do well in a Kaggle competition like this, but rather what are the next steps. Okay, now you did well in Kaggle. What is next? How to use this? so that's me one year ago so this logo there is oilix group and toilix group probably many people here who are from germany didn't hear about this this is actually quite large company like this is a parent bread for many classifieds websites so ivita is one of them i already mentioned they hosted that competition on cargo so this is the largest classifieds in russia then oilix itself is a classified website in a bunch of countries like in many countries like poland ukraine india kazakhstan quite a lot of countries and letgo is also third big brand under alex group this is a large classified mobile in the states so today i'm not going to talk about specifics of the system that we have at Elix but rather about the general approach I want to start the presentation by talking about user generated content so user generated content is content generated by users so there is a website can be a blog post, can be a social network, can be a classified website where users can post content so user can come to this website and create a post about a dog and then write something this dog is so nice then they can get carried away like they love this dog so much or if it's a classified website maybe they want to sell this dog so they can create multiple listings and basically spam the platform or they can post something not appropriate on the platform or maybe something illegal in case of classifieds They might try to sell something that they are not supposed to. So there is a bunch of problems with user-generated content. Especially fraud and duplicates. So these two things, fraud and duplicates, they often come hand by hand. They are not always related, but often they are. And typically it happens like this. So somebody goes to the platform, for example, classifieds and wants to sell something, a dog. And then a fraudster comes. The fraudster copies the picture and waits till the ad disappears. And then they post another listing with the same image, maybe with a better description and better price. And then somebody comes to the platform. Okay, nice dog. I want to buy it. They call the seller. and the seller says yeah you know there are like 10 people in front of you in the queue they all want to get this dog but if you give me 100 i'll reserve it for you and he gets the money and disappears and the buyer is very unhappy and frustrated so how can we help them how can we prevent it. Instead of just letting users publish everything they want, we should first look at what is there and decide whether it should be allowed or not. For that, there are content moderation systems. They might look like this. So user posts something and then there is automatic moderation system that looks at this and uses machine learning to decide is it suspicious or not. And then they can reject it right away saying, okay, this is not allowed. They can accept it and it's fine or in many cases when situation is not clear we can ask people sorry to to ask so moderators are actual people who have some kind of interface to look at these items from the queue and decide to make the final decision whether it should go live on the platform or not this automatic moderation system may contain multiple components like a system for detecting explicit content, a system for detecting forbidden items, and a system for detecting duplicates. So this is what I'm going to cover today. I already gave a talk about duplicates. So that talk here, you can follow it. There is a link. It's more about methodology, like how to do well on a Kaggle competition. So this talk, as I mentioned, is slightly different. It's about the system, but still there is a lot of useful information there so you can have a look in summary how to approach this problem so it's a two-step problem so you can approach it with two steps first step is you select candidates something that is not necessarily duplicates but could be duplicates and ways to do this is okay you have an ad what are the other ads published in the same category or what are are the ads published in the same city? What are the other ads published by the same seller? What are the other ads published from the same IP, from the same device? So this is not necessarily duplicates, but there is very high chance that they can be duplicates. And then on the second step from all these candidates, we actually use machine learning to find what are the real duplicates there. And what we do is we get all these candidates from the previous step, and then we ask people to look at them and say okay is it duplicate or not so people say duplicate or not and we get this training data which consists of a pair id1 id2 and label1 if it's duplicate label0 if it's not a duplicate and then we can compute all kind of features from this then throw it into a machine learning model and then this model will tell us will actually help us find duplicates. Features can be pretty simple like okay what is the absolute price difference, what is the relative price difference, is it published from the same IP, what is the distance between these two listings, same location, same category. We can also look at similarity between two titles. Okay are these two titles similar, are these two titles different. Basically these are all features that we will use in the model. It's quite important when we have images, like in classifieds case, to look at them as well because an image is worth a thousand words and especially in classifieds buyers want to look at the item before deciding do I want it or not. With images hashes are a very useful thing because they summarize the entire image into a simple byte string that we can use for comparison. There are multiple types of hashes. First category of hashes is cryptographic hashes. So these are general purpose hashes like MD5 that are needed to detect if file was modified or not. For example, in case of MD5, if we take a file and change just one bit of this file, it will result in a completely different MD5 hash. These hashes are useful in duplicates, but only to detect byte-byte-byte exact matches of the same images. There are other kinds of hashes. They are called perceptive hashes. So these hashes, when you change only... If you open the image and change only one pixel with Microsoft Paint or whatever, Paint, and save it, it should result in the same hash. So in this example, we changed the image slightly. that resulted in a completely different MD5 hash that we have on the bottom but dhash, which is a perceptive hash, stayed the same and there are many hashes like this, so the way it worked they work, I will not go into the code, I'll just explain how they work this is dhash so we have an image, we then break it in multiple cells and then for each cell we calculate the average pixel value there and we see that for the area where the image was modified the value is different the rest stays the same and then what we do next is we compute the difference between second column and first third column and second and so on so we have this bunch of differences and then finally we just consider uh if it's greater or zero or not so we have a bunch of boolean variables binary and then we can think okay we have this boolean array let's treat this as bits and compress it into one digit like each rows each row of one bit becomes of eight bits sorry becomes one byte image one byte integer sorry and then we can basically represent each integer as a hash put them together as a hex put them together and get a hash other hashes or the perceptive hashes work quite similar to this and then these hashes since they are perceptive so they have this nice property that small modifications in input lead to small modifications in output we can use them to compare two images we can just look at how many bits are different and that will tell us how different these images are this is a quite useful feature but what is more we can use these hashes to actually select candidates we can say okay what are the all other listings that have the same image and that will give us a lot more candidates to consider we can go deeper and include also use neural nets and like in any convolutional neural net we have this layer before the final prediction usually called fully connected layer and this is typically used to extract so-called image embedding so this is like a vector representation of an image so we have an image and it gives us a numpy array that represent this image they have nice semantic properties that two similar images have very similar vectors so this is an official example from keras it's pretty easy just like 10 lines of code that give us this representation. This example, however, uses VGG, which is quite heavy. So like half a gig model. Typically it's not worth it. They are slow. They are heavy. There are lighter models like MobileNet that are 25 times smaller. And they have similar accuracy and the embeddings that we get from MobileNet have similar properties. So it's better to use them. Again, the code is pretty simple. So, okay, we get MobileNet, we extract features, but this gives us quite a large vector. So in this case, it's more than 1000. What do we do with this next? what we can do is take this large vector and use simple dimensionality reduction techniques like singular value decomposition or pca to reduce it to something more manageable like 100 dimensions but then from that we still want to compute hashes because hashes are nice easy to deal with and for that we use lsh lsh is locality sensitive hashing this is a family of hashes a perceptive hash that we covered previously is also LSH because they have this nice property that a small change in input results in a small change in output. So just an idea, one of the hashes of LSH is called random projection. They are built on this idea that if something is close in the regional space, when we project, it stays still close. If something is far, when we project, it's far. so we just generate random vectors we project on them, in this case two cars are still close, two animals are close and then we can generate many such vectors and project on them, so this is the basic idea for random projections it's very easy to implement so we generate many projection vectors, store them somewhere store them somewhere we do it only once and then for each image for each vector that we have we use these projection vectors to calculate hashes and then we store them somewhere where to store of course elastic search so why elastic search elastic search is implementation it uses lucene to implement inverted index. Inverted index, so like in case of direct index, is when by ID... Sorry. Direct index is when from ID we can get a document. So like, for example, we have image ID 1, and we use it to get the actual image. But inverted index, is the other way around we can ask okay for this hash what are the images and this is exactly what we need for this problem because we want to find all other listings that have the same image that has the same hash so we can just throw everything into elasticsearch and it will give us the answers we can also go further in and instead of just using the exact match we can chunk the hash into four or five chunks and then say tell elastic search hey this is a usual string treat it as a usual string because elastic search is a system for text search but can build on top of that saying okay treat this as string as usual tokens as words and then look for this and then when we do this when we search using such queries and then first it will find exact matches then matches where three out of four tokens match then matches when two out of four tokens match we can index everything like every incoming every item that we have we can index in elastic search and to find duplicates we can use more like these queries saying hey i have this document with this id i want to find all the other documents that are similar to this and then we don't just use hashes we can put title description all the textile fields and say okay i want um like using elastic search we can also say i want title to be two times more important than other fields so this is very useful and we can use this to get candidates so how to actually do this now we have this idea that we have hashes how do we put them to elastic search what is the big picture we can build a system for indexing everything so a user creates a listing and this listing is stored somewhere image can go to S3 S3 is storage from AWS where we can keep files so image gets to S3 then every time you put something to S3 S3 generates an event saying hey something was put to this bucket so this is the bucket name and this is the name of the file that was put there then a lambda function AWS lambda function can listen to these events coming from S3 and okay, there is a new file let's fetch it and calculate some hashes so with just these four lines of code we can already compute all these hashes there is library for that image hash it's as simple as that Then we put all these hashes to another queue And then eventually it goes to Elasticsearch So it looks like this So why do we need an extra step from Lambda to Elasticsearch? Not directly, because in case there is a peak We don't want to kill Elasticsearch with many inserts So we want to paste it out That's why we have a separate component in between And Lambda really scales So it really takes away all this complexity of scaling up and down and it picks like when we have for example 200 invocations per second it just scales there is nothing to worry about and there is no invocation it goes down of course and we can process this way like 10 million images per day of course we don't always just insert into elastic search we can we also need sometimes to delete things similarly we can subscribe to delete events from s3 and also have another component that updates records in Elasticsearch saying, hey, this thing was removed from our storage. Also covered neural networks. We can add an extra flow that covers them as well. So we can have a flow parallel to this that takes care of, like again, features images, but instead of computing just hashes, it applies a neural network and then uses LSH to compute hashes. So the reason it's separate is because the load is quite different. In case of hashes, it's quite light, but convolutional neural network is heavier. That's why it's a good idea to separate them. How do we actually create this component? Where do we host it? One of the options is, again, AWS Lambda. it's tricky because if we use tensorflow tensorflow binaries are super big and it's tricky to create a lambda function that stays within AWS limits because the limit is like 50 megabytes compressed but tensorflow is just too big it's still possible to do it and compress after a few days of painful work still possible and if the load is not high it's totally worth it because we can score 1 million images with just 60 bucks however when the load is like 10 million images per day it becomes expensive it's like 600 per day so better option is actually use EC2 machines from AWS or Kubernetes so these machines are always up because if there are and for this reason if it's just not so many images it's more expensive because all these machines are idle but in case the load is high and there is always something it becomes cheaper and it will cost like 600 for example for entire month instead of just one day this is like for high load like the multiple million images per day Kubernetes is probably a better choice and then finally the weak picture looks like this so user uploads something and then the content and images go through this indexing process and then by the time the content reaches the automatic moderation system it's already indexed and then we can talk the duplicate ask the duplicate detection system hey like what are the other duplicates what are the other duplicate candidates what are the other duplicates in case when we are certain we can right away reject these items in case when we are not, we can ask moderators to reject and actually use the output from moderators, the feedback they give, to have a better model. I hope so. Thank you. Alright, thanks very much. Questions, anybody? Is this the only mic? hi do you have any mechanism to guard against false negatives missed in the initial candidate selection yeah it's pretty difficult yeah so like you have to uh like you can include a lot more than you like there is a trade-off like how much computational power you want to invest into doing this so of course you can have your candidate set very large then you have to process a lot of things so depending how costly is the mistake of letting a duplicate slip through so there is no other way just trying to score as much as possible it's a very difficult problem Thank you for your talk very interesting my question would be isn't this also prone for attacks? I mean, do you know of any LSH distance maximization attacks or anything like that? Yeah, so for example, if somebody takes an image and takes a crop from this image, then hashes will already stop working. With LSH, it's like they are more resilient. But again, of course, there will be cases when you can find an angle for which you rotate and then neural network becomes like it doesn't notice it for that we can train cms networks so try to do all this like rotation and all this manipulation with images and train a neural net to recognize these rotations then the hashes will be not just general purpose like not just from the general purpose network but something you specifically train for this particular problem so this is the a good next step after just using a pre-trained model to actually have a special neural net that outputs hashes. Thank you for the talk. I have one question concerning the images because usually the websites are optimizing the images and they are heavily can be heavily modified if they are uploaded several times, like downloading and uploading again. How resistant are the hashes to that? So if you just take an image, open it in any editor and save it with a different compression, hashes should still stay the same. If you change small area, hashes should still stay the same. If you add a logo, like a watermark, some of the hashes will still stay the same depending on the size of this logo. But when you start cropping parts of the image or rotating the image or flipping it somehow, then hashes will stop working. But for these simple things like recompression, they will stay the same. One question. The output of the CNN, why do you hash it? Can't you just put it directly into Elasticsearch? I don't know a simple way to do this to actually to also be able to handle all these loads because like imagine that you insert you need to insert like 10 million images per day to this index and then the like you want to reduce your search space as much as possible so with this load it's kind of difficult. There are other things like things like FICE or Annoy that work directly on these row vectors, but with high load they become very slow. To be honest, I don't know a nice way to put these vectors, like real vectors to Elasticsearch. So hash is the simplest way. Any other questions? no then let's thank the speaker again