PaperlayerView exact revision on arXiv

Source-linked AI summary

Is Extreme Learning Machine Feasible? A Theoretical Assessment (Part II)

Shaobo Lin, Xia Liu, Jian Fang, Zongben Xu

arXiv:1401.6240v1cs.LG

TL;DR

The paper asks whether ELM’s computationally simple training preserves generalization in theory, beyond earlier results for appropriately chosen activations. It analyzes ELM’s disadvantages and remedies, finding randomness-related uncertainty and Gaussian-kernel generalization degradation, with regularization improving the latter.

  • Problem

    The theoretical feasibility of ELM remains underexamined despite prior results that appropriate activation functions preserve generalization capability in expectation.

    Source: §I · p. 1

  • Method

    The paper theoretically analyzes ELM’s advantages and disadvantages, including its randomness-related uncertainty and Gaussian-kernel generalization, and examines remedies.

    Source: §I · p. 1

  • Results

    ELM’s randomness produces uncertainty in approximation and learning, and Gaussian-kernel ELM degrades generalization relative to FNN; l2 coefficient regularization can improve that capability.

    Source: §I · p. 1, §VI · p. 13

  • Takeaways & Limitations

    Multiple training trials can address uncertainty, while l2 coefficient regularization can improve Gaussian-kernel ELM generalization.

    Source: §I · pp. 1–2

Abstract

from arXiv · show

An extreme learning machine (ELM) can be regarded as a two stage feed-forward neural network (FNN) learning system which randomly assigns the connections with and within hidden neurons in the first stage and tunes the connections with output neurons in the second stage. Therefore, ELM training is essentially a linear learning problem, which significantly reduces the computational burden. Numerous applications show that such a computation burden reduction does not degrade the generalization capability. It has, however, been open that whether this is true in theory. The aim of our work is to study the theoretical feasibility of ELM by analyzing the pros and cons of ELM. In the previous part on this topic, we pointed out that via appropriate selection of the activation function, ELM does not degrade the generalization capability in the expectation sense. In this paper, we launch the study in a different direction and show that the randomness of ELM also leads to certain negative consequences. On one hand, we find that the randomness causes an additional uncertainty problem of ELM, both in approximation and learning. On the other hand, we theoretically justify that there also exists an activation function such that the corresponding ELM degrades the generalization capability. In particular, we prove that the generalization capability of ELM with Gaussian kernel is essentially worse than that of FNN with Gaussian kernel. To facilitate the use of ELM, we also provide a remedy to such a degradation. We find that the well-developed coefficient regularization technique can essentially improve the generalization capability. The obtained results reveal the essential characteristic of ELM and give theoretical guidance concerning how to use ELM.

I. INTRODUCTION

The paper examines ELM’s theoretical feasibility beyond earlier results showing that suitable activation functions can preserve generalization in expectation. It identifies randomness-related uncertainty and Gaussian-kernel generalization degradation, then describes remedies for both.

A. Extreme learning machine

  • ELM randomly fixes hidden-neuron connections and tunes output connections, reducing training to a linear problem solved by least squares in the classical system studied here.The paper’s classical ELM analysis focuses on this system rather than its variants.Source: §I · p. 1, A. Extreme learning machine · p. 2

I. INTRODUCTION

  • ELM’s randomness creates uncertainty in approximation and learning, while Gaussian-kernel ELM can degrade generalization relative to classical FNN learning; repeated trials and l2 regularization are proposed as remedies.For Gaussian kernels, the stated regularization remedy adds neurons and uses l2 coefficient regularization; an appropriately tuned parameter can yield an almost optimal FNN learning rate in expectation.Source: §I · pp. 1–2

B. An uncertainty problem for ELM approximation

  • For Gaussian-kernel ELM approximation, increasing σ raises both approximation error and confidence, creating a trade-off that prevents small error from being guaranteed at arbitrarily high confidence.The suggested setting σ^2d = n^(1−ε) gives an asymptotic bound involving the smoothness modulus and n^((−1+ε)/2), with confidence at least 1 − 2exp{−cn^ε} under stated smoothness conditions.Source: B. An uncertainty problem for ELM… · p. 3

III. A GENERALIZATION DEGRADATION PROBLEM OF ELM WITH GAUSSIAN KERNEL

The paper analyzes ELM’s generalization capability using statistical learning theory. It reports a degradation phenomenon, specifically that Gaussian-kernel ELM degrades generalization capability relative to FNN.

