User - MathOverflow

Answer by sheldon-cooper for Can t-test be used for non-inferiority hypothesis testing?

2010-02-23T18:25:13Z

I think the answer is no. T tests, basically, work as follows. You manipulate your input data to obtain something that (under the null hypothesis) is normally distributed with mean zero. For example, if the null hypothesis is that the data is normally distributed with mean 28, then the manipulation is simply subtracting 28 from the data. For more complex cases (e.g. if there are two populations with the same, but unknown, mean), the manipulation is a bit more involved, but still some manipulation is needed that gives you a normal distribution with zero mean. Once you obtain that, you use the fact that $\frac{N}{s}$ (where $s$ is sample standard deviation) is distributed according to Student t (that's where the t in t-test comes from) to determine confidence.

In your case, the null hypothesis encompasses many values for the mean of one population. I don't see an obvious way to manipulate it into something that has mean zero. For example, if you have paired data and subtract the two populations, you get $X_i - Y_i \sim N(m, \sigma)$ where $m \geq \delta$. You can further subtract $\delta$ to get mean $m \geq 0$. But that still encompasses many possible values of the mean. I don't see how to manipulate it further to get something that has just one possible value of the mean.

Answer by sheldon-cooper for Approximating a set with fixed number of elements

2010-02-19T17:42:03Z

I'd use k-means clustering (with k = n) to find the n centroids and use these centroids as the set R.

k-means minimizes the expected L2 distance (i.e. $|x-c|^2$, not $|x-c|$, in case that's important -- in many cases it's not) between a point and its centroid. If all of your new testing points are in the training set, then the ideal distance (in S) would be 0, and the new distance (in R given by the centroids) will be minimized by k-means. If your testing points are different from the training points, but come from the same distribution, then this will minimize an upper bound on the distance.

In principle, k-means clustering is NP-hard in most cases. One particular algorithm (called k-means algorithm) seems to work well in many practical cases.

Answer by sheldon-cooper for Interesting applications of max-flow and linear programming

2010-02-17T20:38:06Z

Not sure how non-obvious this is, but graph cuts and max-flow have been extensively used in computer vision for problems such as image segmentation or finding stereo correspondences. Here's a wiki page and a paper (pdf).

Answer by sheldon-cooper for MicroArray, tesing if a sample is the same with high variance data.

2010-02-17T05:24:36Z

In general, the approach of using additional measurements of other values (not the one you are interested in directly) was useful in many problems in the past, so it sounds like a good idea in your case as well. Here are a few things to look at:

Binary classification

If the task is to determine whether a given probe is a 'match', you can just pose it as a binary classification problem. The input features to a classifier will be ALL the probes in the array. The classifier will determine automatically which of these are useful. If the variance at the target probe is actually small, it may decide to just look at that probe only. If other sites (probes) are helpful too, it may decide to look at them as well. Classifiers can automatically construct complex rules that take into account one or many probes, as needed.

This can be simple to try since there are packages readily available and there are not many parameters to tune. I'd try using a classifier called SVM, it works well in many cases, can deal with limited training data (looks like that's an issue for you). Again, there are SVM packages available that you can download and just run (libsvm is one example, but there are many others).

The disadvantage of this is that it may become resource-consuming if you want a classifier for each probe. Your input dimensionality is 250,000. A simple linear classifier needs roughly one number per dimension, so 250,000 numbers. If you need such a classifier for every probe, this will require 250,000^2 numbers total, which is a lot. There are ways to go around this, but that's one concern.

Collaborative filtering

Collaborative filtering basically allows you to predict the value of one item from the values of related items. Say you know that I liked two movies M1, M2, and disliked two others, M3 and M4. Using collaborative filtering, you can predict whether or not I will like a new movie M5. In your case, you are not doing a completely blind prediction for M5; you do have some (although very noisy) observation. So you would combine that observation with the prediction from other features.

The advantage of this is that there is only one model (as opposed to one classifier per probe). So this is easier to scale.

One model would work something like this. It would group probes that are either all "same" or all "different" most of the time. (These groups would be learned by the model from training data.) Then, given a new array, it would use these groups and data from other probes in each group to determine whether a group is, again, "same" or "different". This question had a link to what looked like an easy intro to collaborative filtering.

