Spring 2010 MATLAB Contest, April 28 - May 5
in [Matlab]
|
Prev: Single number into vector elements
Next: neural network
From: the cyclist on 6 May 2010 10:35 Congratulations on a great victory, Hannes, and on your long-overdue grand prize win. Maybe Cobus was dragging you down before? ;-) Thanks again to the contest team. Great new machinery, and another really interesting and intuitive puzzle. Has the contest suite been made available? I am dying to see it. I had a few of my usual small time improvements that I was adding to the queue at the end, and one that I expected to be huge. The function "kippen" can be vectorized extensively (see the code below), and when I did so, the test suite ran consistently 6 seconds faster. I thought I had a real contender to leap over the parameter-tweaking noise in the end. However, when applied to the contest suite, it did absolutely nothing. It led me to believe that somehow "kippen" was not even being called any more, but that was not the case. I'm eager to see what's actually happening. the cyclist %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function aA = kippen(aA,nnr,Areas,kx,ky) n = size(aA,1); AcorrX = zeros(n); AcorrY = AcorrX ; AB = zeros(n+2); AB(2:end-1,2:end-1) = aA; ab = reshape(cumsum(AB(:)),n+2,n+2); AC = AB'; ac = reshape(cumsum(AC(:)),n+2,n+2); dx = Areas(:,5)-Areas(:,4)+1; dy = Areas(:,7)-Areas(:,6)+1; sz = dx.*dy; m = Areas(:,1) ./ sz; ac_x11_index = sub2ind([n+2,n+2],Areas(:,7)+1,Areas(:,4) ); ac_x21_index = sub2ind([n+2,n+2],Areas(:,6), Areas(:,4) ); ac_x12_index = sub2ind([n+2,n+2],Areas(:,7)+1,Areas(:,5)+2); ac_x22_index = sub2ind([n+2,n+2],Areas(:,6), Areas(:,5)+2); ab_y11_index = sub2ind([n+2,n+2],Areas(:,5)+1,Areas(:,6) ); ab_y21_index = sub2ind([n+2,n+2],Areas(:,4), Areas(:,6) ); ab_y12_index = sub2ind([n+2,n+2],Areas(:,5)+1,Areas(:,7)+2); ab_y22_index = sub2ind([n+2,n+2],Areas(:,4), Areas(:,7)+2); dm1x = m - (ac(ac_x11_index) - ac(ac_x21_index))./dy; dm2x = (ac(ac_x12_index) - ac(ac_x22_index))./dy - m; dmx = (dm1x < 0 & dm2x < 0).*max(dm1x,dm2x) + (dm1x > 0 & dm2x > 0).*min(dm1x,dm2x); dm1y = m - (ab(ab_y11_index) - ab(ab_y21_index))./dx; dm2y = (ab(ab_y12_index) - ab(ab_y22_index))./dx - m; dmy = (dm1y < 0 & dm2y < 0).*max(dm1y,dm2y) + (dm1y > 0 & dm2y > 0).*min(dm1y,dm2y); for ir = 1:nnr if dx(ir) > 1 && dmx(ir) ~= 0 x = (0:dx(ir)-1)'/(dx(ir)-1); AcorrX(Areas(ir,4):Areas(ir,5),Areas(ir,6):Areas(ir,7)) = dmx(ir)*(x - kx)*ones(1,dy(ir)); end if dy(ir) > 1 && dmy(ir) ~= 0 y = (0:dy(ir)-1)/(dy(ir)-1); AcorrY(Areas(ir,4):Areas(ir,5),Areas(ir,6):Areas(ir,7)) = ones(dx(ir),1)*dmy(ir)*(y - ky); end end aA = aA + AcorrX + AcorrY; end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From: Alan Chalker on 6 May 2010 11:17 "Hannes Naudé" <naude.jj+matlab(a)gmail.com> wrote in message <hru0tk$75i$1(a)fred.mathworks.com>... > Alan : Care to share any details of what you did? >....... > 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 ;-) ). > Hannes: Absolutely brilliant! Congrats again on your well deserved victory. While it might not have been a fundamental algorithm change, what you did clearly involved deeper thinking about what was going on and an impressive amount of gamemanship. And no disrespect taken... I know people have varying views on my approaches to the contest.. but as I've said before I like to be involved in a certain way since I can't compete with the 'algorithm experts'. But I do always abide by the explicit rules the contest team puts in place. The fact they've explicitly added a rule about test suite extraction but haven't added one about queue bombing with tweaks speaks volumes. 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. And since Hannes requested it, here's a general breakdown of what I did: In previous contests I had developed all MATLAB based code (primarily using the urlread function) to auto-submit entries, grab entries based upon their ID number, and make very crude parameter adjustments. With the changes to the website, the majority of that code was useless. The biggest issue I had to deal with obviously involved the logging in to your account in order to submit an entry. I spent hours trying to get urlread to work with the new system. However in the end I couldn't because some of the login pages utilize SSL, which urlread doesn't support. (NOTE to MathWorks.. could you please consider adding that support as a feature request? I'd love to continue to do this all in MATLAB) In the end, I ending up having to go with a command line application called CURL, which is available for a variety of platforms and is capable of supporting SSL. Thus I had to develop code to use the MATLAB system command to make calls to CURL to read and submit code. One small hurdle I struggled with was the fact that the code is submitted as a parameter, but can be thousands of characters long. Windows truncates normal command line entries well before that, so I had to write the code out to text files and then funnel the file as a parameter to CURL. Another minor issue was dealing with bad data coming back from CURL. Sometimes the webserver or network 'hiccups' and returns a malformed page. Our normal webbrowsers intelligently deal with that, but for this case I needed to scan for it and reexecute the CURL command. For most of the contest I simply had a MATLAB function that would check what the leading entry was, and if it was a new entry that wasn't my own copy it to a file. It would then use the strrep function to replace certain parameters that seemed ripe for tweaking and resubmit the code. All this would happen once per minute in order to deal with the submission limit rule. Early on I manually selected the parameters by looking closely at the code but later on I just had a set of target parameters that the code would be scanned for and then automatically adjust. As I mentioned in another post, it would do something like this for a parameter of 123: 124, 122, 125,121, 126, 120 etc etc. Thus it would slowly adjust both up and down from the parameter. For the last day of the competition, I had planned on developing code to auto create new accounts and automatically switch to the new accounts when the 10 minute limit was reached, in order to be able to 'tweak bomb' during the final rush. I spent hours and hours trying to get the autocreation code to work, but never code. There is something funky going on with the Javascript and forms for the account creation page that I couldn't figure out how to get to work with CURL. When it got to be only an hour from the contest end I gave up on that approach and just spent 15 minutes hand creating about 30 accounts. Thus at 17 minutes to go I started my code that started grabbing code from the head of the queue and resubmitting 2 -3 copies of each with small parameter changes. When necessary it would switch to a new account. I ended up submitting about 185 entries in that 17 minute window, which averages to one every 5.5 seconds. I've seen other people due that fast by hand, but only for a few entries in a row. As an aside, Hannes somewhat 'lucked out' in that he submitted his winning codes at ~22 minutes to go, and thus my resubmitter function didn't grab a copy of them (not that I'm saying a small tweak would have definitely beaten his code.. but you never know). Finally, to everyone who dismisses 'auto-code' as trivial and not within the spirit of the competition, I respectfully disagree. I've ended up with hundreds of lines of code spread out across dozens of functions that took me hours and hours to develop over the past week. Dealing with all the data handling and error conditions and whatnot requires a lot of effort. Multiple times I'd start it running and come back later to find the program errored out due to some weird occurrence I hadn't taken into account. It's a different sort of challenge from the underlying algorithm of the contest problem, but it still requires a good understanding of MATLAB and thinking through different approaches to a problem.
From: Nicholas Howe on 6 May 2010 11:47 "the cyclist" <thecyclist(a)gmail.com> wrote in message > Has the contest suite been made available? I am dying to see it. I had a few of my usual small time improvements that I was adding to the queue at the end, and one that I expected to be huge. The function "kippen" can be vectorized extensively (see the code below), and when I did so, the test suite ran consistently 6 seconds faster. I thought I had a real contender to leap over the parameter-tweaking noise in the end. I'm curious about this as well, for several reasons. My on disappointment with this contest is that I had detected a small but (on the sample test suite) significant algorithmic improvement in solver2 relating to handling the pixels on the boundary of the image. I had hoped that the effect was small enough to improve results on the true test suite without knocking it out of the optimized minimum. Unfortunately that proved not to be the case, as the solvers I applied my modification to generally did worse than the ones they were based on. (On the sample suite I could get about .2% improvement in score.) My second reason for curiosity is to see whether any images were shared between the sample and true test suites, as has sometimes been the case in the past. A strategy that had occurred to me was to detect a known image (using the sum of some set of pixels as a hash) and return that image exactly. With 65536 characters allowed, you could encode a few of the smaller images in your program. Technically this is not probing the test set; it is rather just an extreme form of overfitting via a lucky guess. I decided not to try it but am curious if it would have worked. And a comment to Alan, since you brought it up: I'm glad you enjoy your game, but it is different from the one most of the rest of us are playing, and sometimes your game disrupts ours. It's also (except when the Mathworks changes everything) the same game every year: you can reuse all your machinery in contest after contest, regardless of the problem everyone else is trying to solve. I guess from my point of view having one player pushing the system in this way keeps things interesting, but I sure hope the practice does not spread or I will cease to enjoy it!
From: Oliver Woodford on 6 May 2010 12:32 Clearly some contestants enjoy the tweaking game, while others enjoy making general algorithmic improvements. Obviously there is a balance to be had to please everyone, and an interesting question is "What is that balance?". The current format, with many different prizes, means there's definitely something for everyone. However, I feel that at the moment there are still not enough incentives for original algorithmic improvements during daylight. This could definitely be improved without removing all the thrill for tweakers. I do feel a good aim for future competitions is that the Grand Prize is won by an algorithm that works well in general, and not just on the test set. I hope the User Voice comes up with some positive suggestions that are adopted. Oliver PS Hannes and Alan, your techniques are impressive and merit kudos.
From: Hannes Naudé on 6 May 2010 13:39
"the cyclist" <thecyclist(a)gmail.com> wrote in message > Congratulations on a great victory, Hannes, and on your long-overdue grand prize win. Maybe Cobus was dragging you down before? ;-) Errm, if you'd like to know who's been dragging me down I'd refer you to the Blockbuster contest archive ;-) > Has the contest suite been made available? I am dying to see it. I had a few of my usual small time improvements that I was adding to the queue at the end, and one that I expected to be huge. The function "kippen" can be vectorized extensively (see the code below), and when I did so, the test suite ran consistently 6 seconds faster. I thought I had a real contender to leap over the parameter-tweaking noise in the end. Yip, been there. In an early contest (can't remember which one) Cobus and myself vectorized a big chunk of code and got a massive speedup. But on the contest machine it was actually slower. Had nothing to do with the testsuite, just the machines, JVM etc. Unless your OS, architecture, matlab version and especially JVM version matches, you shouldn't put too much faith in local timing results. Also, since JIT vectorization aint what it used to be. |