Abner's Postgraduate Days

• Title : Linear and Order Statistics Combiners for Pattern Classification
• Source : Combining Artificial Neural Networks (Amanda Sharkey, editor)
• Author : Kagan Tumer and Joydeep Ghosh
• Speaker : ÄÁ¤¹ª@
• Time: 2.28 (Tuesday) 13:00-15:00

This paper discuss the combination of classifiers. How do we improve the performance of our learning? The usual method is to combine. But we don't have criteria to help us making decision. The two empirical criteria are performance of each learner and diversity of learners. But this paper give us a theoretical foundation.



Those curves are posterior probabilities, i.e., for a given x, the probability of classifier classify it into class i(or j).

Shaded region is Bayes error region; if we know the distributions of two posterior probabilities, then we can determine the optimum boundary; therefore, the Bayes error region is essential. The obtained distribution of posterior probability always include error. That is, we choose a Obtained Boundary according to the obtained distributions of posterior probabilities. And the black region is "Added error region".

Using Linear combining

If the error(bias and noise) of different classifiers are i.i.d., then we use linear approximation to estimate error region, and linear combining those. We will got the average error:

$E^{avg}_{add}=\frac{E_{add}}{N}$

i.e., average error equals 1/N of each error.

If bias is not i.i.d., then

$E^{avg}_{add}=E_{add}(\frac{1+\delta(N-1)}{N})$

Order Statistics

Similar.

Syllabus:

1. Introduction to quantum mechanics
2. Introduction to Computation theory
3. Quantum circuits
4. Quantum Fourier transform and its applications
5. Finding hidden subgroup
6. Quantum search
7. Quantum Integer factorization
8. Quantum Circuit lower bounds
Refewnce:

1. Quantum Computation and Quantum Information, Michael Nielsen and Isaac Chuang, Cambridge University Press, 2000.
2. Handouts.

Time and Location:
1. 18:30~21:20, Tuesday. Room 305, ¤uµ{¥|À], NCTU.
2. 18:30~21:20, Thursday. Room 302, ¤uµ{¥|À], NCTU.

This course, "research method", in college of science or engineering, seems a sugar course. Nevertheless, this course in college of social science is a very important course.

I had read a book, "The Craft of Research," by Wayne Booth, Gregory G. Colomb, Joseph M. Williams. This well-known book seems for students of social sicence. Although there are some advices useful, this book lacks the research method of science.

From some uselful articles on internet such as How to Succeed in Postgraduate Study, by Marie desJardins, I got the informations about research method book of sicence. The following are some books.

• Writing the Laboratory Notebook, by Howard M. Kanare (I checked out this book from NCU.)
• An Introduction to Scientific Research by E. Bright Wilson (NTHU)
• Writing Successful Science Proposals, by Andrew J. Friedland, Carol L Folt (NCTU)
• Communicating in Science : Writing a Scientific Paper and Speaking at Scientific Meetings, by Vernon Booth (NTHU)
• The Craft of Scientific Presentations : Critical Steps to Succeed and Critical Errors to Avoid, by Michael Alley (NTHU)
• The Craft of Scientific Writing, by Michael Alley (NCTU)
• At The Helm: A Laboratory Navigator, by Kathy Barker (NTHU)
• Lab Dynamics: Management Skills for Scientists, by Carl M. Cohen, SUZANNE L. COHEN

18.S66 The Art of Counting, Spring 2003

18.433 Combinatorial Optimization, Fall 2003

18.314 Combinatorial Analysis, Fall 2005

18.312 Algebraic Combinatorics, Spring 2005

18.997 Topics in Combinatorial Optimization, Spring 2004

18.435J / 2.111J / ESD.79J Quantum Computation, Fall 2003

6.854J / 18.415J Advanced Algorithms, Fall 1999

6.854J / 18.415J Advanced Algorithms, Fall 2001

18.409 Behavior of Algorithms, Spring 2002

18.404J / 6.840J Theory of Computation, Fall 2002

18.315 Combinatorial Theory: Hyperplane Arrangements, Fall 2004

6.050J / 2.110J Information and Entropy, Spring 2003

6.231 Dynamic Programming and Stochastic Control, Fall 2002

6.854J / 18.415J Advanced Algorithms, Fall 2001