The main disadvantage is, I'm not sure you can find an implementation of the model you need for microarrays online (or anywhere). You'd probably need to derive something suitable for your data, which is not difficult, but requires knowing what to do.

Another disadvantage is, you'll probably need more training data for collaborative filtering to work.

Note: neither of this will give a "significance score" (as in t-test, for example). You'll get a confidence value, but you won't be able to say that the findings are statistically significant with a certain confidence.

Answer by sheldon-cooper for Are there nonequivalent randomnesses?

2010-02-09T22:04:31Z

Cox's theorem states that if you accept certain `common sense' rules (e.g. consistency with logic), then standard probability laws are the only valid inference laws. I.e. you cannot arbitrarily change sums to products and such. Wikipedia page is not bad, and a longer derivation appears in Jaynes's book here.

If you don't accept some (or all) of these rules as 'common sense', then it seems you can derive other laws, which I guess could be called 'nonequivalent probabilities' in the sense that they are inference laws not corresponding to any standard probability. One example is given in [3] (also listed on the wiki page).

[3]: J. Halpern, "A counterexample to theorems of Cox and Fine," JAIR 1999

Answer by sheldon-cooper for Are there Generalisations of a Limit (for Just-divergent Sequences)?

2010-02-04T21:23:00Z

Another possibility is to look at how the values are distributed and see whether that converges to some distribution. This is mostly used in stochastic series (e.g. people want to construct Markov chains that converge to a certain distribution of interest).

Answer by sheldon-cooper for How can I tell if y is a function of x in a random sample?

2010-01-18T00:23:23Z

If you are only interested in correlation between the two feature values, then there are a lot of ways to compute it (simple correlation, rank correlation, linear or nonlinear regression, etc.).

If you are interested in causality, a few places to look at are: Granger causality

and NIPS workshops on causality: 2008, 2009

Answer by sheldon-cooper for Mathematics for machine learning

2010-01-15T00:42:24Z

For basic neural networks (i.e. if you just need to build and train one), I think basic calculus is sufficient, maybe things like gradient descent and more advanced optimization algorithms. For more advanced topics in NNs (convergence analysis, links between NNs and SVMs, etc.), somewhat more advanced calculus may be needed.

For machine learning, mostly you need to know probability/statistics, things like Bayes theorem, etc.

Since you are a biologist, I don't know whether you studied linear algebra. Some basic ideas from there are definitely extremely useful. Specifically, linear transformations, diagonalization, SVD (that's related to PCA, which is a pretty basic method for dimensionality reduction).

The book by Duda/Hart/Stork has several appendices which describe the basic math needed to understand the rest of the book.

Answer by sheldon-cooper for How seriously should a graduate student take teaching evaluations?

2010-01-11T22:32:28Z

Positions not associated with teaching (such as industrial or government labs) will very rarely care about your teaching. When I applied for these, I didn't even bother to list my teaching on the cv.

Teaching positions (such as at a community college) will probably care about it a lot more, since they want some proof that you can teach well. But I can't say much since I don't have experience with these.

Research universities are somewhere in-between. In general, their main priority is the quality of your research. So for a standard tenure-track faculty positions, they will likely focus on selecting an interesting (research-wise) colleague rather than the best teacher.

Of course, research universities need to teach too, and they do feel the pressure to teach well. Also, "research university" is not a uniform designation; different universities will have different priorities which may include more or less emphasis on teaching.

Generally, teaching works like this at a research university. The department (math, in your case) needs to teach some courses. These are service courses to other departments (such as "calculus 1 for biology students") and internal courses (e.g. "graduate group theory"). These need to be taught adequately. If the service courses are not taught well, other departments will complain and your dean will not like it. If the internal courses are not taught well, then your colleagues will have underprepared students to deal with, and they will not like it. So people will want to know that you can teach adequately. Generally, at a research university, I would take "adequately" to mean that you will not leave the students grossly underprepared. Whether they love your teaching or not is less of an issue. So, as long as you have some teaching experience, I would say you are OK.

