Discussion Forums

Automatic detection and classification of "Squiggles"

22 replies [Last post]
JayZee99
Offline
Joined: 2011-03-29
Posts: 3

Hello!  At about this time last year, one of the problems posted to  the Google Summer of Code  was to come up with a way to automatically detect the “squiggle” signals. The problem was described in this page:

http://setiquest.org/wiki/index.php/Enhancement_of_Algorithm_to_Detect_P...

I was wondering if any progress has been made in that area since then.
 
Are squiggles still a false alarm problem?  Would an automated detector/classifier benefit the search?
 
Thank you,

- jz

Dave Robinson
Dave Robinson's picture
Offline
Joined: 2010-04-29
Posts: 196
Low energy state

Sigblips has labelled the state that SETI Quest is in as a Low energy state; the only way that anyone can assist the search for E.T. is go and label some straight lines at SETI Live, there is no interest at all in following up any advanced algorithms developed by any real Citizen scientists. As far as I can see SETI Quest is dead - more a zero energy state than a low energy state. It might even be degenerate, with the electrons crushed into the nucleus by the pressure of group apathy and lack of time/interest from the SETI Institute staff. As far as I know, the existing data sets are still available for download, so if you want to do the work for your own interest fine - but just don't expect any help, appreciation or recognition from anyone at the quest. A sad state for such a great idea.

Regards

Dave Robinson

robackrman
Offline
Joined: 2010-04-15
Posts: 235
setiQuest fail

setiQuest is a failure because it did not open source the search for ET signals as originally stated. Its main achievement was to release the source code for SonATA for which there is little community interest. There are a number of reasons I attribute towards the failure of setiQuest of which I will site two:
 
- Avinash was a poser (with shocking gaps in knowledge of information technology given things stated in his resume) who mostly ignored internal and external suggestions and advice
- Jill thought of open source contributors as “free (unpaid) workers” that she could control and treat like her own staff. She only found one person like that.

 

In various places in this forum you will see jrseti comment that there are not enough internal staff to support setiQuest. This demonstrates once again how little internal understanding there is at the SETI Instute for how successful open source projects work. There are a number of very talented people that would have contributed towards the maintenance and growth of setiQuest if the proper framework had been established. A few tried under the environment that existed, but were forced to give up.

People are not interested in SonATA because it too large and cumbersome to run on typical home computers and there is no method by which to experiment (e.g., live data and telescope control). Also, I suspect that many people intuitively suspect that ET does not allocated a huge power budget to an information-less narrow-band signal (Doppler shifted <= 1Hz line in Fourier space). Yes, I have read the relevant books and articles and understand the reasons given for looking for this type of signal, but the arguments are made by people trapped in the context of our current technological abilities. If radio signals are the preferred method of communication, where will be our ability to search the dimensions of received electromagnetic space be in say 100 years given the current exponential grown in classical computers and the beginning of success in constructing quantum computers? If there is a similar evolution in computing for other civilizations might not ET choose to make some SNR trade-offs, if necessary, to send their version of pictures, videos, music, and other information about their technology and culture knowing that receiving civilization would have sophisticated methods and vast computing power to tease the signals out of the noise? At our current level of development (i.e., small ground-based telescopes and limited processing power) , I suspect we need to be lucky enough to be very close to one of these transmitters and to stumble upon the method of modulation.

The best teachers, when observing a student taking a path that is “known” by established principles will lead to failure, will not interfere, knowing that the journey is a learning process which occasionally leads to new discoveries and ideas. The same care should have been applied to setiQuest contributors. They should have been given the ability to freely experiment within the constraints of available telescope time and computing resources allocated to setiQuest. Who know what interesting tools might have been developed and what natural or artificial phenomena may have been discovered?
 

a_feder
Offline
Joined: 2011-10-09
Posts: 34
Going out on a limb

Going out on a limb here, is the Fourier space actually "privileged" in any way in relation to radio communications, other than by anthropogenic tradition? Would it not be possible to apply some other transform (e.g. the Laplace transform) to a time series from the ATA and would that not yield a significantly different result than a Fourier transform (I assume it would). And if so, is there any reason at all to believe that an alien civilization would "prefer" the Fourier space in any way over this other space?

I have trouble imagining how the advantages that are cited for narrowband carrier-like signals in Fourier space (durability, low power cost, ease of detection) would not apply in any other such space.

robackrman
Offline
Joined: 2010-04-15
Posts: 235
Re: Going out on a limb

The Fourier Transform maximizes the signal-to-noise when detecting sine waves because its analytic basis functions (which are multiplied against the signal) are themselves sine waves.

