Spring 2010 MATLAB Contest, April 28 - May 5
Helen Chen
This is your reminder that the Spring MATLAB Programming Contest will start today at noon Eastern time. We will announce the contest start on this thread and also on the contest blog.
Please use this thread if you have questions or comments during the contest.
Talk to you soon!
Helen and the MATLAB Central Contest Team
Helen Chen
The contest website has been redesigned. You now need to log into your MATLAB Central account in order to submit or to comment on an existing submission.
Good luck to everyone! Have a great week!
Will Dampier
I've downloaded the example files and it seems like the testsuite_sample.mat file is corrupt and won't unzip properly. Is anyone else having this problem or just me?
Alan Chalker
I was able to open it just fine.
Alan Chalker
> The contest is now live. Go to the Sensor Contest Rules to start. http://www.mathworks.com/matlabcentral/contest/contests/2/rules
>
> The contest website has been redesigned. You now need to log into your MATLAB Central account in order to submit or to comment on an existing submission.
>
> Good luck to everyone! Have a great week!
I'm note sure if you intended this or not, but I can see the actual code of an entry I submitted, even though we are in darkness.
Alan Chalker
>
> The contest website has been redesigned. You now need to log into your MATLAB Central account in order to submit or to comment on an existing submission.
>
> Good luck to everyone! Have a great week!
I also just noticed that Jan's entry is showing up as a 'failed' result, instead of that being hidden. I hope this is intentional, since that was one of the major suggestions in the fall.
Can you somehow summarize the major changes to the contest? There were a lot of ideas bounced around last year and I'm curious as to what you ended up implementing.
Helen Chen
Will - Can you download a new file? As Alan noted, the file seems to open ok for us, but Ned resaved the file and reposted just in case...
Thanks,
Helen
Helen Chen
> I'm note sure if you intended this or not, but I can see the actual code of an entry I submitted, even though we are in darkness.
Hi Alan - As long as the code you are looking at is yours, it is ok that you see it. It is also ok that you see someone else's failed entry in the queue, since you can't see the score.
Helen
Dario Ringach
Helen,
Are these supposed to be actual natural images (pictures) or just any arbitrary random matrix?
Lucio Cetto
We are using a sample of real images, at different resolutions and different themes.
Lucio
"Dario Ringach" <da...@ucla.edu> wrote in message <hr9s7h$9b7$1...@fred.mathworks.com>...
John
Helen Chen
Hi Alan -
I posted a response to this question on the contest blog so that we could make this a mini-discussion if this is a popular topic.
http://blogs.mathworks.com/contest/2010/04/28/new-contest-website-features/
There have been 74 submissions made by 40 players so far. Any feedback on the updated look and feel?
Helen
Alan Chalker
>
> Hi Alan -
>
> I posted a response to this question on the contest blog so that we could make this a mini-discussion if this is a popular topic.
>
> http://blogs.mathworks.com/contest/2010/04/28/new-contest-website-features/
>
> There have been 74 submissions made by 40 players so far. Any feedback on the updated look and feel?
>
> Helen
Thanks Helen. I really like the new look and feel. It'll be interesting to see how it looks once we are in daylight and all the features are visible.
Helen Chen
> Thanks Helen. I really like the new look and feel. It'll be interesting to see how it looks once we are in daylight and all the features are visible.
Thanks Alan! :-)
Seth Popinchalk
> would there be some type of gui created for this contest ? Looks to be just a compression matrix overlay on sensors .
Hi John,
I don't know of any GUI created for this contest. If you make one based on the test suite, be sure to submit it to the file exchange so others can try it out!
-Seth
mavs favs
Daniel Armyr
Unfortunately, I can't squeeze in the time to participate in this year's contest.
I would just like to share my thought that this seems to essentially be a deconvolution problem. Maybe you guys allready know this, but if not, I would seriously look into how deconvolution can be applied.
My possibly worthless 0.02SEK.
//DA
the cyclist
If you run "runcontest" with the option argument
>> runcontest(true)
you will see graphical output of your solver.
the cyclist
Seth Popinchalk
> can we use interp2 function for the solver?
Interp2 is part of core MATLAB under $matlab/toolbox/matlab
>> which interp2
C:\Program Files\MATLAB\R2010a\toolbox\matlab\polyfun\interp2.m
What is allowed and not allowed is explained in the fine print here:
http://www.mathworks.com/matlabcentral/contest/contests/2/rules#fineprint
Daniel
Hi,
at which times start/end the visibility periods?
Daniel
Nicholas Howe
Alan Chalker
> Is it just me, or are the timestamps on the submissions (and newsgroup posts) off by four hours? Maybe that's why the contest doesn't seem to be in twilight yet?
I think they are being displayed in GMT, not Eastern.
Helen Chen
Sorry, I was late on switching that over. We are now in twilight!
About the hours, MATLAB Central is on UTC time. I will try to be better about announcing contest dates in UTC.
Helen
Ravi
In the rules, when you say the code should not run for more than 180 seconds - do you mean each call to our solver, or the overall runcontest code, which calls the entire testsuite?
Ravi
Sergey
> I'm a newbie to the MATLAB Contest
> In the rules, when you say the code should not run for more than 180 seconds - do you mean each call to our solver, or the overall runcontest code, which calls the entire testsuite?
>
> Ravi
entire testsuite
Sergey (SY)
John
Oliver Woodford
Oliver
Nicholas Howe
> I'm dropping out now - time to get back to work! Thanks to the contest team for another fun problem. I look forward to seeing the quality of images at the end of the week. Best of luck to everyone.
>
> Oliver
Oliver,
If you're dropping out, would you mind sharing the key ideas behind your twilight winner?
Alan Chalker
Oliver Woodford
> Oliver,
> If you're dropping out, would you mind sharing the key ideas behind your twilight winner?
Hi Nick
Sure. There are 3 key concepts:
1. I made sure my queries gave a unique and exact solution for the sum of each region, the regions being the intersections of all query masks. Given n queries that means I can only solve this uniquely for n (or fewer) regions - any more regions and you need regularization. To keep things tractable at every iteration I make each new region a subset of a current region, i.e. each query divides a current region in two. The method I ended up selecting was to divide a given region in half across the middle, either vertically or horizontally. I also made the constraint that no region could be more than twice as long as it was wide. This constraint (and not dividing a region of length 1) is enforced using the value 300 (see code), so remove it to see why it's necessary.
2. The question this poses is which region to split next. You want to split regions that are textured, so you get more information out; splitting a textureless region gains you nothing. At every iteration (query) I kept a record of the maximum (average) colour difference between each region and its neighbours, in both the horizontal and vertical directions. I then split the region with the largest difference, in the direction appropriate to the largest difference, subject to the constraints already mentioned. This was a simple heuristic, but seemed to work well! However, I believe that improving this decision process is where the real improvements will come in this contest.
3. Finally, rather than assign each region the average value for the region at the end, I smooth the image (as real images tend to be smooth, not blocky), still making sure that each region's average is correct. This gives a significant improvement in quality, more so with the edge preserving bilateral filter. Interestingly, the regular sampling grid helped here. Having a non-regular grid messed up the smoothing (try adding the smoothing to my "Prime I" method to see what I mean).
Hope that's useful.
Oliver
Oliver Woodford
> The question this poses is which region to split next. You want to split regions that are textured, so you get more information out; splitting a textureless region gains you nothing. I believe that improving this decision process is where the real improvements will come in this contest.
Incidentally, I started work on a method that tries to focus on regions where the gradient is not spatially linear. Since regions with linear gradient are well reconstructed by the post-processing smoothing step, splitting them up is wasted effort. However, I couldn't get it to work well. Perhaps someone else will...
Oliver
Oliver Woodford
> I made sure my queries gave a unique and exact solution for the sum of each region, the regions being the intersections of all query masks. Given n queries that means I can only solve this uniquely for n (or fewer) regions - any more regions and you need regularization.
Lastly (really), num regions >> queryLimit (by having queries overlapping many other queries) combined with regularization/Bayesian inference could well prove to be another rich vein for improvement. It's what all the cutting edge compressive sensing algorithms do, after all. The only problem is squeezing it all into 180 seconds!
Oliver
Amitabh Verma
#1 less nodes? srach 14184133 57.361 28378.3 (cyc: 14, node: 2959)
http://www.mathworks.com/matlabcentral/contest/contests/2/submissions/1472
#2 *linear cycler the cyclist 14184133 57.216 28378.6 (cyc: 14, node: 3263)
http://www.mathworks.com/matlabcentral/contest/contests/2/submissions/1464
Even though the computing time is more in less nodes? just because of the lesser node count it ranks above.
Also I had seem some entries where the complexity at 10 resulted in no score variation to an entry and same code with a higher than 10 complexity.
Any thoughts ?
srach
It is stated in the rules that the node count contributes to the score: http://www.mathworks.com/matlabcentral/contest/contests/2/rules#notes
Regards
srach
Alan Chalker
score = k1*result + k2*e(k3*runtime) + k4*max(complexity-10,0) + k5*nodes
Where:
k1 = 0.002
k2 = 0.01
k3 = 0.1
k4 = 1
k5 = 0.001
The current leading entry has a time of 77s, result of 14064009, cyc of 23, and nodes of 3537. Here’s a breakdown of the current tradoffs:
-cyc and score are a 1:1 ratio (i.e. each point shaved off cyc is a point shaved off the score)
-time and score are a 1:2.2 ratio
-result and score are a 1:0.002 ratio
-node and score are a 1:0.001 ratio
As is common at this point in the contest, Abhisek Ukil’s entries have already settled in just below the ‘knee’ of the time exponential curve, which is rather flat until about ~85s. However, because of results are so high right now and change quite a bit with small tweaks, I think we are going to find more payoff in trying to reduce the results by processing the images for a bit longer, at least until the times get up around the 95s range. Unfortunately that also means that during the various contest end times the queue is going to get very backlogged, since each entry will take several minutes to execute.
Sergey Y.
To avoid confusion with time zone change could you please clarify what will be the time of final Wednesday deadline?
(And do we need to expect one more sudden challenge on Tuesday?)
Sergey
Matthew Simoneau
(Remember the 10-entry-per-hour limit as we approach the deadline.)
With respect to additional mid-contest challenges, Ned announced a longevity prize for Tuesday on the contest blog.
Helen Chen (gmail)
"It would be usefull for players to be able to cancel their submission while the last is yet in qeue, if they realise that this submission has bugs or errors. With this capability the qeue list would shrinked giving a breath to mathworks contest computer and reducing the mean waiting time till submission evaluation. I hope mathworks contest team take this as a usefull peace of advice. Please reply me wether or not you agree with me. "
I'm interested in feedback from other players. Is this something that you would think would enhance your contest experience?
Thanks for your feedback!
Helen
Amitabh Verma
I totally agree with Dimitri. It doesn't make much sense to wait for an entry which is not going to yield the expected result. I am definitely in favor of such an option coz it will only make the contest more fast paced.
Sergey Y.
If you remove deleted submission from submission counter, then life will be even more hectic – possible rush of submission deleting when new leader appears.
I am sorry for beating a dead horse, but I have only one dream – CAPTCHA.
Sergey
"Helen Chen (gmail)" <hhch...@gmail.com> wrote in message <hrpaf5$1nd$1...@fred.mathworks.com>...
the cyclist
I would personally almost never use such a utility. Unless lots of people are submitting buggy code at crunch times (doubtful), and they realize that between time of submission and time of processing (doubtful), it will have minimal impact on the contest.
Amitabh Verma
> I do not expect anybody to use it in real life if it does not affect submission counter.
> If you remove deleted submission from submission counter, then life will be even more hectic – possible rush of submission deleting when new leader appears.
>
> I am sorry for beating a dead horse, but I have only one dream – CAPTCHA.
> Sergey
Now that everyone has to login before submitting their code. Is it possible to only process 1 entry per user at a time so that others who are in queue do not have to wait. Of course CAPTCHA is there but will it still deter the determined ones. The 1 entry processing was one of suggestions from last year.
Sergey Y.
Sergey
"Amitabh Verma" <amt...@gmail.com> wrote in message <hrpde8$mvs$1...@fred.mathworks.com>...
Alan Chalker
Yes, I can think of several situations where this would be nice to have. I've several times submitted some code only to realize I made some sort of infinite loop mistake. Instead of waiting for the 3 min limit to time the code out (and backing up the queue) it'd be nice to be able to dequeue it.
Alan Chalker
> Yes, submission limit helps partially with queue lag. I am not saying I do not like it. My main problem is with automatic tweaking machines. If one wants to do tweaking then one has to do it manually.
> Sergey
>
I'd like to point out that the contest has 3 distinct phases for a reason. Darkness and twilight mostly prevent tweaking and are almost always won by those contestants with an expert level understanding of the underlying algorithms. Many of those contestants deliberately don't participate during the daylight phase because of the nature of the contest completely shifts to tweaking and optimizing.
With the 10 entries / 10 mins limit now, there is no speed advantage of manual tweaking over auto tweaking - it's just a time commitment issue. If we are going to suggest arbitrary rules, I have a major issue with non-descriptive variable names and poorly documented code and think all leading entries need to be screened for that. But most competitors don't want to do that because again it's a time commitment issue.
One of the things I personally enjoy about the contest is developing code the deals with the contest mechanics (i.e. the auto submission code). I found it particularly challenging to create new code to handle the new site. In fact I spent most of the weekend doing that (which is unfortunately why I didn't get a chance to submit a documented leading solver like I usually do).
Alan Chalker
#1: Scored at: 2010-05-04 15:09:25 UTC , CPU Time: 174.418
#2: Scored at: 2010-05-04 15:12:33 UTC , CPU Time: 169.166
#3: Scored at: 2010-05-04 15:15:55 UTC , CPU Time: 173.046
#4, 5,6 etc etc etc.
The scored at time of these should be 6 mins apart not 3 mins apart if the code was being run twice. Was this an intentional change or an oversight in the new contest machinery?
Matthew Simoneau
Nicholas Howe
Helen Chen
> I'd like to encourage more competitors to add a photo to their profile. For those who have won in a past contest there are already photos in the hall of fame, but it would be nice to be able to put a face to all the new names that keep showing up.
That is such a really great suggestion, Nick! I second that request. :-)
Helen
Helen
the cyclist
Out of curiosity, Alan, will you just run your auto-generator continuously until the end of the contest? If so, it looks like we can safely assume that the queue will continue to grow until the end, since you can feed the queue at one entry per minute, and each entry requires more than that in processing time. (Note that this is not a complaint, just an observation.)
Also, out of curiosity (and only if you don't mind sharing, of course!): Does your code automatically grab the leader, and tweak any and all numerical parameters? Or do manually seek out more likely parameter for tweaking?
the cyclist
Amitabh Verma
I had a few questions on the above from the contest blog. Does the Longevity contest end at midnight Tues, UTC or run into Wed. ?
Is the score the cumulative time spent in lead or the longest entry that was in lead ?
Thanks.
Best,
Amitabh
PS: I agree pics would be nice to have :)
Sergey Y.
>
> the cyclist
As we discussing technical part of automatic tweaking I am curious too (If it is not a secret of course) : does your software reads result and looks for the minimum in multidimensional space or just tries all parameter values?
Sergey
Alan Chalker
>
> Out of curiosity, Alan, will you just run your auto-generator continuously until the end of the contest? If so, it looks like we can safely assume that the queue will continue to grow until the end, since you can feed the queue at one entry per minute, and each entry requires more than that in processing time. (Note that this is not a complaint, just an observation.)
>
> Also, out of curiosity (and only if you don't mind sharing, of course!): Does your code automatically grab the leader, and tweak any and all numerical parameters? Or do manually seek out more likely parameter for tweaking?
>
> the cyclist
No I won't run it overnight.. I'll take a break after the end of the current mini contest until about an hour before the ultimate contest end tomorrow. I have a special super duper strategy to implement then;)
I'm happy to share any and all details of my auto-submission code. Yes, I continuously scan to see who the current leader is. If it's my own entry I don't do anything at all. If it's another new code I grab the code, then have a ordered set of 'likely numeric parameters' to tweak. A lot of this is just gut feel from earlier in the contest. For example, say a key parameter to tweak is currently at 0.1234. Then my code would first submit an entry with that changed to 0.1235, the next one would be 0.1233, next 0.1236, then 0.1232, etc. etc. I repeat this about 10 times on average, trying to tweak slightly on both sides of the parameter. Then I go to the next likely parameter (unless of course the leader changes during this process, in which case it starts over again with the new code).
Alan Chalker
It's essentially just doing an educated parameter sweep. With the level of tweaking we are doing it's overfitting to the test suite, so there's no real way to truly 'algorithmically optimize'.
Helen Chen
<snip>
A Third Way
It seems a shame that many of the competitive entries are still dominated by just two basic solvers that query non-overlapping regions. Why, when there are so many other approaches available?
To try to make the mix more interesting here is a third approach. In itself it is not competitive, but I think that if tweaked to the level of existing entries it would outperform them on some images, particularly where contrast is reasonably even across the whole image rather than being focussed around a few features.
A Third Way carries out an initial scan using two rectangular overlapping scans, with the second a grid offset by half a grid width. Between them these scans take up about 80% of the available queries, and they each give a different, coarse version of the image. Every pixel has two estimated values, and if you form a combined image from their means you see an image with pixel blocks half the size of the initial scans. In effect you have faked the resolution you could get with 1.6x the permitted number of scans, which sounds good. In particular it should make smoothing more effective.
The catch is that in place of exact answers you would have with a real 1.6x scan you only have two estimates for the result of each query. Clearly you have lost accuracy near any sharp edges, which is where the remaining 20% of queries come in. Because we have two estimates for each subarea we have a good idea where the uncertainties are highest, so we can query these subareas in order to improve the overall quality of the estimate. Not only do these queries pin down exact answers for the queried subarea, they also reduce uncertainties for all 8 adjacent subareas. In low contrast areas of course the two initial estimates will be similar so we won't waste queries there; queries cluster near high-contrast areas the two estimates differ most, and this is why we only need to query about 1/8 of the subareas to get a reasonable-quality image.
The result should be an image with reasonably accurate subarea estimates, and subareas smaller on average than can be produced by the two main approaches. The problem seems to be that this improvement is spread rather evenly across the whole image instead of being as strongly focussed on sharp edges as it is with subdivision.
I don't have time to take development any further, but if you want to have a play I'd suggest an number of areas for attention (on top of the sloppy coding).
-- Ideally you don't want to query too many subareas that are very close together, as this is redundant. It may be worth recalculating uncertainties as subareas are queried?
-- Subarea boundaries have been allocated evenly along both x and y axes, but if t is the usual edge of a subarea this results in some subareas that are (t+1)^2 pixels while most subareas are t^2 or t.(t+1). Might it be better to put all the large gaps along just one axis so the largest area is t.(t+1)?
-- Smaller areas give better estimates; this should slightly modify the dispersion and mean estimates?
-- The complexity of the code gives great scope for optimisation and bug hunts, so many hours of tweaking are available 8-)
Good luck to anyone who can get this into competitive form!
Incidentally, if anyone fancies a collaborative effort I am out of coding time but have a number of other ideas that might be interesting, a sketch for a fourth solver based on edge detection and a few others for improvements in late scans and post-processing. Email me at ff95 a t dial dot pipex dot com if you are interested.
</snip>
Alan Chalker
>
> I had a few questions on the above from the contest blog. Does the Longevity contest end at midnight Tues, UTC or run into Wed. ?
>
> Is the score the cumulative time spent in lead or the longest entry that was in lead ?
>
> Thanks.
>
> Best,
> Amitabh
>
Another question is whether it's based upon submission time or scoring time. Also, please note both the stats page and the twitter feed seem to be missing some of the leaders. For example, right now leader 259 is an entry from Yi Cao, and 260 is one of my entries. However, if you look at entry # 4012 submitted by Amitabh Verma, it was in the lead for a while and should be listed as 260.
Alan Chalker
> Another question is whether it's based upon submission time or scoring time. Also, please note both the stats page and the twitter feed seem to be missing some of the leaders. For example, right now leader 259 is an entry from Yi Cao, and 260 is one of my entries. However, if you look at entry # 4012 submitted by Amitabh Verma, it was in the lead for a while and should be listed as 260.
Just to clarify, depending on what your actual meaning of the mini-contest rules is and whats going on with the stats page is likely to determine who the mini-contest winner is. As of right now, the stats page shows the 2 longest entries as mine and then Yi Cao's:
259 Yi Cao tomorrow is another day. Tue 20:47 0.02% 2.96
260 Alan Chalker Auto tweaker Tue 23:45 0.00% 4.14
However I'm not sure these are correctly indicating the actual durations.
Oliver Woodford
> A Third Way carries out an initial scan using two rectangular overlapping scans, with the second a grid offset by half a grid width. Between them these scans take up about 80% of the available queries, and they each give a different, coarse version of the image. Every pixel has two estimated values, and if you form a combined image from their means you see an image with pixel blocks half the size of the initial scans. In effect you have faked the resolution you could get with 1.6x the permitted number of scans, which sounds good. In particular it should make smoothing more effective.
Robert, sounds like we're on the same wavelength here. You are suggesting, in more concrete form, an approach I have suggested a couple of times already. Indeed, my Super Slim entry implements the first stage of just such a method, but using two overlapping scans to get 9 times the resolution rather than your 4. I think it's definitely a winning approach, but like yourself I haven't the time to implement it fully.
Oliver
Sergey Y.
Sorry for being so slow. What about 10-entry-per-hour limit?
I can not find it.
Helen Chen
>
> Sorry for being so slow. What about 10-entry-per-hour limit?
> I can not find it.
Sergey - It is 10 entries per 10 minutes not per hour. If you submit 10 entries, you will see a message that tells this.
Helen
Helen Chen
Thanks Alan. I've forwarded this to Matt to look into.
Helen
Amitabh Verma
Thanks Alan, for bringing it to notice.
Cheers !
Nicholas Howe
I've often wished that there was some way to keep separate development threads alive at the same time, so that people could be rewarded for the best block-style solver, the best overlapping solver, etc. There were other contests where I've felt like a really interesting approach never saw the light of day because it was impossible for one person to compete with the combined optimizations of the group. With development on multiple fronts, you might see totally different solvers competing for the lead, and possibly cross-pollination of ideas. But I don't know how you would structure such a contest, without relying on people's subjective judgments that 'this is a X-type of solver".
In this contest, I have long wondered if we would see an entry based upon the recent research in compressive sensing. (I suspect that reading about this may have inspired the current competition.) In theory these allow excellent reconstruction of images with many fewer bits than the Nyquist limit would suggest. All the current solvers are essentially limited by Nyquist, so I think a CS solver would win.
The queries of such a solver look very different than either the block solver or the periodic solver outlined above. They are essentially random pixel sets from the image. Each one gives you a little information about all the pixels in the image, and you can recover the original by performing a convex optimization via linear programming. Personally I found the research results a little too diverse to condense into a specific contest entry in the amount of time I had, and I was not sure from my reading whether the required computation would even fit into the 3-minute window. But perhaps some other brave soul has succeeded in doing so, and will surprise us all in the final minutes of the contest.
Helen Chen
>
I just heard from Ned and posted his decision on the blog.
Helen
ps. Time is always the time of submission.
Alan Chalker
http://blogs.mathworks.com/contest/2010/04/28/new-contest-website-features/#comment-6569
"Regarding the login requirements, there is no rule that a given player use only one login ID, but if we start giving awards for most prolific, or greatest improved, multiple IDs would hurt your chances. It might be interesting if your own submissions were competing for the top spot."
And I'll also point to the newsgroup conversations from past contests, in particular: http://www.mathworks.com/matlabcentral/newsreader/view_thread/238684
Helen Chen
ttys,
Helen
Alan Chalker
>
> Helen
> ps. Time is always the time of submission.
Helen: I'm glad to hear that. One of the tactics I tried yesterday morning was to wait until an entry of mine was in the lead, and the queue was empty, and then to fill the queue with lots of entries that take up almost the full 180 second limit (this was my Queue delay series of entries). The thought was that if it was scoring time that counts, those queue delay entries would significantly increase the time it took before other entries could be scored, artificially inflating my longevity time.
Interestingly, Sergey seems to have been wondering what I was doing and resubmitted several of those entries, even further increasing the queue delay. I thought it important to publicly disclose this tactic now, and the fact that it doesn't actually help, in order to avoid anyone else from trying it in future contests and unnecessarily lengthening the queue processing time.
Oliver Woodford
> Just to pre-emptively respond to any comments about me flooding the queue at the end, I'd like to point to the following blog post from a week ago from Seth:
>
> http://blogs.mathworks.com/contest/2010/04/28/new-contest-website-features/#comment-6569
True, but I'd like to post-emptively quote Ned's post from yesterday (http://blogs.mathworks.com/contest/2010/05/04/smaller-than-one-thousand/) which states "Sock puppet accounts are frowned upon". Consider this a stern frowning. :)
Sergey Y.
> Interestingly, Sergey seems to have been wondering what I was doing and resubmitted several of those entries, even further increasing the queue delay. I thought it important to publicly disclose this tactic now, and the fact that it doesn't actually help, in order to avoid anyone else from trying it in future contests and unnecessarily lengthening the queue processing time.
Actually I was using similar tactics, however differently.
Couple times I strongly suspected that my code is better then current best. In that case I was trying to submit several submissions and then my code. That way code will be scored at earlier times, but becomes visible as best significantly later delaying start of your “tweaking machine gun”
Then I saw your slow code and tested it for the same purpose.
Robert Macrae
Hah! I liked the idea of using 3 or 4, but decided that I might hit problems with instability as sharp features would cause ripples two or 3 subareas away. Then I got bogged down in coding the edges and ran out of time; with hindsight I should not have hand-coded rectangular areas, the gain nothing like worth the hassle.
I think overlapping regions like this are potentially a step forward, but as Nick comments below there are others that may be better...
Robert Macrae
Alan Chalker
>
> Actually I was using similar tactics, however differently.
> Couple times I strongly suspected that my code is better then current best. In that case I was trying to submit several submissions and then my code. That way code will be scored at earlier times, but becomes visible as best significantly later delaying start of your “tweaking machine gun”
>
> Then I saw your slow code and tested it for the same purpose.
That's an excellent counter-tactic! I'm glad to see someone trying to 'beat me at my own game';)
Alan Chalker
> The Contest queue is now officially closed. There are 380 entries in the queue at this point, so after those entries are processed, we will have an answer to our big question - Who is the Grand Prize Winner for this contest!
>
> ttys,
> Helen
Helen:
I'd like to extend my thanks again to you and the rest of your team for organizing and running this event. I always look forward to the contests and enjoy the various activities and community that has been built up around them. The new website and machinery is great (even if it did cause me a lot of extra work at the start of the contest to adapt;).
One minor suggestion: would it be possible to add an explicit hidden field to the submission form that indicates the id number of the 'based on code'? Right now you have this encoded somehow in the auth-token field. With auto-tweaking code it's not really possible to create that reference back to the original code, however I think there is a lot of value in being able to track the relationships between entries, particularly with the new abilities of the website to show both based on and is the basis for data.
Robert Macrae
> I've often wished that there was some way to keep separate development threads alive at the same time, so that people could be rewarded for the best block-style solver, the best overlapping solver, etc.
Pretty much why I posted in the newsgroup; it makes it possible to find if anyone is interested, rather than being just one more noncompetitive entry.
> In this contest, I have long wondered if we would see an entry based upon the recent research in compressive sensing.
The problem with overlapping regions is that they have to be
1) reasonably localised (so that they capture smooth features well) and
2) reasonably orthogonal (so that the information from them can be combined without too much iteration.
It is quite hard to achieve both, but here are two sketches:
1) Create square regions 8 pixels across. Its then easy to construct local orthogonal subregions 8x4 and 2x(8x2), with 1s and 0s arranged so that the 1s are all on the side expected to be lighter. A substantial subset of the subregions (or all of them) can then queried together, so we learn the average difference between the two sides and can update our estimates.
2) Keep a list of the masks that have been used so far. To select a new query, construct a score (perhaps by smoothing the current image) of pixels expected to be brighter, and orthogonalise this score against previous masks. Query the brightest half. Again this allows us to update our estimates, though the orthogonality will not be perfect.
> ... But perhaps some other brave soul has succeeded in doing so, and will surprise us all in the final minutes of the contest.
Here is hoping 8-)
Jan
> 1) Create square regions 8 pixels across. Its then easy to construct local orthogonal subregions 8x4 and 2x(8x2), with 1s and 0s arranged so that the 1s are all on the side expected to be lighter. A substantial subset of the subregions (or all of them) can then queried together, so we learn the average difference between the two sides and can update our estimates.
> 2) Keep a list of the masks that have been used so far. To select a new query, construct a score (perhaps by smoothing the current image) of pixels expected to be brighter, and orthogonalise this score against previous masks. Query the brightest half. Again this allows us to update our estimates, though the orthogonality will not be perfect.
First thanks for the great contest! I joined this contest for the first time now and enjoyed it a lot.
I think the problem was particularly prune towards overfitting. Although maybe if the players would only train their algorithms on the test data set and only now the official data set would be applied, that might have helpeda bit. Anyway, seeing the auto tweaking (although kind of foolish indeed) approaches was just as funny.
Also I liked the twilight phase most and would love to have it a bit elongated next time, definitely more than the daylight phase which could have been easily one day shorter in this case.
Anyway I wonder if there are solutions for this problem available from the Mathworks people? I wonder where they would stand:) Or if there is some working algorithm with good results along the lines of what Robert writes?
Regards, Jan
Nicholas Howe
> 1) reasonably localised (so that they capture smooth features well) and
> 2) reasonably orthogonal (so that the information from them can be combined without too much iteration.
Robert,
I'm not an expert on this field, but the reading that I have done suggests that you actually want queries that are as random as possible (and hence entirely unlocalized). This runs counter to our usual intuition, but so does beating the Nyquist limit. If people are interested in reading more about this, there's a lot out there but here is one article that describes the basic idea:
http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/CSintro.pdf
Somebody actually tried something along these line early in the contest (see entries commented concerning cosamp code) but I don't think they got it working.
Hannes Naudé
> "Robert Macrae" <robertR...@arcusinvest.com> wrote in message
> > The problem with overlapping regions is that they have to be
> > 1) reasonably localised (so that they capture smooth features well) and
> > 2) reasonably orthogonal (so that the information from them can be combined without too much iteration.
>
> Robert,
That's exactly right. Typical compressive sampling queries are just random masks. I experimented with some compressive sampling code in the darkness phase of the competition (from the L1 magic website as well as from David Wipf's homepage), but it wasn't competitive.
The reason why our simple block based solvers appear to outperform the cutting edge stuff from academia is the fact that the problem as stated here does not actually correspond exactly to the compressive sampling problem typically studied in the real world. In that case, one is not able to adjust your query pattern dynamically based on the results from earlier queries. Rather, the entire set of query masks need to be specified at the outset.
Being able to adjust our queries to zoom in on areas with detail is a significant (allthough not realistic) advantage and allows the custom developed code to outperform the off the shelf CS code by orders of magnitude.
Regards
Hannes
Amitabh Verma
Just an afterthought... about the possibilities of using a tool.
In Daylight using a tool/utility one can also query for actual pixel value checking against Result. If one runs it for 2 days with 10 ids. 48*60*10 attempts can yield (48*60*10)/255 true pixels.
255 is the max attempts required sequentially. Using a simple algorithm (2^n) one can find the true pixel value in <8 attempts. Highly increasing the remainder value >3600.
The queue will also not get backed up since this entry will run in ~2-3 sec.
Now the smallest image in the test suit had ~2500 pixels.
Now I have got one image accurate pixel to pixel. Wonder how much score difference that can make ?
My stand on this is as long as it is within the rules defined by the Matlab team, its fine. However, if a number of people start doing this, thing can go astray. Just my 2 cents.
PS: I used a modest total of 10 ids only who were named 'Uncle_Sam' 8-)
Nicholas Howe
>
> Being able to adjust our queries to zoom in on areas with detail is a significant (allthough not realistic) advantage and allows the custom developed code to outperform the off the shelf CS code by orders of magnitude.
Thanks for clarifying this, Hannes. I feel better now about not putting the time into delving through that CS material! (As I write this your entry stands at the top of the heap, so it looks like you managed to do quite well with other techniques also.)
Sergey Y.
I personally spend first half of darkness trying to implement that method
(It is widely used in neuroscience for receptive field mapping in visual cortex).
Unfortunately it did not look promising. Maybe using Gabor function as mask is better but I did not try it.
Sergey Y.
However, direct probing is against the rules.
Sergey Y.
> One minor suggestion: would it be possible to add an explicit hidden field to the submission form that indicates the id number of the 'based on code'?
If we go that way I would respectfully request “official Web API” :)
I lot of thanks to Matlab contest team for wonderful problem and new site.
Good luck to all participants. Hopefully I will see you in a half a year
Sergey
Yi Cao
I was thinking a zooming approach, even with diagonal masks but was not successful to compete with current approahes. My view is that the contest is a game. We cannot and should not treat it too academically.
It sounds like Hannes' random entry will finally beat my 'final effort' series. Well-done!
Yi
Alan Chalker
>
> However, direct probing is against the rules.
To reinforce that, here's the relevant section of the rules:
"Extraction of puzzles in the test suite by manipulating the score, runtime, or error conditions is also forbidden. In the small scale, this has been an element of many past contests, but in the Blockbuster Contest, Alan Chalker turned this into a science."
Alan Chalker
Helen (and all): Just a minor error I never noticed before in the rules. It was the Blackbox contest, not the Blockbuster contest.
Robert Macrae
> I'm not an expert on this field, but the reading that I have done suggests that you actually want queries that are as random as possible (and hence entirely unlocalized).
"Reading" -- dubious concept, it will never catch on
I had a look at random queries. They handle the "nearly orthogonal" bit well, but I don't think they can be best. The value of a query is (at least roughly) how different the answer is from your prior estimate. That is the argument for large overlapping queries, but it works best if you can pick pixels that for some reason seem likely to be all be higher or lower than their current means suggest (eg because they are all on the dark side edges). Pure random queries can't do this so the gain per query seems rather low... but I'll take a look at your reference, I'm probably missing something.
Robert Macrae
Robert Macrae
> The reason why our simple block based solvers appear to outperform the cutting edge stuff from academia is the fact that the problem as stated here does not actually correspond exactly to the compressive sampling problem typically studied in the real world. In that case, one is not able to adjust your query pattern dynamically based on the results from earlier queries. Rather, the entire set of query masks need to be specified at the outset.
That is exactly why I rejected random (and Hadamard). However I think the concept of large overlapping queries can still be made to work.
> Being able to adjust our queries to zoom in on areas with detail is a significant (allthough not realistic) advantage
Its a different problem, but I don't think its unrealistic.
Robert
Amitabh Verma
> "Alan Chalker" <alanc...@osc.edu> wrote in message
> > "Extraction of puzzles in the test suite by manipulating the score, runtime, or error conditions is also forbidden. In the small scale, this has been an element of many past contests, but in the Blockbuster Contest, Alan Chalker turned this into a science."
Guess I have lots to learn :)
Thanks to all the contestants and the Matlab team, it was a real fun and educational trip !
Hannes Naudé
>
> Yi
Take a closer look my friend, it's not as random as you might think. ;-)
Cheers
H
Hannes Naudé
> That is exactly why I rejected random (and Hadamard). However I think the concept of large overlapping queries can still be made to work.
Agree with you there. The algorhithms you and Oliver discussed here sounded very promising. However, I've learnt the hard way not to attempt any global changes after about sunday. Past a certain point in the contest the only edits that stand a chance are nested inside lots of conditions and fire only very rarely, so as not to disturb the solver from its resting place in the deep local minima. :-(
Another unimplemented idea is excluding the outer edge from the estimation process until the very end and then just assigning each pixel in the outer edge the value of its nearest neighbour on the inner. This gives us more resolution towards the center (where the detail is more likely to be in any case) in exchange for a minimal loss on the outer edge.
In a similar way one can leave open regions BETWEEN queries and then use standard image inpainting algorithms to fil them in.
> > Being able to adjust our queries to zoom in on areas with detail is a significant (allthough not realistic) advantage
Well, by unrealistic I meant unrealistic in typical compressive sensing applications where minimal processing power/battery life is available on the sensor end . I'm sure real-world applications which match the problem as studied here exist, I just don't know what they are.
Hannes Naudé
Thanks for clarifying this, Hannes. I feel better now about not putting the time into delving through that CS material! (As I write this your entry stands at the top of the heap, so it looks like you managed to do quite well with other techniques also.)
Thanks. Unfortunately, in this case, "other techniques" refers to intentionally overfitting the dataset, something for which I have a deep seated dislike. But hey if you can't beat them, join them.
Alan Chalker
>
> Take a closer look my friend, it's not as random as you might think. ;-)
>
> Cheers
> H
Hannes: Congrats on being the grand winner! It's nice to see that you were able to sneak in some fundamental solver changes at the last minute that leaped far ahead of everyone else (particularly since far too often last minute tweaking is what wins). Care to share any details of what you did?
Nicholas Howe
Well, whatever you did, you did it better than everyone else. Well done!
In the past they have sometimes awarded a generality prize by running the submissions on a brand new test set after the contest ends. I wonder if they'll do that this time around?
I want to add my thanks to the Mathworks contest team. I think this was a great contest topic, very accessible and lots of fun to work on. The new contest machinery is very nice too. My one suggestion: in the past I think it was easier to diff two submissions; now I find it harder to find the link to do that. (Once I have the page up I can just replace the submission numbers in the URL.) Anyway, kudos to everyone involved in setting up this spring's contest!
Darren Rowland
And thanks to the contest team for a well organised contest.
Hannes Naudé
I don't mind at all. But it'll take me a while. So expect a post in the next few hours, but in the meantime I'd imagine you can have a lot of fun seeing whos the first to figure it out ;-). I'm afraid there were no fundamental solver changes. Last minute tweaking did win, just not random tweaking.
My overfitting series of entries were designed to look like random variation, with the only parameter changing between them being a 20-bit binary key stored in a lookup table. One of them got a very good result and people are quick to accept that I got a lucky key. In fact there are only 8 keys in the entire keyspace that would have defeated Sergey's top entry. That's a 1 in 131 071 chance.
A clue that something was afoot can be found in the comment on the first line of the code which contains the result that it eventually achieved.
A last few clues for anyone taking up the challenge to reverse engineer: Overfitting was based on information collected using the "Random Randomness" probe series which was in turn based on "Random Change" by Magnus. Sorry for not crediting correctly. Heat of battle and all that.
Cheers
H
srach
It was again a great contest; I liked the problem very much as well as the new contest machinery. Especially the 10 entries per minute barrier is a nice improvement, although it did not seem to work for all of us. ;)
Many thanks to the people at mathworks who organized this great event and, of course, to all the participants who made it such an enjoyable time full of new things to learn.
On a side note: will there be high resolution versions of the contest badges suitable for tattooing? :D
Hope to see you all in Fall.
Best regards
Stefan
Gerbert Myburgh
After seeing you being tweeked out in the last minutes before, I'm very glad you made it to the top this time.
(Whoops, accidently posted as new message thread)
Thank you very much to the contest team for a great contest. Like always it was fun to compete.
Just a comment.
It should be fairly obvious from the statistics page (number of participants per day) that there are in fact many many more people interested in the algorithmic solving than the daylight tweaking.
Yet darkness is 1 day, twilight is 1 day, and Daylight stretches out for a week.
Not only that, Both Darkness and Twilight falls in the middle of the week, when most of us have to work.
I don't suggest you change your unique competition format entirely, but I do think we will see a stronger start to Dayilght if the algortihm guys can have a weekend day to work on the problem. ahead of everyone else (particularly since far too often last minute tweaking is what wins). Care to share any details of what you did?
Oliver Woodford
> The reason why our simple block based solvers appear to outperform the cutting edge stuff from academia is the fact that the problem as stated here does not actually correspond exactly to the compressive sampling problem typically studied in the real world. In that case, one is not able to adjust your query pattern dynamically based on the results from earlier queries. Rather, the entire set of query masks need to be specified at the outset.
Firstly, congrats on winning the grand prize, Hannes. Secondly, I disagree with this analysis of why "block based solvers" or "fully constrained solvers" (that's my term) performed best in this competition.
I spent about a day skim reading the literature (hence why I wasn't competitive during darkness). On the point of published compressive sensing algorithms providing the next query based on the current data, "Bayesian Compressive Sensing" (Ji, Xue, Carin, 2008) does exactly this. There are almost certainly more examples too.
During the course of the competition I implemented random, DCT and overlapping block queries (what I'll refer to as "under constrained solvers"). The problem with this type of approach, as I've said before, is that the value of each pixel, or rather each region (regions being the intersection of all the queries), is not fully constrained. This contrasts with the "fully constrained solvers", which give n regions from n queries, allowing the average value of each region to be computed in closed form. Because of the ambiguity in the "under constrained solvers" you need to add extra information to solve the problem, in the form of prior information on the nature of images. My PhD happened to be on the form of such priors and the techniques required to optimize them. Images are generally smooth, but the distribution of gradients is "heavy tailed", meaning there are more large gradient
discontinuities than a smooth (Gaussian) prior would predict. This makes the priors non-convex and difficult to optimize efficiently - certainly not possible in 180s. I tried to use a naive smooth prior in a very ad hoc way in my Super Slim entry, but you can see from Ned's mid-contest analysis that it over-smoothed the results. I also tried this approach on the random and DCT queries, but the smoothing generated worse results for both.
In short, "under constrained solvers" require prior information. Fast priors over-smooth and produce poor results. Good priors are slow to optimize, hence not feasible. Some of the test-suite images were distinctly unnatural anyway, also biasing against "under-constrained solvers" using natural image priors. This is my 2 cents on why the "fully constrained solvers" prevailed.
Oliver
Hannes Naudé
Okay, here goes. If you are currently reverse engineering my probing entries, this is a SPOILER ALERT. Stop reading now.
Parameter tweakers typically operate by trial and error. That is, a parameter is adjusted and if the score improves the adjustment is kept, if the score gets worse, the entry is consigned to the nether regions of the scoreboard and forgotten. I wondered whether these "failed" attempts at tweaking could not somehow inform future tweaking endeavours. In most cases the answer appears to be no, since knowing that changing x from 0.37 to 0.38 worsens the score does not in general imply anything about the effect changing it to 0.36 (or any other value) will have, since score changes near the optimal settings of parameters are typically not linear (or even continuous) in any of the parameters.
Also, the parameters are not usually independent, that is, if keeping x constant and increasing y yields a score improvement and keeping y constant and increasing x yields a score improvement, it does not follow that increasing both x and y will yield the combined improvement.
However, the popularity of lines like:
if (e>=8 && e<=25) || (e>=100) || (e>=36 && e<=46) || (e>=60 && e<=66)
yields an important clue. This line is essentially a manually coded hash table with 0 or 1 entries and the parameter e functioning as the hashkey for indexing into the table. In this case the entries determine which solver will be run for a specific problem. The core observation here is that the implicit ones and zeros in this hash table are INDEPENT parameters affecting the result.
So, if adding an (e==7) clause above improves the result by 10 points and adding an (e==9) clause improves the result by 7.5 points , then adding both is guaranteed to improve the result by 17.5 points.
Now note that we can transform any parameter in the code (in my case i chose blockSize) to a set of independent parameters with code similar to the following:
rand('seed',SomeParameterThatIdentifiesTheProblem);
lookup=[ 0.5 1;1 0];
i=find(rand(1)<lookup(1,:),1,'first');
blockSize = ExistingFormula+lookup(2,i)*DELTA;
The pseudocode above implements a hashtable with 2 equally spaced buckets (In practice I used 20). The hashkey is a random value, which provides the benefit of being uniformly distributed over a known range. It should be simple to see now that one could probe out the effect of each individual bucket and then, at a time of your choosing activate all beneficial buckets at the same time to get the aggregate score improvement.
This is the basic concept, allthough I did not follow this route exactly for social engineering reasons. Firstly, if I probed out the leader (at that time) in this way, the first beneficial bucket that I hit would have placed me in top spot and attracted undue attention to what I was doing. Secondly, once someone cottoned on, it would be very simple for them to arrive at the same beneficial set of buckets that I had deduced by simply observing the scores of my entries.
For these reason I deduced the impact of each of my 20 buckets by submitting a set of 20 solvers each with a different random selection of buckets enabled. The individual bucket contributions to each score change can then be solved for by pre-multiplying the vector of score differentials by the inverse of the sampling matrix (where the sampling matrix is a 20x20 matrix with rows corresponding to the random 20 bit keys used in each of the solvers).
This meant that anyone trying to piggyback would have to first reconstruct my sampling matrix by opening each of my 20 entries and copy-pasting appropriately.
I was quite chuffed with this aspect until I shutdown thoughtlessly, losing my precious sampling matrix and having to recover it in the way just described. #@!%$. You can't get pills for stupid.
As a sidenote, since runtime is additive, just like result is, it is possible to predict the runtime (and therefore the final score) in the same way. However, the problem of finding the entry with the best score (given all bucket contributions to both result and runtime) is not a nice linear one like the problem of finding best result. Luckily Matlab can still handle this by brute-force for a 20 bit key but it might get messy at 30 bits. As it happens, this was irrelevant, since changing the blocksize has minimal impact on runtime and because my runtime estimates were noisy in any case since large values in the inverse of my sampling matrix amplified random timing variations in my probe set.
I initially came up with this scheme a few years ago after a contest (not sure which one, might have been blackbox). I have not used it until now, partly due to limited opportunity (would not have worked in Army Ants, I was unable to participate in Color Bridge) and partly due to concern for the impact widespread use of this and related strategies could have on the game. This will exacerbate the overfitting problem significantly. Twenty probes gave me the ability to predict exactly the results that would have been achieved by over a million hypothetical submissions. 30 probes would push that to over a billion. A person with an auto-submitter and the inclination to use it in this way could stall essentially all further algorithmic progress within hours of the start of daylight. Banning the approach, by any means other than manual inspection is not viable, since it does not depend on any
single function that could be banned. Having a bot win a mid-contest prize provided the push I needed to overcome my hesitation. After all, if bots are beating us, then how much more mindless can it get (no disrespect intended to Alan’s bot, I’m sure I’d like him if I got to know him ;-) ).
For this reason, I think we should seriously discuss options for promoting better generality. Simply running all entries through a validation set afterwards will not work, since the usefulness of a validation set stems from the fact that it is seen far fewer times than the test set. In this context the validation set will see just as many entries as the test set did and the validation winner is therefore also likely to be an overfitted solution. For validation to work one must restrict the number of solvers to be run against it. Just running the top X entries against the validation suite doesn't work either, because the truly general solutions end up WAAAY down in the rankings. One way would be if each contestant is allowed to nominate one or two entries to be evaluated against the validation set, perhaps once-off or perhaps daily. Unfortunately this might require non-trivial changes to
the interface. This also requires that sock puppet accounts be banned, not just frowned upon.
The only foolproof way I can think of in the current framework is to restrict the problems so that it is impossible to split the test suite into independent pieces. Examples of such problems are the Ants and Army Ants contests. Even though these were my favourite contests of all time, I consider this quite restrictive. Another way would be to have a king of the hill style contest where competitors' codes are pitted directly against one another ala Army Ants. A third option is to have daily test suite switches. These have the downside of introducing discontinuities in score, which messes with the stats page. That may or may not be an acceptable price to pay.
Jan
1. Generalization: why not using a different data set each day (or couple of days) and then in the end letting all algorithms run against all data sets and take the average score? So e.g. if there are three data sets and an algorithm is learning against one data sets it surely goes away from the other two and since they are not available at the same time one can never learn for them all. Should drive the contest more towards generality of concepts.
2. Submission restriction: instead of 10 per 10 minutes, maybe having an increasing limit in time like : 2 per minute, 4 per 10 minute, 8 per hour so the queue is loaded more evenly and not flooded by the tweaking gurus. One gets results faster and well, any new addition to an algorithm that does not consists of pure tweaking will certainly take 5 minutes.
3. Categorization: Since the leading 1000 or 2000 submissions are all the same algorithm with small changes its really difficult to get an overview of what really different approaches there are. Here in the newsgroup people use categories in their texts (block solver, ...) - so its only natural to have them. I would suggest, that participants categorize other submissions (although this could be difficult e.g. for hybrid algorithms) and maybe get a reward for it like a place in a priority queue for each categorization of another submission. Then have winners in each categorization. Actually what I want is some kind of clustering of algorithm not for similar performance but for similar usage of algorithms, maybe some kind of genealogical grouped tree.
Example here: categories: random blocks, equal blocks, blocks + importance sampling, blocks + importants sampling + problem overfitting, ...
Then I would suggest that the submission table is initially displayed grouped for categories. So spectators have a better overview.
4. Maybe it would make the contest more popular if there would be a small prize like the winner gets a free science book from amazon (which also has its problems since amazon doesn't ship everywhere in the world). Actually just taking part for the fun of it is absolutely sufficient, but the popularity and visibility maybe goes up.
Regards,
Jan
Hannes Naudé
Interesting, I see they refer to this alternate construction as Adaptive Compressive sensing. I had not come across this before. I'd be very curious to see what the best is that can be achieved if the time consideration is neglected. If anyone investigates this, please publish your results on the file exchange.
Hannes