Necessary and Sufficient Conditions of &epsilon;-Separability

Maria A. Ivanchuk; Igor V. Malyk

doi:doi:10.11648/j.ijtam.20160202.11

| Peer-Reviewed

Necessary and Sufficient Conditions of ε-Separability

Maria A. Ivanchuk, Igor V. Malyk

Published in International Journal of Theoretical and Applied Mathematics (Volume 2, Issue 2)

Received: 13 September 2016 Accepted: 28 October 2016 Published: 21 November 2016

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

In this paper we propose a new approach for solving the classification problem, which is based on the using ε-nets theory. It is shown that for ε-separating of two sets one can use their ε-nets in the range space w.r.t. halfspaces, which considerably reduce the complexity of the separating algorithm for large sets’ sizes. The separation space which contains the possible values of ε for ε-nets of both sets is considered. The separation space is quasi-convex in general case. To check necessary and sufficient conditions of ε-separability of two sets one can solve an optimisation problem, using the separation space as constraints. The lower bound of the separation space is convex for the exponential distribution and linear for the uniform distribution. So, we have convex and linear optimisation problems in these cases.

Published in	International Journal of Theoretical and Applied Mathematics (Volume 2, Issue 2)
DOI	10.11648/j.ijtam.20160202.11
Page(s)	28-34
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2016. Published by Science Publishing Group

Keywords

ε-nets, Separability, Quasiconvexity

References

[1]	Haussler D. and Welzl E. “Epsilon-nets and simplex range queries”, Discrete Comput. Geom., 1987, №2, p.p. 127–151.
[2]	Aronov B., Ezra E., Sharir M. “Small-size epsilon-nets for axis-parallel rectangles and boxes”, Symposium on Theory of Computing, 2009, p.p. 639–648.
[3]	Gärtner B., Hoffmann M. Computational Geometry, http://www.ti.inf.ethz.ch/ew/lehre/CG12/lecture/CG%20lecture%20notes.pdf.
[4]	Hausler S. VC Dimension. A Tutorial for the Course Computational Intelligence, http://www.igi.tugraz.at/lehre/CI.
[5]	Kulkarni J., Govindarajan S. “New -Net Constructions”, Canadian Conference on Computational Geometry (CCCG), 2010, P.P.159-162.
[6]	Matousek J., Seidel R., Welzl E. “How to Net a Lot with Little:Small -Nets for Disks and Halfspaces” In Proc. sixth annual symposium on Computational geometry, 1990, P.P. 16–22.
[7]	Ivanchuk M.A., Malyk I.V. “Solving the Classification Problem Using ε-nets”, Cybernetics and Systems Analysis, Vol.52, Iss.4 (2016), p.p. 613-622.
[8]	M. A. Ivanchuk, I. V. Malyk “Using ε-Nets for Linear Separation of Two Sets in a Euclidean Space R d “ , Cybernetics and Systems Analysis, Vol.51, Iss.6, 2015, P.P. 965-968. - DOI 10.1007/s10559-015-9789-7.
[9]	Embrechts P., Hofert M. “A note on generalized inverses”, Mathematical Methods of Operations Research , 2013, 77(3), 423-432.
[10]	Boyd S., Vandenberghe L. Convex Optimization, Cambridge University Press, 2009, 716 p.

Cite This Article

Plain Text BibTeX RIS

APA Style

Maria A. Ivanchuk, Igor V. Malyk. (2016). Necessary and Sufficient Conditions of ε-Separability. International Journal of Theoretical and Applied Mathematics, 2(2), 28-34. https://doi.org/10.11648/j.ijtam.20160202.11

Copy | Download

ACS Style

Maria A. Ivanchuk; Igor V. Malyk. Necessary and Sufficient Conditions of ε-Separability. Int. J. Theor. Appl. Math. 2016, 2(2), 28-34. doi: 10.11648/j.ijtam.20160202.11

Copy | Download

AMA Style

Maria A. Ivanchuk, Igor V. Malyk. Necessary and Sufficient Conditions of ε-Separability. Int J Theor Appl Math. 2016;2(2):28-34. doi: 10.11648/j.ijtam.20160202.11

Copy | Download

