- -

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 completo del ítem

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

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/195001

Ficheros en el ítem

Thumbnail
Nombre: FalcianiSanchez - ...
Tamaño: 1.726Mb
Formato: PDF
Descripción: Versión editorial
Abrir/Preview

Metadatos del ítem

Título: Semi-Lipschitz functions and machine learning for discrete dynamical systems on graphs
Autor: Falciani, H. Sánchez Pérez, Enrique Alfonso
Entidad UPV: 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
Fecha difusión:
Resumen:
[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 ...[+]
Palabras clave: Graph distance , Quasi-pseudo-metric , Reinforcement learning , Lipschitz function , Bifurcation metric
Derechos de uso: Reconocimiento (by)
Fuente:
Machine Learning. (issn: 0885-6125 )
DOI: 10.1007/s10994-022-06130-x
Editorial:
Springer-Verlag
Versión del editor: https://doi.org/10.1007/s10994-022-06130-x
Agradecimientos:
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.
Tipo: Artículo

References

Asadi, K., Misra, D., & Littman, M.L. (2018). Lipschitz continuity in model-based reinforcement learning. arXiv preprint arXiv:180407193.

Barnes, J. A., & Harary, F. (1983). Graph theory in network analysis. Social Networks, 5(2), 235–244.

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. [+]
Asadi, K., Misra, D., & Littman, M.L. (2018). Lipschitz continuity in model-based reinforcement learning. arXiv preprint arXiv:180407193.

Barnes, J. A., & Harary, F. (1983). Graph theory in network analysis. Social Networks, 5(2), 235–244.

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.

Bellman, R. (1957). Dynamic programming. Princeton University Press.

Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87–90.

Bondy, J. A., & Murty, U. S. R. (1976). Graph theory with applications. Macmillan.

Boutilier, C. (1999). Sequential optimality and coordination in multiagent systems. IJCAI, 99, 478–485.

Brandes, U. (2005). Network analysis: methodological foundations (Vol. 3418). Springer.

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.

Buckley, F., & Harary, F. (1990). Distance in graphs. Addison-Wesley.

Bunke, H., & Shearer, K. (1998). A graph distance metric based on the maximal common subgraph. Pattern Recognition Letters, 19(3–4), 255–259.

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.

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.

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.

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.

Cao, S., Lu, W., & Xu, Q. (2016). Deep neural networks for learning graph representations. AAAI, 16, 1145–1152.

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.

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.

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.

Chebotarev, P. (2011). A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. Discrete Applied Mathematics, 159(5), 295–302.

Chen, H., & Giménez, O. (2010). Causal graphs and structurally restricted planning. Journal of Computer and System Sciences, 76(7), 579–592.

Chen, J., & Safro, I. (2011). Algebraic distance on graphs. SIAM Journal on Scientific Computing, 33(6), 3468–3490.

Cobzaş, Ş, Miculescu, R., & Nicolae, A. (2019). Lipschitz functions. Springer.

Daswani, M., Sunehag, P., & Hutter, M. (2013). Q-learning for history-based reinforcement learning. In Asian Conference on Machine Learning (PMRL) (pp. 213–228).

Deza, M. M., & Deza, E. (2009). Encyclopedia of distances. Springer.

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).

Dong, M., Yang, X., Wu, Y., Xue, J.H. (2018). Metric learning via maximizing the lipschitz margin ratio. arXiv preprint arXiv:180203464.

Driessens, K., Ramon, J., & Gärtner, T. (2006). Graph kernels and gaussian processes for relational reinforcement learning. Machine Learning, 64(1–3), 91–119.

Entringer, R., Douglas, C., Jackson, E., & Synder, D. A. (1976). Distance in graphs. Czechoslovak Mathematical Journal, 26(2), 283–296.

Gao, X., Xiao, B., Tao, D., & Li, X. (2010). A survey of graph edit distance. Pattern Analysis and applications, 13(1), 113–129.

Goddard, W., & Oellermann, O. R. (2011). Distance in graphs. Structural Analysis of Complex Networks (pp. 49–72). Birkhäuser.

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.

Gottlieb, L. A., Kontorovich, A., & Krauthgamer, R. (2014). Efficient classification for metric data. IEEE Transactions on Information Theory, 60(9), 5750–5759.

Goyal, P., & Ferrara, E. (2018). Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems, 151, 78–94.

Graham, R. L., Hoffman, A. J., & Hosaya, H. (1977). On the distance matrix of a directed graph. Journal of Graph Theory, 1, 85–88.

Hakimi, S., & Yau, S. (1965). On the distance matrix of a directed graph. Quarterly of Applied Mathematics, 22, 305–317.

He, K., Banerjee, B., & Doshi, P. (2020). Cooperative-competitive reinforcement learning with history-dependent rewards. arXiv preprint arXiv:2010.08030.

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.

Howard, R. (1960). Dynamic programming and Markov processes. John Wiley & Sons.

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.

Klein, D., & Randić, M. (1993). Resistance distance. Journal of Mathematical Chemistry, 12(1), 81–95.

Kubat, M. (2017). An introduction to machine learning. Springer.

Kyng, R., Rao, A., Sachdeva, S., & Spielman, D. A. (2015). Algorithms for Lipschitz learning on graphs. In Conference on Learning Theory (pp. 1190–1223).

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).

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.

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.

N’Guyen, S., Moulin-Frier, C., & Droulez, J. (2013). Decision making under uncertainty: a quasimetric approach. PloS one, 8(12), e83411.

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.

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).

Puterman, M. (1994). Markov decision processes. John Wiley & Sons.

Rao, A. (2015). Algorithms for Lipschitz Extensions on Graphs. Yale University.

Romaguera, S., & Sanchis, M. (2000). Semi-Lipschitz functions and best approximation in quasi-metric spaces. Journal of Approximation Theory, 103(2), 292–301.

Shaw, B., Huang, B., & Jebara, T. (2011). Learning a distance metric from a network. In Advances in Neural Information Processing Systems (pp. 1899–1907).

Sigaud, O., & Oe, Buffet. (2013). Markov decision processes in artificial intelligence. Wiley & Sons.

Singh, S., & Cohn, D. (1998). How to dynamically merge Markov decision processes. Advances in Neural Information Processing Systems, 10, 1057–1063.

Sutton, R., & Barto, A. (2017). Introduction to reinforcement learning. MIT Press.

von Luxburg, U., & Bousquet, O. (2004). Distance-based classification with Lipschitz functions. Journal of Machine Learning Research, 5, 669–695.

Waradpande, V., Kudenko, D., & Khosla, M. (2020). Graph-based state representation for deep reinforcement learning (pp. 1–17), arXiv:200413965.

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.

Xia, P., Zhang, L., & Li, F. (2015). Learning similarity with cosine similarity ensemble. Information Sciences, 307, 39–52.

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).

Zhang, T., Gao, Y., Chen, L., Chen, G., & Pu, S. (2019). Efficient similarity search on quasi-metric graphs. IEEE Access, 7, 101496–101512.

[-]

recommendations

 

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

Mostrar el registro completo del ítem