III. A GENERALIZATION DEGRADATION PROBLEM OF ELM WITH GAUSSIAN KERNEL

  • The analysis follows a statistical learning theory framework to examine ELM’s generalization capability.The paper contrasts this result with the earlier analysis in.Source: §III · p. 3
  • The analysis finds that ELM can exhibit a generalization degradation phenomenon.Source: §III · p. 3
  • With a Gaussian kernel, ELM degrades generalization capability relative to FNN.Source: §III · p. 3

A. A fast review of statistical learning theory

This section sets out a statistical learning setting in which samples are drawn independently from an unknown distribution. It introduces the prediction function and generalization error, while noting that the ideal minimizer is unknown although random examples are available.

A. A fast review of statistical learning theory

B. The generalization capability of ELM with Gaussian kernel

For Gaussian-kernel ELM, the expected learning-error bound exposes a trade-off between generalization error and confidence. The paper argues that this rate is essentially worse than Gaussian-kernel FNN’s, and that the derived rate is nearly optimal in the univariate case.

B. The generalization capability of ELM with Gaussian kernel

  • Theorem 2 bounds expected learning error with a confidence level that depends on ε, so extremely small generalization error and high confidence cannot both be obtained.The expectation is over training-sample realizations for fixed sample size; choosing ε small gives a rate close to m^-r/(2r+d), up to a logarithmic factor.Source: B. The generalization capability of… · p. 4
  • The ELM learning rate cannot be essentially improved in the univariate case: its upper and lower bounds are asymptotically identical modulo ε and a logarithmic factor.The lower-bound argument is presented for d = s = 1.Source: B. The generalization capability of… · p. 4
  • The neuron count is selected to balance approximation error against sample error, the bias–variance trade-off used to justify its choice.The paper also argues that the kernel parameter σ is selected optimally based on the approximation uncertainty analysis.Source: B. The generalization capability of… · p. 4
  • Gaussian-kernel ELM’s learning rate cannot be faster than m^-r/(r+d), versus m^-2r/(2r+d) for FNN; with equal neuron counts, ELM’s rate is worse still.The paper concludes that Gaussian-kernel ELM degrades generalization capability relative to FNN, even when ELM uses more neurons.Source: B. The generalization capability of… · p. 4

IV. REMEDY OF THE DEGRADATION

The section addresses Gaussian-kernel ELM’s generalization degradation by applying l2 coefficient regularization in the output stage. With an appropriately adjusted neuron count and regularization parameter, the estimator can attain an almost optimal learning rate, at a higher neuron cost than FNN.

IV. REMEDY OF THE DEGRADATION

  • The remedy applies l2 coefficient regularization in ELM’s second stage, where output-neuron connections are determined.The estimator uses a positive regularization parameter λ; the theorem’s result requires its conditions and neuron count to be appropriately set.Source: §IV · p. 4
  • With l2 coefficient regularization, Gaussian-kernel ELM can attain the almost optimal learning rate m^(-2r/(2r+d)) with high probability, up to an arbitrary ε and a logarithmic factor.The paper compares this rate with the best rates of SVM and FNN using Gaussian kernels and describes the regularized ELM as an almost optimal FNN learning strategy.Source: §IV · p. 5
  • Matching the stated optimal learning rate requires substantially more neurons in regularized ELM than in traditional FNN learning.The paper identifies this increased neuron requirement as a higher price than FNN pays for the rate.Source: §IV · p. 5

A. Proof of Theorem 1

The proof of Theorem 1 assembles probabilistic inequalities and approximation estimates into error bounds for random sampling. Its lemmas include numerical integration formulas for polynomial classes and a confidence-qualified error estimate.

A. Proof of Theorem 1

  • Random samples yield probabilistic numerical integral formulas for trigonometric and algebraic polynomials.The argument builds these formulas from sampling and norm-generation results.Source: A. Proof of Theorem 1 · p. 6
  • Lemma 9 considers a > 0, u,l ∈ N, and n iid samples from μ on [−a, 1 + a], and states a result with confidence at least 1 − 2 exp{−cn/(u + l)^d}.Source: A. Proof of Theorem 1 · p. 7
  • The proof combines nine lemmas to establish Theorem 1’s probabilistic result.The lemmas include bounds for random sampling and approximation, culminating in a confidence-qualified estimate.Source: A. Proof of Theorem 1 · pp. 5, 8

B. Proof of Proposition 1

The proof of Proposition 1 establishes a one-dimensional lower bound on approximation by the Gaussian-kernel space Hσ,1,n. It uses approximation and Bernstein-type arguments to show that the bound cannot be improved beyond the stated rate.

