Search Method

1. Basic Search

   1. Blind Search: Search tree를 만든 후, (모든 경우가 탐색 가능 ==> 너무 많은 시간 소요)

      1. DFS: 깊이 우선으로 탐색 (Local Max에 빠질 가능성)
      2. BFS: 너비 우선으로 탐색 (너무 많은 시간 소요)

   2. Heuristic Search: Search tree에서 경험에 의한 기대치를 반영 ==> 시간 개선을 위해

      1. Hill-Climb(DFS with weight): 각 노드에 경험에 의한 가중치를 부여한 후 우선하여 검색 (local max에 빠질 가능성, 방향전환의 어려움, 평평한 고원 문제)
      2. Beam(BFS with weight): level로 확장한 후 확장된 곳에서 노드의 경험적 가중치를 기반으로 w만큼 선택, 이 과정을 goal를 찾을 때까지 반복
      3. Best First: 어떠한 휴리스틱에 따라서 최근의 모든 경로들을 순서화하여 DFS를 최적화하는 탐색 알고리즘 (???)

2. Optimal Search

   1. British Museum:
   2. Branch and Bound: branch(노드 확장)한 후 확장된 노드 중 가장 좋은 노드로 bound, goal을 찾을 때까지 이 과정을 반복
   3. Branch and Bound with Underestimates: B&B의 과정을 휴리스틱 가중치를 합산하여 적용
   4. A*: 3번 방법(B&B with U)에 Dynamic Programming Principle를 적용한 방법

#. Dynamic Programming Principle: 노드 탐색시 같은 이름의 노드가 존재하면 효율적인 하나만 확장

(예) S-A-D(8) S-D(4)이면 D까지 가는데 후자가 4만큼의 비용이 절약되므로 전자는 고려하지 않음

Rule Based Expert System

1. 개   요

E.S

  |

----------------------------

|                                       |

 Knowledge Base                Inference Engine

|

 -------------------------

|                                    |

    Rule                      Facts, Assertions

예) A toy deduction system identifies animals: 사용자와 system이 질의응답을 통해 어떤 동물인지 알아내는 것

1. Inference Engine

   1. Forward Chaining: Facts, Assertions과 Rule을 이용한 Inference Engine을 기반으로 사실을 찾아내는 방법 (Bottom-Up)

      1. A Toy Deduction System Identifies Animals
         "우유를 주다"  ==> If x가 우유를 준다 then x는 포유동물 이다
         "chews cud(되새김질을 하다)" ==> If x가 표유동물이고 되새김질을 한다 then x는 발굽을 가진 유제동물이다
         "다리가 길다", "목이 길다', "황갈색이다", "얼룩 점이 있다" ==> If x가 발굽을 가진 유제동물이고, 다리와 목이 길고, 황갈색에 얼룰점이 있다. then x는 기린이다
      2. A Toy Reaction System Bags Groceries
         
   2. Backward Chaining: 사실이 주어지고 그 사실이 되기위한 조건을 찾아가며 검증하는 방법 (Top-Down)
      

2. Conflict Resolution Strategies

   1. Rule Ordering: Rule에 우선순위를 두라
   2. Context Ordering: 특정 상황에 맞는 Rules를 그룹화 해라
   3. Specificity Ordering: Superset of the conditions of triggered rule을 이용하라 (???)
   4. Data Ordering: 어떤 우선순위된 list에서 가능한 모든 assertions를 정렬하고 가장 우선순위가 높은 assertions를 이용하라 (???)
   5. Size Ordering: 조건(conditions)의 수가 많은 rule을 사용하라
   6. Recency Ordering: Use the least recently used rule

Simulation Methodology

1. Simulation System Classification

   1. Discrete (time) simulation
   2. Continuous (time) simulation
   3. Discrete event simulation

이 글은 스프링노트에서 작성되었습니다.

3. Deductive Reasoning Agents

연역적 추론 에이전트???

