RELIEF Algorithm

A RELIEF algorithm is an online learning feature weighting algorithm that uses an instance based learning algorithm to assign a relevance weight to each Preditor Feature.

• AKA: RELIEF.
• Context:
  • It uses instance based learning to assign a relevance weight to each feature.
  • It is a specialization of an LFE Algorithm.
  • It uses a margin-based objective function to solve a convex optimization task.
• See: Feature Extraction Algorithm.

---

---

References

2009

• (Sun & Wu, 2009) ⇒ Yijun Sun, and Dapeng Wu. (2009). “Feature Extraction Through Local Learning.” In: Statistical Analysis and Data Mining, 2(1). doi:10.1002/sam.10028
  • RELIEF is considered one of the most successful algorithms for assessing the quality of features. It has been recently proved that RELIEF is an online learning algorithm that solves a convex optimization problem with a margin-based objective function.

2006

• (Sun & Li, 2006) ⇒ Yijun Sun, and J. Li. (2006). “Iterative RELIEF for Feature Weighting.” In: Proceedings of the 23rd International Conference on Machine Learning (ICML 2006). doi:10.1145/1143844.1143959
  • CITED BY ~57 http://scholar.google.com/scholar?q=%22Iterative+RELIEF+for+Feature+Weighting%22+2006

2003

• (Guyon & Elisseeff, 2003) ⇒ Isabelle M. Guyon, and André Elisseeff. (2003). “An Introduction to Variable and Feature Selection.” In: The Journal of Machine Learning Research, 3.
  • QUOTE: The relief algorithm uses another approach based on the nearest-neighbor algorithm (Kira and Rendell, 1992). For each example, the closest example of the same class (nearest hit) and the closest example of a different class (nearest miss) are selected. The score [math]\displaystyle{ S(i) }[/math] of the [math]\displaystyle{ i^{th} }[/math] variable is computed as the average over all examples of magnitude of the difference between the distance to the nearest hit and the distance to the nearest miss, in projection on the [math]\displaystyle{ i^{th} }[/math] variable.

1992

• (Kira & Rendell, 1992) ⇒ Kenji Kira, and Larry A. Rendell. (1992). “A Practical Approach to Feature Selection.” In: Proceedings of the 9th International Conference on Machine Learning (ICML 1992).
  • NOTES: It describes a statistical feature selection algorithm called RELIEF that uses instance based learning to assign a relevance weight to each feature.
  • CITED BY ~914 http://scholar.google.com/scholar?q=%22A+Practical+Approach+to+Feature+Selection%22+1992
  • ABSTRACT: In real-world concept learning problems, the representation of data often uses many features, only a few of which may be related to the target concept. In this situation, feature selection is important both to speed up learning and to improve concept quality. A new feature selection algorithm Relief uses a statistical method and avoids heuristic search. Relief requires linear time in the number of given features and the number of training instances regardless of the target concept to be learned. Although the algorithm does not necessarily find the smallest subset of features, the size tends to be small because only statistically relevant features are selected. This paper focuses on empirical test results in two artificial domains; the LED Display domain and the Parity domain with and without noise. Comparison with other feature selection algorithms shows Relief's advantages in terms of learning time and the accuracy of the learned concept, suggesting Relief's practicality

---