B. Proof of Proposition 1

  • The proof uses a Bernstein inequality for Hσ,1,n and a lemma linking sufficiently small approximation error to membership in F_r.The latter implication is used to obtain a contradiction in the lower-bound argument.Source: B. Proof of Proposition 1 · pp. 8–9
  • The argument concludes that the lower bound holds uniformly over F_r, with C independent of n.The proof first assumes a contrary approximation bound and derives an impossible membership conclusion.Source: B. Proof of Proposition 1 · p. 9
  • For d = 1, s = 1, and σ ≥ n^(-1/2), the approximation error over the class F_r is at least Cn^(-r/2−ε).The proposition states this lower bound for the supremum over f in F_r and the infimum over g in Hσ,1,n.Source: B. Proof of Proposition 1 · pp. 8–9

C. Proof of Theorem 2

The proof of Theorem 2 combines a dimension-based estimate with the approximation result from Theorem 1 to bound the learning error. It then chooses the kernel scale in terms of sample size and ε to obtain a confidence-qualified bound.

C. Proof of Theorem 2

  • The proof relies on a covering-number lemma for the n-dimensional linear space Hσ,s,n.The lemma supplies the dimension-based step used to control the learning error.Source: C. Proof of Theorem 2 · p. 9
  • The proof bounds the learning error by combining a dimension-based estimate for Hσ,s,n with the approximation result from Theorem 1.The argument applies the result to fρ in F_r, with r ≤ s.Source: C. Proof of Theorem 2 · p. 9
  • Setting σ = n(−1+ε)/(2d), the passage says a statement holds with probability at least 1 −2 exp{−nε}, though the supplied excerpt does not identify that statement.Source: C. Proof of Theorem 2 · p. 9

D. Proof of Proposition 2

The proof uses interpolation and Bernstein-type lemmas to establish a lower bound for approximation by the Gaussian-kernel ELM hypothesis space. Its intermediate result relates membership in the approximation class to distance from that space.

D. Proof of Proposition 2

  • The proof of Lemma 14 uses the interpolation theorem for linear functionals and applies a convexity inequality with φ(x) = x².Lemma 14 is presented as a Bernstein inequality for the Gaussian-kernel ELM hypothesis space.Source: D. Proof of Proposition 2 · p. 10
  • Under the stated conditions, the distance condition in Lemma 15 implies that f belongs to F_r.The lemma specifies d = 1, s = 1, and σ ≥ n^(−1/2).Source: D. Proof of Proposition 2 · p. 10
  • The proof establishes a lower bound on worst-case approximation error over F_r in Hσ,1,n.The bound is stated as sup_f∈F_r inf_g∈Hσ,1,n ||f−g||ρ ≥ Cn^(−r/2−ε).Source: D. Proof of Proposition 2 · p. 10

E. Proof of Theorem 3

The proof of Theorem 3 combines covering-number bounds and concentration inequalities with an approximation result for the ELM hypothesis space. It derives a bound holding jointly with high confidence over the sample and randomization.

E. Proof of Theorem 3

  • Lemma 19 supplies an approximant f0 in Hσ,s,n with confidence at least 1−2 exp{−cnσ²d}.The proof then uses this approximant in its definition of fz,σ,s,λ,n.Source: E. Proof of Theorem 3 · p. 11
  • The proof bounds its concentration terms using a variance estimate and an empirical covering-number bound for a function class.It invokes Lemma 18 for the variance-controlled term and Lemma 17 for the covering-number term.Source: E. Proof of Theorem 3 · pp. 11–12
  • The proof combines approximation and concentration bounds to obtain a final inequality holding with confidence at least (1−δ) × (1−2 exp{−cnσ²d}).The confidence is with respect to ρm × μn.Source: E. Proof of Theorem 3 · pp. 11–12

VI. CONCLUSIONS

The conclusions report theoretical uncertainty and generalization degradation for ELM, alongside remedies for both. They also leave open a general criterion for classifying activation functions by their effect on generalization.

VI. CONCLUSIONS

  • ELM's theoretical performance depends heavily on its activation function and randomness mechanism.The authors contrast this paper's disadvantages with the prior result that appropriately selected activation functions avoid expectation-sense degradation.Source: §VI · pp. 12–13
  • The paper concludes that ELM can suffer uncertainty and generalization degradation, including degradation with Gaussian-type activation.Multiple trials are recommended for uncertainty, while l2 coefficient regularization is reported to improve generalization.Source: §VI · p. 13
  • A general condition classifying activation functions by whether their ELM degrades generalization remains an open question.The authors state that enumerating all activation functions is not possible and identify a classification criterion as future work.Source: §VI · p. 13
Loading 1401.6240v1…