@article{10.11648/j.ijtam.20160202.11,
  author = {Maria A. Ivanchuk and Igor V. Malyk},
  title = {Necessary and Sufficient Conditions of ε-Separability},
  journal = {International Journal of Theoretical and Applied Mathematics},
  volume = {2},
  number = {2},
  pages = {28-34},
  doi = {10.11648/j.ijtam.20160202.11},
  url = {https://doi.org/10.11648/j.ijtam.20160202.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijtam.20160202.11},
  abstract = {In this paper we propose a new approach for solving the classification problem, which is based on the using ε-nets theory. It is shown that for ε-separating of two sets one can use their ε-nets in the range space w.r.t. halfspaces, which considerably reduce the complexity of the separating algorithm for large sets’ sizes. The separation space which contains the possible values of ε for ε-nets of both sets is considered. The separation space is quasi-convex in general case. To check necessary and sufficient conditions of ε-separability of two sets one can solve an optimisation problem, using the separation space as constraints. The lower bound of the separation space is convex for the exponential distribution and linear for the uniform distribution. So, we have convex and linear optimisation problems in these cases.},
 year = {2016}
}

Copy | Download

TY  - JOUR
T1  - Necessary and Sufficient Conditions of ε-Separability
AU  - Maria A. Ivanchuk
AU  - Igor V. Malyk
Y1  - 2016/11/21
PY  - 2016
N1  - https://doi.org/10.11648/j.ijtam.20160202.11
DO  - 10.11648/j.ijtam.20160202.11
T2  - International Journal of Theoretical and Applied Mathematics
JF  - International Journal of Theoretical and Applied Mathematics
JO  - International Journal of Theoretical and Applied Mathematics
SP  - 28
EP  - 34
PB  - Science Publishing Group
SN  - 2575-5080
UR  - https://doi.org/10.11648/j.ijtam.20160202.11
AB  - In this paper we propose a new approach for solving the classification problem, which is based on the using ε-nets theory. It is shown that for ε-separating of two sets one can use their ε-nets in the range space w.r.t. halfspaces, which considerably reduce the complexity of the separating algorithm for large sets’ sizes. The separation space which contains the possible values of ε for ε-nets of both sets is considered. The separation space is quasi-convex in general case. To check necessary and sufficient conditions of ε-separability of two sets one can solve an optimisation problem, using the separation space as constraints. The lower bound of the separation space is convex for the exponential distribution and linear for the uniform distribution. So, we have convex and linear optimisation problems in these cases.
VL  - 2
IS  - 2
ER  -

Copy | Download

Author Information

Maria A. Ivanchuk

Department of Biological Physics and Medical Informatics, Bucovinian State Medical University, Chernivtsi, Ukraine
Igor V. Malyk

Department of the System and Analysis and Insurance Financial Mathematics, Yuriy Fedkovych Chernivtsi National University, Chernivtsi, Ukraine

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Maria A. Ivanchuk, Igor V. Malyk. (2016). Necessary and Sufficient Conditions of ε-Separability. International Journal of Theoretical and Applied Mathematics, 2(2), 28-34. https://doi.org/10.11648/j.ijtam.20160202.11

Copy | Download

ACS Style

Maria A. Ivanchuk; Igor V. Malyk. Necessary and Sufficient Conditions of ε-Separability. Int. J. Theor. Appl. Math. 2016, 2(2), 28-34. doi: 10.11648/j.ijtam.20160202.11

Copy | Download

AMA Style

Maria A. Ivanchuk, Igor V. Malyk. Necessary and Sufficient Conditions of ε-Separability. Int J Theor Appl Math. 2016;2(2):28-34. doi: 10.11648/j.ijtam.20160202.11

Copy | Download

@article{10.11648/j.ijtam.20160202.11,
  author = {Maria A. Ivanchuk and Igor V. Malyk},
  title = {Necessary and Sufficient Conditions of ε-Separability},
  journal = {International Journal of Theoretical and Applied Mathematics},
  volume = {2},
  number = {2},
  pages = {28-34},
  doi = {10.11648/j.ijtam.20160202.11},
  url = {https://doi.org/10.11648/j.ijtam.20160202.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijtam.20160202.11},
  abstract = {In this paper we propose a new approach for solving the classification problem, which is based on the using ε-nets theory. It is shown that for ε-separating of two sets one can use their ε-nets in the range space w.r.t. halfspaces, which considerably reduce the complexity of the separating algorithm for large sets’ sizes. The separation space which contains the possible values of ε for ε-nets of both sets is considered. The separation space is quasi-convex in general case. To check necessary and sufficient conditions of ε-separability of two sets one can solve an optimisation problem, using the separation space as constraints. The lower bound of the separation space is convex for the exponential distribution and linear for the uniform distribution. So, we have convex and linear optimisation problems in these cases.},
 year = {2016}
}

Copy | Download

TY  - JOUR
T1  - Necessary and Sufficient Conditions of ε-Separability
AU  - Maria A. Ivanchuk
AU  - Igor V. Malyk
Y1  - 2016/11/21
PY  - 2016
N1  - https://doi.org/10.11648/j.ijtam.20160202.11
DO  - 10.11648/j.ijtam.20160202.11
T2  - International Journal of Theoretical and Applied Mathematics
JF  - International Journal of Theoretical and Applied Mathematics
JO  - International Journal of Theoretical and Applied Mathematics
SP  - 28
EP  - 34
PB  - Science Publishing Group
SN  - 2575-5080
UR  - https://doi.org/10.11648/j.ijtam.20160202.11
AB  - In this paper we propose a new approach for solving the classification problem, which is based on the using ε-nets theory. It is shown that for ε-separating of two sets one can use their ε-nets in the range space w.r.t. halfspaces, which considerably reduce the complexity of the separating algorithm for large sets’ sizes. The separation space which contains the possible values of ε for ε-nets of both sets is considered. The separation space is quasi-convex in general case. To check necessary and sufficient conditions of ε-separability of two sets one can solve an optimisation problem, using the separation space as constraints. The lower bound of the separation space is convex for the exponential distribution and linear for the uniform distribution. So, we have convex and linear optimisation problems in these cases.
VL  - 2
IS  - 2
ER  -

Copy | Download