Artificial Intelligence and Quantum Computing for Advanced Wireless Networks. Savo G. Glisic. Читать онлайн. Newlib. NEWLIB.NET

Автор: Savo G. Glisic
Издательство: John Wiley & Sons Limited
Серия:
Жанр произведения: Программы
Год издания: 0
isbn: 9781119790310
Скачать книгу
equation

      holds where images and images are the element in position i, j of matrix An, u and the corresponding output of the transition network, respectively, while images is the the element of vector images is the corresponding output of the forcing network (see Eq. (5.83))], and images is the i‐th element of xu . Then

equation

      where y images δ = ∣ ne[n] ∣ · z′(t), and images is a vector that stores images in the position corresponding to i, j, that is, images . Thus, in linear GNNs, d is computed by calling the backpropagation procedure on each arc and node.

      In positional and nonlinear GNNs, the transition function must be activated itf · ∣ N∣ and itf · ∣ E∣ times, respectively. Even if such a difference may appear significant, in practice, the complexity of the two models is similar, because the network that implements the fw is larger than the one that implements hw . In fact, fw has M(s + lE) input neurons, where M is the maximum number of neighbors for a node, whereas hw has only s +lE input neurons. A significant difference can be noticed only for graphs where the number of neighbors of nodes is highly variable, since the inputs of fw must be sufficient to accommodate the maximum number of neighbors, and many inputs may remain unused when fw is applied. On the other hand, it is observed that in the linear model the FNNs are used only once for each iteration, so that the complexity of each iteration is O(s2E∣) instead of images. Note that images holds, when hw is implemented by a three‐layered FNN with hih hidden neurons. In practical cases, where hih is often larger than s, the linear model is faster than the nonlinear model. As confirmed by the experiments, such an advantage is mitigated by the smaller accuracy that the model usually achieves.

      Formally, the cost of each learning epoch is given by the sum of all the instructions times the iterations in Table 5.2. An inspection of the table shows that the cost of all instructions involved in the learning phase are linear with respect to both the dimension of the input graph and of the FNNs. The only exceptions are due to the computation of z(t + 1) = z(t) · A + b, (∂Fw/∂x)(x, l) and ∂pw/w, which depend quadratically on s.

      The most expensive instruction is apparently the computation of ∂pw/w in nonlinear GNNs, which costs O images On the other hand, the experiments have shown [1] that tR is usually a small number. In most epochs, tR is 0, since the Jacobian does not violate the imposed constraint, and in the other cases, tR is usually in the range 1–5. Thus, for a small state dimension s, the computation of ∂pw/w requires few applications of backpropagation on h and has a small impact on the global complexity of the learning process. On the other hand, in theory, if s is very large, it might happen that images and at the same time tR ≫ 0, causing the computation of the gradient to be very slow.

      Let G = (V, E) be an undirected graph with vertex set V = {v1, …, vn}. In the following, we assume that the graph G is weighted, that is, each edge between two vertices vi and vj carries a non‐negative weight wij ≥ 0. The weighted adjacency matrix of the graph is the matrix W = (wij)i, j = 1, …, n . If wij = 0, this means that the vertices vi and vj are not connected by an edge. As G is undirected, we require wij = wji . The degree of a vertex viV is defined as

equation

      Note that, in fact, this sum only runs over all vertices adjacent to vi , as for all other vertices vj the weight wij is 0. The degree matrix D is defined as the diagonal matrix with the degrees d1 , …, dn on the diagonal. Given a subset of vertices AV, we denote its complement V\A by images. We define the indicator vector IA = (f1, …, fn)′ ∈ n as the vector with entries fi = 1 if viA and fi = 0 otherwise. For convenience, we introduce the shorthand notation iA for the set of indices {iviA}, in particular when dealing with a sum like ∑i ∈ A wij . For two not necessarily disjoint sets A,