연역법(deductive method): 이미 증명된 하나 또는 둘 이상의 명제를 전제로 하여 새로운 명재를 결론으로 이끌어내는 것을 연역(deduction)이라 하며, 이러한 연역적 추리의 방법과 절차를 논리적으로 체계화 한 것

 예) 아리스토텔레스의 삼단논법 (간접추리)

      모든 사람은 죽는다.          A -> B (대전제)

      소크라테스는 사람이다.     C -> A (소전제)

      소크라테스는 죽는다.        C -> B (결론)

원문보기

3.0  Intorduce

    Symbolic AI

• AI system 구축을 위한 전통적인 방법
• 주어진 시스템의 환경과 그에 적합한 행동의 symbolic한 representation(묘사, 표현???), 그리고 이 representation에 대한 syntactically manipulating(언어적 조작???)이 적용된 시스템으로 지능적 행동을 생성하는 방법

 본 책에서는 이러한 전통적 방법을 극치화 하는데 중점을 둠

 symbolic representation => logical formulae

 syntactically manipulating => logical deduction(논리적 연역) / theorem-proving(논리적 명제 증명법???)

사무실을 돌아다니며 쓰레기를 줍는 로봇 에이전트가 있다.

이러한 로봇을 구현하기 위한 방법은 여러가지가 있다.

그중 하나의 방법은 작동을 위한 description, 환경의 representation을 에이전트에게 주는것이다.

 RALPH는 복도와 큰 블럭들이 있는 환경에서 작동하는 자동로봇 에이전트이다.

Sensory 입력은 비디오 카메라를 통하고,

'interp' subsystem은 이 영상입력을 내부적 representation format으로 변환, based on first-order logic.

 knowledge base라는 historical reasons를 위한 자료구조로 구성.

이 RALPH를 위해서는 다음 두가지의 문제점을 해결해야 함.

1. The transduction problem: 현실세계를 정확하고 적절하며 유용한 symbolic description으로 변환하는 문제
2. The representation/reasoning problem: 정보를 symbolic하게 표현하고 이것을 조작하고 추론하여 유용한 결과를 내는 에이전트를 얻는 문제

1번문제는 비젼, 음성인식, 학습과 관련된 기술이고, 2번문제는 지식 표현, 자동화 추론, 자동화 계획과 관련된 기술이다.

매우 어렵다. ㅡㅡ;

 하지만, theorem-prover(논리적 명제 증명)을 이용한 에이전트는 이러한 문제를 해결하는데 흥미로울 수도 있다.

 우리가 어떤 theory of agency를 가지고 있다고 생각해 보자. 이 theory of agency는 어떤 performance measure의 최적화를 위해 지능적 에이전트가 어떻게 해야하는지 알려준다. 예를 들면, 에이전트의 궁극적 목적을 만족하기 위한 부분적 목표를 어떻게 생성하는지, 이러한 목표를 달성하기 위해 goal-directed하고 reactive한 행동을 어떻게 interleave하는지

즉, 이 theory는 에이전트가 어떻게 행동해야 하는지에 대한 specification이라 볼 수 있다.

이러한 specification을 만족하는 시스템을 implementation하는 전통적인 방법은 궁극적 목적에 도달하기 까지 점차 concrete되어 가는 stage에 따라 specification의 재정의(refining)이 가능해야 한다.

 그러나 theorem-prover을 이용한 에이전트는 이러한 재정의가 발생하지 않는다. 대신, executable specification이란 것이 있다.

 executable specification: 에이전트의 행동을 생성하기 위해 directly executed된 것이다.

 3.1 Agents as Theorem Provers

deliberate 라는 logic 기반의 에이전트를 만들어 보자.

이러한 에이전트는 내부적으로 전통적 first-order predicate logic formulae의 db로 구성된다.

예를들면, 다음과 같은 fomulae들이 포함되어 있다.

Open(value221)

Temperature(reactor 4726, 321)

Pressure(tank 776, 28)

이 db는 그 에이전트의 환경정보를 가진다. 에이전트의 db는 인간의 belief와 유사한 역활을 한다.

 3.2  Agent-Oriented Programming

 3.3 Concurrent MetateM

