A* Algorithm
adds an extra heuristic value on how far we have to go to reach the destination most efficiently/find the best route
A* algorithm steps
- start from source node
- calculate values of g (movement cost), heuristic values, and the sum of f (g+h) for each adjacent node
- select node with smallest f
- from f, calculate all values for adjacent nodes and choose the one with the smallest f
- repeat until the end goal is reached
(h values are not considered in further stages, but the movement costs are cumulative)
Dijkstra’s algorithm
An algorithm for finding the shortest path from one node to all other nodes, aiming to find the best route
Dijkstra’s algorithm steps
in physical working (this is marked)
* initialisation - setting base to 0
* setting the rest of the towns to infinity
* update the values at nodes when visiting - finding alternate paths
* show visited node(s)
in actual calculation:
* just calculate all possible routes from the node you are starting with to the node you want to go to
* pick the shortest one
* show alternative paths being considered
machine learning
where a system improves its performance through analysis of previous performance
types: supervised, unsupervised, reinforcement, deep
supervised learning
- type of machine learning.
- known input and associated ouputs are given // given labelled input data.
- trains the system to predict future outcomes based on past data
- uses regression analysis and classification of data - draw correlations
unsupervised learning
- type of machine learning.
- the system draws its own conclusions by identifying hidden patterns.
- only requires input data,
- uses unlabelled input data - (system is trained with no “right” output)
reinforcement learning
type of machine learning.
the system learns on the basis of reward and punishment.
- receives weighted rewards based on how effective the action was in relation to the achievement of the overall goal
- depending on the evaluation/feedback the policy the system uses will be adjusted
- to improve its performance in similar tasks
deep learning
- a specialised form of machine learning
- …that uses artificial neural networks that contain
- …many hidden layers,
- …and are modelled to function like the human brain.
- uses many layers to progressively extract higher level features from the input
reasons for using deep learning
- makes good use of unstructured data
- enable machines to process data with a nonlinear approach
- effective at drawing out complex hidden patterns
- more accurate outcome with many hidden layers
- especially effective when the data size is large
applications of machine learning
Self Driving Cars
Image Classification
Text Classification
Search Engine
Banking, Healthcare Domain
Logic game theory e.g. backgammon
labelled data
data that has a meaning attached
unlabelled data
data to which no meaning is attached
artificial neural networks in machine learning
- have an input layer, many hidden layers, and an output layer. neurons as nodes represented on a graph.
- intended to replicate the way human brains work
- weighted values for each connection between nodes
- data is input at the input layer and is analysed at each subsequent layer
- this process is repeated many times - reinforcement learning takes place
- decisions can be made without being specifically programmed
- back propagation of errors will be used to correct any errors that have been made
- results are outputted
reasons for having (multiple hidden layers in) an artificial neural network
(Q works both ways)
- enables deep learning
- problems of high complexity can be solved
- the neural network can learn and make decisions of its own
- improve the accuracy of the result
back propagation
Adjusting the weights in a neural network based on the error rate from the previous trial.
* initial outputs from the system are compared to the expected output
* the system weightings are adjusted to minimise the difference between actual and expected result
* if the errors are still too large, the weightings are altered
It is applied first to the nodes in the output layer and then works backward through the nodes in hidden layers until finally the input nodes are considered.
regression analysis
predicting certain outcomes based on the relationship between variables.
A mathematic function that provides the best fit to the actual outcomes when outcomes are calculated from previous inputs.
how have graphs aided ai?
- graphs provide relationships between nodes and a way to observe/analyse them
- ANN can be represented using graphs
- graphs may be analysed by a range of algorithms e.g. A* which is used in machine learning
- graphs provide methods for AI to learn/analyse e.g. back propagation of errors, regression analysis
- AI problems can be solved as finding a path in a graph
machine learning vs deep learning
- ML enables machines to make decisions on their own based on past data while DL enables machines to make decisions using an artificial neural network
- ML needs only a small amount of data to carry out the training while DL requires large amounts of data for the training stage
- for ML, most features in the data need to be identified in advance and then manually coded into the system while DL learns the features of the data from the data itself and doesn’t need to be identified in advance
