![]() It’d be like the 5-lottery having the same numbers 3 times in a row. Now if I ask the sampler to give me 50 balls at random, and all of them are green, I’d be a bit surprised to say the least. Imagine having a box with 1000 balls, half of them blue and the other half green. Knowing the solution space, Barbarik can then verify how non-uniform the sampler is. Barbarik is a pretty neat idea that basically constructs solution spaces with known solution distributions and then asks the sampler to generate uniform samples. Unfortunately, the paper by Chakraborty et al and its resulting code Barbarik showed that these uniform-like samplers are highly non-uniform. There are two well-known samplers that are supposed to generate uniform samples on complex solution spaces, QuickSampler ( code), and STS ( code), but give no guarantees, let’s call these “uniform-like” samplers. properly uniform samples), but if it’s too slow, we may want to exchange quality of samples for speed of generation. It would give very good quality samples (i.e. Deep neural networks tend to be extremely complex when translated to binary constraints, so UniGen will likely not be fast enough. Say, you want to generate interesting test inputs for your deep learning algorithm. However, for really complex solution spaces, it can have trouble. It’s a great sampler and will work very fast on many instances. I personally have worked on one called UniGen, a guaranteed approximate probabilistic sampler, meaning that it’ll give approximately uniform samples most of the time, and we have a proof to back this up. There have been many samplers proposed in the literature. For this, I need a fast way of generating uniform samples given the constraints on the solution space. If I want to test that this function operates correctly, one way to do it is to generate 100 uniformly random inputs that don’t violate any of the constraints, run the function, and see if all is OK. ![]() the 1st parameter must be larger than the second, the 2nd parameter must be divisible by the 3rd etc. Let’s say that I have a function I want to test, but the input to the function has some real-world constraints like e.g. ![]() However, when there are constraints on the solution space, it starts to get tricky. Just pick 5 random numbers from a box and we are done! For the lotto the solution space is very easy to generate. In some cases, this is quite simple, say, for the lotto. Uniform sampling is a problem where you are given a solution space and you have to present solutions uniformly, at random. ![]()
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
January 2023
Categories |