Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Managing Natural Noise in Recommender Systems Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

A Quantum Annealing Approach to Biclustering

verfasst von : Lorenzo Bottarelli, Manuele Bicego, Matteo Denitto, Alessandra Di Pierro, Alessandro Farinelli

Erschienen in: Theory and Practice of Natural Computing

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Several problem in Artificial Intelligence and Pattern Recognition are computationally intractable due to their inherent complexity and the exponential size of the solution space. One example of such problems is biclustering, a specific clustering problem where rows and columns of a data-matrix must be clustered simultaneously. Quantum information processing could provide a viable alternative to combat such a complexity. A notable work in this direction is the recent development of the D-Wave™  computer, whose processor is able to exploit quantum mechanical effects in order to perform quantum annealing. The question motivating this work is whether the use of this special hardware is a viable approach to efficiently solve the biclustering problem. As a first step towards the solution of this problem, we show a feasible encoding of biclustering into the D-Wave™  quantum annealing hardware, and provide a theoretical analysis of its correctness.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Implementation of Turing Machine Using DNA Strand Displacement
Nächstes Kapitel Determining Player Skill in the Game of Go with Deep Neural Networks
Fußnoten
1
According to the quantum adiabatic theorem, a quantum system that begins in the non-degenerate ground state of a time-dependent Hamiltonian will remain in the instantaneous ground state provided the Hamiltonian changes sufficiently slowly.
 
Literatur
1.
Ayadi, W., Elloumi, M., Hao, J.: Bimine+: An efficient algorithm for discovering relevant biclusters of DNA microarray data. Knowl. Based Syst. 35, 224–234 (2012)CrossRef
2.
Badea, L.: Generalized clustergrams for overlapping biclusters. In: IJCAI, pp. 1383–1388 (2009)
3.
Barahona, F.: On the computational complexity of Ising spin glass models. J. Phys. A: Math. Gen. 15(10), 3241–3253 (1982)MathSciNetCrossRef
4.
Ben-Dor, A., Chor, B., Karp, R., Yakhini, Z.: Discovering local structure in gene expression data: The order-preserving submatrix problem. J. Comput. Biol. 10(3–4), 373–384 (2003)CrossRef
5.
Bicego, M., Lovato, P., Ferrarini, A., Delledonne, M.: Biclustering of expression microarray data with topic models. In: International Conference on Pattern Recognition (ICPR2010), pp. 2728–2731 (2010)
6.
Cai, J., Macready, W.G., Roy, A.: A practical heuristic for finding graph minors. ArXiv e-prints, June 2014
7.
Cheng, Y., Church, G.: Biclustering of expression data. In: Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology (ISMB00), pp. 93–103 (2000)
8.
9.
Denchev, V.S., Boixo, S., Isakov, S.V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., Neven, H.: What is the computational value of finite-range tunneling? Phys. Rev. X 6(3), 031015 (2016)
10.
Denitto, M., Farinelli, A., Franco, G., Bicego, M.: A binary factor graph model for biclustering. In: Fränti, P., Brown, G., Loog, M., Escolano, F., Pelillo, M. (eds.) S+SSPR 2014. LNCS, vol. 8621, pp. 394–403. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44415-3_​40
11.
Dhillon, I.: Coclustering documents and words using bipartite spectral graph partitioning. In: Proceedings of the International Conference on Knowledge Discovery and Data Mining, pp. 269–274 (2001)
12.
Dolnicar, S., Kaiser, S., Lazarevski, K., Leisch, F.: Biclustering : overcoming data dimensionality problems in market segmentation. J. Travel Res. Q. Publ. Travel Tourism Res. Assoc. 51(1), 41–49 (2012)
13.
14.
Finnila, A.B., Gomez, M.A., Sebenik, C., Stenson, C., Doll, J.D.: Quantum annealing: A new method for minimizing multidimensional functions. Chem. Phys. Lett. 219, 343–348 (1994)CrossRef
15.
Flores, J.L., Inza, I., Larranaga, P., Calvo, B.: A new measure for gene expression biclustering based on non-parametric correlation. Comput. Methods Programs Biomed. 112(3), 367–397 (2013)CrossRef
16.
Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58(5), 5355–5363 (1998)CrossRef
17.
Kochenberger, G., Hao, J., Glover, F., Lewis, M., Lü, Z., Wang, H., Wang, Y.: The unconstrained binary quadratic programming problem: a survey. J. Comb. Optim. 28(1), 58–81 (2014)MathSciNetCrossRefMATH
18.
Kurihara, K., Tanaka, S., Miyashita, S.: Quantum annealing for clustering. In: Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pp. 321–328. UAI 2009, AUAI Press, Arlington, Virginia, United States (2009)
19.
Madeira, S., Oliveira, A.: Biclustering algorithms for biological data analysis: a survey. IEEE Trans. Comput. Biol. Bioinform. 1, 24–44 (2004)CrossRef
20.
Mukhopadhyay, A., Maulik, U., Bandyopadhyay, S., Coello, C.: Survey of multiobjective evolutionary algorithms for data mining: Part ii. Evol. Comput. IEEE Trans. 18(1), 20–35 (2014)CrossRef
21.
Neven, H., Rose, G., Macready, W.G.: Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization, ArXiv e-prints, April 2008
22.
23.
24.
Prelić, A., Bleuler, S., Zimmermann, P., Wille, A., Bühlmann, P., Gruissem, W., Hennig, L., Thiele, L., Zitzler, E.: A systematic comparison and evaluation of biclustering methods for gene expression data. Bioinformatics 22(9), 1122–1129 (2006)CrossRef
25.
Rieffel, E.G., Venturelli, D., O’Gorman, B., Do, M.B., Prystay, E.M., Smelyanskiy, V.N.: A case study in programming a quantum annealer for hard operational planning problems. Quantum Inform. Process. 14, 1–36 (2015)CrossRefMATH
26.
Santoro, G.E., Tosatti, E.: Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J. Phys. A Math. Gen. 39(36), R393–R431 (2006)MathSciNetCrossRefMATH
27.
Tu, K., Ouyang, X., Han, D., Honavar, V.: Exemplar-based robust coherent biclustering. In: SDM, pp. 884–895. SIAM (2011)
Metadaten
Titel
A Quantum Annealing Approach to Biclustering
verfasst von
Lorenzo Bottarelli
Manuele Bicego
Matteo Denitto
Alessandra Di Pierro
Alessandro Farinelli
Copyright-Jahr
2016
Buch
Theory and Practice of Natural Computing

Print ISBN: 978-3-319-49000-7

Electronic ISBN: 978-3-319-49001-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-49001-4_14

Premium Partner

    Bildnachweise