Math 2.0

Computer science Definition

Empirical risk minimization

Builds on Loss functionRisk functionLeast squares

Definition

Let 𝒳\mathcal X and 𝒴\mathcal Y be sets, let L ⁣:𝒴×𝒴→[0,∞)L \colon \mathcal Y \times \mathcal Y \to [0, \infty) be a loss function, and let ℱ\mathcal F be a class of functions f ⁣:𝒳→𝒴f \colon \mathcal X \to \mathcal Y. Let (x1,y1),…,(xn,yn)∈𝒳×𝒴(x_1, y_1), \dots, (x_n, y_n) \in \mathcal X \times \mathcal Y be data. The empirical risk of f∈ℱf \in \mathcal F is Rn(f)=1n∑i=1nL(f(xi),yi).R_n(f) = \frac1n \sum_{i=1}^{n} L(f(x_i), y_i). Empirical risk minimization over ℱ\mathcal F selects a function f^∈ℱ\hat f \in \mathcal F with Rn(f^)=inf⁡f∈ℱRn(f)R_n(\hat f) = \inf_{f \in \mathcal F} R_n(f), when such a function exists.

Remarks

When the data are a random sample from a distribution PP, Rn(f)R_n(f) is an unbiased estimate of the risk R(f)=E[L(f(X),Y)]R(f) = E[L(f(X), Y)] for each fixed ff. For the selected f^\hat f, however, Rn(f^)R_n(\hat f) tends to underestimate R(f^)R(\hat f), because f^\hat f was chosen to fit the same data.

Example: with 𝒳=ℝ\mathcal X = \R, 𝒴=ℝ\mathcal Y = \R, the squared loss L(a,y)=(a−y)2L(a, y) = (a - y)^2 and ℱ={x↦a+bx:a,b∈ℝ}\mathcal F = \set{x \mapsto a + bx : a, b \in \R}, empirical risk minimization is fitting a line by least squares.

Non-example: ridge regression minimises Rn(f)+λ∥β∥2R_n(f) + \lambda \norm{\beta}^2 with λ>0\lambda > 0 over linear functions f(x)=βTxf(x) = \beta^T x. Its minimiser is in general not a minimiser of RnR_n alone, so it is regularized empirical risk minimization, not empirical risk minimization.

Reading path

To understand this page from the ground up, read these 22 pages in order. The foundations come first.

Show the path as a graph
Loss function, concept, no evidence levelLoss functionconceptMatrix, definition, no evidence levelMatrixdefinitionRisk function, concept, no evidence levelRisk functionconceptVector space, definition, no evidence levelVector spacedefinitionTranspose, definition, no evidence levelTransposedefinitionInner product, definition, no evidence levelInner productdefinitionLinear map, definition, no evidence levelLinear mapdefinitionLinear subspace, definition, no evidence levelLinear subspacedefinitionNorm, definition, no evidence levelNormdefinitionInner product space, definition, no evidence levelInner product spacedefinitionOrthogonal vectors, definition, no evidence levelOrthogonal vectorsdefinitionEndomorphism, definition, no evidence levelEndomorphismdefinitionSum of subspaces, definition, no evidence levelSum of subspacesdefinitionNorm induced by an inner product, definition, no evidence levelNorm induced by an in…definitionOrthogonal complement, definition, no evidence levelOrthogonal complementdefinitionDirect sum of subspaces, definition, no evidence levelDirect sum of subspac…definitionA space is the direct sum of a subspace and its orthogonal complement, statement, no evidence levelA space is the direct…statementProjection, definition, no evidence levelProjectiondefinitionOrthogonal projection, definition, no evidence levelOrthogonal projectiondefinitionOrthogonal projection is the closest point, statement, no evidence levelOrthogonal projection…statementLeast squares, concept, no evidence levelLeast squaresconceptEmpirical risk minimization, definition, no evidence levelEmpirical risk minimi…definition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Loss function concept
  2. Matrix definition
  3. Risk function concept
  4. Vector space definition
  5. Transpose definition
  6. Inner product definition
  7. Linear map definition
  8. Linear subspace definition
  9. Norm definition
  10. Inner product space definition
  11. Orthogonal vectors definition
  12. Endomorphism definition
  13. Sum of subspaces definition
  14. Norm induced by an inner product definition
  15. Orthogonal complement definition
  16. Direct sum of subspaces definition
  17. A space is the direct sum of a subspace and its orthogonal complement statement
  18. Projection definition
  19. Orthogonal projection definition
  20. Orthogonal projection is the closest point statement
  21. Least squares concept
  22. Empirical risk minimization definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Empirical_risk_minimization
About this page
TagP4DFMJTD09
URIm2://P4DFMJTD09
Kinddefinition
WritingW0 stub
MSC68Q32, 62H30, 68T05
DefinesEmpirical risk minimization
UsesLoss function, Risk function, Least squares

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.