6.243J / 2.156J / 16.337J Dynamics of Nonlinear Systems, Fall 2003

I settled on this paper, Theory of cellular automata: A survey by Jarkko Kari, for presenting at Lab meeting.

In fact, I sent a mail with seven papers to ask prof. Tang to choose one. It is lucky that prof. Tang told me that each one is good as material for presenting at Lab meeting. The seven papers which I chose can be classified into three classes, complex science, complex graph (random graph), and combinatorial algorithms. Why did I choose them? The reason is that I want to study theory and it can connect to the research of our Lab. Since biological systems are one kind of complex systems, I think theory about complex science, such as CA and scalar-free graph, will be good choices.

The question which reside in my heart long time is the topics of my thesis.

I recall that my senior, Dr. Chen, said "Master degree of theory study is meaningless. Two years are too short to learn enough to do real research." Personally, I think the master program as a preparation of Ph.D. But it really made me to think the future seriously.

Let's come back to the topic of thesis. Actually, the topic doesn't matter. What I ask repeatedly is the direction I really want to spend my life on. I observed myself in many aspects; I seem not a programmer, not a combinatorialist, not a engineer. Combinatorics is interesting, programming too. But I can't keep my interests on one and one problem. I more like to think some intrinsic problems.

The first time I like math is because of combinatorics. But I still want to join some Labs about OS or VLSI design. At the final year of my undergraduate days, I attend the Algebra I,II of dept. of math. That is first time I think the math greater than man's mind.

I thought that math is developed by a group of geniuses for fun or for solving real problems. After I learned algebra, I thought that math is with intrinsic great properties. It must come form THE BOOK, like physics. I want to present this paper because I want to connect the real world and math.

Ref. Computer Science and Its Relation to Mathematics, by Donald E. Knuth, The American Mathematical Monthly, 1974.

The most concise and funny story I ever heard to explain the relationship between CS and Math is in above article written by Knuth.

Ref. Combinatorics - Wikipedia, the free encyclopedia

Overview and history

Modern combinatorics began to develop in the late nineteenth century and became a distinguishable field of study in the twentieth century, partly through the publication of the systematic enumerative treatise Combinatory Analysis by Percy Alexander MacMahon in 1915 and the work of R.A. Fisher in design of experiments in the 1920s. Two of the most prominent combinatorialists of recent times were the prolific problem-raiser and problem-solver Paul Erd?s, who worked mainly on extremal questions, and Gian-Carlo Rota, who helped to formalize the subject beginning in the 1960s, mostly in enumeration and algebraization.

Paul Erdos is really a famous mathematician, but Gian-Carlo Rota seems not. According to the description from his entry on Wikipedia, he did great work on combinatorics

His series of ten papers on "Foundations of Combinatorics" in the 1960s is credited with making it a respectable branch of modern mathematics. He said that the one combinatorial idea he would like to be remembered for is the correspondence between combinatorial problems and problems of the location of the zeroes of polynomials.[1] He worked on the theory of incidence algebras (which generalize the 19th-century theory of M Ébius inversion) and popularized their study among combinatorialists, set the umbral calculus on a rigorous foundation, unified the theory of Sheffer sequences and polynomial sequences of binomial type, and worked on fundamental problems in probability theory.

Why does he be ignored?

This two masters' blog talked about Academia. I gathered those articles but I had not time to read it. I just put it on blog to record it.

Retirement:
Comment on Retirement--BECKER
Refusing to Retire: What Can Be Done When People Overstay Their Welcome?

Tenure:
Comment on Tenure-BECKER
Tenured Employment--Posner
Tenure--Posner's Reply to Comments
Response on Tenure-BECKER


For-Profit Colleges:
For-Profit Colleges and Universities--Posner's Comment
For-Profit Colleges-BECKER
On For-Profit Colleges Again-BECKER

Ref. How to Succeed in Postgraduate Study, by Marie desJardins

The Daily Grind:

Keeping a journal of your research activities and ideas is very useful. Write down speculations, interesting problems, possible solutions, random ideas, references to look up, notes on papers you've read, outlines of papers to write, and interesting quotes. Read back through it periodically. You'll notice that the bits of random thoughts start to come together and form a pattern, often turning into a research project or even a thesis topic. I was surprised, looking back through my journal as I was finishing up my thesis, how early and often similar ideas had cropped up in my thinking, and how they gradually evolved into a dissertation.