이 글은 스프링노트에서 작성되었습니다.

로그 (logarithm)

요약

수학용어.

설명

수학용어. 를 1이 아닌 양수, 를 임의의 양수라 할 때 에 대하여 ＝를 성립시키는 실수 는 오직 하나만 존재하는데, 이 를 ＜를 밑으로 하는 의 로그＞라고 하며 =log라 나타낸다. 또 여기서 를 log(즉 )의 ＜진수(眞數)＞라고 한다. 로그(log)는 logarithm의 약칭으로서, 구용어로는 대수(對數)라 하였다. 로그의 기본적인 성질을 간추려보면 다음 다섯 공식과 같다.
＞0, ≠1, ＞0, ＞0, 는 임의의 실수 일 때,









=log에서 밑 를 정해 놓고, 의 값에 대한 log의 값을 나타낸 표를 ＜로그표＞라 한다. 위의 공식 ⑵ 의 경우는 이 로그표에서 log와 log의 값을 각각 읽어서 합 log＋log=log의 값을 계산한다. 이와 같이 로그표를 읽음으로써 로그값을 구할 수 있는데, 반대로 로그값을 알고 그 진수의 값을 구하려면, 로그값을 구하는 경우의 반대 절차에 따라 로그표를 읽으면 된다. 즉 합 log의 값을 로그표를 읽어서 계산했다면, 그 반대 절차로 로그표를 읽어서 log의 진수 의 값을 구할 수 있다. 따라서 진수의 곱셈을 로그표에 의해 로그의 덧셈으로 바꿀 수 있다. 마찬가지로 공식 ⑶ 에 의해 진수의 나눗셈을 로그의 뺄셈으로 바꿀 수 있으며, 공식 ⑷ 에 의해 진수의 거듭제곱 또는 거듭제곱근을 구하는 계산을 각각 로그와 실수의 곱셈 또는 나눗셈으로 바꿀 수 있다. 로그는 이상과 같은 실용적인 필요성에 의해 개발된 것으로 J. 네이피어에 의해 개척되었으며, 또한 그는 처음으로 로그표를 만들어 공표하기도 했다. 이와는 별도로 J. 뷔르기도 1603∼1611년에 걸쳐서 로그표를 만들었으며, 1620년에 이를 간행하였다. 기수법은 보통 십진법에 의하기 때문에, 실용상의 계산에는 10을 밑으로 하는 로그를 사용하는 것이 편리하다. 이와 같은 로그를 ＜상용(常用)로그(common logarithm)＞라 하는데, 초등수학에서는 보통 밑 10을 생략하여 log라 나타낸다. 따라서 공식 ⑴ 에 의해 log10=1로 된다. 1이고 의 정수부분이 ＋1자리(0)인 수이면 =10′, 1′＜10이라 쓸 수 있으므로 log=＋log′, 0log′＜1로 된다. 또 0＜＜1이고 의 소숫점 아래 째 자리에서 처음으로 0이 아닌 숫자가 나타나는 소수는, =10′′, ′=－, 1′＜10이라 쓸 수 있으므로, log=′＋log′, 0log′＜1로 된다. 위의 (1인 경우) 또는 ′(0＜＜1인 경우)을 상용로그 log의 ＜지표＞라 하며, log′을 ＜가수(假數)＞라 한다. 이상의 설명에 의거하여 1′＜10인 ′에 대한 상용로그표에서 가수(로그의 소수부분)를 구하고, 이것에 의 자리수에 의해 정해지는 정수 또는 ′, 즉 지표를 더함으로써 의 상용로그 log의 값이 구해진다. 상용로그표는 이상과 같은 원리에 의거해서 작성되었으며, 1794년에 G.F. 베가에 의해 완전한 것으로 만들어졌다. 한편, 수학 이론에서는



를 밑으로 하는 로그인 log가 이용된다. 이 로그를 ＜자연(自然)로그(natural logarithm)＞라 하며, 보통 밑 를 생략하여 log라 나타내지만, 드물게 ln라 나타내는 경우도 있다. 자연로그와 상용로그의 상호 관계를 간추리면 다음과 같다.





