Japan: It's Not Funny Anymore

http://kotaku.com/5484581/japan-its-not-funny-anymore

First Order Logic - FOL

Propositional logic is declarative but not expressive, hence we have First Order Logic (FOL), also called Predicate Calculus

Has quantifiers, universal ∀x (usually use ->), existential ∃x (usually use ^)

∃x ∀y is not the same as ∀y ∃x

∃x ∀y Loves(x,y)
“There is a person who loves everyone in the world”
∀y ∃x Loves(x,y)
“Everyone in the world is loved by at least one person”

∀x Likes(x,IceCream) = ¬∃x ¬Likes(x,IceCream)

kinship domain:
object are people
Properties include gender and they are related by relations
such as parenthood, brotherhood,marriage
predicates: Male, Female (unary)
Parent,Sibling,Daughter,Son...
Function:Mother Father

{a/Shoot} <- substitution

Rule Based Reasoning

Entailment means that one thing follows from another:
KB ╞ α

Propositional Logic
--------------------

The proposition symbols P1, P2 etc are sentences
conjunction ^
disjunction V
implication (if-then) a -> b ≡ ~a V b // false iff a=T and b=F
biconditional a <-> b ≡ (a->b) ^ (b->a)

logically equivalent α ≡ ß iff α╞ β and β╞α

for:
1. (a ^ b) V (c V d)
2. (a V c V d) ^ (b V c V d)

We say we pick all the operand and operators after "a" except "^ b" since we are distributing over "^" in phrase "^ b" i.e. "a" operates on "V (c V d)" and "b" operates on the same phrase and the final operator is "^" which will go in the middle.

The same is true for the second example you mentioned...

1. (a ^ b) V (c ^ d) // Distribute over "^" in "a^b"
2. (a V (c ^ d)) ^ (b V (c ^ d)) // Expand
3. ((a V c)^(a V d)) ^ ((b V c)^(b V d)) // all operators outside parentheses are of type "^" so good to remove extra ones
4. (a V c) ^ (a V d) ^ (b V c) ^ (b V d)



A sentence is valid if it is true in all models (truth tables where α=True),

Validity is connected to inference via the Deduction Theorem:
KB ╞ α if and only if (KB ⇒ α) is valid

A sentence is satisfiable if it is true in some model

A sentence is unsatisfiable if it is true in no models

Satisfiability is connected to inference via the following:
KB ╞ α if and only if (KB ∧¬α) is unsatisfiable [] (empty clause)

Interpretation: any assignment of true and false to atoms

Rules of inference


Model checking
⌧truth table enumeration (always exponential in n)
⌧improved backtracking, e.g., Davis--Putnam-Logemann-Loveland (DPLL), Backtracking with constraint propagation, backjumping.
⌧heuristic search in model space (sound but incomplete)
e.g., min-conflicts-like hill-climbing algorithms

Resolution is sound

Resolution is NOT complete:
P and R entails P V R but you cannot infer P V R From (P and R) by resolution

Resolution is complete for refutation: adding (¬P) and (¬R) to (P and R) we can infer the empty clause. (proof by contradiction)

CNF = conjunctive normal form eg. (A V B) ^ C

( P ∧ ¬Q ) ∨ ( ¬R ∨ P ) ≡ ( P ∨ ¬ R ∨ P ) ∧ ( ¬ Q ∨ ¬R ∨ P ) ≡ ( P ∨ ¬R ), (¬Q ∨ ¬R ∨ P )

The set of support: those clauses coming from negation of the theorem or their decendents.

Horn clause: Eg C ^ (B -> A) ^ ( C ^ D -> B) NOT! (C V D -> B)

Forward chaining (data driven) - linear time
Idea: fire any rule whose premises are satisfied in the KB,
add its conclusion to the KB, until query is found

Backward chaining (goal driven) - linear time
Idea: work backwards from the query q:
to prove q by BC,
check if q is known already, or
prove by BC all premises of some rule concluding q
Avoid loops: check if new subgoal is already on the goal stack
Avoid repeated work: check if new subgoal
1. has already been proved true, or
2. has already failed


Efficient propositional inference:
- DPLL 1. early termination 2. purse symbol (same sign for everywhere, so either all nots or positives) 3. unit clause - clause with only a literal
- WalkSAT (incomplete), local search using randomness

Ch. 5 - Game Playing - games

Minimax
eg. chess, othello, backgammon (chance node due to Dice, use Expecti-minimax), tic-tac-toe, Grundy's game
- complete, optimal, like DFS: time complexity - O(b^m), space complexity O(bm)
- players take turn, max-min-max-min-max etc.

An Evaluation Function:
- Estimates how good the current board configuration is for a player.
- linear weighted sum of features eg. Eval(s) = w1f1(s) + w2f2(s) + ... + wnfn(s)
f1 = number of white queens - number of black queens

Ply - number of look-ahead levels

Aplha(max of children)-beta(min of children) pruning
- in practice alpha-beta pruning, often get O(b^(d/2)) rather than O(b^d) remember b^(1/2) = sqrt(b)


Expectiminimax - use weights that are linear due to average score, ie. Sum(prob_state*score), Dice has 21 (1+2+3+4+...+6 = n*(n+1)/2 = 6*7/2 http://polysum.tripod.com/) unique dice rolls (6-5 is the same as rolling 5-6)

Nintendo DS Games for the Brain

Brain Age Part 1 and 2 Bundle For Nintendo DS. Train Your Brain!

Professor Layton

Brain Challenge

Flash Focus

Big Brain Academy

Ultimate Brain Games

Brain Challenge

Left Brain Right Brain
---------------------

Others

http://www.mrbass.org/nintendoDS/games/

My Japanese Coach

Lunar Knights

Constraint Satisfaction Problems - CSP

• The constraint network model
– Variables, domains, constraints, constraint graph, solutions
• Examples:
– graph-coloring, 8-queen, cryptarithmetic, crossword puzzles, vision
problems,scheduling, design
• The search space and naive backtracking,
• The constraint graph (nodes=variables, edges=constraints, solution=assignment of value to variable such that constraint is not violated)
• Like DFS, go deep, called backtracking search
- state = assignment of values to variables while constraints are satisfied
- operator = assignment to next variable such that constraints are not violated
- goal = consistent assignment of all variables
- depends on variable ordering, so d={z,x,y} gives different tree when d={x,y,z}

Maybe:
• Consistency enforcing algorithms
– arc-consistency, AC-1,AC-3

Eg. map-coloring
variables - locations / countries / regions
values - colors in domain of red, green, blue
constraints - adjacent countries are colored differently
graph - nodes are variables (locations), edges are constraints so put an edge between two adjacent regions

Eg. 9x9 sudoku
variables - cells / squares that hold numbers, 81 variables for 9x9 problem
values - numbers in domain 1 to 9
constraints (27 constraints) -
a) each row has unique numbers ie all numbers from 1 to 9, 'Not-equal', AllDiff(a11, a12, a13, ..., a19) - 9 constraints
b) each col has unique numbers ie all numbers from 1 to 9, AllDiff(a11, a21, a22, ..., a29) - 9 constraints
c) each 3x3 grid (9 of them) sums contains all numbers from 1 to 9 - AllDiff(a11, a12, a13, a21, a22, a23, a31, a32, a33) 9 constraints

Eg. Four queen
variables - rows (x1, x2, x3, x4)
values - columns {1,2,3,4}
constraint ((4 choose 2) = 6 constraints)
- graph - (x1-x2), (x1-x3), (x1-x4), ..., (x4-x2), (x4-x3) (a box with a cross inside)
- so each variable constrains all other variables

Look-ahead schemes:
• Value ordering/pruning (choose a least restricting value),
• Variable ordering (choose the most constraining variable)
• Constraint propagation (take decision implications forward)

Heuristics:
1. Minimum Remaining Values (MRV) heuristic - choose the variable with the fewest legal values
2. Degree heuristic: MRV tie breaker, choose the variable with the most constraints on remaining variables
3. Given a variable, choose the least constraining value:
– the one that rules out the fewest values in the remaining variables
4. min-conflicts

Forward checking
- Idea: Keep track of remaining legal values for unassigned variables
Terminate search when any variable has no legal values
- constraint propagation

Arc-consistency (AC-3)
Arc ( X i ,X j ) is arc-consistent if for any value of X i there exist a matching (allowed) value of X j
Begin
1. For each a in Di if there is no value b in Dj that matches a then delete a from the Dj.
End.
X → Y is consistent iff
for every value x of X there is some allowed y
- detects error earlier than forward checking

• Time complexity: O(ed3)
• e = # edges, d = variable domain size)

Local search for CSPs - h(n) = min-conflicts
• Variable selection: randomly select any conflicted variable
• Value selection by min-conflicts heuristic:
– choose value that violates the fewest constraints
– i.e., hill-climb with h(n) = total number of violated constraints

WalkSAT - adds random walk to GSAT ( hill climbing )

Simulated Annealing
Theoretically, with a slow enough cooling schedule, this algorithm will find the optimal solution. But so will searching randomly.

Tree structured CSPs (eg by cutset) can be solved in linear time (O(d^C*d^2) c = cut-set size

conditioning - instantiate a variable, prune its neighbours' domain

VLC does not support the audio or video format "undf"

VLC does not support the audio or video format "undf". Unfortunately there is no way for you to fix this.

http://ubuntuforums.org/showthread.php?t=1117283

$ sudo apt-get install ffmpeg libavcodec-unstripped-51

http://ubuntuforums.org/showthread.php?t=1103825

$ sudo apt-get install ffmpeg ubuntu-restricted-extras

Install FFmpeg and x264 on Ubuntu Hardy Heron 8.04 LTS
http://ubuntuforums.org/showpost.php?p=6963607&postcount=360

Compiling VLC
http://wiki.videolan.org/UnixCompile

Wikimapia

http://wikimapia.org

First-order-logic FOL

General rule:
Use ⇒ for ∀
Use ∧ for ∃

Every student loves some student.
∀ x ( Student(x)⇒∃ y ( Student(y)∧ Loves(x,y) ))

There is a student who is loved by every other student.
∃ x ( Student(x)∧∀ y ( Student(y)∧¬(x = y)⇒ Loves(y,x) ))

There is a student who is loved by every other student.
∃ x ( Student(x)∧∀ y ( Student(y)∧¬(x = y)⇒ Loves(y,x) ))

Bill takes either Analysis or Geometry (but not both)
Takes(Bill, Analysis)⇔¬ Takes(Bill, Geometry)

No student loves Bill.
¬∃ x ( Student(x)∧ Loves(x, Bill) )

Bill has at most one sister.
∀ x, y ( SisterOf(x, Bill)∧ SisterOf(y, Bill)⇒ x = y )

Bill has exactly one sister.
∃ x ( SisterOf(x, Bill)∧∀y ( SisterOf(y, Bill)⇒ x = y ))

Bill has at least two sisters.
∃ x, y ( SisterOf(x, Bill)∧ SisterOf(y, Bill)∧¬ (x = y) )

Only one student failed History.
∃ x ( Student(x)∧ Failed(x, History)∧∀y ( Student(y)∧ Failed(y, History)⇒ x = y ))

No student can fool all the other students.
¬∃ x ( Student(x)∧∀ y ( Student(y)∧¬ (x = y)⇒ Fools(x,y) ))

AI references

http://sli.ics.uci.edu/Classes/2009W

http://www.cc.gatech.edu/classes/AY2003/cs4600_fall/

http://www.ics.uci.edu/~smyth/courses/cs271/schedule.html

http://www.cs.sfu.ca/~hkhosrav/personal/310.html

http://www.cs.sfu.ca/~mori/courses/cmpt310/

http://www.cs.sfu.ca/CC/310/pwfong/

http://www.cs.unb.ca/profs/hzhang/CS4725/

http://www.earlham.edu/~peters/courses/log/transtip.htm

http://pages.cs.wisc.edu/~dyer/cs540/

http://www.ics.uci.edu/~smyth/courses/cs271/schedule.html

http://www.ics.uci.edu/~welling/teaching/271fall09/

Abscissic Acid (ABA)

Physiological effects
- promotes seed dormancy
- prevents seed germination

Seed germination is inhibited by ABA in antagonism with Gibberellin.

http://en.wikipedia.org/wiki/Abscisic_acid

Cytokinins (CK)

Cytokinins - promotes controlled cell division

Physiological effects:
- occurs to repair leaf abscission and wounds
- leaf senescence signals expression of CKs, and so leaf senescence is prevented and plant remains green
- promotes growth of shoots (lateral bud growth), some regulation of cell division in shoot apical meristem (SAM) (pg 25)
- suppresses growth of roots
- enhance de-etiolation (greening of plants), thylakoid formation, cotyledon expansion
- limited duration

Forms:
- zeatin (found in coconut milk), some kinetin (amino-purine), biosynthetic ipt gene

Experiment:
- excised root grow indefinitely
- excised shoot grow after adding coconut milk and herring sperm DNA with auxin
- so this means, the hormone CK suppresses root growth and is needed for shoot growth
- Infection by Agrobacterium tumefaciens -> crown gall tumours

Infection by Agrobacterium tumefaciens leads to uncontrolled cell division and tumour formation 'crown gall tumours'
- baterium's cell contain a circular Ti-DNA that contains T-DNA which encodes for cytokinin and auxin, this T-DNA integrates with the host DNA during transformation and starts infecting the wound

Cytokinin oxidase metabolizes cytokinin (irreversible degradation, produces adenine + alcohol)

When CK oxidase is over-expressed
- you get REDUCED SAM (shoot apical meristem)
- and INCREASED ROOT growth

Morphogenesis in cultured plants - AUXIN / CK flux:
- low auxin, high CK => formation of shoots
- high auxin, low CK => formation of roots
- med auxin, med CK => undifferentiated

4. (2 marks) Morphogenesis of cultured plant cells
CK:
- High auxin and low CK promotes root growth
- Low auxin and high CK promotes shoot growth
- Equal concentration of auxin and CK shows no differentiation

5. (1 mark) De-etiolation of seedlings (greening)
CK:
- CK enhances de-etiolation of seedlings
- CK promotes chloroplasts development by converting etioplasts in dark-growing seedlings to thylakoids
- CK promotes cotyledon expansion

6. (5 marks) Induction of alpha-amylase production in cereal aleurone layer cells
GA: In Ca2+ independent pathway
1. GA1 binds to membrane receptor in aluerone cell
2. GA-receptor complex binds to heterotrimeric G protein initiating Ca2+ independent and Ca2+ dependent signaling pathway
3. In Ca2+ independent pathway, the Ca2+ activates the F-protein, the F-protein diffuses to the nucleus
4. the SCF-ubiquitin ligase complex degrades the DELLA repressor
5. GAMYB gene is expressed and it binds to the alpha-amylase hydrolytic enzyme promoter
6. alpha-amylase enzymes are expressed and secreted from the aleurone cell for starch degradation in endosperm

Gibberellins (GA)

http://universe-review.ca/I10-22a-anatomy2.jpg


http://media-1.web.britannica.com/eb-media/97/5597-003-9A3253A5.gif

Gibberellins - promotes internode (between nodes) elongation

Gibberellins Physiological Effects
- promotes internode elongation (creating taller plants vs rosette/dwarf plants - cabbage, dandelions lack GA)
- promotes juvenile to mature stages eg. cone buds in conifers
- sex determination eg. +GA prevent anther development in corn
- promotes seed germination via reserve mobilization (alpha-amylase production) and phytochrome induced transcription of genes
- anatagonistic to ABA (Abscisic acid)
- GA biosynthesis occurs throughout the entire life cycle

Forms:
- GA1 (active form, has COOH at C6 and beta-OH at C3) encodes CPS, the first enzyme in GA biosynthesis
- GA3 commercial form
- mostly inactive form
- GA20 + OH + GA-3beta-hydrolase => GA1

Reserve mobilization by GA
1. GA secreted in embryo
2. GA reaches aleurone layer via scutellum
3. Aleurone layer secretes alpha-amylase (starch hydrolase)
4. Starch is broken down to simple sugars and is transported back to the embryo

Experiment:
- 5'GA1-GUS reporter show sites of GA biosynthesis
- GA1 encodes CPS, the first committed enzyme in GA biosynthesis.

Commercial applications of GA:
- increases stalk length that offsets fruit compaction
- promotes fruit development without pollination (parthenocarpy = virgin/seedless fruit)
- beer, GA promotes malting (start germination by water then quickly halt it by heat then development of color and flavour is produced by kilning) of barley
- sugar - GA increase sugar yield and internode length
- hasten cone production

Commercial applications of GA Inhibitors:
- ornaments - crysanthemums (sprayed with GA inhibitor, reduces internode elongation so they are small)
- prevents lodging (bending of stems to ground) by reducing stem length


GA induces alpha-amylase production via Ca2+ independent pathway.
1. GA binds to receptor
2. GA-receptor binds to G-protein
3. G-protein activates F-box protein
4. F-box protein binds to DELLA-domain repressor (which is degraded by SCF-ubiquitin ligase)
5. GAMYB gene expression is activated
6. GAMYB activates alpha-amylase expression

1. (1 mark) Reproduction in conifers
GA:
Influence the transition from juvenile to
mature stages e.g. induction of cone-
buds in conifers


2. (2 marks) Seed germination
GA:
- Promotes post-germinative mobilization of reserves in cereal
grains

- promotes light-sensitive germination mediated by phytochromes which are induced by transcription of genes encoding GA biosynthetic enzymes

3. (3 marks) Control of root growth
CK:
- CK suppresses root growth so plants that are CK deficient show root growth compared to wild-types
- CK suppresses the size and rate of cell division activity of roots
- bell-shaped curve (X axis = CK signaling, Y axis = Root growth rate):
a) wild-type shows supraoptimal levels of CK
b) Over-expression of CK oxidase decreases CK signaling concentration to optimum level and root growth occurs
c) Further decreasing CK signaling below the optimum amount causes decrease in root growth