- -

Semi-Lipschitz functions and machine learning for discrete dynamical systems on graphs

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

Semi-Lipschitz functions and machine learning for discrete dynamical systems on graphs

Mostrar el registro sencillo del ítem

Ficheros en el ítem

Thumbnail
Nombre: FalcianiSanchez - ...
Tamaño: 1.726Mb
Formato: PDF
Descripción: Versión editorial
Abrir
dc.contributor.author Falciani, H. es_ES
dc.contributor.author Sánchez Pérez, Enrique Alfonso es_ES
dc.date.accessioned 2023-07-14T18:01:24Z
dc.date.available 2023-07-14T18:01:24Z
dc.date.issued 2022-05 es_ES
dc.identifier.issn 0885-6125 es_ES
dc.identifier.uri http://hdl.handle.net/10251/195001
dc.description.abstract [EN] Consider a directed tree U and the space of all finite walks on it endowed with a quasi-pseudo-metric-the space of the strategies S on the graph,-which represent the possible changes in the evolution of a dynamical system over time. Consider a reward function acting in a subset S-0 subset of S which measures the success. Using well-known facts of the theory of semi-Lipschitz functions in quasi-pseudo-metric spaces, we extend the reward function to the whole space S. We obtain in this way an oracle function, which gives a forecast of the reward function for the elements of S, that is, an estimate of the degree of success for any given strategy. After explaining the fundamental properties of a specific quasi-pseudo-metric that we define for the (graph) trees (the bifurcation quasi-pseudo-metric), we focus our attention on analyzing how this structure can be used to represent dynamical systems on graphs. We begin the explanation of the method with a simple example, which is proposed as a reference point for which some variants and successive generalizations are consecutively shown. The main objective is to explain the role of the lack of symmetry of quasi-metrics in our proposal: the irreversibility of dynamical processes is reflected in the asymmetry of their definition. es_ES
dc.description.sponsorship Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Support of Tactical Whistleblower, KPI, and Observatori de Transparencia y Gestio de Dades, Generalitat Valenciana-UPV. es_ES
dc.language Inglés es_ES
dc.publisher Springer-Verlag es_ES
dc.relation.ispartof Machine Learning es_ES
dc.rights Reconocimiento (by) es_ES
dc.subject Graph distance es_ES
dc.subject Quasi-pseudo-metric es_ES
dc.subject Reinforcement learning es_ES
dc.subject Lipschitz function es_ES
dc.subject Bifurcation metric es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title Semi-Lipschitz functions and machine learning for discrete dynamical systems on graphs es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s10994-022-06130-x es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos - Escola Tècnica Superior d'Enginyers de Camins, Canals i Ports es_ES
dc.description.bibliographicCitation Falciani, H.; Sánchez Pérez, EA. (2022). Semi-Lipschitz functions and machine learning for discrete dynamical systems on graphs. Machine Learning. 111(5):1765-1797. https://doi.org/10.1007/s10994-022-06130-x es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1007/s10994-022-06130-x es_ES
dc.description.upvformatpinicio 1765 es_ES
dc.description.upvformatpfin 1797 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 111 es_ES
dc.description.issue 5 es_ES
dc.relation.pasarela S\484594 es_ES
dc.contributor.funder Universitat Politècnica de València es_ES
dc.description.references Asadi, K., Misra, D., & Littman, M.L. (2018). Lipschitz continuity in model-based reinforcement learning. arXiv preprint arXiv:180407193. es_ES
dc.description.references Barnes, J. A., & Harary, F. (1983). Graph theory in network analysis. Social Networks, 5(2), 235–244. es_ES
dc.description.references Barrett, C. L., Chen, W. Y., & Zheng, M. J. (2004). Discrete dynamical systems on graphs and boolean functions. Mathematics and Computers in Simulation, 66(6), 487–497. es_ES
dc.description.references Bellman, R. (1957). Dynamic programming. Princeton University Press. es_ES
dc.description.references Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87–90. es_ES
dc.description.references Bondy, J. A., & Murty, U. S. R. (1976). Graph theory with applications. Macmillan. es_ES
dc.description.references Boutilier, C. (1999). Sequential optimality and coordination in multiagent systems. IJCAI, 99, 478–485. es_ES
dc.description.references Brandes, U. (2005). Network analysis: methodological foundations (Vol. 3418). Springer. es_ES
dc.description.references Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A., & Vandergheynst, P. (2017). Geometric deep learning: Going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4), 18–42. es_ES
dc.description.references Buckley, F., & Harary, F. (1990). Distance in graphs. Addison-Wesley. es_ES
dc.description.references Bunke, H., & Shearer, K. (1998). A graph distance metric based on the maximal common subgraph. Pattern Recognition Letters, 19(3–4), 255–259. es_ES
dc.description.references Bu, C., Yan, B., Zhou, X., & Zhou, J. (2014). Resistance distance in subdivision-vertex join and subdivision-edge join of graphs. Linear Algebra and its Applications, 485, 454–462. es_ES
dc.description.references Calabuig, J. M., Falciani, H., & Sánchez-Pérez, E. A. (2020). Dreaming machine learning: Lipschitz extensions for reinforcement learning on financial markets. Neurocomputing, 398, 172–184. es_ES
dc.description.references Camacho-Collados, J., & Pilehvar, M. T. (2018). From word to sense embeddings: A survey on vector representations of meaning. Journal of Artificial Intelligence Research, 63, 743–788. es_ES
dc.description.references Cao, Q., Ying, Y., & Li, P. (2012). Distance metric learning revisited. Joint European Conference on Machine Learning and Knowledge Discovery in Databases (pp. 283–298). Springer. es_ES
dc.description.references Cao, S., Lu, W., & Xu, Q. (2016). Deep neural networks for learning graph representations. AAAI, 16, 1145–1152. es_ES
dc.description.references Casteigts, A., Flocchini, P., Quattrociocchi, W., & Santoro, N. (2011). Time-varying graphs and dynamic networks. International Conference on Ad-Hoc Networks and Wireless (pp. 346–359). Springer. es_ES
dc.description.references Chami, I., Abu-El-Haija, S., Perozzi, B., Ré, C., & Murphy, K. (2020). Machine learning on graphs: A model and comprehensive taxonomy. arXiv preprint arXiv:200503675. es_ES
dc.description.references Chávez, E., Navarro, G., Baeza-Yates, R., & Marroquín, J. L. (2001). Searching in metric spaces. ACM Computing Surveys (CSUR), 33(3), 273–321. es_ES
dc.description.references Chebotarev, P. (2011). A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. Discrete Applied Mathematics, 159(5), 295–302. es_ES
dc.description.references Chen, H., & Giménez, O. (2010). Causal graphs and structurally restricted planning. Journal of Computer and System Sciences, 76(7), 579–592. es_ES
dc.description.references Chen, J., & Safro, I. (2011). Algebraic distance on graphs. SIAM Journal on Scientific Computing, 33(6), 3468–3490. es_ES
dc.description.references Cobzaş, Ş, Miculescu, R., & Nicolae, A. (2019). Lipschitz functions. Springer. es_ES
dc.description.references Daswani, M., Sunehag, P., & Hutter, M. (2013). Q-learning for history-based reinforcement learning. In Asian Conference on Machine Learning (PMRL) (pp. 213–228). es_ES
dc.description.references Deza, M. M., & Deza, E. (2009). Encyclopedia of distances. Springer. es_ES
dc.description.references Dolgov, D., & Durfee, E. (2006). The effects ofllocality and asymmetry in large-scale multiagent mdps. In Coordination of large-scale multiagent system (pp. 3–26). es_ES
dc.description.references Dong, M., Yang, X., Wu, Y., Xue, J.H. (2018). Metric learning via maximizing the lipschitz margin ratio. arXiv preprint arXiv:180203464. es_ES
dc.description.references Driessens, K., Ramon, J., & Gärtner, T. (2006). Graph kernels and gaussian processes for relational reinforcement learning. Machine Learning, 64(1–3), 91–119. es_ES
dc.description.references Entringer, R., Douglas, C., Jackson, E., & Synder, D. A. (1976). Distance in graphs. Czechoslovak Mathematical Journal, 26(2), 283–296. es_ES
dc.description.references Gao, X., Xiao, B., Tao, D., & Li, X. (2010). A survey of graph edit distance. Pattern Analysis and applications, 13(1), 113–129. es_ES
dc.description.references Goddard, W., & Oellermann, O. R. (2011). Distance in graphs. Structural Analysis of Complex Networks (pp. 49–72). Birkhäuser. es_ES
dc.description.references Goldberg, A., & T R,. (1993). A heuristic improvement of the bellman-ford algorithm. Report STAN-CS-93-1464 (pp. 1–5). Dept. of Computer Sc.: Stanford University, Stanford University. es_ES
dc.description.references Gottlieb, L. A., Kontorovich, A., & Krauthgamer, R. (2014). Efficient classification for metric data. IEEE Transactions on Information Theory, 60(9), 5750–5759. es_ES
dc.description.references Goyal, P., & Ferrara, E. (2018). Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems, 151, 78–94. es_ES
dc.description.references Graham, R. L., Hoffman, A. J., & Hosaya, H. (1977). On the distance matrix of a directed graph. Journal of Graph Theory, 1, 85–88. es_ES
dc.description.references Hakimi, S., & Yau, S. (1965). On the distance matrix of a directed graph. Quarterly of Applied Mathematics, 22, 305–317. es_ES
dc.description.references He, K., Banerjee, B., & Doshi, P. (2020). Cooperative-competitive reinforcement learning with history-dependent rewards. arXiv preprint arXiv:2010.08030. es_ES
dc.description.references Hjaltason, G. R., & Samet, H. (2003). Index-driven similarity search in metric spaces (survey article). ACM Transactions on Database Systems (TODS), 28(4), 517–580. es_ES
dc.description.references Howard, R. (1960). Dynamic programming and Markov processes. John Wiley & Sons. es_ES
dc.description.references Jia, H., Ym, Cheung, & Liu, J. (2015). A new distance metric for unsupervised learning of categorical data. IEEE Transactions on Neural Networks and Learning Systems, 27(5), 1065–1079. es_ES
dc.description.references Klein, D., & Randić, M. (1993). Resistance distance. Journal of Mathematical Chemistry, 12(1), 81–95. es_ES
dc.description.references Kubat, M. (2017). An introduction to machine learning. Springer. es_ES
dc.description.references Kyng, R., Rao, A., Sachdeva, S., & Spielman, D. A. (2015). Algorithms for Lipschitz learning on graphs. In Conference on Learning Theory (pp. 1190–1223). es_ES
dc.description.references Majeed, S. J., & Hutter, M. (2018). On q-learning convergence for non-markov decision processes. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI) (pp. 2546–2552). es_ES
dc.description.references Mustăţa, C. (2001). Extensions of semi-lipschitz functions on quasi-metric spaces. Revue d’analyse numérique et de théorie de l’approximation, 30(1), 61–67. es_ES
dc.description.references Mustăţa, C. (2002). On the extremal semi-lipschitz functions. Revue d’analyse numérique et de théorie de l’approximation, 31(1), 103–108. es_ES
dc.description.references N’Guyen, S., Moulin-Frier, C., & Droulez, J. (2013). Decision making under uncertainty: a quasimetric approach. PloS one, 8(12), e83411. es_ES
dc.description.references Nickel, M., Murphy, K., Tresp, V., & Gabrilovich, E. (2015). A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1), 11–33. es_ES
dc.description.references Ou, M., Cui, P., Pei, J., Zhang, Z., & Zhu, W. (2016). Asymmetric transitivity preserving graph embedding. In: In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1105–1114). es_ES
dc.description.references Puterman, M. (1994). Markov decision processes. John Wiley & Sons. es_ES
dc.description.references Rao, A. (2015). Algorithms for Lipschitz Extensions on Graphs. Yale University. es_ES
dc.description.references Romaguera, S., & Sanchis, M. (2000). Semi-Lipschitz functions and best approximation in quasi-metric spaces. Journal of Approximation Theory, 103(2), 292–301. es_ES
dc.description.references Shaw, B., Huang, B., & Jebara, T. (2011). Learning a distance metric from a network. In Advances in Neural Information Processing Systems (pp. 1899–1907). es_ES
dc.description.references Sigaud, O., & Oe, Buffet. (2013). Markov decision processes in artificial intelligence. Wiley & Sons. es_ES
dc.description.references Singh, S., & Cohn, D. (1998). How to dynamically merge Markov decision processes. Advances in Neural Information Processing Systems, 10, 1057–1063. es_ES
dc.description.references Sutton, R., & Barto, A. (2017). Introduction to reinforcement learning. MIT Press. es_ES
dc.description.references von Luxburg, U., & Bousquet, O. (2004). Distance-based classification with Lipschitz functions. Journal of Machine Learning Research, 5, 669–695. es_ES
dc.description.references Waradpande, V., Kudenko, D., & Khosla, M. (2020). Graph-based state representation for deep reinforcement learning (pp. 1–17), arXiv:200413965. es_ES
dc.description.references Wu, Y., Jin, R., & Zhang, X. (2016). Efficient and exact local search for random walk based top-k proximity query in large graphs. IEEE Transactions on Knowledge and Data Engineering, 28(5), 1160–1174. es_ES
dc.description.references Xia, P., Zhang, L., & Li, F. (2015). Learning similarity with cosine similarity ensemble. Information Sciences, 307, 39–52. es_ES
dc.description.references Xu, Z., Ke, Y., Wang, Y., Cheng, H., & Cheng, J. (2012). In: Proceedings of the 2012 ACM SIGMOD international conference on management of data. A model-based approach to attributed graph clustering (pp. 505–516). es_ES
dc.description.references Zhang, T., Gao, Y., Chen, L., Chen, G., & Pu, S. (2019). Efficient similarity search on quasi-metric graphs. IEEE Access, 7, 101496–101512. es_ES


Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem