add regression capabilities

[jovo]

[david-z-shi]

Can I be assigned to this issue?

[david-z-shi]

@levinwil @jdey4 should I be writing a new forest class for this, along with its deciders/transformers/voters? I think once I do that, I can find some regression dataset benchmarks to test the implementation in a notebook

[levinwil]

@latasianguy I will mention that this is a very difficult and tricky issue.

In terms of implementation, we already have code that implements regression that is clearly the same algorithm as in classification, just modified to be regression instead. That code currently exists on the regression branch of this repository, both for networks and forests.

However, code is just language you use to communicate an algorithm to the computer. The difficulty comes in with this issue in figuring out what that algorithm should be. Regression is hit very hard by adversarial transformers, in terms of transfer efficiency. Typically, we would hope (and in classification, we do see this) that adding more transformers results in a backward transfer efficiency >= 1. However, in regression, my impression is that the algorithms that have been tried and implemented have not always resulted in backward transfer efficiency >= 1. I have had several discussions with those who previously attempted to come up with various deciders (and voters, but more emphasis on deciders) to alleviate this problem, and some things have worked for certain datasets. So there is hope. But I wanted to mention that this is not a straight forward "we have this algorithm and I need to implement it and then it will work just as well as classification." We already have that and it exists on the regression branch. This issue will primarily be coming up with new algorithms (most likely voters and deciders) to alleviate adversarial transformers.

If you like designing algorithms, then great! But I wanted to give a full disclosure about what this issue entails.

[david-z-shi]

@levinwil are there any papers you would recommend for me to get a scope of this problem?

[levinwil]

@latasianguy I personally don't know of any papers that directly address the problems we have been experiencing. I can provide some papers that are related to potential solutions I think might be worth trying. Would that be useful? It's up to you how you'd like to spend your time, and there's a chance I send you some papers and you spend days (or weeks) reading them, implement them in our framework, and none work. Up to you if you're fine with that potential.

@jovo Might have some papers that he thinks are useful.

I will also mention that, in general, the regression landscape is very sparse and there isn't much to read (not to mention, most of the stuff isn't great). I can go into my impression of why that is, but I don't think that's particular important - I just wanted to mention that it might be difficult to find papers that directly address this issue.

I will also mention that I spoke with Microsoft people yesterday and am speaking with them again tomorrow regarding this specific issue, so I might have some more useful information tomorrow.

[david-z-shi]

@levinwil I think that would be useful, it'll be a good experience for me working on this type of open-ended problem that may or may not have a good solution. Let me know if Microsoft people have more information

[levinwil]

@latasianguy

Here is a vague description of the ideas I think might work. For reference, I think of progressive learning as a democratic system. The decider is like the president. The voters are like individual committee members. The transformers inform how those individual committee members view the question of interest. When you get a new point, one transformer says "I'm going to provide economic data" and another says "I'm going to provide social data" etc. Then you have one committee member (i.e. voter) who looks just at that economic data and casts his/her vote as to his/her answer to the question, one who just looks at the social impact and casts his/her vote as to his/her answer to the question, etc. Then the president (i.e. decider) looks at all the casted vote and goes "hmmmmm how do I decide on an answer, given these committee votes"

Difficulty comes in when there are some really stupid committee members, in the sense that the data that they're looking at is pretty bad and not particularly helpful in answering the questions of interest (i.e. voters trained on adversarial transformers) and the president just average all the committee votes. There are a couple potential solutions I've thought of:

1. The president just doesn't trust stupid committee members. Intuition approach: look at their past histories and ask 'how has this committee member done in the past? If they've provided me with useful votes, then trust them more. If they've provided me with stupid votes, trust them less." And then we (hopefully) can do even better: we don't need to think of all committee members as always better or worse. We have a question of interest. So look at their past histories on questions really similar to the inference question, and form your trust based on if they've been successful at answering those similar past question (e.g. trust biologists on biological questions, trust economics on economic questions, etc.). Everyone has their strengths and weaknesses. So just trust the committee members whose strengths line up with the inference question of interest.

2. The president gets frustrated and can't work out who is stupid and who isn't, so he/she just tells his/her assistant to do it and the president doesn't care about how it gets done; he/she just care that it works. Intuition approach: let the assistant know about past votes cast by each member (i.e. voter outputs) and if they were or weren't stupid (i.e. task labels). Then the assistant figures things out and in the future just whispers in the president's ear on how to make decisions and essentially becomes the decider.

3. The president gets frustrated and does everything him/herself. Intuition approach: forget the voters even are there. Literally don't train voters. We have transformers that give us the "relevant data" the voters would've gotten anyways. Bypass the voters. Concatenate all the relevant data (i.e. transformer output) together and train a single decider mapping the relevant data to the ultimate decision (i.e. task label).

My first attempt at all of these (and the attempts of Microsoft people) have been/are some version of KNN as far as I am aware (although that could be wrong). So here's some KNN background, tailored to the approaches.