단

이 글은 스프링노트에서 작성되었습니다.

영통~~~강남역:영통막차:23:20분.영통첫차:05:30분
노선번호:3001번.
영통살구골ㅡ동아아파트ㅡ청명주공아파트ㅡ태평양화학ㅡ아주대ㅡ경찰청ㅡ경기대
동수원IC.~~~~고속도로ㅡ양재역 ㅡ강남역 (참고로,영통은 버스가 일직끊어짐)


영통~~~사당역
노선번호:7000번
영통첫차:05:30분
영통막차:23:20분
경희대학교ㅡ영통살구골ㅡ동아아파트ㅡ삼성홈플러스(영통점)ㅡ그랜드마트ㅡ청명삼익아파트
.황골주공아파트ㅡ영통빌리지ㅡ단오극장ㅡ원천유원지ㅡ매원초등학교ㅡ남부경찰서ㅡKT
(동수원지사)ㅡ법원사거리ㅡ아주대학교입구ㅡ아주대학교ㅡ유신고교ㅡ효성초교ㅡ동성여중
.수원월드컵경기장ㅡ풍림아파트ㅡ우만주공4단지ㅡ우만3단지ㅡ경기지방경찰청ㅡ경기대후문
.영동고속도로(동수원IC ㅡ 북수원IC ),~~~~~과천,의왕간 고속도로ㅡ 관문사거리
ㅡ 남태령역 ㅡ 사당역 

수원역~~~~~강남역:수원기점막차:00:30분
노선번호:3000번
수원역ㅡ수원세무서ㅡ중부소방서ㅡ팔달문ㅡ장안문ㅡ수원전화국ㅡ장안문ㅡ장안구청ㅡ한일타운
ㅡ수일여중ㅡ가스안전공사ㅡ파장동삼익아파트ㅡ의왕고속도로경유~~양재.강남역회차


수원역~~~~~사당역 << 30분 간격으로 24시간 운행함!!>>
노선번호:7770번
수원역ㅡ화서문ㅡ장안문ㅡ종합운동장ㅡ한일타운ㅡ과천,의왕고속도로경유~~~사당역
참고 : 7770번 ..토.일요일 (공휴일포함) 에는 24시간,운행을 안합니다.

사당역에서 영통가는 막차는 02:00입니다.

단 일요일은 24:30차가 막차임

참고로 강남역에서 3007번을 타면 수원터미널을 가는데 강남역 막차는 01:40입니다.

단 일요일은 24:10차가 막차임

→3000번은 강남역 막차가 02:00임

→공휴일만 막차가 24:10임

이 글은 스프링노트에서 작성되었습니다.

BreadthFirst Search Crawling Yields HighQuality Pages

Compaq system research center (2001)

page를 crawl할 때 PageRank를 이용하여 page를 평가한다.

web graph를 순회할 때 너비우선검색 이 좋은 crawl 전략이며, 이것이 crawl에서 high-quality page를 빨리 찾을 수 있다.

가장 쉽게 생각할 수 있는 방법은 random 방식이다. Scooter가 이 방식을 사용

Internet Archive crawler는 64개의 host를 동시에 병행적으로 crawl 한다. 하지만 이 방식은 high-quality page를 고려하지 않는다.

많은 전략이 있겠지만 각 검색회사들은 자신의 crawl 전략을 공개하지 않아 알려진 전략은 거의 없다.

The Intelligent Surfer:
Probabilistic Combination of Link and Content Information in PageRank

University of Washington

전통적인 웹 정보검색 기술은 그 방대한 정보의 양과 다양한 정보의 내용으로 인해 만족할 만한 검색 결과를 내지 못함.

이러한 문제를 해결하기 위해 page간의 연결구조(link structure)에 포함된 정보를 활용한 연구가 진행되었고

가장 잘 알려진 알고리즘은 HITS와 PageRank이다. 이러한 알고리즘은 더 많이 연결되어 있는 page가 더 나은 page라는 믿음(belief)을 기반으로 한다.

