Welcome to MilkyWay@home

search progress visualization


Advanced search

Message boards : Number crunching : search progress visualization
Message board moderation

To post messages, you must log in.

1 · 2 · 3 · 4 · Next

AuthorMessage
ProfileTravis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
10 thousand credit badge10 year member badge
Message 11115 - Posted: 17 Feb 2009, 6:53:01 UTC
Last modified: 9 Jun 2009, 15:52:21 UTC

So I've been thinking about make things a little more interesting on your end. Dave and myself are going to be trying to get some small visualizations available (that should be updated quasi-real time) that should show how our different searches are progressing.

We'd also like to put some other (possibly interesting) information in these, like what user crunched the most accurate fit, and things of that nature, as well as having the graphs be a bit more dynamic.

So I'm starting this thread as a preliminary version, and hopefully you guys can give us some good suggestions. I'm working on a script that will generate these images automatically as something we can have running every couple minutes in the background to keep the plots up to date.

At any rate, here's what the current searches are doing:

Search Plots
ID: 11115 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileTravis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
10 thousand credit badge10 year member badge
Message 11117 - Posted: 17 Feb 2009, 7:22:35 UTC - in response to Message 11115.  
Last modified: 17 Feb 2009, 8:35:44 UTC

For a little more information about what you're looking at:

The graphs are showing the particle swarm population being updated over time (ie, the best fitness in the population, the worst fitness in the population, and the average fitness in the population).

Typical particle swarm optimization updates the jth parameter of particle i as follows:

p[i][j] = w * v[i][j] + c1 * r1 * (g[j] - p[i][j]) + c2 * r2 * (l[i][j] - p[i][j])

w, c1 and c2 are constants, typically ~1, 2.0 and 2.0. However for the milkyway application, we've found that having w around 1 doesn't converge at all, so with these searches we're trying different w values. ps_x_2 is using w = 0.4, ps_x_3 is using w = 0.6 and ps_x_4 is using w = 0.8.

r1 and r2 are numbers randomly generated between 0 and 1.

v[i][j] refers to the previous velocity of the jth parameter of particle i (how far it moved from it's last position), g[j] refers to the jth parameter of the globally best found particle, l[i][j] refers to jth parameter of the ith particles best found position.

So as the search progresses, the particles are updated by moving according to their previous velocity, but pulled towards the best found position of the search ("global" knowledge) and the particles on previously best found position ("local" knowledge).

A lot of optimization people like this approach because as you can see, it's pretty simple but offers rather good results.

What we're doing is a little different because instead of generating a population of particles and waiting for the results, we're letting the particles continue to fly around the search space, and only updating the global and local best positions when the results arrive.

Interestingly enough, so far it seems that our asynchronous particle swarm optimization is giving much better results than the newton method searches we were doing, because the newton method searches would converge to a local minima rather quickly and not be able to escape it.
ID: 11117 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Otter

Send message
Joined: 20 Jan 09
Posts: 9
Credit: 17,289,621
RAC: 0
10 million credit badge10 year member badge
Message 11120 - Posted: 17 Feb 2009, 8:14:49 UTC

Interesting stuff.

Travis wrote:
p[i][j] = w * v[i][j] + c1 * r1 * (g[j] - p[i][j]) + c2 * r2 * (l[i][j] - p[i][j])


So tell me, your equation looks similar to the SOR iterative method (but not). Is that what W is? (The relaxation constant). I have studied (introductory) iterative methods, so please be gentle ><
ID: 11120 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileTravis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
10 thousand credit badge10 year member badge
Message 11125 - Posted: 17 Feb 2009, 8:33:47 UTC - in response to Message 11120.  
Last modified: 17 Feb 2009, 8:38:18 UTC

Interesting stuff.

Travis wrote:
p[i][j] = w * v[i][j] + c1 * r1 * (g[j] - p[i][j]) + c2 * r2 * (l[i][j] - p[i][j])


So tell me, your equation looks similar to the SOR iterative method (but not). Is that what W is? (The relaxation constant). I have studied (introductory) iterative methods, so please be gentle ><


That's interesting. I've actually never heard of the SOR method, so I just looked it up ;) But just from looking, they do seem somewhat similar.

What w is doing here is putting some kind of limit on the particles velocity. If w is too high, the particle's velocity will increase over time, while if it's too low the particle's velocity will slow down over time.