Now, you don't have to list ALL teaching evaluations on your cv. If the evaluations are great, mention them. If not, you can omit them and just list the course. For example:

TEACHING

Fall 2008: Calculus 1

Spring 2009: Algebra (received 4.5 / 5 evaluation)

Fall 2009: Linear algebra

...

Also, I don't think good evaluations will affect your candidacy negatively. It's true that some people might interpret interest in teaching as lack of interest in research, but I don't think good evaluations are enough for that. If you teach a lot, if you publish papers on teaching, go to teaching conferences, etc. -- in that case, yes, people might be suspicious of whether you are interested in research at all (especially if you don't have an equally active research program). But I don't think that just having good evaluations will do you any harm.

Answer by sheldon-cooper for Why isn't Likelihood a Probability Density Function?

2010-01-06T22:47:07Z

If $X$ is data and $m$ are the parameters, then the likelihood function $l(m) = p(X | m)$. I.e. it's $p(X | m)$, considered as a function of $m$.

Both $p(X|m)$ and $p(m|X)$ are pdfs: $p(X|m)$ is a density on $X$ and $p(m|X)$ is a density on $m$. But the likelihood is $p(X|m)$, not as a function of $X$ (it would indeed be a density as a function of X), but as a function of m. So it's not a pdf; in particular, it's not necessarily true that $$\sum_m p(X|m) = 1.$$

Edit: just to clarify, $p(m|X)$ isn't the likelihood. $p(X|m)$ is.

Answer by sheldon-cooper for Methods for choosing a result from a multiple output node Neural Network

2010-01-06T09:38:56Z

Regarding your intuition, it may or may not be true. In many cases people do the opposite, i.e. downweight classes with low membership. This happens any time someone uses a prior p(c) on the class membership.

If you still think you need to boost the probability of small classes, then using different weights for different classes may help. Define the weight of class $i$ to be $W_i \sim 1/p(c_i)$ ($p(c_i)$ is the prior probability of class $i$). Then pick $i$ that minimizes something like $W_i \cdot p(c_i|MLP)$. Designing the weights has to be done empirically, I think.

For Tom: MLP is multi-layer perceptron, a type of neural network.

The problem can be reformulated as follows. Suppose you have some data (like an image of a glyph). It can belong to one of several classes (say, an English character, 'a' to 'z', so 26 classes in this case). You magically get a set of probabilities $p(c_i | data)$ (the probability that your data is in class $c_i$). In our case, this is given by the MLP. You need to decide on a single class. The most obvious rule is to pick $c_i$ for which $p(c_i | data)$ is maximal. But OP feels that if one class has very few members, it should be given advantage. Another option is to have weights and pick the class that maximizes $W_i p(c_i | data)$. The disadvantage of this is that we don't have a principled method of choosing the weights $W_i$.

One possibility is to use $W_i \sim 1/p(c_i)$. In this case, $p(c_i | data) / p(c_i) \simeq p(data | c_i)$, which seems somewhat principled (not completely arbitrary). But maybe there are better ways of doing that.

Comment by

2010-03-10T21:16:34Z

Are you interested in what math can contribute to programming in general, or specifically what math can say about OOP? If the former, then there are quite a few things (complexity, computability, program analysis/verification, formal languages) that can be discussed.

Comment by

2010-02-26T02:14:20Z

I don't know of any t-test that has A >= B as null hypothesis. If such a test were available, then, sure, a test for A - d >= B would be trivially available as well. But all t-tests I know of have A = B as null hypothesis (thus "only one mean").

Comment by

2010-02-21T04:04:27Z

What is the final goal of this; i.e. what do you want your cumulative ranking to reflect? Depending on this, there are various possibilities. E.g. if you just want to get something that generally reflects the popularity of each movie, you can go with a trivial extension of what you do now. For each movie, just compute the fraction of people who ranked it 1st, 2nd, etc. -- the fraction is relative to the total number of people who ranked this movie. Then do something with this (take the average w.r.t. the fractions, or the mode, etc.)

Comment by

2010-02-20T05:51:15Z

But these are not unit vectors. These are vectors of 250,000 +-1's.

Comment by

2010-02-20T01:38:49Z