Keep the papers you read filed away so you can find them again later, and set up an online bibliography (BibTeX is a popular format, but anything consistent will do). I find it useful to add extra fields for keywords, the location of the paper (if you borrowed the reference from the library or a friend), and a short summary of particularly interesting papers. This bibliography will be useful for later reference, for writing your dissertation, and for sharing with other postgraduate students (and eventually, perhaps, supervising).

Those advices are well-known, but not everyone could do it well. As I ever mentioned, Dr. Shalizi's website is great, I don't know that why he has so much time to write down such articles. He must have good habits and techniques of gathering and managing informations. I want to follow those advices but I always hastily put papers on desktop when I am surveying.

Finding a Thesis Topic:

A good source of ideas for honours and master's projects (and sometimes for PhD topics) is the future work section of papers you're interested in. Try developing and implementing an extension to an existing system or technique.

In order to do original research, you must be aware of ongoing research in your field. Most students spend up to a year reading and studying current research to identify important open problems. However, you'll never be able to read everything that might be relevant -- and new work is always being published.

Ref. Michael Faraday quotes

``The five essential entrepreneurial skills for success are concentration, discrimination, organization, innovation and communication.''

``Why, sir, there is every possibility that you will soon be able to tax it! (to PM William Gladstone, on the usefulness of electricity)''

In fact, I looked for the one of my favorite quotations from Faraday, which I read it from a chinese biography of Faraday. But I can't find that...:(

I thought I should training myself that do nothing at Lab but working.

When I was surfing on Internet, I suddenly thought about that besides Nevanlinna Prize How many combinatorists are awarded by "MATH MEDAL"?

Fields Medal

• William T. Gowers (Cambridge Univ.), for his work in functional analysis and combinatorics
• Gregori Aleksandrovich Margulis Provided innovative analysis of the structure of Lie groups. His work belongs to combinatorics, differential geometry, ergodic theory, dynamical systems, and Lie groups.
• Jean Bourgain His work is in various areas of mathematical analysis such as the geometry of Banach spaces, harmonic analysis, analytic number theory, combinatorics, ergodic theory and partial differential equations.

Wolf Prize

• Hassler Whitney for his fundamental work in algebraic topology, differential geometry and differential topology.
• PAUL ERDOS, Hungarian Academy of Sciences, Budapest, Hungary, for his numerous contributions to number theory, combinatorics, probability, set theory and mathematical analysis, and for personally stimulating mathematicians the world over.
• LASZLO LOVASZ, Yale University, New Haven, Connecticut, U.S.A., and Eotvos University, Budapest, Hungary, for his outstanding contributions to combinatorics, theoretical computer science and combinatorial optimization.
• GREGORY A. MARGULIS, Yale University, New Haven, Connecticut, USA, for his monumental contributions to algebra, in particular to the theory of lattices in semi-simple Lie groups, and striking applications of this to ergodic theory, representation theory, number theory, combinatorics, and measure theory

Ref. WOLF PRIZE RECIPIENTS IN MATHEMATICS

The first time I heard the term "complex" is on my senior high school days; I found a book, Complexity: The Emerging Science at the Edge of Order and Chaos of Mitchell M. Waldrop, in library. I don't know what complexity is. I just like to read some stories about science so that I checked out this book and read it in a day.

I love this book, the idea of complexity is amazing. And The great part is this story is unfinished (at least, in the book.) Unlike other books about subjects of science, the author said : "This is a book about the science of complexity-a subject that's still so new and so wide-ranging that nobody knows quite how to define it, or even where its boundaries lie." Books about other subjects of science usually told readers the stories of its glory days and history, such as physics, quantum theory. That make me thought I might study it when I am a scientist.

That's one of reasons I overtook the paper "Methods and Techniques of Complex Systems Science: An Overview " to read.

But another question raised. Why don't I hear many discussion on it?

In the formal education, I hardly heard people discuss about complexity in Taiwan. There are two possible answers, one is that the level of science research in Taiwan is behind the top level of world very much, the other is that the achievement of complex science is not good as expecting.

How do other scientists think about complexity science?

Science Magazine, April 1999, Vol 284, Special Issue "Complex Systems" might be a good start point.

Btw, Cosma Rohilla Shalizi's Website is great!