Since the search space that we're looking at here isn't particularly pretty, having a high w can be nice in that it will help a particle escape a local minima by increasing it's velocity until it can jump out. However, if it's too high the particles wont ever converge to a decent value in any of the minima found (making it more or less a random search). So in that way it's rather similar to the temperature used by simulated annealing.

You can pretty much see this happening in the graphs above. The searches with a low w (ps_s79_2, ps_s82_2 and ps_s86_2) are converging rather quickly, while the other searches are keeping a wider populuation, meaning they're searching a larger area and not converging as quickly.

Basically the tradeoff is with a low w you can converge to a solution really quickly, however you run a much higher risk of the solution being a local minima instead of the globally best point.
ID: 11125 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Otter

Send message
Joined: 20 Jan 09
Posts: 9
Credit: 17,289,621
RAC: 0
10 million credit badge10 year member badge
Message 11128 - Posted: 17 Feb 2009, 9:24:23 UTC

Fun stuff!

SOR is just an optimal Gauss-Seidel method, which is just an optimized Jacobi method. I'll be honest, I have almost no idea what you are talking about, but I think I get the big picture. But when you say convergence - what the particles converging to? Also in the big picture how does this relate to images of the galaxy?
ID: 11128 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileTravis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
10 thousand credit badge10 year member badge
Message 11129 - Posted: 17 Feb 2009, 9:29:50 UTC - in response to Message 11128.  
Last modified: 17 Feb 2009, 9:34:44 UTC

Fun stuff!

SOR is just an optimal Gauss-Seidel method, which is just an optimized Jacobi method. I'll be honest, I have almost no idea what you are talking about, but I think I get the big picture. But when you say convergence - what the particles converging to? Also in the big picture how does this relate to images of the galaxy?


The particles are trying to find the optimum fit of a cylinder to the sagittarius stream in the milkyway galaxy in the corresponding stripe of the sky. The parameters to our search basically define things like the size and shape of the cylinder, it's density and other information about how the background stars (the stars not in the stream) are distributed. The stripes are thin enough that we can get away with using a cylinder :P

Once we have a accurate fits of these cylinders across multiple stripes we can fit them together to get an image of the sagittarius stream.


*edit* So basically, each particle is a set of parameters, and we use these different particles to generate new sets of parameters to try and find one that gives the best fit to the data.
ID: 11129 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileDaniel

Send message
Joined: 25 Nov 07
Posts: 25
Credit: 54,173,252
RAC: 0
50 million credit badge10 year member badge
Message 11171 - Posted: 17 Feb 2009, 15:59:28 UTC

I think that is the most thorough explanation of a project I've ever read. Thank you Travis, I knew there was a reason this is my favorite project.
ID: 11171 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileTravis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
10 thousand credit badge10 year member badge
Message 11397 - Posted: 18 Feb 2009, 12:21:45 UTC - in response to Message 11171.  

I saw some interesting things in the last set of searches, so I started up a new batch. Each of these have a w = 0.8 so they're rather exploratory.

