Reference: Ping Ma & Xiaoxiao Sun: Leveraging for big data regression. WIREs Comput Stat 2014. doi: 10-.1002/wics.1324
Don't let the Chinese names fool you. These guys are at University of Georgia and they write quite well in English. The "paper" (I have no idea if Wiley peer reviews this publication, but it seems legit) focuses on applying linear models to very large data sets. While I have no particular interest in that, if you can fit a linear model, you can obviously estimate a mean (or, at least a median), and that I do want to do. In fact, this paper is basically the theoretical validation of CISS that I was looking for.
Ordinary Least Squares is really unstable when using heavy-tailed distributions. By intentionally biasing the sample towards the tails (and, obviously, adjusting for that bias via a Weighted Least Squares), you get better convergence. Hooray, I already knew that. Some of their proofs are useful, though. In particular, they show the estimators are unbiased. Since showing the estimator of a mean is unbiased is pretty obvious, I had done that a little less formally in my paper. Rather than beef up those arguments, I can leave them as is and just cite this as backup.
More importantly, they reference two other lines of inquiry that will get put on the must read list, plus another that probably is only marginally relevant, but might be good to know about anyway:
Priority papers:
Drineas & Mahoney: Looking at computational efficiency of sub-sampled regression. Two papers cited: Sampling algorithms for l2 regression and applications. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami 2006 and Faster least squares approximation. Numer Math 2010.
Ma & Mahoney: Generalizing the above results. Again, two papers: A statistical perspective on algorithmic leveraging. ArXiv e-prints, 6/2013 and the same title (same paper?) in Proceedings of the 31st International Conference on Machine Learning, Beijing 2014
Background:
Hansen & Hurwitz: Defines an estimator based on a weighted sample where the weight is the inverse of the probability of the point being selected (this is sort of what CISS uses, though since CISS samples without replacement, there's a little more to it). The reference is old, which means it's probably one of those results that you simply have to cite in a complete literature review: On the theory of sampling from a finite population. Ann math Stat 1943, 14:333-362.
So, there's one paper reviewed. Everybody sing now:
99 bottles of beer on the wall...
Thursday, May 18, 2017
Wednesday, May 17, 2017
Coming Eclipse
No, I'm not talking about the total eclipse this summer (though that is also plenty cool and I plan on being in Columbia Missouri for optimal viewing when it happens). Rather I'm talking about Yaya.
As parents, it's natural to want your child to do great things. Even not great things are often puffed up to seem like great things. This is natural. I happily listen to folks telling me about how their kid scored a goal or won a Science Fair ribbon. It's not really bragging (well, usually not); it's just joy in your kid's success and you want to share it. I totally get that and I'm happy to share in it.
It's a little different when your kid gets better than you ever were.
That hasn't happened yet. I was a pretty decent musician by High School standards. My parents were fairly strict about practice time. My private teacher's day job was at Julliard (really!). That kind of support pays dividends. People who knew what they were talking about said with a straight face that I should consider it as a profession.
I indulged that thought for a while but came to realize that it wasn't going to happen. I just didn't have the passion for it that's required to make it your life's work. Music is very cruel to those who give some but not all.
Yaya may well come to the same conclusion. She's not better than I was quite yet (she's only in 7th grade) but, barring some major change of heart, she will be. Whether she has enough passion to make it her life, only she can judge. What's obvious to me is that she has more than I did. She practices more. I never have to enforce it; if anything, I'm telling her to put it down and tend to her other subjects. She asks more. She's constantly hitting me with questions about music. The questions are getting deep enough that I'm having to bust out my music theory texts for some of them and flat out defer to her teachers on others.
Most importantly, she dabbles. She picks up new instruments on a whim. Listens to weird stuff. Tries new things. All the really good musicians I know do these things. Almost all the people I know who do these things are really good musicians.
There was a brief time when I was a bit whimsical about all this. I saw what she was doing, saw the joy it was bringing her, and wondered why I didn't take the same path. I'm past that. As much as I value all the things I learned both about music and life from my years performing, I'm fine with the fact that I gave it up and soon my daughter will be way better than I ever was. It's not pride, it's joy.
Here she is playing her feature with her school jazz band. And, yes, she likes dressing like a dude. Deal with it.
As parents, it's natural to want your child to do great things. Even not great things are often puffed up to seem like great things. This is natural. I happily listen to folks telling me about how their kid scored a goal or won a Science Fair ribbon. It's not really bragging (well, usually not); it's just joy in your kid's success and you want to share it. I totally get that and I'm happy to share in it.
It's a little different when your kid gets better than you ever were.
That hasn't happened yet. I was a pretty decent musician by High School standards. My parents were fairly strict about practice time. My private teacher's day job was at Julliard (really!). That kind of support pays dividends. People who knew what they were talking about said with a straight face that I should consider it as a profession.
I indulged that thought for a while but came to realize that it wasn't going to happen. I just didn't have the passion for it that's required to make it your life's work. Music is very cruel to those who give some but not all.
Yaya may well come to the same conclusion. She's not better than I was quite yet (she's only in 7th grade) but, barring some major change of heart, she will be. Whether she has enough passion to make it her life, only she can judge. What's obvious to me is that she has more than I did. She practices more. I never have to enforce it; if anything, I'm telling her to put it down and tend to her other subjects. She asks more. She's constantly hitting me with questions about music. The questions are getting deep enough that I'm having to bust out my music theory texts for some of them and flat out defer to her teachers on others.
Most importantly, she dabbles. She picks up new instruments on a whim. Listens to weird stuff. Tries new things. All the really good musicians I know do these things. Almost all the people I know who do these things are really good musicians.
There was a brief time when I was a bit whimsical about all this. I saw what she was doing, saw the joy it was bringing her, and wondered why I didn't take the same path. I'm past that. As much as I value all the things I learned both about music and life from my years performing, I'm fine with the fact that I gave it up and soon my daughter will be way better than I ever was. It's not pride, it's joy.
Here she is playing her feature with her school jazz band. And, yes, she likes dressing like a dude. Deal with it.
Tuesday, May 16, 2017
Roadmap
So, when you want to get somewhere, it's helpful to have a map. In that spirit, here's the lay of the land for my summer literature review:
The two rectangles at the top are what I've got now: completed algorithms with demonstrated performance on reasonable test sets. That seems like a good start. So, how to tie them together and pull in enough bona-fide research to make it a dissertation?
My thought is this can evolve into the lower rectangle, which is basically a framework for performing multi-dimensional analysis on huge data sets in real time. The multi-dimensional part is what I've been missing up until now and it's the glue that holds all this together. I didn't really understand that until I put together my term presentation for D-BESt. Generalizing this to relational databases will kill a lot of the optimizations. Restricting the scope greatly increases the potential gains and also moves the research into a bit more of a niche (less likely to get scooped).
The fact that it's a niche, doesn't mean it doesn't have very real value. There are still lots of applications for multi-dimensional analysis. And, multi-dim datasets are growing much faster than existing tools can keep up with.
To get to the lower rectangle will require adding some important features, which are indicated by the diamonds. I thought about drawing arrows, but I don't know that I'll necessarily do them in the most logical order, which would be top to bottom. I'll probably implement them in the order I come up with decent ideas.
As for the ideas, the rounded boxes indicate related topics I can draw from. Again, I considered arrows, showing what related to what, but it got really busy. In general, the closer a rounded box is to a rectangle or diamond, the more relevant it is.
I'm figuring this creates a seed group of around 100 papers, which should be a good start. I'm sure I can't fully digest that many papers over the summer, but I should be able to at least locate them and get the major points into a survey. I'll revisit the details as I move through the actual research.
The two rectangles at the top are what I've got now: completed algorithms with demonstrated performance on reasonable test sets. That seems like a good start. So, how to tie them together and pull in enough bona-fide research to make it a dissertation?
My thought is this can evolve into the lower rectangle, which is basically a framework for performing multi-dimensional analysis on huge data sets in real time. The multi-dimensional part is what I've been missing up until now and it's the glue that holds all this together. I didn't really understand that until I put together my term presentation for D-BESt. Generalizing this to relational databases will kill a lot of the optimizations. Restricting the scope greatly increases the potential gains and also moves the research into a bit more of a niche (less likely to get scooped).
The fact that it's a niche, doesn't mean it doesn't have very real value. There are still lots of applications for multi-dimensional analysis. And, multi-dim datasets are growing much faster than existing tools can keep up with.
To get to the lower rectangle will require adding some important features, which are indicated by the diamonds. I thought about drawing arrows, but I don't know that I'll necessarily do them in the most logical order, which would be top to bottom. I'll probably implement them in the order I come up with decent ideas.
As for the ideas, the rounded boxes indicate related topics I can draw from. Again, I considered arrows, showing what related to what, but it got really busy. In general, the closer a rounded box is to a rectangle or diamond, the more relevant it is.
I'm figuring this creates a seed group of around 100 papers, which should be a good start. I'm sure I can't fully digest that many papers over the summer, but I should be able to at least locate them and get the major points into a survey. I'll revisit the details as I move through the actual research.
Friday, May 12, 2017
Full marks
I'll say this for my Evolutionary Programming prof: he turns around grades in a hurry. Less than 12 hours after the exam closed, my grade had been posted. I got full marks on the final which sealed an A in the course. As that's most likely a wrap on my coursework (barring some odd circumstance, the remaining credit hours will be research), that pretty much seals up a 4.0 GPA. Of course, nobody particularly cares about your GPA in a PhD program but, it's still a nice thing to have.
Thursday, May 11, 2017
Final final
Stranger things have happened, but I'm pretty sure I just took my last Final Exam. Ever.
Seems like it went OK, though I'll abstain from bold predictions and just wait for grades to be released.
Seems like it went OK, though I'll abstain from bold predictions and just wait for grades to be released.
Wednesday, May 10, 2017
Genetic Programming
Genetic programming is an approach to arbitrary problems where the goal is not so much to optimize a particular function, but to produce a program that optimally solves a more general problem. That is, find a program that maps an input space to an output space as accurately as possible. While the idea has been kicking around since the 1950's, the work of Koza in the late 1980's.
Notes:
Genetic programs typically store their algorithm as a tree. The tree may represent an arithmetic expression, a classification scheme, or any other logical structure where operations are applied sequentially based on the results of prior operations.
Fitness is assessed via supervised learning. That is, inputs are selected where the correct output is known. The fitness of the program is how closely the program output matches the correct outputs.
Crossover is applied by grafting pieces of the tree from one solution to another.
Mutation is applied by changing part of the tree.
Theoretically, the search space is all computer programs which are guaranteed to terminate. In reality, it works best to limit the complexity of the tree to keep things from drifting off into irrelevant parts of the solution space where the gradient is very flat.
A special structure, the Automatically Defined Function (ADF). Such functions encapsulate more complex operations and can be grafted into the tree as part of mutation or crossing.
Notes:
Genetic programs typically store their algorithm as a tree. The tree may represent an arithmetic expression, a classification scheme, or any other logical structure where operations are applied sequentially based on the results of prior operations.
Fitness is assessed via supervised learning. That is, inputs are selected where the correct output is known. The fitness of the program is how closely the program output matches the correct outputs.
Crossover is applied by grafting pieces of the tree from one solution to another.
Mutation is applied by changing part of the tree.
Theoretically, the search space is all computer programs which are guaranteed to terminate. In reality, it works best to limit the complexity of the tree to keep things from drifting off into irrelevant parts of the solution space where the gradient is very flat.
A special structure, the Automatically Defined Function (ADF). Such functions encapsulate more complex operations and can be grafted into the tree as part of mutation or crossing.
Tuesday, May 9, 2017
NSGA-II
I joked at the start of my term presentation that one thing I've learned in this class is that you can't use actual words in the name of your algorithm (hence D-BESt). NSGA-II follows form and stands for Non-dominated Sorting Genetic Algorithm. It is designed for solving multi-objective functions where the objectives are conflicting (that is, improving one may hurt the other).
Primary paper: Actually two, since NSGA-II is a refinement of the original by the same principal author. But, we'll just give the latter for now: Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. (2002). "A fast and elitist multiobjective genetic algorithm: NSGA-II". IEEE Transactions on Evolutionary Computation. 6 (2): 182.
Notes:
The idea of all multi-objective algorithms is not to find the optimal solution, but rather to identify the optimal pareto front, that is, the set of points that beat every other point on at least one objective. Put another way, the point is non-dominated: there is no point that beats it on all counts.
NSGA sorts the existing solutions into "fronts". The first front is non-dominated by all other points in the sample. The second front is non-dominated by all points not in the first front. This is repeated for as many front as you want.
The fitness is then determined by the front and by how "crowded" the point is. This is to force the solution away from a single point, since the idea is to capture the front, not an optima.
Points are then selected for the next generation based on fitness (tournament selection is most common).
Having selected parents, the rest of the generation is normal Genetic Algorithm (GA) stuff. Cross, mutate, etc. The NSGA-II algorithm does not mandate any particular strategy for these steps.
Convergence is somewhat problematic to assess since you can't measure progress against a single optimal value. Elitist strategies are employed so there can at least be an assessment of whether the best values from the previous generation are surviving in the first front of the next. If they consistently wind up in the first front, that's a clue that the front isn't moving very much.
Primary paper: Actually two, since NSGA-II is a refinement of the original by the same principal author. But, we'll just give the latter for now: Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. (2002). "A fast and elitist multiobjective genetic algorithm: NSGA-II". IEEE Transactions on Evolutionary Computation. 6 (2): 182.
Notes:
The idea of all multi-objective algorithms is not to find the optimal solution, but rather to identify the optimal pareto front, that is, the set of points that beat every other point on at least one objective. Put another way, the point is non-dominated: there is no point that beats it on all counts.
NSGA sorts the existing solutions into "fronts". The first front is non-dominated by all other points in the sample. The second front is non-dominated by all points not in the first front. This is repeated for as many front as you want.
The fitness is then determined by the front and by how "crowded" the point is. This is to force the solution away from a single point, since the idea is to capture the front, not an optima.
Points are then selected for the next generation based on fitness (tournament selection is most common).
Having selected parents, the rest of the generation is normal Genetic Algorithm (GA) stuff. Cross, mutate, etc. The NSGA-II algorithm does not mandate any particular strategy for these steps.
Convergence is somewhat problematic to assess since you can't measure progress against a single optimal value. Elitist strategies are employed so there can at least be an assessment of whether the best values from the previous generation are surviving in the first front of the next. If they consistently wind up in the first front, that's a clue that the front isn't moving very much.
Subscribe to:
Posts (Atom)