Skip to main content

2015 | OriginalPaper | Buchkapitel

Robust Inference and Local Algorithms

verfasst von : Yishay Mansour

Erschienen in: Mathematical Foundations of Computer Science 2015

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We introduce a new feature to inference and learning which we call robustness. By robustness we intuitively model the case that the observation of the learner might be corrupted. We survey a new and novel approach to model such possible corruption as a zero-sum game between an adversary that selects the corruption and a leaner that predict the correct label. The corruption of the observations is done in a worse-case setting, by an adversary, where the main restriction is that the adversary is limited to use one of a fixed know class of modification functions. The main focus in this line of research is on efficient algorithms both for the inference setting and for the learning setting. In order to be efficient in the dimension of the domain, one cannot hope to inspect all the possible inputs. For this, we have to invoke local computation algorithms, that inspect only a logarithmic fraction of the domain per query.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
One can clearly map the dynamic setting to the static setting, by encoding the adversary action in the modification rules, but this will imply that the number of modifications rules would be \(m^{|\mathcal{X}|}\).
 
2
This also implicitly implies that in the dynamic setting \(|\mathcal{X}|/m\le |\mathcal{Z}|\le m |\mathcal{X}|\).
 
Literatur
1.
Zurück zum Zitat Alon, N., Rubinfeld, R., Vardi, S., Xie, N.: Space-efficient local computation algorithms. In: SODA, pp. 1132–1139 (2012) Alon, N., Rubinfeld, R., Vardi, S., Xie, N.: Space-efficient local computation algorithms. In: SODA, pp. 1132–1139 (2012)
2.
Zurück zum Zitat Angluin, D., Laird, P.: Learning from noisy examples. Mach. Learn. 2(4), 343–370 (1988) Angluin, D., Laird, P.: Learning from noisy examples. Mach. Learn. 2(4), 343–370 (1988)
3.
Zurück zum Zitat Ben-Or, M., Linial, N.: Collective coin flipping, robust voting schemes and minima of banzhaf values. In: FOCS, pp. 408–416 (1985) Ben-Or, M., Linial, N.: Collective coin flipping, robust voting schemes and minima of banzhaf values. In: FOCS, pp. 408–416 (1985)
4.
Zurück zum Zitat Ben-Tal, A., El Ghaoui, L., Nemirovski, A.S.: Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2009)CrossRefMATH Ben-Tal, A., El Ghaoui, L., Nemirovski, A.S.: Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2009)CrossRefMATH
5.
Zurück zum Zitat Even, G., Medina, M., Ron, D.: Best of two local models: local centralized and local distributed algorithms. In: CoRR, abs/1402.3796 (2014) Even, G., Medina, M., Ron, D.: Best of two local models: local centralized and local distributed algorithms. In: CoRR, abs/1402.3796 (2014)
6.
Zurück zum Zitat Feige, U., Mansour, Y., Schapire, R.: Learning and inference in the presence of corrupted inputs. In: COLT (2015) Feige, U., Mansour, Y., Schapire, R.: Learning and inference in the presence of corrupted inputs. In: COLT (2015)
7.
Zurück zum Zitat Kahn, J., Kalai, G., Linial, N.: The influence of variables on boolean functions. In: FOCS, pp. 68–80 (1988) Kahn, J., Kalai, G., Linial, N.: The influence of variables on boolean functions. In: FOCS, pp. 68–80 (1988)
9.
Zurück zum Zitat MacKay, D.J.C.: Information Theory. Inference and Learning Algorithms. Cambridge University Press, New York (2002) MacKay, D.J.C.: Information Theory. Inference and Learning Algorithms. Cambridge University Press, New York (2002)
10.
Zurück zum Zitat Mansour, Y., Rubinstein, A., Tennenholtz, M.: Robust probabilistic inference. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4–6, 2015, pp. 449–460 (2015) Mansour, Y., Rubinstein, A., Tennenholtz, M.: Robust probabilistic inference. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4–6, 2015, pp. 449–460 (2015)
11.
Zurück zum Zitat Mansour, Y., Rubinstein, A., Vardi, S., Xie, N.: Converting online algorithms to local computation algorithms. ICALP 1, 653–664 (2012)MathSciNet Mansour, Y., Rubinstein, A., Vardi, S., Xie, N.: Converting online algorithms to local computation algorithms. ICALP 1, 653–664 (2012)MathSciNet
12.
Zurück zum Zitat Mansour, Y., Vardi, S.: A local computation approximation scheme to maximum matching. In: APPROX-RANDOM, pp. 260–273 (2013) Mansour, Y., Vardi, S.: A local computation approximation scheme to maximum matching. In: APPROX-RANDOM, pp. 260–273 (2013)
13.
Zurück zum Zitat Mossel, E., O’Donnell, R., Oleszkiewicz, K.: Noise stability of functions with low influences invariance and optimality. In: FOCS, pp. 21–30 (2005) Mossel, E., O’Donnell, R., Oleszkiewicz, K.: Noise stability of functions with low influences invariance and optimality. In: FOCS, pp. 21–30 (2005)
14.
Zurück zum Zitat Pearl, J.: Causality: Models, Reasoning, and Inference. Cambridge University Press, New York (2000) Pearl, J.: Causality: Models, Reasoning, and Inference. Cambridge University Press, New York (2000)
15.
Zurück zum Zitat Rubinfeld, R., Tamir, G., Vardi, S., Xie, N.: Fast local computation algorithms. In: ICS, pp. 223–238 (2011) Rubinfeld, R., Tamir, G., Vardi, S., Xie, N.: Fast local computation algorithms. In: ICS, pp. 223–238 (2011)
16.
Zurück zum Zitat Valiant, L.G.: Learning disjunction of conjunctions. In: Proceedings of the 9th International Joint Conference on Artificial Intelligence - Volume 1, IJCAI 1985, pp. 560–566 (1985) Valiant, L.G.: Learning disjunction of conjunctions. In: Proceedings of the 9th International Joint Conference on Artificial Intelligence - Volume 1, IJCAI 1985, pp. 560–566 (1985)
Metadaten
Titel
Robust Inference and Local Algorithms
verfasst von
Yishay Mansour
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-48057-1_4