In one of the s79 searches we found a point point that was a bit higher than we've seen before so we'd like to see if we could find it again (to verify our stuff isn't going crazy).

Also, I noticed there was a bit of a problem with the optimization over a few of the parameters (which are in radians so they don't have bounds), so I made a few code changes to helpfully make that situation a bit better -- capping out the velocity of those parameters at PI or -PI, and having the parameters wrap around.
ID: 11397 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Otter

Send message
Joined: 20 Jan 09
Posts: 9
Credit: 17,289,621
RAC: 0
10 million credit badge10 year member badge
Message 11468 - Posted: 18 Feb 2009, 18:10:22 UTC

Bump, I would highly recommend you keep the little blurb about this thread on the main page. It is definitely more interesting than credit/code changes!
ID: 11468 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileDoctorNow
Avatar

Send message
Joined: 28 Aug 07
Posts: 146
Credit: 10,276,862
RAC: 0
10 million credit badge10 year member badge
Message 11479 - Posted: 18 Feb 2009, 19:03:42 UTC
Last modified: 18 Feb 2009, 19:12:07 UTC

Hehe, seems I misunderstood the news about that a bit.
I thought visualization in real-time would be a screensaver. ;-D
Now I see the diagrams in the first post are regularly updated, that's pretty cool also. :-)
I know there was another (rather old) thread asking the same, but how about a screensaver anyway, is it possible?
Member of BOINC@Heidelberg and ATA!

My BOINCstats
ID: 11479 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileTravis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
10 thousand credit badge10 year member badge
Message 11494 - Posted: 18 Feb 2009, 19:42:46 UTC - in response to Message 11479.  

Hehe, seems I misunderstood the news about that a bit.
I thought visualization in real-time would be a screensaver. ;-D
Now I see the diagrams in the first post are regularly updated, that's pretty cool also. :-)
I know there was another (rather old) thread asking the same, but how about a screensaver anyway, is it possible?


Well, I don't know about a screen saver because what we're doing on the individual processors isn't particularly interesting... it's much more interesting when you put it all together as a whole.

What we have in this post is pretty much preliminary work, so we'd really like to hear your ideas and suggestions as to what you'd like to know is going on server-side, and what we're doing as a whole.

Right now we would like to get these graphs (and some other ones) automatically generated in their own webpage, with information like what users have given us the best fitness and things like that.

Pretty much we could have whatever information you guys think would be interesting, and we'll also have things we're interested about and looking into on their for our own benefit.

Basically, we'd like a webpage we could check to easily know the status of our different searches, and I thought it would be more interesting with some user input, so we could make that information more interesting to you guys, and also add things you'd be interested in as crunchers.
ID: 11494 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Otter

Send message
Joined: 20 Jan 09
Posts: 9
Credit: 17,289,621
RAC: 0
10 million credit badge10 year member badge
Message 11557 - Posted: 19 Feb 2009, 2:19:50 UTC
Last modified: 19 Feb 2009, 2:21:37 UTC

I'd like to know the definition of fitness.

Also when you say the particles are 'swarming' - how do stars swarm? Or better - what are particles? My naive thoughts are - I look at the sky from time to time, and (from my perspective), those stars move reallllly slowly. So if you are looking at telescopic imagery, how are you getting motion?

Edit- I am being naive on purpose, as people that crunch aren't necessarily astrophysicists, so simple things are undefined to them, the galaxy just boils down to stars and space, and they may have little knowledge of anything more!
ID: 11557 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfilePaul D. Buck

Send message
Joined: 12 Apr 08
Posts: 621
Credit: 161,934,067
RAC: 0
100 million credit badge10 year member badge
Message 11580 - Posted: 19 Feb 2009, 6:40:47 UTC - in response to Message 11494.  

Well, I don't know about a screen saver because what we're doing on the individual processors isn't particularly interesting... it's much more interesting when you put it all together as a whole.


The screen saver does not have to be "perfectly" real if that is not possible. LHC for example has this "swarm" display (I think the UBW has an image of it) which is nonsesnse with the exception of the turn counter which is accurate.

It is just a thought to consider, to make the application more "real" to those that like the graphics ...

Priority wise I would put it below the change to the client to detect ATI cards and the OpenCL application (conserve resources, make the one additional application instead of four) ...
ID: 11580 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Misfit
Avatar

Send message
Joined: 27 Aug 07
Posts: 915
Credit: 1,503,319
RAC: 0
1 million credit badge10 year member badge
Message 11581 - Posted: 19 Feb 2009, 6:42:54 UTC - in response to Message 11494.  

Screensavers won't be a part of a fully optimized app anyway. So you'll need to determine what percentage use the stock app and prioritize accordingly.
me@rescam.org
ID: 11581 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileTravis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
10 thousand credit badge10 year member badge
Message 11587 - Posted: 19 Feb 2009, 9:17:51 UTC - in response to Message 11557.  

I'd like to know the definition of fitness.


The astronomy application does a maximum likelihood fit of the stars in a stripe to a model of star stream(s) and the background stars.

Also when you say the particles are 'swarming' - how do stars swarm? Or better - what are particles? My naive thoughts are - I look at the sky from time to time, and (from my perspective), those stars move reallllly slowly. So if you are looking at telescopic imagery, how are you getting motion?


It's basically just terminology that the particular search uses. In essence each particle is a set of parameters that gets updated over time. The particles continue to move in their previous direction in the search space, but are also pulled to their own previous best found position, and the best found position by the entire swarm.

Basically, we have some function:

fitness = f(parameters)

and we want to find parameters that give us the best fitness. What each of our applications is doing is calculating that function f with a different set of parameters.

The higher the fitness is, the higher the likelihood of those set of parameters being the most accurate fit of the model to the data.

Edit- I am being naive on purpose, as people that crunch aren't necessarily astrophysicists, so simple things are undefined to them, the galaxy just boils down to stars and space, and they may have little knowledge of anything more!


That's good! Part of the point of this thread is to try and accurately describe what we're doing to all our crunchers, so if you guys have any questions please feel free to fire away :)
ID: 11587 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileTravis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
10 thousand credit badge10 year member badge
Message 11588 - Posted: 19 Feb 2009, 9:20:27 UTC - in response to Message 11580.  

Well, I don't know about a screen saver because what we're doing on the individual processors isn't particularly interesting... it's much more interesting when you put it all together as a whole.


The screen saver does not have to be "perfectly" real if that is not possible. LHC for example has this "swarm" display (I think the UBW has an image of it) which is nonsesnse with the exception of the turn counter which is accurate.

It is just a thought to consider, to make the application more "real" to those that like the graphics ...

Priority wise I would put it below the change to the client to detect ATI cards and the OpenCL application (conserve resources, make the one additional application instead of four) ...


Whenever we're looking for a new undergrad to work with us, usually one of the first things we throw out there is "you could make a screen saver for our application." And usually they want to do something else :P

We have kind of a tight ship right here, so the real issue is finding someone with the knowledge and desire to make one. Personally, I have no experience doing any kind of graphical design, so I think my skills are best used elsewhere... reducing credit and things of that nature :D
ID: 11588 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileTravis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
10 thousand credit badge10 year member badge
Message 11590 - Posted: 19 Feb 2009, 9:22:16 UTC - in response to Message 11581.  

Screensavers won't be a part of a fully optimized app anyway. So you'll need to determine what percentage use the stock app and prioritize accordingly.


I want so say maybe 90% or more of the WUs returned aren't from a stock app :P

... it might actually be interesting to count what WUs are generated from what applications and make that information available for you guys. Would let whoever compiled whichever application strut their stuff a bit. :)
ID: 11590 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileGlenn Rogers
Avatar