KNN Background

1. Have you read the original Stone's consistency theorem of KNN regression paper? If not, it's fine. It's a very technical, old, and dense paper to convey a simple point (and this is an oversimplified interpretation): as a KNN regressor trains on increasingly more IID data from the distribution it'll see at inference time, the test error (measured through, I believe, mean absolute error) approaches 0. This just means it's a consistent estimator.

2. KNN is great. But it's hit hard by the curse of dimensionality. Here is some background on why (and some more useful background): https://www.cs.cornell.edu/courses/cs4780/2018fa/lectures/lecturenote02_kNN.html

3. Here is a post about one way to alleviate the curse of dimensionality when using KNN: https://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data. It mentions one way of alleviating the curse of dimensionality: Locally Sensitive Hashing (LSH). There may be other ways, I'm not sure. This is just my go-to.

4. Here's a post that explains LSH in a way that I think is simple: https://stackoverflow.com/questions/12952729/how-to-understand-locality-sensitive-hashing. There are plenty of other resources which likely explain it well.

Selfish Background That Describes a Method I Want to Try Since I Developed The Idea

1. I wrote an an algorithm (click on that blue link and it should down the PDF) a few months ago that I believe directly addresses adversarial task alleviation, and in a local way. I have a conjecture (and a pretty strong one at that but could be wrong) that it will alleviate adversarial tasks. Maybe there exists other methods that alleviate it even more, and maybe my conjecture is wrong. But I selfishly want to try this idea, because everyone thinks there ideas are going to work haha. This is a very simple idea: 'we want to know, at inference time, if we will perform well on the given point. Look at the k points on a holdout set that most resemble that infernence point. Of those similar points, what is the proportion of points you performed well on? That's the approximate chance you'll do well on the given inference point of interest. Oh, and by the way, if those most similar points aren't actually that similar, we'll tell you that we don't have a good estimate.' If you get confused by the main body experiments, just look at Appendix A. It contains the experiment that are, in my opinion, the most simple to understand without all the knowledge from the test metrics section or a background in predictive uncertainty. This paper directly is approach 1 in that the president assigns uncertainties to each voter output and says "hey, I know you've been stupid/smart about votes on questions like this in the past. So I'm going to let you know that I do/don't trust you according to that past history and will weight your vote according to that level of trust. I'll call that level of trust 'uncertainty' and the smartest thing you can do when you're clueless or wrong is say that you're uncertain"

[david-z-shi]

@levinwil I think I want to play around with running regression forests with normal data and adverserial data. I'm working on the branch for regression. Will a toy example of a underlying polynomial curve like Ax^2 + Bx + C and a higher order polynomial, both with added noise, work to simulate a two task regression problem? This way I can understand the transfer efficiencies and play around with some parameters. Let me know if there is a better way to create toy datasets

[levinwil]

@latasianguy That is along the lines of what MSR people and I discussed. That was how we started (thinking of a simple curve and a higher order polynomial). Just a quick reminder: an adversarial transformer with respect to task A transforms the data such that - when a voter is trained on top of task A data transformed with the adversarial transformer - BTE < 1 with respect to task A (i.e. that voter harms the overall voter ensemble). This will be most apparent when there is high loss on that voter that is trained on task A data that went through the adversarial transformer.

This is where we ended up in terms of setting up toy adversarial experiments. For all of the below experiments, we care about Task A, which is a simple linear function of y = x, with very high sample size and very low noise (make standard deviation = 0.1 or less). This can be easily made with the following function: https://scikit-learn.org/stable/modules/generated/sklearn.datasets.make_regression.html. Here are the following Task B settings we were thinking of making:

1. (simplest and most unrealistic) make a new transformer class that outputs random partitions. That should results in data that is pretty much random, and the voter that is trained on top of that data should result in pretty high loss, and be unhelpful with respect to BTE for previous tasks. Thus, to simulate an adversarial transformer, simply make this random transformer the transformer for task B.
2. (slightly more realistic) the data used to train the task B transformer is the line y = 0. The partitions, therefore, should be pretty much random since it doesn't make a difference where they lie: every leaf is automatically pure.
3. (most realistic) the data used to train the task B transformer is the line y = x, but with a VERY low sample size and MUCH more noise (e.g. make standard deviation = 2.0 or more). You can use the same function to make this as to make the task A data.

Keep in mind that the steps for training the PL should be as follows for each setting:

1. use add_task on the Task A data
2. use predict to get task A test predictions
3. compute test loss and save it
4. use add_transformer on the task B adversarial transformer (it will train everything internally)
5. use predict to get task A test predictions
6. compute test loss and save it
7. compare More general progressive learners #3 and rotated xor problem #6. In the presence of an adversarial transformer, rotated xor problem #6 will likely be much higher than More general progressive learners #3. We want to lower that difference as much as possible.