# Use Learnable Knowledge Graph in Dialogue System for Visually Impaired Macro Navigation
## 2 Methods
### Reasoning with Knowledge Graph  
The reasoning of the knowledge graph mainly revolves around the reasoning of the relationship. Based on the facts or relationships in the graph, it infers unknown  
Figure 4: Dependency trees to RDF triple maps.  
Figure 5: Concept conversion via knowledge graph.  
facts or relationships [22], and generally pays attention to checking the three aspects of the entity, the relationship, and the structure of the graph. Knowledge graph reasoning techniques are mainly divided into two categories, those based on the deduction (such as description logic [23], Datalog, production rules, etc.) and those based on induction (such as path reasoning [24], representation learning [25], rule learning [26] and reinforcement learning [27], etc.).  
This article uses induction-based path reasoning, mainly through the analysis and extraction of existing information in the knowledge graph, since most of the information in the graph represents a certain relationship between two entities. After syntactic analysis, the user's speech is also converted into triples as input so that the two can use triple maps as a communication interface.  
We use the PRA (Path Ranking Algorithm) to find the most suitable destination for the user [28], learn the relationship characteristics of the knowledge graph through random walks, quantitatively calculate whether there is a relationship between two nodes, and determine the probability of the relation. The following examples illustrate the application of the PRA algorithm in macro-navigation.  
In this case, a visually impaired person wants to go to a restaurant for dinner, but he doesn't know which one to go to, so he says to the navigator, _\"I want to have dinner.\"_ The content of dinner in the knowledge graph is shown in Figure 6.  
Step 1: \(E_{q}=\{\text{Restaurant, Supermarket, Online Service}\}\), \(R_{1}=\text{locate, for any }\text{e}\in\text{E}_{q}/R_{1}\), assuming the scoring function h = 1/3, then the following path is shown in Figure 7.  
Figure 6: The part of knowledge graph in the case.  
Figure 7: The part of knowledge graph in step 1.  
Step 2: \(E_{q}\) = {Restaurant, Fast food}, \(R_{2}\) = locate, calculate \(h\)(Restaurant, locate, Fast food) and \(h\)(Restaurant, hold, Performance), obviously \(h\)(Restaurant, hold, Performance) = 0. For \(P_{1}\): Dinner-Restaurant-Fast food, \(P_{2}\): Dinner-Restaurant-Performance, \(h\)(\(P_{1}\)) > \(h\)(\(P_{2}\)). Step 3: And so on, the result is shown in Figure 8.  
Suppose there is a path \(P\): Dinner-Restaurant-Fast food-... -Burger King A1 Store, the path length is \(n\), the \(h_{i}\) between two nodes is calculated, and then all \(h\) is added to get the entire path \(P\). The score value is \(h\)(\(P\)).  
But it should be noted that the weight of each path is not necessarily the same. For example, the user may prefer to eat McDonald instead of Burger King, so the final score \(h\)(\(P\)) is given the weight parameter \(\theta\), which is also a learnable parameter.  
Step 4: Calculate weighted summation.  
\[\textit{Score}(\text{Dinner-}\ldots\text{ - Burger King A1 Store})=\theta_{1}P(1)+\theta_{2}P(2)+\ldots\text{ + }\theta_{n}P(n) \tag{1}\]  
More generally, given a set of paths \(P_{1}\), \(P_{2}\),..., \(P_{n}\), one could treat these paths as features for a linear model and rank answers \(e\) to the query \(E_{q}\) by  
\[\theta_{1}\ hE_{q},\,P_{1}\left(e\right)+\theta_{2}\ hE_{q},\,P_{2}\left(e \right)+\ldots\ \theta_{n}\ hE_{q},\,P_{n}\left(e\right) \tag{2}\]  
The final scoring function:  
\[s(e;\theta)=\sum_{P\in\mathcal{P}(q,t)}h_{E_{q},P(e)}\theta_{P} \tag{3}\]  
We can construct the training set with the set of relation \(R\) and the starting point \(s\) and ending point \(t\), and obtain the weight parameter \(\theta\) through logistic regression. After each conversation, according to the user's decision, the weight parameter will be updated, making the knowledge graph more and more suitable for the user's habits.