Abner's Postgraduate Days

This morning I attended a seminar, which was given by professor K. J. Ray Liu, for the topic: Can Signal Processing Predict Cancer?

This talk was in Chinese so that I had less pressure and more pleasure in this seminar than last one.

Prof. Liu said that the old approaches, data-driven approches, have made some successes on classifing cancer and normal samples based on microarray data, but the model-driven approach could give us some insights. However, it's very difficult to construct a model.

Prof. Liu and his team took the data from mircoarray as input signals and tried to investigate those signal by statistic techniques. Prof. Liu thought it as a system so that they didn't try to find out each function of genes, they builded a simple model, ensemble dependence model (EDM).

They clustered dataset into 4 clusters. By some least square and statistic methods, Prof. Liu got two 4x4 matrice A_c and A_n. X' = A_c x X + N_c X' = A_n x X + N_n

A_c means cancer smaples and N_c means nosie of cancer smaples. A_n means normal smaples and N_n means nosie of normal smaples. The nosie might mean the system can't operate clearly. They found the matrix of clustered smaples have very insteresting porperties. When they assumed N_c = 0, the eigenvalues of this matrix are 1, 1, 1, -3. They changed the number of culsters(the dimension of matrix), and found the property still holds.

Using EMD to classify cancer and normal samples had very good perfromence.

Further, Prof. Liu wrote program to investigate, they found the eigenvalues had consistent distrubution and showed some insights between normal, early stage of cancer, and cancer. They were convinced that they could use this property to predict the status of health, not only cancer or noraml but also the transition between cancer and normal.

In this talk, Prof. Liu told us the difficulty when they tried to build such model. The most impressive thing is so much things we don't know. The area even not formed.

The best number of clusters is 4. Why? The eigenvalues of matrix have such property. Why?

There are many results from statistic techniques and try-and-error. We don't know much about the truth behind the model, but it's useful and insightful.

It's impressive that the power from changing your mind.

The preprint "Ensemble dependence model for classification and prediction of cancer and normal gene expression data." and supplemental analysis.

I read two papers of Pei-Zhi Lee, Chong-Wei Huang, about SFC at frist. I didn't satisfied by them so that I searched and collected some papers as following:

• Asano, T., Ranjan, D., Roos, T., Welzl, E. and Widmayer, "Space-filling curves and their use in the design of geometric data structures", Theoretical Computer Science, (18)1: 3-15, 1997.
• Mokbel, M. F. and Aref, W. G., "Irregularity in Multi-Dimensional Space-Filling Curves with Applications in Multimedia Databases", Proc. of the 2nd Intl. Conf. on Information and Knowledge Management, Atlanta, GA, 512-519, 2001.
• Breinholt, G. and Schierz C., "Algorithm 781: Generating Hilbert¡¦s space-filling curves by recursion", ACM Trans. On Mathematical Software, TOMS, 24(2): 184-189, 1998
• Mokbel, M. F., Aref, W. G. and Kamel, I., "Performance of MultiDimensional SpaceFilling Curves", In Proc of ACM GIS, pages 149¡V154, 2002.
• GUOHUA JIN and JOHN MELLOR-CRUMMEY, "SFCGen: A Framework for Efficient Generation of Multi-Dimensional Space-Filling Curves by Recursion", ACM Transactions on Mathematical Software, Vol. 31, No. 1, March 2005.
• Jun Gao and J. Michael Steele, "General spacefilling curve heuristics and limit theory for the traveling salesman problem", Journal of Complexity , Volume 10 , Issue 2, Pages: 230 - 245, June 1994
• Skubalska-Rafajlowicz, E., "Pattern recognition algorithms based on space-filling curves andorthogonal expansions", IEEE Transactions on Information Theory, Volume: 47, Issue: 5 , page 1915-1927, Jul 2001.

And there is a homepage, Some combinatorial applications of spacefilling curves.

It might be the final topic I regard as I am a undergraduate student. :)

The content of the two paper I mentioned at beginnig is all about the algorithm for 1D/2D encoding/decoding. It doesn't talk about the application and property of SFC. I thought SFC useless. The distance between a point and its adjacent points are to long. It's hard to match a pattern in a very long string. And, I thought the advantage of SFC might be the property about storing in the memory(when the data is too large to place in meoey in the same time.)

Therefore, intuitively, I thought the well-designed SFC should be a pattern that are recursively constructed, and the structure of such pattern will be reserved anywhere in the big one. (scalable?)

But when I tried to find out such SFC, I found that the Sierpinski space-filling curve is near what I want when I visited the homepage for spacefilling curves and applications.

I am interested in this topic more. :) I will read above papres ^^"

Tetsuo Asano , Desh Ranjan , Thomas Roos , Emo Welzl , Peter Widmayer, Space-filling curves and their use in the design of geometric data structures, Theoretical Computer Science, v.181 n.1, p.3-15, July 15, 1997

The ACM Digital Library has no electronic copy, and the lib. of NTHU, CYCU, NCU have no print copy. Only the lib. of NCTU has print one.

While I considered to go to NCTU to copy this paper, I found the electronic copy on Google Scholar.

Ha~! It's great~~~!!!

Another paper, ¡mPattern Recognition Algorithms Based on Space-Filling Curves and Orthogonal Expansions¡n, by Skubalska-Rafajlowicz, Ewa, on IEEE Transactions on Information Theory; Jul2001, Vol. 47 Issue 5, p1915, might useful. But, there is internet trouble between CYCU lib. and database of IEEE so that I can't download full text.

The SEMINAR, I mentioned before, was presented in English today. It's the first time that I attend a lecture in English.

Actually, I were scared a little bit. Fortunately, the speaker, Benjamin W. Wah, is a Chinese people. His accent is familiar to me. The topic belongs to the my field. Besides, prof. Wah prepare good slides for this talk so that I can understand them about 50~60 %.

Prof. Wah introduced a new (not exactly) approach to solve problems.

In the real world, most of problems are nonlinear not linear. There are much difficulties to solve nonlinear programming problems. The complexity will be exponential. For the large-scale case, the time will grow too fast to solve it.

Prof. Wah and his team tried to solve this kind of problems by subspace partition for several years, but this approach was powerless because of the dependence among variables. The subspace partition approach means divide orignal problem into subproblems by the number of elements. (like divide-and-conquer?)

In recent years, they tried to solve this kind of problems by constraints partition.

This approach likes the approach of subspace partition, but this approach has no problem about the dependence among variables. Because each subproblem has its constraints, and global constraints for whole problem. This approach is iteration style.

So, the most important issues are how to partite constraints and how many iterations will do.

According prof. Wah's study, this approach is really powerful!

The number of iteration is less than 10 in general by the property of convexity. The solver of each subproblem is not important. That means the advantage of constraints partition is based on the structure, not particular algorithm. However, finding out the partition of constraints is still hrad.

Prof. Wah is convinced this approach useful and powerful by statistical data. The next goal of prof. Wah is to analysis and to partite constraints automatically.

Prof. Tang said that It's amazing. I could understand, the approach seems so simple that improvement of performance is unbelievable.

This experience of auditing lecture is great.