You mention the Laplace Transform. A discrete version of the Laplace Transform would maximize the detection of the electromagnetic equivalent of striking a gong (a exponentially decaying sine-wave).

The best method of detecting a GPS satellite is to de-spread the received time-series by multiplying it against the proper (for a particular satellite) Gold code sequence.

An interesting mathematician and statistician, David Messerschmitt (Berkeley Prof?) who spent some time at the SETI Institute, suggested that ET might send information-rich wide-band signals that would be maximally detected by correlating them somehow against an important transcendental number such as pi or e.

So why are many SETI researchers so enamored with the idea that ET would sent a narrow-band sine-wave? It is because a narrow-band sine-wave (actually to be more specific a circularly-polarized narrow-band sine wave) is unaffected in terms of its detection by dispersion and polarization rotation due to effects of the vast interstellar medium. There is a bit of frequency spreading due to multi-path and a lag effect due to ions “sloshing back-and-forth” in the oscillating electromagnetic field which is why most searches do not integrate deeper than about 1Hz.

A secondary consideration, of which I feel would have no influence on the decision making of an advanced transmitting ET civilization, is that the Fourier transform has small log(n) computational time-complexity. Many other detection algorithms have n^2, n^3, and even larger time-complexity (for classical computers and algorithms as we understand them now. The Fourier transform switched from n^2 to log(n) complexity in the 1960s due to a very significant mathematical advancement).

When posed with the question of why ET would send a signal containing no information (would we do that?), SETI researchers counter with the idea that associated with the narrow-band “beacon” signal there would be in the same location a weaker wide-band information bearing signal that a larger telescope might have to be constructed to detect. I and some others – and the dividing line is often generational – believe that much of the power would go into carrying information even at the cost, if necessary, of detection signal-to-noise ratio. And that the information carrying signal would also be the “beacon” signal. And that significant computing power for implementing advanced multi-dimensional search algorithms would be the minimum requirement to join the club. At our current level of development, we will have to work hard and be lucky to find a signal.

I spend some time while at the SETI Institute, and after leaving the SETI Institute, searching for pulses having negative dispersion: pulses purposely emitted by ET with dispersion opposite than that caused by nature. The idea is that receiving civilizations would know about dispersion due to their discovery of pulsars, but that pulses with negative dispersion (low component frequencies arriving first) would be surprising because (as far as we know) they are not produced by nature. It would be possible to encode information by changing the degree of artificial negative dispersion.

It is an interesting fact that radio (and optical) photons have a mode, orbital momentum, for which no significant telescope has been constructed to detect (search the Internet for “twisted light” or POAM which stands for photon orbital angular momentum). Some rudimentary transmission and reception demonstration have been done. The best telescope would have a large extent, with receiving elements spread across the Earth (or ideally in space), but would be difficult to calibrate.

a_feder
Offline
Joined: 2011-10-09
Posts: 34
Thanks! If we imagine that

Thanks! If we imagine that the ET was, for some reason, oriented towards the Laplace transform in the same way we are oriented towards the Fourier transform (that is, if they considered the Laplace transform the holy grail of radio communications), would it then not be possible for them to pick a signal which, in Laplace space, would be virtually unaffected by passage through the interstellar medium? (Perhaps the "gong" signal would be such a signal?) I'm struggling to understand why any physical process in the ISM would be biased towards a transform which some French guy happened upon while trying to solve the heat equation, rather than any other transform.

Dave Robinson
Dave Robinson's picture
Offline
Joined: 2010-04-29
Posts: 196
Doing poor old Fourier an injustice

Hi Anders

"I'm struggling to understand why any physical process in the ISM would be biased towards a transform which some French guy happened upon while trying to solve the heat equation, rather than any other transform."

Methinks that you are doing poor old Fourier an slight injustice here. There certainly are many interesting astronomical features that the Frenchman can process to great advantage. For example any repetitive signal, irrespective of the actual pulse shape generates a sparse spectrum where all of the information from the signal gets 'compressed' into a series of spikes whose spacing is exactly the repeat period of the signal. So although it is not as effective a method of removing the noise as would be found on a pure sinewave, the effect is still very useful; as you know there are astronomical phenomena such as Pulsars that have this characteristic; and would it be too surprising if E.T. repeats his message on a regular basis?even if E.T. does send real information as Rob suggests, if he repeats it regularly then Fourier might still help extract it.

