unit 4 aos 3 Flashcards
Hilbert’s Completeness goal
every mathematical statement could be proven true or false within a formal system based on a fixed set of axioms and rules of inference (logic)
or
Mathematics would be complete if all mathematical statements could be derived from a finite set of axioms.
Hilbert’s Consistency goal
demonstrate there were no contradictions within the system, meaning that it would be impossible to derive both a statement and its negation
OR
Mathematics would be consistent if no contradiction could exist within mathematics
Hilbert’s Decidability goal
there existed an effective algorithm or method to determine the truth or falsity of any methodical statement.
Hilbert’s Formalization goal
develop a symbolic language and formal system that would allow mathematical reasoning to be carried out mechanically and without ambiguity
Kurt Gödel Incompleteness Theorem:
- Proved that Hilbert’s plan to formalize math was impossible
- So not all maths can be proved by axioms
- That completeness and decidability is not possible
Church-Turing thesis
VCAA:
“The Church-Turing Thesis states that any function is effectively calculable by some method if it is computable on a Turing Machine, which helps defines the hard limits of computation” - 2019
———–
certain problems which have finite algorithms are computable; while other problems are incomputable, since they do not have finite algorithms.
finite algorithm = an algorithm that will halt
- With the Turing Machine, a problem could be considered computable if it could be solved by the Turing machine, as it represented the maximal capability of any mechanical algorithm.
Support vector machines
definition
- supervised machine learning algorithm
- map into higher dimension until it can be sparable with a hyperplane
- classification problems
Bias (in terms of training)
def + factors
underfitting
- The size of the training dataset used is not enough
- The model is too simple
Variance
def + factors
overfitting
- the model is too complex
- Data used for training is not cleaned and contains noise (garbage values) in it
Weak AI
def
can perform a specific task
Strong AI
def
- human-like intelligence (simulate)
- can learn
VCAA:
strong AI describes the concept of artificial intelligence mechanisms that are able to go beyond mimicry of human behavior or language and that have human-like understanding and thinking processes.
Robot reply
Agruments for and against the chinese room agrument
AGAINST (is sentient)
- Consider adding sensors such as hearing and seeing Chinese to the man in the room
- Then from the sensors, it can get attachment to the words, thus be able to understand Chinese.
“Robot reply: what is preventing the man in the room from understanding Chinese is the sensory motoric disconnect between him and the outside world. If we attach sensors as input methods and robotic arms and legs as output methods, then the man is able to attach meaning to the Chinese characters by interacting with the world. This is exactly how babies learn language.” - VCAA 2016
For (is not sentient)
- even if they were able to mimic the behaviour of someone speaking Chinese, it would lack understanding (of the outside world)
- The same scenario stays the same except the man in the room is given extra inputs.
Systems reply
Reply:
- We can consider the man in the room and the book of Chinese characters as a system as a whole
- By considering this, the system as a whole actually does understand Chinese.
- This is similar to how each neuron in the brain does not actually understand anything, but the brain as a whole does
———–
Counter reply
- Suppose the man in the room has remembered the book of Chinese
- When given a set of characters, the man in the room can respond by memorization
- Here, the man in the room is not understanding anything, even though they can be seen as a ‘system’, but rather just providing outputs based on inputs
Ethical concerns
BIAS
* can be bias towards data
* learns from bias data
Privacy issues
* who has access to your personal data
* what happens with a data leakage
Sustainability issues
* is it environmentally sustainable
* e.g., pc takes lot of power to train lots of data
Advantages of Neural networks
- capability to learn complex data
- parallel processing
Disadvantages of Neural networks
- black box nature -> Hard to interpret.
- can overfit if it is too complex -> can perform badly on unseen data.
- requires large amounts of data
- tend to get stuck at local minima
Advantages of SVM’s
- works well when there is a clear margin of separation between classes
- relatively memory efficient
- more effective in high dimensional spaces
name any 2
Disadvantages of SVM’s
- not suitable of large data sets
- classes overlap is bad (alot of noise)
Resurgence of neural networks in the late 20th century
- Backpropagation algorithm
- Availability of data
- Increased computation power
- Contributions from the research community
Parts of a turing machine
Tape
Infinite tape divided into discrete cells. Each cell can store a symbol from a finite set of symbols (0 or 1)
Head
Reads the cell at a position on the tape and moves left or right after writing to that cell.
State
- finite set of states (including the halting state)
- At any given moment, the machine is in one specific state.
- By reading the symbol from the head it determines the machine’s next action
Transition function
- finite set of instructions
- determines the next state (responding to the current state)
- direction of head
Describe the parts in a Neural network
Input signals
Inputting the weights
Synaptic weights
Low number, input not important
High number, input important
- start as random
- change the weights until fit data
Propagation function (or sum):
Adding weights and the input signals
- n = p1w1 + p2w2 +…+ pm*wm
Activation function
* Output of activation function will be an __input to another neuron__ or the __output of the neural network__.
Output
outputs 0 or 1
Decidabile problems
Decidable as there is a finite algorithm that terminates on all inputs for it (runtime is irrelevant)
VCAA - “if there existed a general algorithm that would be able to solve [a problem] in a finite number of steps”
Undecidable problems
“Undecidable problem is one for which there is no single algorithm that can be used to solve every instance of such problems.” - vcaa
Undecidable problems are those for which no algorithm is possible. Intractable problems are those for which an algorithm is possible, but all algorithms are inefficient.
Brain Simulator Reply
Against
since the coputer works the very same way as the brain of a native Chinese speaker, processing information in just the same way, it will understand Chinese
For:
even if a brain simulator were to perfectly mimic the behavior of a Chinese-speaking human, it would still lack genuine understanding and consciousness
Dynamic programming
| what problems perform the best for dynamic programming
Dynamic programming is useful on problems that have optimal substructure and overlapping subproblems
* solves the subproblem once
Soft limits of computation
Is relate to te computability, as some problems cannot be solved in P time, but given unlimited resources are still computable and a correct solutioncan be found eventually
Advantages and disadvantages of supervised learning
advantages
- allows you to be very specific
- more accurate
- input data is very well known and is labeled
disadvantages
- can be complex
- computationally expensive (takes a while)
P
define
P is a complexity class that represents the set of all decision problems that can be solved in polynomial time
NP
define
A decision problem whose answer can be verified in polynomial time
NP-Complete
def
A decision problem whose solution can be reduced to solve all other NP problems in polynomial time.
NP-hard
def
A problem where the solution to the problem can be reduced to solve all other NP-Complete problems in polynomial time
Tractable Problem
def
a problem that is solvable by a polynomial-time algorithm
The upper bound is polynomial.
Feasibility
def
if you can solve it in polynomial time based on the input
Deep neural network
what is it
network has more than 3 layers
including input and output
soft margin
SVM
allow some misclassification.
* compromise so we do not overfit to the data
halting problem
the proof
Algorithm h(p, i):
if p(i) halts:
return True
else:
return False
end if
end algorithm
Algorithm h*(q):
if h(q, q):
Loop forever
end algorithm
Case 1: h* halts
If the h* halts, this get passed into h* such that h* runs forever. This implies that h* halts and does not halt thus a contradiction.
Case 2: h* does not halt
If h* does not halt, when it gets passed to h* it halts. This implies that h* halts and does not halt thus a contradiction.
Entscheidungsproblem
The Entscheidungsproblem (decision problem) asked if there was a mechanical procedure (i.e. It was effectively calculable) to determine if a statement was true or false based on a fixed set of axioms.
Fix high bias/varience
high bias:
* more parameters
high variance:
* less paramaters
* increase training data
bias = underfit | variance = overfit
optimisation objectives for training SVM
optimise (maximase) margin between hyperplane and support vectors
optimisation objectives for training neural networks
optimisation is to minimise the error between the expected result and the actual result