Send message
Joined: 4 Jul 08
Posts: 165
Credit: 364,966
RAC: 0
100 thousand credit badge10 year member badge
Message 11592 - Posted: 19 Feb 2009, 9:27:08 UTC - in response to Message 11590.  

Isnt that interesting Hmmm!! So so the results from these are good one would presume??
ID: 11592 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileTravis
Volunteer moderator
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 30 Aug 07
Posts: 2046
Credit: 26,480
RAC: 0
10 thousand credit badge10 year member badge
Message 11595 - Posted: 19 Feb 2009, 9:40:52 UTC - in response to Message 11592.  

Isnt that interesting Hmmm!! So so the results from these are good one would presume??


So far so good, every now and then we're having a little trouble with the outlier detection (which is why you see the best fitness go up, then back down), but the results we're getting using particle swarm for stripes 20, 21, 79, 82 and 86 are comparable (or better!) than what we've gotten doing more traditional searches (conjugate gradient descent) on the bluegene at RPI.

We don't have any information about the values that stripes 22 and 23 should come out to... these are entirely new and we don't have any results for them. So you guys are really doing new astronomy with those two :)
ID: 11595 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
ProfileGlenn Rogers
Avatar

Send message
Joined: 4 Jul 08
Posts: 165
Credit: 364,966
RAC: 0
100 thousand credit badge10 year member badge
Message 11596 - Posted: 19 Feb 2009, 9:44:15 UTC - in response to Message 11595.  
Last modified: 19 Feb 2009, 9:47:35 UTC

Im about 50% through s23 now have to see how it reports..

EDIT: heres one i found...
Task ID 5603831
Name ps_s23_9_179749_1235009280_0
Workunit 5428244
Created 19 Feb 2009 2:08:04 UTC
Sent 19 Feb 2009 2:09:27 UTC
Received 19 Feb 2009 7:15:03 UTC
Server state Over
Outcome Success
Client state Done
Exit status 0 (0x0)
Computer ID 21898
Report deadline 22 Feb 2009 2:09:27 UTC
CPU time 1491.703
stderr out <core_client_version>6.4.5</core_client_version>
<![CDATA[
<stderr_txt>
Running Milkyway@home version 0.19 by Gipsel
CPU: Genuine Intel(R) CPU T2300 @ 1.66GHz (2 cores/threads) 1.66678 GHz (889ms)

WU completed. It took 1491.7 seconds CPU time and 1510.59 seconds wall clock time @ 1.66678 GHz.

</stderr_txt>
]]>

Validate state Valid
Claimed credit 4.06538192328865
Granted credit 12.732925
application version 0.19
ID: 11596 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
1 · 2 · 3 · 4 · Next

Message boards : Number crunching : search progress visualization

©2019 Astroinformatics Group