In Signal Processing the Fast Fourier Transform has proved to be an indispensible tool, it is my opinion (which isn't shared by Sigblips) that had not Cooley and Tukey discovered this shortcut. DSP wouldn't be where it is today - if it existed at all.

Yes there are other transformations, and as some of my notes have indicated, I really feel that the Wavelet transform has a great deal to offer SETI, and have demonstrated some possible applications; however even here one of the most effective ways of doing a Wavelet transform is using the Fourier Transform as a mathematical short cut. A Convolution, which is an n^2 operation maps to a multiplication after Fourier Transforming the data which makes this a nlog(n) calculation.

It is good to see both you and Rob back on the site again, I have missed you both.

Regards

Dave Robinson

a_feder
Offline
Joined: 2011-10-09
Posts: 34
Fourier was a great chap, yet only human

Hi Dave. I'm not really disputing that the Fourier transform has applications to us - I'm just not sure how the idea has come about that any species would necessarily favor it over other transformations... we like things that repeat with a fixed period, but what if ET doesn't?

robackrman
Offline
Joined: 2010-04-15
Posts: 235
These sorts of discussions

These sorts of discussions are interesting.  I remember Carl Sagan in the Cosmos series speculating that if an intelligence were to evolve in a different environment than us, say in a gas cloud rather than on land, they would probably develop science in a different direction, not attaching importance to models we have adopted, such as rectilinear coordinates.

sigblips
sigblips's picture
Offline
Joined: 2010-04-20
Posts: 733
Hello Dave, "In Signal

Hello Dave,

"In Signal Processing the Fast Fourier Transform has proved to be an indispensible tool, it is my opinion (which isn't shared by Sigblips) that had not Cooley and Tukey discovered this shortcut. DSP wouldn't be where it is today - if it existed at all."

Did I really say that someplace? As the author of the world's most sophisticated signal analysis tool I'm the first to sing the praises of the FFT. (:
 
Obviously frequency domain manipulations would not be as feasible without the FFT's O(n log n) efficiency but that wouldn't spell the end of DSP.  What I probably meant was that there is a lot more to DSP than just the FFT and that the FFT isn't always the best tool for solving a problem.

robackrman
Offline
Joined: 2010-04-15
Posts: 235
Another argument, I did not

Another argument, I did not explicitly state, given by SETI researchers for ET sending a narrow-band tone in addition to the fact that its detectability is unchanged by ISM dispersion and polarization rotation is that it has a very high signal-to-noise ratio because after the Fourier transform all signal power is contained in one output channel whereas the noise power has been divided and spread evenly in all output channels.

If the narrow-band tone, which I will now call the "carrier," is modulated with information,  say enough modulation to spread the signal over 16 output channels, the signal-to-noise ratio (ability to detect the signal) will drop by one fourth (the square root of the number of channels) because the total additive signal power across the channels will be the same but the number of channels of noise power will have increased.

You are correct that other signal types and matching transforms could be used. As long as the transform basis functions are orthogonal and the input signal matches one of the basis functions the same isolation of signal to background noise would occur, but the signal would be spread in frequency because it is not a sine wave so it would be subject to ISM dispersion, which would cause a transmit-receive channel mismatch. So extra work would be necessary to remove dispersion.

Regardless, modulation required to encode information is unpredictable, which causes a mismatch between signal and transform analysis vectors, which results in more background noise (reduced detectability).

If electromagnetic radiation is the preferred method of communication, I believe aliens *do* send information in the primary signal (don't send a tone) and that they expect us to have telescopes with significantly greater effective area. Telescopes that would be a major feature if Earth were viewed from space. We will have to be lucky to find a nearby signal at our current level of sensitivity.

a_feder
Offline
Joined: 2011-10-09
Posts: 34
Obedient plasma

I see. So it is some property (I don't know which one) of the interstellar plasma which causes the velocity of all waves of the same frequency to be shifted by the exact same amount, every time. I suppose I'd have to delve into quantum mechanics or something equally inaccessible to understand why the plasma's behavior is so consistent with respect to frequency/wavelength.

Dave Robinson
Dave Robinson's picture
Offline
Joined: 2010-04-29
Posts: 196
Just an odd thought

Hi Rob

You provide a thought provoking note. I started to think if I was in charge of setting up an interstellar beacon system what I might be tempted to do. I thought the following system might just work.

1) You set up 2 beacons, not just the one. The first would transmit a 'carrier' tone of exactly Pi * the Hydrogen line frequency, the second would transmit another 'carrier' that would be 'e' * the Hydrogen Line, so any alien intercepting the signal, even if all they were equipped with is E.T. SETI Live, would recognize that the probability of there being 2 lines relatively close together in frequency both defining what I think will be universally recognized mathematical constants from the same source by natural causes would be very low indeed. ( I remember reading about this concept of the PiHy line somewhere recently, but alas a senior moment, I can't recall who to give the credit to)

2) Knowing something about the noise background, I would amplitude modulate the carrier at such a low frequency that the spectral line broadening effect that you describe was lower than my 1Hz bandwidth, that you described. Further more what I would broadcast is the same information on both channels, but in phase reversed state, so in effect what I would do is make my two channels a differential pair. Hopefully E.T. would recognize that the signal could be obtained by subtracting the amplitude modulation from the two channels, thus providing a relatively robust communincation link which would be immune to common mode noise.

Of course the concept might be flawed, it could be that the PiHy or the eHy lines are right in the bad bands, or there may be much better universal constants to select.

Regards

Dave Robinson

P.S 'e' represents the Universal constant 2.71828...... not the charge on an electron.

Also, maybe I am wrong about the Quest being in a zero energy state, seems to have been more activity on this thread than we have seen in months

sigblips
sigblips's picture
Offline
Joined: 2010-04-20
Posts: 733
Hello Rob,"- Jill thought of

Hello Rob,

"- Jill thought of open source contributors as “free (unpaid) workers” that she could control and treat like her own staff. She only found one person like that."

I agree with you that open source doesn't work like that and control (or lack there of) was one of setiQuest's greatest faults. I can only think that I'm the "one person" you mention.  While I have done a number of things for the general good of the project such as participating in GSoC and more recently importing parts of the History of SETI Searches page, most of the setiQuest things that I've done have been for my own self interest. And that's the way it should be. It's the proper motivation. Other expectations lead to disappointment when your work is ignored or underutilized.  I also don't think I was ever treated like staff because if I was then I would of had some influence on the direction of this project.

"In various places in this forum you will see jrseti comment that there are not enough internal staff to support setiQuest. This demonstrates once again how little internal understanding there is at the SETI Institute for how successful open source projects work."

Unfortunately one of the most important things that Avinash never setup was a self-sustaining infrastructure and framework for setiQuest. Avinash was TED funded and when he left the project's funding shifted to SETI Live. What caused this shift in funding? I don't know the reasons and I can only speculate. The effect of this funding shift basically froze setiQuest in its current state as the SETI Institute focused on SETI Live. I'm unhappy with this but I can't blame the SETI Institute for following the money.  As Jill said several IRC meetings ago "SETI Live is paying the bills."

Let me reiterate. The funding setiQuest had is gone. The project has no money. Two weeks ago the duration of the IRC community meetings was cut in half to 30 minutes because the weekly time commitment of 60 minutes could no longer be justified.  The project needs to make the best that it can with zero funding. Can the project re-organize by itself? If we want the canceled data collection program to be restarted then we need to build a convincing argument of why it would benefit the SETI Institute.

a_feder
Offline
Joined: 2011-10-09
Posts: 34
You can lead a horse to water...

Sigblips, when was last time you - or Jill for that matter - had to walk up to Linus Torvalds and build a convincing argument of why it should benefit him to develop the OS which both your and SI's software runs on (I know yours run on other OSs too)? I can tell you when that was - never. Because that is not how open source (or, dare I say, Free Software) works. It's not a service you have to earn. It's something sensible people like Linus Torvalds choose to do because they have found by themselves that it makes sense. And now his OS runs on a majority of the devices in the emerging paradigm in computing, namely mobile devices, as well as on most supercomputers and many internet servers. (And he certainly didn't get a dime from Paul Allen to get to this point! On the contrary, one might say.) So now tell me why SETI Institute can't do that?

sigblips
sigblips's picture
Offline
Joined: 2010-04-20
Posts: 733
Hello Anders, What you

Hello Anders,

What you describe is a very nice ideal but unfortunately the reality of setiQuest just isn't going to work like that. As you might remember, we had a window of opportunity in late 2010 to have a real-time data stream from the ATA.  That effort fizzled for numerous unknown reasons. We had our chance and we missed it.

Since then the data collection program has been canceled as the SETI Institute's priorities changed and as the funding shifted from setiQuest to SETI Live. The SETI Institute isn't going to do anything that it feels doesn't help it's mission. If we, the community, want the SETI Institute to do something then we're going to have to work with them and come up with a convincing and persuasive data plan that benefits them. The fact that this plan also benefits us is secondary. I don't see any other way forward.

a_feder
Offline
Joined: 2011-10-09
Posts: 34
It's not an ideal

It's not an ideal, it's a matter of basic economics. The one who receives the pay does the job. SI receives external funding from various sources. As a non-profit, they have a moral - if not legal - obligation to spend these funds in the best interest of their mission. The idea that they can ask Joe Public to pay them, and then expect Joe Public to come and ask if he can please be allowed to do the job he just paid them to do, is just ridiculous. So ridiculous that it would raise questions as to whether SI should be funded at all.

You also make a false distinction which underscores how off base your argument is: there is no "our" benefit and "their" benefit. There is the benefit to SETI. Avinash made the same mistake of wanting to seperate "the project" from "the community" (he said so much in one of his e-mails) and this is where it has led us - the "project" is all but dead.

At the end of the day, you can't change an organization that is unwilling to improve. But I think it was a small - if Pyrrhic - victory that jrseti at least acknowledged in his latest blog post that the project failed due to a lack of internal "resources" rather than due to a lack of external resources. Without our efforts, I suspect they would just have concluded that there is no interest in hard-data SETI and pulled the plug.

a_feder
Offline
Joined: 2011-10-09
Posts: 34
Dave, to add a small point

Dave, to add a small point to what Rob said so well above: the frustration you express is exactly why I and others advocate unfettered public access to some form of raw real-time data from the ATA. SI will never have the competency/time to exhaustively evaluate all the merits of expert suggestions such as yours. That is why you (and anyone else) should be given the ability and the conditions to be able to just go ahead and implement and operate your own detectors on the ATA live data stream - perhaps in collaboration with others - on whatever hardware is available to you, without having to waste endless amounts of time 'lost in space', chasing the elusive prospect that your algorithm may one day be awarded some sort of stamp of approval by SI that will allow it to be implemented on the hardware at HCRO.

JayZee99
Offline
Joined: 2011-03-29
Posts: 3
Dave: Thanks for your reply. 

Dave: Thanks for your reply.  This is indeed s sad state of affairs. 

Seeing as how I have a little time availabe for the next few months, my plan was to tinker with an approach to detect the squiggles using a high-level MATLAB/Octave approach.  If successful, I would then bring up the issue of how to include the approach in SONAta.  However, if the problem has been solved, or if there is no interest from SETIQuest then I would be wasting my time and I should go work on some other project.

I'll watch the boards for a few days to see if I can get an idea of what's going on before I give up on this.

Thanks again,

- jz

a_feder
Offline
Joined: 2011-10-09
Posts: 34
Just so everyone knows

Just so everyone knows, I've been banned from SETILive for "propagating the misinformation" that SETI Institute has chosen to prioritize SETILive over programs for automatic detection and classification of trivial RFI. Judge for yourselves on the relevant pages (though they have deleted my final post on the matter): http://talk.setilive.org/discussions/DSL100004i?page=23&per_page=10

a_feder
Offline
Joined: 2011-10-09
Posts: 34
Paraphrasing

Paraphrasing, my final post was:

"lnigra, I'm saddened that I can't speak to my disappointment with this project without feeling as if you would prefer to silence me. My views aren't based on any "apparent" certainty, they are simple observations. SETI Institute could have chosen to develop programs to detect these trivial RFI signals automatically, but they chose not to. I don't know how you can describe that choice as anything but a decision, unless you use some other vocabulary than standard English.

You claim to have advance knowledge suggesting that developing such a program would not be simple. Perhaps if you shared this knowledge with the public, your argument would be more convincing not just to me but to the thousands upon thousands of people who signed up to this project, only to lose interest again a few weeks later, as well.

Of course, your aim may not be to reach a convincing conclusion. As you correctly point out, you are free to waste everybody's time if you so desire. I only wish that we could take it as a given that this is not your aim, and debate the merits of your methodology instead."

In other words, if I am mistaken in thinking that many RFI signals can be marked automatically, there are better ways of addressing that misunderstanding than by shooting the messenger. Sadly, Zooniverse did not agree.

JayZee99
Offline
Joined: 2011-03-29
Posts: 3
a_feder:  That's unfortunate

a_feder:  That's unfortunate you have been banned. 

Needless to say, I cannot speak to SetiQuest's intentions with SETI Live, but I can speculate that one possible use of the people-classified SETI Live data is to use it to train and test machine learning algorithms.  If so, it would be great if they made the human-classified images available for us hobbyists to experiment with.  Maybe we could develop an automatic classifer that would be useful to them.

The topic of a recent SETI Talk was   "Machine Learning for Exploring Data Streams: Lessons from the VLBA" by David Thompson of JPL.  This talk has not yet appeared on youtube as of this writing, but perhaps there is some info there on machine learning endeavours at SETIQuest.

- jz

robackrman
Offline
Joined: 2010-04-15
Posts: 235
I can't find a description of

I can't find a description of policy so must assume that action was arbitrary.  It seems to me they can't afford to ban people given deterioration of SETILive participation to single digit "people classifying" along with correspondingly low forum activity.