Ref. [nlin/0307015] Methods and Techniques of Complex Systems Science: An Overview

Ref. Methods and Techniques of Complex Systems Science: An Overview (Part I)

My original thought is to note what I read in this paper, but it is difficult to write down without misunderstanding.

Section II B. Choice of Architecture

The basic idea of data mining is to fit a model with minimal assumptions about what the correct model should be, or how the variables in the data are related.

This subsection seems about Non-parametric statistics, but some terms, such as kernel method, casual inference, in this subsection seem to be topics of pattern recognition or AI.

Section III Time series analysis

1. The old school of time series analysis:

   They view the time series as samples from a stochastic process, and applies a mixture of traditional statistical tools ans assumptions(linear regression, the properties of Gaussian distributions) and the analysis of the Fourier spectrum.

2. The new school of time series analysis:

   They view time series as distorted or noisy measurements of an underling dynamical system, which it aims to reconstruct.)

I don't know, but it looks like the concepts of stochastic process which I learned from communication theory. Therefore I don't feel this part too untouchable. The part of "The Nonlinear Dynamics approach" is very scare.

I can't differ agent-based model and CA, clearly. They both look like variants of automata....

The Complexity Measures part are interesting. But the name "algorithmic complexity" is weird. As I know the Kolmogorov complexity should be called descriptive complexity.

Further Reading:

• General: Shalizi CR, Crutchfield JP, "Computational Mechanics: Pattern and Prediction, Structure and Simplicity. Author said it is one of best available survey about the complexity (of complex science) and required grad. level statistical mechanics.
• Data mining and Statistical Learning: This field seems very very important in complex science. The author Dr. Shalizi spent half of pages to introduce this fields, and it seems really a powerful tools. But I am not interested in it currently.
• Time series: Same as above. The part of symbolic dynamics seems more interesting, but it seems very difficult.
• Cellular Automata: This field is what I am interested in at first. But I am more interested in the automata-theoretic aspect not modeling. Cellular Automata : A Discrete Universe, by Ilachinski, Andrew., Cellular Automata: Theory and Experiment by Howard Gutowitz (Editor), Cellular Automata and Complexity by Stephen Wolfram, New Constructions in Cellular Automata by David Griffeath, Cristopher Moore.
• Agent-Based Modeling: Self-Organization in Biological Systems by Scott Camazine, Jean-Louis Deneubourg, Nigel R. Franks, James Sneyd, Guy Theraula, Eric Bonabeau, The Complexity of Cooperation: Agent-Based Models of Competition and Collaboration by Robert Axelrod. I just want to check the differences between CA and ABM.
• Information Theory: The relationship between physics and information seem funny. Complexity, Entropy and the Physics of Information: The Proceedings of the 1988 Workshop on Complexity, Entropy, and the Physics of Information Held by Wojciech Hubert Zurek, Crystalline Computation, Norman Margolus.
• Complexity Measure: I don't know its usage, but it seems funny topics.

I thought to create a article to collect some classical papers as prof. Papadimitriou's course. But one of difficulties is that I don't have the ability to evaluate those papers.

However, there is a great article about computer science of Wikipedia. List of publications in computer science

This is a list of important publications in computer science, organized by field.

I updated Nanoblogger to version 3.3 RC4, and changed the name of this blog. The old name "blog in English" show less on the main interest of this blog.

Ref. John von Neumann

The sciences do not try to explain, they hardly even try to interpret, they mainly make models. By a model is meant a mathematical construct which, with the addition of certain verbal interpretations describes observed phenomena. The justification of such a mathematical construct is solely and precisely that it is expected to work.

Ref. Convergence!

Carl Gustav Jakob Jacobi

