图 书 馆
统计杠杆和改进的矩阵算法Statistical Leverage and Improved Matrix Algorithms |
|
| 课程网址: | http://videolectures.net/icml09_mahoney_itslima/ |
| 主讲教师: | Michael Mahoney |
| 开课单位: | 斯坦福大学 |
| 开课时间: | 2009-08-26 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Given an m x n matrix A and a rank parameter k, define the leverage of the i-th row of A to be the i-th diagonal element of the projection matrix onto the span of the top k left singular vectors of A. In this case, "high leverage" rows have a disproportionately large amount of the "mass" in the top singular vectors. Historically, this statistical concept (and generalizations of it) has found extensive applications in diagnostic regression analysis. Recently, this concept has also been central in the development of improved randomized algorithms for several fundamental matrix problems that have broad applications in machine learning and data analysis. Two examples of the use of statistical leverage for improved worst-case analysis of matrix algorithms will be described. The first problem is the least squares approximation problem, in which there are n constraints and d variables. Classical algorithms, dating back to Gauss and Legendre, use O(nd2) time. We describe a randomized algorithm that uses only O(n d log d) time to compute a relative-error, i.e., 1+/-epsilon, approximation. The second problem is the problem of selecting a "good" set of exactly k columns from an m x n matrix, and the algorithm of Gu and Eisenstat provides the best previously existing result. We describe a two-stage algorithm that improves on their result. Recent applications of statistical leverage ideas in modern large-scale machine learning and data analysis will also be briefly described. This concept has proven to be particularly fruitful in large data applications where modeling decisions regarding what computations to perform are made for computational reasons, as opposed to having any realistic hope that the statistical assumptions implicit in those computations are satisfied by the data. |
| 关 键 词: | 机器学习; 数据分析; 基本矩阵问题 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-04-23：lxf |
| 阅读次数: | 89 |