page content와 지능적 random surfer의 form에 있는 연결구조를 확률적으로 결합한 모델을 제안함.

이 모델은 오늘날 사용되는 대부분의 query relevance function을 지원하며 PageRank보다 더 나은 결과를 낸다.

대신 시간과 저장용량이 필요하지만 그것은 오늘날의 검색엔진에서 수용가능한 수준이다.

이 글은 스프링노트에서 작성되었습니다.

query에서 specify된 keyword를 {K1, K2, ..., Kk}로 놓는다

Keyword search는 3개의 단계를 가진다

1. query의 keyword를 하나라도 포함하는 DB table을(columns와 cells) identify하기 위해서 symbol table이 검색된다(생성된 SQL을 통하여)
2. join trees를 열거하고
3. match하는 row를 identify(확인, 감정, 식별) 한다

 2번과정을 상세히 보면

이 단계는 모든 symbol table granularity(시스템의 세분화 정도)와 유사하다

query keyword를 하나라도 포함하는 DB tables의 set을 MachedTables로 놓자

만약, schema graph G를 undirected graph로 본다면, 이 단계는 join trees를 열거한다.

즉, G의 sub-tree

(a) leaves(단말노드) belong to(부속하다) MatchedTables

(b) together, the leaves contain all keywords of the query

그러므로, 만약 join tree에서 발생한 tables을 join하면 결과 relation은 모든 potential rows(query에서 specify된 모든 keywords를 가진)를 포함할 것이다

이 단계는 검색의 다음 단계로 전달될 data의 많은 쓸모없는 join scenarios를 제거할 것이다

예를 들면, 5개 table을 포함하는 그림 4의 schema graph G를 보자

query keywords를 { K1, K2, K3 }로 놓자. 검은색 node는 MatchedTables set을 나타낸다

K1, K2, K3가 모두 T2의 다른 columns에서 발생한다고 가정하자

K2는 T4, K3는 T5에서 발생한다고 가정하자

이 가정하에 가능한 4개의 join tree는 우측의 그림과 같다.

여기서, T2 혼자서도 join tree가 가능한 반면 { T4, T3, T5 }에서 유도되는 tree는 join tree가 될 수 없다.

왜냐하면, 이 tables는 모든 keywords를 포함하지 않기 때문이다.

이것은 join tree를 열거하는 알고리즘을 요약한 것이다. 단순한 exposition(전시, 진열, 보여주기)을 위해 G자신이 tree라고 가정했다

먼저, 반복적으로 white 단말노드(leaves)를 제거하며 모든 단말노드가 black으로 될때까지 G를 pruning한다

(이것은 universal relations에서 window functions를 computing하는 ear removal operation과 유사하다)

결과 tree G'는 모든 matching join tree를 잠재적으로 포함한다

 다음 단계는 G'의 모든 qualifying(후보) sub-trees를 열거한다. 즉, sub-trees such that all keywords in the query occur among the black nodes of the sub-tree.

효율성을 위하여 추천되는 후보 sub-trees의 first-node 선택에 다음과 같은 heuristic을 적용한다

G'에서 fewest black node 에서 발생하는 keyword를 선택한다.(We pick the keyword that occurs in the fewest black nodes of G')

이제 앞에서 indentify된 각각의 black node에서 G'의 모든 sub-trees에 breath-first 열거를 실행한다 그리고 그것이 qualifying sub-tree인지 검사한다

이 heuristic의 이용은 열거되는 trees의 수를 상당히 감소시킨다

만약, G가 tree라고 가정할 수 없다면(즉, cycle을 가진다면), join tree 열거는 G의 bi-connected component decomposition(상당한 정신적 스트레스가 가중될 문서ㅡㅡ;)을 필요로 한다.

Undirected graph

: Edge(변)이 방향을 가지지 않고 두 개의 꼭지점을 연결하는 graph

• 단순 그래프(simple graph)

꼭지점 집합 V와 변의 집합인 E로 이루어지는 단순 그래프 는 두 개의 꼭지점 과 사이에 최대한 한 개의 변만을 허용하고 각 변은 서로 다른 두 꼭지점에 접하여야 하는 무향그래프이다.