It is often more convenient to possess the ashes of great men than to possess the men themselves during their lifetime.
[Commenting on the return of Descartes' remains to France]
In H. Eves Mathematical Circles Adieu, Boston: Prindle, Weber and Schmidt, 1977.

The real end of science is the honor of the human mind.
In H. Eves In Mathematical Circles, Boston: Prindle, Weber and Schmidt, 1969.

It is true that Fourier had the opinion that the principal aim of mathematics was public utility and explanation of natural phenomena; but a philosopher like him should have known that the sole end of science is the honor of the human mind, and that under this title a question about numbers is worth as much as a question about the system of the world.
In N. Rose Mathematical Maxims and Minims, Raleigh NC:Rome Press Inc., 1988.

Does it worth to pursue Ph.D. degree? That is a question in my mind. In spite of few people, most of them can't be influential.

Research and pursue truth might be meaningful, but it can't be all of their life. There are so many exciting things to do. Why do they stay in doing research?

It might be a answer.

Ref. Michael A. Nielsen, Principles of Effective Research

Fundamental principles

The fundamental principles of effective research are extremely similar to those for effectiveness in any other part of life. Although the principles are common sense, that doesn't mean they're common practice, nor does it mean that they're easy to internalize. Personally, I find it a constant battle to act in accord with these principles, a battle requiring ongoing reflection, rediscovery and renewed commitment.

Integrating research into the rest of your life

Research is, of course, only a part of life, and must be understood in relation to the rest of life. The foundation of effective research is a strong motivation or desire to do research. If research is not incredibly exciting, rewarding and enjoyable, at least some of the time, then why not do something else that is? For the purposes of this essay, I'll assume that you already have a strong desire to do research [*].

[*] People sometimes act or talk as though desire and motivation cannot be changed. Within limits, I think that's wrong, and we can mold our own motivations. But that's a subject for another essay.

Motivation and desire alone are not enough. You also need to have the rest of your life in order to be an effective researcher. Make sure you're fit. Look after your health. Spend high quality time with your family. Have fun. These things require a lot of thought and effort to get right. If you don't get them right, not only will your life as a whole be less good, your research will suffer. So get these things right, and make sure they're integrated with your research life.

As an example, I once spent three years co-authoring a technical book, and for the final eighteen months I concentrated on the book almost exclusively, to the neglect of my health, relationships, and other research. It is tempting to ask the question "Was the neglect worth the benefits?'' But that is the wrong question, for while the neglect paid short-term dividends in increased productivity, over the total period of writing the book I believe it probably cost me productivity, and it certainly did after the book was complete. So not only did I become less fit and healthy, and see my relationships suffer, the book took longer to complete than if I'd had my life in better order.

Ref. 2005-12-26 Note on linear programming

I still can't understand the simplex method; It's amazing! I must misunderstand or miss something!

Ref. Chvatal, Chapter 2, Linear Programming, Freeman, 1983.

In general, given a problem

Maximize $\sum^n_{j=1} c_jx_j$

subject to $\sum^n_{j=1} a_{ij}x_j\leq b_i$ ($i=1,2,\cdots,m$)

$x_j\geq 0$ ($j=1,2,\cdots,n$)

We will transform it into a linear equations system called dictionary by introducing slack variables.

$x_{n+i}=b_i - \sum^n_{j=1} a_{ij}x_j$ ($i=1,2,\cdots,m$)

$z=\sum^n_{j=1}c_jx_j$.

Every solution of the set of equations comprising a dictionary must be also a solution of (2.13), and vice versa.(pp. 18, (2.13) means the math formulation of the problem.)

The equations of every dictionary must express $m$ of the variables $x_1, x_2,\cdots,x_{n+m}$ and the objective function $z$ in terms of the remaining $n$ variables.(pp. 19)

Books of LP are introducing much different terminologies, like basic, feasible solution, dictionary, feasible dictionary, and so on, but they doesn't tell me which terminologies are important and meaningful.

They said, the variables in left-hand side are called basic, the variables in the right-hand side are called nonbasic, and the basic variables are said to constitute a basis; the formula for the leaving variable appears in the pivot row of the dictionary; the computational process of constructing the new dictionary is referred to as pivoting.

The simplex method is a procedure that build a dictionary; find a initial solution; pivoting (chose a nonbasic variable to become basic variable and build a new dictionary.), and then find out a better feasible solution.

In each pivoting, $z=\sum^n_{j=1}c_jx_j$. will become less flexible. (more and more terms will be with negative sign.) The constant term will enter the objective equation like $z=c+\sum^n_{j=1} d_jx_j$.(Note that the $c$ term in objective equation will restrict the feasible solution. Although each dictionary will be equivalent, but the optimal solution will be produced step by step because we will pick the pivoting variable from the objective equation for maximizing $z$.)

At beginning, I don't understand that how to produce the optimal solution since each dictionary are equivalent. The answer is in the objective equation. The change of objective equation will make us have less and less choice for improvement.

Ref. Chvatal, Chapter 3, Linear Programming, Freeman, 1983.

1. If $b_i$ will not nonnegative, it might be without feasible solutions. (The author discussed it on pp.39-42.)

   The trouble with an infeasible origin is twofold. First, it may not be clear that our problem has any feasible solutions at all. Second, even if a feasible solution is apparent, a feasible dictionary may not be.

   The strategy is known as the two-phase simplex method. In the first phase, we set up and solve the auxiliary problem; if the optimal dictionary turns out to have the property (3.15) then we proceed to the second phase, solving the original problem itself.

   The property (3.15) is on pp. 41 of this book. i.e., $x_0$ is nonbasic, and so the value of $w$ is zero. This property about auxiliary problem is respect to the relation of auxiliary problem's solution and original problem's solution. A important key point is the policy to choose leaving variable of candidates: $x_0$ is prior. But I don't really understand its argument. Why does the original problem be infeasible, if the property, $x_0$ is basic and the value of $w$ is zero, held?

2. If no suitable variables to be chosen as entering variable, then it means current solution optimal. If candidates more than one, any one of them will OK!
3. We chose the leaving variable that is that basic variable whose non-negativity impose the most stringent upper bound on the increase of the entering variable.
4. Simplex iterations that do not change the basic solution are called degenerate. It is harmless but annoying.

Theorem 3.1 If the simplex method fails to terminate, then it must cycle.

Note that cycle must occur in the presence of degeneracy. Cycling is rare in LP so that regardless on most implementation. There are some ways to avoid cycling.

• perturbation method
• lexicographic method
• smallest-subscript rule

The Fundamental theorem of Linear Programming

Every LP problem in the standard form has the following three properties:

1. If it has no optimal solution, then it is either infeasible or unbound.
2. If it has a feasible solution, then it has a basic feasible solution.
3. If it has an optimal solution, then it has a basic optimal solution.

Simplex method is a clever and powerful method, but its procedure is not so clear. There are many pitfalls in each steps.

"Methods and Techniques of Complex Systems Science: An Overview," forthcoming as a chapter in Thomas S. Deisboeck and J. Yasha Kresh (eds.), Complex Systems Science in Biomedicine (Kluwer Academic) = nlin.AO/0307015. A 27,000 words summary of the tools people should use to study complex systems, covering statistical learning and data-mining, time series analysis, cellular automata, agent-based models, evaluation techniques and simulation, information theory and complexity measures, with 265 references (a personal record). I'm told the actual book should appear either in late 2004 or early 2005.

(Information of this paper from auther's website.)

I chose this paper for presentation on Lab meeting. This field, complex systems science, seems most intersection of fields which I am interested in. I hope this paper can guide me to know what I need to learn. And this paper is for biomedical research, it satisfy the direction of our Lab.

Ref. [nlin/0307015] Methods and Techniques of Complex Systems Science: An Overview

In this chapter, I review the main methods and techniques of complex systems science. As a first step, I distinguish among the broad patterns which recur across complex systems, the topics complex systems science commonly studies, the tools employed, and the foundational science of complex systems. The focus of this chapter is overwhelmingly on the third heading, that of tools. These in turn divide, roughly, into tools for analyzing data, tools for constructing and evaluating models, and tools for measuring complexity. I discuss the principles of statistical learning and model selection; time series analysis; cellular automata; agent-based models; the evaluation of complex-systems models; information theory; and ways of measuring complexity. Throughout, I give only rough outlines of techniques, so that readers, confronted with new problems, will have a sense of which ones might be suitable, and which ones definitely are not.

The techniques of complex systems science:

1. For analyzing data

   In this part, the popular techniques are statistical learning, data mining, time series analysis

2. For building and understanding models

   nonlinear dynamics, cellular automata, agent-based models

3. For measuring complexity

   information theory

I am much interested in the last two parts than the first one. I want to emphasize them on the Lab. meeting, so that I just browse part I.

NTHU library will connect collections and Google Scholar via SFX.

Google Scholar --> Scholar Preference --> Library Links
Key in "NTHU" and click the button of "Find Library".

After finishing above steps, the search results of Google Scholar with the label "SFX@NTHU" mean that those data can connect directly to the e-resources of NTHU library.