Spring 2010 MATLAB Contest, April 28 - May 5
in [Matlab]
|
Prev: Single number into vector elements
Next: neural network
From: Hannes Naudé on 7 May 2010 03:02 Yi:”Thanks for sharing this great idea. By revising your 20 'Random Randomness' entries, I got the same loopup table your implemented in your winning code and the predicted result is exactly the same as the actual one show on the website. However, onething still puzzels me: in two solvers, you used two independent rand calls to determined the corresponding column of lookup table. In theory, these two calls should give two different columns, shouldn't they? If so, the above calculation cannot be right, can it?" Glad to hear someone took up the challenge to reverse engineer the code. I'm not 100% sure that I understand your question correctly, but I'll try to answer anyway. As I understand, you problem is with the fact that there are two independent calls to rand(1). One is in solver1 and the other in solver2. But only one of these solvers will get called for each problem, so for any given problem the existence of the other lookup table will be irrelevant. The calls don't give different columns because only one of them gets called. If you wanted to go all out, you could fix the solver to always call solver1 and use these results to optimize the lookup table there. Then fix the solver to always call solver2 and optimize the lookup table there independently. Then use a third lookup table to determine which solver gets called. I chose not to go this route in order to keep a low profile by using a small number of probes. Cheers H
From: srach on 7 May 2010 03:07 > Having coded an autosubmitter that is nowhere near as sophisticated as yours, I fully agree that what you did is not trivial. But it IS disruptive and it DOES change the nature of the game. And most of us agree that it changes the nature of the game for the worst. I think that it is not the autosubmitter per se that is frustrating, but an autosubmitter that continuously scans the highscore and starts submitting when another entry takes the lead. Such kind of code does not need humans anymore once it is created. Personally, I think the "big" prizes of the matlab contests are the darkness and twilight awards and I have the deepest respect for all those people who have won these before. And although these are contest phase I am terribly bad in, I like them the most and I would really be happy if twilight would last a bit longer. However, I also like daylight, because that is the phase where I could learn the most, but often the tweaking drags away my attention from trying to understand the algorithms to playing with the profiler. Therefore I would love to have another phase after twilight, something like a "reverse twilight" where you can see the code of entries, but not the score. (only the code and score of entries scored in darkness and twilight are visible, but nothing of entries submitted in "reverse twilight". This would allow for studying the code of others, adopting and combining ideas, learning and probing, without tweaking. Especially I think that this would lead to an overall improvement of the algorithms and probably more diversity of algorithms, hence, more to learn. Regards Stefan
From: Hannes Naudé on 7 May 2010 04:51 Alan:"My understanding of the origin of that rule is that in the past there were certain players who would in the middle of the contest repeatedly submit hundreds and hundreds of the same code just for the sake of wrecking havoc on the overall contest. This would cause hours long backups in the middle of the contest and usually required the MathWorks staff to manually remove the entries from the queue. Note that a long-standing tradition is that the queue gets overwhelmed in the last 20 minutes of the contest, but that's ok because it doesn't prevent anyone from getting feedback from entries or anything. " The intentions of previous queue spammers are not and can not be known. Personally I think it much more likely that the incident you refer to was caused by an buggy autosubmitter than by malicious intent. In any case it is not relevant, since the rules do not refer to intentions. They state clearly and simply : "...we ask that you not overwhelm the queue. " and (allthough technically this is from the blog not the rules): "Max 10 submits per player in 10 minutes: This is another request from the community do minimize the queue flooding ESPECIALLY TOWARDS THE END OF THE CONTEST" (Caps are my own) So, no. It is not "ok" to intentionally delay the queue nor is it "ok" to flood the queue at the end. Alan:"What I did was essentially delay the queue by ~30 minutes (10 entries * 3 mins per entry). I see the viewpoint of some that this might be 'overwhelming the queue', but in my opinion it's not since it's no more of a delay than is often present at many other times in the contest." Correction. You submitted 20 queue delaying entries causing a delay of an hour. As a percentage of the 24 hour Longevity period that's pretty significant. And the argument that its acceptable since it is no more of a delay than is present at other times is circular and disingenious. It also implies that delays of up to 8 hours are acceptable since that is how long we had to wait for the queue to finish at the end of daylight. Alan: "The MathWorks doesn't expend staff time and resources just to let people see who's a better problem-solver. They run this to build excitement about using MATLAB and perhaps expose users to capabilities and techniques they normally wouldn't see in their everyday usage. Interfacing to a web server is one of those items in my viewpoint." Silly argument, given that we have agreed publicly that if you want to interface to a web server sporting SSL and cookies then Matlab is not the right tool for the job. Alan:"I'm glad to see that for the past several contests code obfuscation hasn't reared it's ugly head, nor has the 'hacking' that used to completely crash the contest machine." Not so sure of that on two counts. Firstly the simplest form of hacker attack on a server is a denial-of-service attack. It's clear that we had several of these during the contest. Secondly, at some point someone defaced Oliver's solver giving us variable names like lllli to replace blockSize. I'm not sure what that is if not obfuscation. It obviously never bothered any of the leaders enough for them to remove it from the code since it survived all the way to the winning entry. But it does present a significant barrier to entry for novices. > Hannes: "In previous contests I developed a mechanism for copy protection that would harm performance (typically by dropping out of the local minimum) if the code was edited or even if it was resubmitted identically. " > Alan:"This is another brilliant idea Hannes, but is completely going against the spirit and letter of the rules: "any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and copy any entry in the queue. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries. " Sorry, I don't understand your problem. Could a copy protected entry be viewed? Check. Edited? Check. Resubmitted? Check. Can people examine it and optimize it? Check. Any significant optimization would still improve the score. It's just the miniscule parameter tweaks that would most likely cause more harm then benefit. And the same can be said of any entry that is overfitted to a great enough extent. In any case this is a moot discussion as I never used this trick and will now most likely never get the opportunity. So I consider it acceptable and will not comment further on this topic. Alan:"Why do more than 2/3rds of people just submit a couple times instead of being involved more? I propose it's because they quickly find they are overwhelmed or unable to come even close to the expert players. How many of those even come back to subsequent contests? " Per Rutquist submitted a single entry. Mike Bindschadler submitted 2. Cobus Potgieter and Ander Skjal both submitted 3. These are just the names that leapt out at me. I'm sure I missed a few. I don't think these guys were overwhelmed by anything. I just think that many players expert and novice alike are so disilusioned with daylight that they no longer play beyond the end of twilight. I know that both Cobus Potgieter and Gerbert Myburgh fall in this category. I agree that we should try to make the contest more acessible to novices and a "best rookie" prize would be a great place to start. I don't see how massively overfitted solutions driven by bots do anything to make the contest more accesible to anyone. Incidentally, don't get me wrong, I have nothing against daylight per se. When I started playing the contest EVERYTHING was in daylight. I absolutely loved being part of the hectic groupmind superorganism that spontaneously emerged and I learnt an incredible amount from guys like Stijn Helsen, Paulo Uribe, Christian Ylamaki etc. This got me hooked, but somehow the contest experience seems to have changed and today, you'd be hard pressed to really learn anything by investigating what the current leader changed to "improve" the code. In those days we used to moan about small time tweaks taking the lead. Oh, how I yearn for time tweaks. Alan:"We are all very vocal about our opinions, but we represent only a small fraction of the playerbase. Most people are casual players and I suspect the contest team is looking for ways to better involve them and cater to them. They've repeatedly shown in the past that if they feel the goals of the contest are being compromised by a technique or player that they will change the rules or call them out on it. I've yet to hear a negative comment from any of them regarding my involvement. " Please don't take anything I write as a negative comment regarding your involvement. You are probably the most involved player in the entire contest and make great contributions contest after contest. If you were no longer involved it would be a great loss to this community. I'm merely suggesting that some of your techniques are extremely disruptive and need to be toned down or abandoned. I know that you will respect a ban on any given technique imposed by TMW, but I've also seen from past contests that the contest team don't lightly make changes to the rules. Rather a rule is only changed if there is overwhelming community support. The fact that you are quite vocal on this forum make this seem like a balanced argument, when in fact it is not. I doubt that there is more than 2 or 3 players in this entire contest who believe that auto submitters and sock puppet accounts are beneficial, or even benign. The rest of us are pretty unanimously against them.
From: Jan on 7 May 2010 05:13 "Alan Chalker" <alancNOSPAM(a)osc.edu> wrote in message .... > As a general comment to everyone asking for various changes to put the focus more on the algorithm development side of things, I'd like to point out that that would have the effect of reducing the overall number of participants in the contest. Most of the user community who could potentially be involved doesn't have the time or skill set to dive into the literature and try to develop new algorithms. There is a need for that obviously, but if the overall purpose of the contest is to increase awareness and excitement about using MATLAB, then making the contest as accessible as possible to anybody is vital. Allowing tweaking is one way of doing that. .... I don't think it decreases the number of participants. For me it was rather frustrating to see that a general approach cannot come below rank 2000 in the final submission list. Overfitting is not so interesting for me (although I did take a small part in the game because everybody seemed to do it - wanted actually to change the algorithm instead of tweaking the parameters which was not effective), so I am more interested in the twilight phase and it seemed like many other people were mainly active on twilight. However, I really don't mind the tweaking attempts. Hannes actually showed how much thought can be behind such things. :) But I would also love to see what was the best general approach. So, inspired by Alans description I will try to run all passed algorithms over the weekend on the testset (3000-4000 entries times ~1 minute makes 2-3 days running time) using urlopen and some hand crafted matlab script. Then make a plot comparing old and new rank. The region where the data is diagonal will probably depict development of generalized algorithms (since people optimized for the validation set), the region where it will be scattered is the tweaking region. Or maybe there isn't such a region? With colorcoding for submission date, this will be nice, I am sure. Using other test-sets with relatively large/small number of queries per area will also be interesting, but is optional. And for the flooding of the score list, why not restricting the number of entries to the 10 best entries per player. It's just demotivating to not come below 2000 without taking part in the tweaking game. Regards, Jan
From: Hannes Naudé on 7 May 2010 06:09
@Alan: I just thought of a great way in which your bot could be productively used in future contests. The fact that the new interface allows us to leave comments on other submissions implies that one could create a cleanup bot that would automatically post as a comment on a submission, an autocleaned version of that submission. Autocleaning could include: 1) Tagging entries that differ significantly (as measured by matlab's codediff) from the current leader (comments are searchable so one could then easily isolate all submissions belonging to a specific family). 2) Crediting lines of code to their creators. 3) Keeping comments associated with specific code segments in place (if the associated segment has not changed). Obviously someone will have to manually define what comments are associated with what segments. Allthough if you define a protocol that your bot understands along the lines of: %COMMENT identifier %This segment waste time %STARTCODE identifier for x=1:1e6 y=y+1; end %ENDCODE identifier Then all willing participants could comment segments, and any time that that segment appears the bot would automatically comment it in the annotated code resulting in a segment that displays as: %thecyclist : This segment waste time for x=1:1e6 y=y+1; end This would turn the commenting of the leading entry into more of a collaborative effort. 4) Deobfuscation. This will require some careful thought, but is also possible. The complexity required will depend on the level of determination of the obfuscator. Light obfuscation (like we had in this contest) can easily be removed (perhaps with a user supported text translation protocol like for the commenst), while heavy Dr. Seuss style obfuscation would require a bit more effort. One way would be to diff the code after all alphanumerical characters were removed. This uses characters like + [ ] ; etc as tokens. If you could line up the tokens appropriately, you could deduce which string repacements were made to obfuscate the code and undo it automatically. I am sure there is alot more that could be done. I also realise that what I am describing here is a significant task. But luckily the tasks described above are largely independent and we could easily split this up over a number of volunteers. If your code could handle the scraping of entries from the queue (this you can allready do), provide the data to our modules in a known format and then do the placing of the comment when we return results (this you would have to add, but it should be fairly simple?), that would be a fantastic addition to the contest, don't you think? |