(예) 가 단순그래프이고, , 일 때, 라면, 이다.

• 다중 그래프(multigraph)

다중 그래프는 단순 그래프와 비슷하지만, 두 개의 꼭지점 사이에 여러 개의 변이 있을 수 있다.

(예) , ,

Directed graph

• 유향 그래프(directed graph)

유향 그래프는 변이 방향성을 지닌다.

(예)일 때, 이다.

• 유향다중 그래프(directed multigraph)

다중 그래프와 같이, 유향다중 그래프는 동일한 두 개의 꼭지점을 잇는 변이 여러 개 있을 수 있다.

leaf(leaves): tree의 마지막 노드

DB table: columns + rows

columns: property?

rows: instance?

Granularity

시스템의 세분화 정도, 세분화 정도가 클 수록 선택 할 수 있는 증분(세분화 된 값) 크기가 더 작아져 증분 수가 늘어나기 때문에 시스템 사용자 정의에 더 유연해 진다

Join Tree

전통적으로 join tree는 주어진 query를 위해 query optimizer에 의해 결정되는 join operation의 ordering을 나타낸다

하지만 여기서는 schema(where edges depict key foreign key relationship)의 subgraph의 종류를 나타낸다

이 글은 스프링노트에서 작성되었습니다.

스프링노트와의 연동을 시험해보며 예전에 작성한 글을 보내봤다.

전체적인 양식은 조금 깨지는 것 같지만 그래도 이 정도면 훌륭한 것 같다.

빨리 웹에 어느정도의 표준이 자리잡았으면 한다. (문서만이라도...)

(번외로 스프링노트는 리눅스와 윈도우에서 빈칸이 다르게 적용된다. 왜 그렇지? ㅡㅡ;)
==================================

얼마전 여친이랑 "카핑베토벤"이란 영화를 보았다. 베토벤이 궁금했고, 소나타, 교향곡, 그리고 협주곡이 궁금했다.

--------------
소나타: 독주악기를 위한 곡

교향곡: 오케스트라를 위한 곡

- 오케스트라: 관현악단을 뜻함.

- 관현악단: 관악기와 현악기가 함께 있는 연주단체

협주곡: 독주악기와 오케스트라를 위한 곡, 독주악기를 위해서 오케스트라가 반주를 해 주는 곡

-카덴차: 오케스트라의 반주 없이 독주악기 홀로 자신의 기교를 뽑내기 위해 있는 것

1. 소나타
   베토벤 피아노 소나타 "비창"   듣기
   베토벤 피아노 소나타 "월광"   듣기
   베토벤 피아노 소나타 "발트슈타인"
   베토벤 피아노 소나타 "열정"
   베토벤 피아노 소나타 "고별"
   베토벤 피아노 소나타 "하머클라비어"
   베토벤 바이올린 소나타 "봄"   듣기
   베토벤 바이올린 소나타 "크로이처"
   

2. 교향곡
   베토벤 교향곡 3번 "영웅"
   베토벤 교향곡 5번
   베토벤 교향곡 6번 "전원"
   베토벤 교향곡 7번   듣기
   베토벤 교향곡 9번 "합창" (교향곡이긴 하지만 특이하게 합창과 독창을 결합시킨 곡입니다.)  듣기
   

3. 협주곡
   베토벤 피아노 협주곡 3번 다 장조
   베토벤 피아노 협주곡 4번 사 장조
   베토벤 피아노 협주곡 5번 내림 마 장조 "황제"   듣기1   듣기2   듣기3   보기  
   베토벤 삼중 협주곡 다 장조(독주악기는 바이올린, 첼로, 피아노입니다)
   비발디 바이올린 협주곡 "봄"
   비발디 바이올린 협주곡 "여름"
   비발디 바이올린 협주곡 "가을"
   비발디 바이올린 협주곡 "겨울"

 베토벤 가곡 아델라이데   듣기

<원문>

이 글은 스프링노트에서 작성되었습니다.