OK, I see. Seems correct for orthogonal vectors. 25 is not a large margin, though. We have 250,000 random +-1 numbers; the average dot product is clearly zero, but I suspect that standard deviation will be much larger than 25.

Comment by

2010-02-19T20:24:42Z

Thanks. I corrected some terminology to account for that.

Comment by

2010-02-19T20:23:16Z

So the question is, do you really care about the feelings of that one person enough to modify your paper significantly and maybe even withhold some interesting results?

Comment by

2010-02-19T20:21:43Z

One question is, how important this diplomacy is to you? For example, you are worried about spending time in the paper to show that you provably improve their work. I don't think that mathematical community in general will find this "undiplomatic". They may or may not find your improvements interesting, but just because you prove that you improved somebody else's work will not bother anyone (again, assuming the improvements are actually interesting and you are not dwelling on them just to show how much smarter you are). The only person who could be bothered by this is the original author.

Comment by

2010-02-19T19:53:12Z

I'd advise against that. First, you will be sharing credit with other people for something you already did all by yourself. More importantly, I suspect your contribution may go completely unnoticed in such case. If a person X is already known for working on this problem, them most of the credit will go to them. It will be just another paper in a series "X with this student", "X with another student", "X with third student", and most of the credit goes to X.

Comment by

2010-02-18T16:52:18Z

Now, the probability that one probe is always +1 on a set of N positive examples is 1/2^N. If N = 100, then 2^N ~= 1000^10 ~= 10^30. I.e. you'd need an input dimensionality of at least 10^30 to have a spurious correlation among 100 positive examples.

Comment by

2010-02-18T16:48:57Z

Second, the correct solution for this training set is the hyperplane p_0 = 0; or, in terms of weights, w_0 = 1, w_i = 0 for i > 0. It looks like SVM will find exactly this solution in most cases. Basically, if a probe p_i takes on both +1 and -1 values in the positive set, then its weight w_i will be 0. The only way a weight could be non-zero is if a probe is always +1 or always -1 in the positive set (and an additional condition on top of that, which is that it should always be the opposite value in the negative set, which we will ignore for now).

Comment by

2010-02-18T16:41:25Z

I'm not sure where the numbers like 25 and 144 come from. Let me try to state it in terms I understand and see if that's useful. Suppose we are splitting on probe p_0. I.e. p_0 = +1 in all positive examples, p_0 = -1 in all negative examples. The rest of the probes are +- 1 at random. So, first, this is the only split I care about. It may be true that other splits of the same set of vectors give bigger margins, but that doesn't seem relevant. Since this is the split I want to learn, all I care about is this split and the margins of different planes separating it.

Comment by

2010-02-17T18:38:13Z

fedja: For many classifiers, overfitting like that is a concern. For SVM specifically, less so. There are two reasons. First, for $n$ training points SVM effectively has only $n$ (or $n+1$) parameters, regardless of input dimensionality. Second, the risk of SVM is bounded by a number that doesn't depend on input dimension (it depends on the margin instead). In fact, SVM in infinite-dimensional spaces is routinely used (via Gaussian kernel) with success. 36 is still a small number (but note that training would be done on pairs, and there are a few hundred possible pairs), but I think worth tryi

Comment by

2010-02-17T06:41:36Z

OK, so let's assume for a moment that you are only interested in one probe. The task is, given two microarrays, to determine whether they are the same or different at that probe. But it doesn't look like you have training data suitable for that task directly. To apply classification, you'd need a set of microarray pairs, and for each pair whether the two arrays are the same or different AT THAT PROBE. But what you have is only whether or not the two arrays are from the same strain. This is more difficult, since two arrays from the same strain might be different at that probe, right?

Comment by

2010-02-17T06:02:21Z

Is the original individual also a parasite, similar to the other 15 parasites? If yes, you could use other parasites as examples too. A training example is really a pair of microarrays with a label "same" or "different". You have 12 arrays for the main subject; you can build 66 positive pairs from them. But if you have a parasite you sampled 3 times, you can build 3 more positive pairs from it too. That can be useful if you think they are all similar. If they are very different (e.g. one is a human and others are worms), this will not work.