unit 4 aos 3

Question 1

Hilbert’s Completeness goal

Answer 1

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.

Question 2

Hilbert’s Consistency goal

Answer 2

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

Question 3

Hilbert’s Decidability goal

Answer 3

there existed an effective algorithm or method to determine the truth or falsity of any methodical statement.

Question 4

Hilbert’s Formalization goal

Answer 4

develop a symbolic language and formal system that would allow mathematical reasoning to be carried out mechanically and without ambiguity

Question 5

Kurt Gödel Incompleteness Theorem:

Answer 5

• 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

Question 6

Church-Turing thesis

Answer 6

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.

Question 7

Support vector machines

definition

Answer 7

• supervised machine learning algorithm
• map into higher dimension until it can be sparable with a hyperplane
• classification problems

Question 8

Bias (in terms of training)

def + factors

Answer 8

underfitting
- The size of the training dataset used is not enough
- The model is too simple

Question 9

Variance

def + factors

Answer 9

overfitting
- the model is too complex
- Data used for training is not cleaned and contains noise (garbage values) in it

Question 10

Weak AI

def

Answer 10

can perform a specific task

Question 11

Strong AI

def

Answer 11

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

Question 12

Robot reply

Agruments for and against the chinese room agrument

Answer 12

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.

Question 13

Systems reply

Answer 13

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

Question 14

Ethical concerns

Answer 14

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

Question 15

Advantages of Neural networks

Answer 15

• capability to learn complex data
• parallel processing

Question 16

Disadvantages of Neural networks

Answer 16

• 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

Question 17

Advantages of SVM’s

Answer 17

• works well when there is a clear margin of separation between classes
• relatively memory efficient
• more effective in high dimensional spaces

name any 2

Question 18

Disadvantages of SVM’s

Answer 18

• not suitable of large data sets
• classes overlap is bad (alot of noise)

Question 19

Resurgence of neural networks in the late 20th century

Answer 19

• Backpropagation algorithm
• Availability of data
• Increased computation power
• Contributions from the research community

Question 20

Parts of a turing machine

Answer 20

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

Question 21

Describe the parts in a Neural network

Answer 21

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

Question 22

Decidabile problems

Answer 22

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”

Question 23

Undecidable problems

Answer 23

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

Question 24

Brain Simulator Reply

Answer 24

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

Question 25

Dynamic programming
| what problems perform the best for dynamic programming

Answer 25

Dynamic programming is useful on problems that have optimal substructure and overlapping subproblems
* solves the subproblem once

Question 26

Soft limits of computation

Answer 26

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

Question 27

Advantages and disadvantages of supervised learning

Answer 27

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)

Question 28

P

define

Answer 28

P is a complexity class that represents the set of all decision problems that can be solved in polynomial time

Question 29

NP

define

Answer 29

A decision problem whose answer can be verified in polynomial time

Question 30

NP-Complete

def

Answer 30

A decision problem whose solution can be reduced to solve all other NP problems in polynomial time.

Question 31

NP-hard

def

Answer 31

A problem where the solution to the problem can be reduced to solve all other NP-Complete problems in polynomial time

Question 32

Tractable Problem

def

Answer 32

a problem that is solvable by a polynomial-time algorithm
The upper bound is polynomial.

Question 33

Feasibility

def

Answer 33

if you can solve it in polynomial time based on the input

Question 34

Deep neural network

what is it

Answer 34

network has more than 3 layers

including input and output

Question 35

soft margin

SVM

Answer 35

allow some misclassification.
* compromise so we do not overfit to the data

Question 36

halting problem

the proof

Answer 36

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.

Question 37

Entscheidungsproblem

Answer 37

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.

Question 38

Fix high bias/varience

Answer 38

high bias:
* more parameters

high variance:
* less paramaters
* increase training data

bias = underfit | variance = overfit

Question 39

optimisation objectives for training SVM

Answer 39

optimise (maximase) margin between hyperplane and support vectors

Question 40

optimisation objectives for training neural networks

Answer 40

optimisation is to minimise the error between the expected result and the actual result