Information Cycle 1. Information Level Hideaki Takeda National Institute of Informatics takeda(@nii.ac.jp http://www-kasm.nii.ac.jp/~takeda/ »Hideaki Takeda / National Institute of Informatics  NII ■
- - -
O Information Gathering ■ Browsing ■  Filtering/Recommendation ■ Ranking O Information Integration ■ Clustering ■ Classification ■ Extraction ■ Mashup
O o Model: Relationship between agents and information sources Main task: how to provide access from the agent to information sources
O Information Retrieval ■■ Explicit specification of users needs ● Browsing ■■ Implicit specification of users needs ■ Finding it by oneself O Information Filtering/Recommendation ■■ Implicit specification of users needs ◾ Guessing users preference ●  Ranking-based search ■■ Explicit specification of users needs + general preference
Characteristics as Information Gathering o ■ Pros: ◆Users initiative ◆ Applicable even with vague purpose ■  Cons: No warranty to reach the goal ◆ Human habit: up to down, side trip ◆ Human limitation: Sequential access ● Problems ■■ How to support users with keeping users initiative ■  How to obtain users preference
»Hideaki Takeda / National Institute of Informatics  NII ■

● Problems
■■ How to support users with keeping users initiative ■  How to obtain users preference ■  How to obtain users preference ◆ Web Watcher ◆ Letizia ◆ Syskill & Webert
»Hideaki Takeda / National Institute of Informatics  NII ■

File http://cranium.learning.cs.cmu.edu:8080/cqi- WebWatcher Comman ched | Exit: Goal Not Found | Your Commen owed each link? | Show me similar pages this page changes 1 link suggested. Click HERE to see it. Welcome to the WebWatcher Project
Overview
WebWatcher is a "tour guide" agent for the world wide web. Once you tell it what kind of information you seek, it accompanies you from page to page as you browse the web, highlighting hyperlinks that it believes will be of interest. Its strategy for giving advice is learned from feedback from earlier tours.
Try it!
WebWatcher can help you search for information starting from any of the following pages. (but it has learned the most about the first of these). ● CMU School of Computer Science Front Door After arriving at this page, click on The WebWatcher tour guide." under the heading SCS Resources ● Machine Learning Information Services 1ARPA Intelligent Integration of Information Home Page  ダッ● ARPA Real Time Planning and Control Home Page Inal Reached | Exit: Goal Not Pearnd | Ymur Coruznents | [Ie] [ Hew mail me if this each link? | Show me simular neges | Email me if this chaugh Tcm Mitcheil 2 Heros Page Ton Letcheil s Homa Pag Ama Ret 1 " samics [[ 3 ] Port Meshire Learcar for 3 Tslece Parasska Terkral Papcrae Tschaces, Reparde TR 87 4    6 ma Resli, ms Hinocaos or4 Caotra, Histo Paos ARPA Res ？ U st W Arelia Lixe seers Lab ARCA RITY soe U st X v é e P v é r  B  X  l og s a  X  l y  s t  X  l  is  e  X  l  is  e  x  l  y  s  c  r 6 - X ener Dots TocBar fAc CoMU Looming Lot soxtcry Dits 8 [3]: 4 ntver " s ar Proy 3 [1]: 5 ntv er " au n Pro Xs Ás Pacesca Overas Carac Pacesrch, 1 60 cx2 10   Adoptro letclaguat systems A Curl: Stermay Pulpavo . So So i : Enc c c 1 2 2 c 1 d  C 1 c 4 HE E E  to c 1 c ARPA Real Time Planning and Cantral Program Pn gran Ma sea  Pen en i Kluc s Try out ver systiments] bu WebWember 50 search search search Resench Project Hoce Pagan
(PI: Paziax Bijcay) w ai日本人 202
●  Use of machine learning ■■ Learn users preference from browsing process ● Functions ■■ Recommendation of links which the system infers useful to the user among links in browsing pages ■■ Recommendation of links which the systems infers useful to the user among all links
●  Learning target LinkUtility: Page × Goal × User × Link→[0,1] UserChoice: Page × Goal × Link→[0,1] Page: Keyword vector of 200 words extracted from pages link: Keyword vector of 200 words from links and 100 words from texts surrounding links Goal: Keyword vector of 30 words u Hideaki Takeda / National Institute of Informatics  NII (
Information Gathering O ■ Browsing ■  Filtering/Recommendation ■ Ranking O Information Integration ■ Clustering ■ Classification ■ Extraction ■ Mashup
●  Content-based filtering ■■ Estimate  users preference by comparing keywords in pages and users profiles O Social filtering / Collaborative filtering ■■ Estimate users preference by collecting and analyzing preferences of many users
How to estimate missing information from the given matrix? ■■ Each vector represents preference of each person ■■ Some values are missing because she has not experience them ■  Estimate these values Solution: Use similarity between users ● O
Calculate relation between user k and k’ by correlation coefficient (相関係数)
Person A Person B Person C Person D 2 44 55 1 ıHideaki Takeda / National Institute of Informatics  Nl
X' kl
2 44 5 11
/home/neural01/gradst/bmiller/bin/xemacs [19,14 XEmacs Lucid (beta6)]   *Summary rec.food.recipe it Apps Options Buffers Tools Article Threads Misc Post Score Mailcrypt
Gnus  rec.food.recipes/17026 {143 more} From: The Ripper (ripper@Onramp.NET) Subject: Popeye's Famous Fried Chicken Newsgroups: rec.food.recipes Date: 1 Jan 1996 07:28:51 -0700 Organization: Onramp Reply-To: The Ripper <ripper@Onramp.NET> Followup-To: rec.food.cooking >From the book written by Todd Wilbur. 6 cups vegetable oil 2/3 cup all-purpose flour 1 tbls salt 2 tbls white pepper 1 tsp cayenne pepper 2 tsp paprika 3  eggs frying chicken w/skin, cut up 1 : 48 pm ( Summary
● Pros ■  Robust for content change ◆ No need for content analysis ♦ Applicable for non-text data ■  Few users actions ◆ Just only evaluate items ● Cons ■  “Cold start” problem ◆ Massive evaluation data is need before reliable recommendation ■  No evaluation, no recommendation ◆ Items without evaluation are never recommended
: MovieLens – Netscape File   Edit   View   Go Communicator Help ↑ _ _ Rating more movies improves your predictions; you've rated 0 so far. [5] = Must See [2] = Fairly Bad [1] = Awri [4] = Will Enjoy It [3] = It’s OK
comments & Suggestions Submit ratings and see next 10 titles (of 78 remaining)
Title Search  ,  Ganra (Data Search  |  Review My Patings

● Pros ■■ Precise recommendation is possible ◆For users ◆ For providers ● Cons ■  For providers: Difficulty to design profiles ■■ For users: Difficulty for keeping users profiles ◆ Input ◆ Update ■  Not adaptive for new contents » Hideaki Takeda / National Institute of Informatics  NII ■
O Sort contents by some criteria ■ Relativeness to the given keywords ◆TF/IDF, NLP ◆ metadata, full text ◆ Early Search Engines (e.g. infoseek) ■■ Importance/reliability/creditability of contents ◆ PageRank (google) ♦HITS Algorithm ◆ ...
»Hideaki Takeda / National Institute of Informatics  NII ■

●  A link analysis algorithm ■  Probability distribution to represent the likelihood for random access to pages ■ Assumptions similar to academic papers: ◆ More cited papers are more valuable ◆Papers cited by more Valuable papers are more valuable
O The Simplified Model
● where L is the number of links in Page v O Dumping factor

u Hideaki Takeda / National Institute of Informatics  NII (
PR(p )
R
u Hideaki Takeda / National Institute of Informatics  NII ■
0 Computation
■ Algebraic
uHideaki Takeda / National Institute of Informatics  NII (
O Information Gathering ■ Browsing ■  Filtering/Recommendation ■ Ranking O Information Integration ■ Clustering ■ Classification ■ Extraction ■ Mashup
O Clustering ■ Group data into some numbers of classes (not given) ■ Unsupervised learning ■ ex. Hierarchical Clustering, decision tree, C4.5 , k-means clustering Classification O ■ Divide data into the given classes ■ Supervised learning ■  ex. k-nearest neighbor, Bayesian Classification »Hideaki Takeda / National Institute of Informatics  NII ■
● An algorithm to build up a hierarchy of clusters ■ Agglomerative: Bottom up approach. A pair of clusters are merged into one ■ Divisive: Top down approach. A cluster is split into two.
Metric: A measure of dissimilarity     a = (a 1 ,a 2 ,...,a n )  b = (b 1 ,b 2 ,...,b n ) ■ Euclidean distance: ■ Manhattan distance: ■ Maximum distance: ■ Cosine similarity:  cosθ = (a·b)/llallbl ●  Metric for text ■ Hamming distance: minimum number of substitution between two strings with the same length ■ Levenshtein distance: minimum number of single-character edits (insertion, deletion or substitution)
Linkage criteria: the distance between two sets of data ■ Maximum: max'ƒ°¦{d(a,b):a∈A, b∈B} ■  Minimum: min{d(a,b):a∈A, b∈B}

uHideaki Takeda / National Institute of Informatics  NII (

»Hideaki Takeda / National Institute of Informatics  NII (
o Classifying objects based on closest training examples in the feature space 0 Classify an object into a class to which most frequent training samples near it belong (among nearest k samples) O Benefit: simple, often useful ●  Drawback: “majority voting” the major classes may dominate classification O Parameter ■ If k is larger, it tends to be noise tolerant but classes ambiguous ■ If k is 1, it is called “nearest neighbor algorithm”
O Curse of dimensionality /次元の呪い■ 0<a<1 ■ δV/V=1-ad ■  If d becomes bigger, δV/V→1
O Characteristics of the methods ■ Chaining (a) data (b) dendrogram B.S.Everitt: Cluster Analysis, Edward Arnold, third edition (1993) S.Guha, R.Rastogi, and K.Shim: CURE: An Efficient Clustering Algorithm for Large Databases, in Proc. of the ACM SIGMOD International Conference on Management of Data, pp.73-80 (1998) ıHideaki Takeda / National Institute of Informatics  NII ■ ■ k-means
O Extract the specified information from information sources. Natural Language Processing Techniques o ■ Sentence segmentation ■  Word segmentation ◆ Little problem for most Latin languages ◆ Serious problem for Japanese, Chinese etc. ■ Part-of-speech tagging ■ Synthetic analysis (parsing) ● Ngram Keyword extraction ■ TF/IDF
o Part-of-speech tagging ■ Identify a word class to each word in a sentence ♦ Noun, pronoun, verb, adjective, verb, adverb, preposition, conjunction, interjection (English) ◆  Verb, adjective, noun, prenominal adjective (連体詞), adverb, conjunction, interjection, auxiliary verb, postpositional particle (Japanese) ■ Tools ◆ English Stanford Log-linear Part-Of-Speech Tagger ● ●  Postagger (Tsujii lab) ●  •Lingua::EN::Tagger ◆ Japanese ● KAKASI ●  MeCab(和布蕪) , Sen ● Chasen(茶先)
0 Synthetic analysis (parsing) ■ Selection of grammar ■ Tree structure ■ Tools ◆ Japanese • KNP ● Cabocha ◆ English ● OPEN NLP
»Hideaki Takeda / National Institute of Informatics  NII ■

●   An n-gram is a substring of n item from a given string ■  1-gram (unigram) ■  2-gram (bigram, digram) ■ 3-gram (trigram) ●   N-gram model: statistical model of n-gram occurrence ■ Indexing texts

O
NLP Platform ■  UIMA , Unstructured Information Management Architecture ■  U-Compare: All-in-one NLP system
»Hideaki Takeda / National Institute of Informatics  NII ■

o Information Gathering and Integration ■  Basic technologies for handling information Knowledge is treated implicitly ■ ♦ e.g., classification reflects our knowledge how we classify information ♦ Recent development of deep learning technologies is the same trend ■   But we have some explicit knowledge ♦ We have categories for information for the specific aspects ◆ We have typologies to represent typical information pieces ◆ … ■ Need for two types of knowledge working together ◆ Implicit ◆ Explicit
0 Pick up two of the algorithms as follows. Explain them in general and make some example using the programs (find some libraries, don’t make them from the scratch). ◾ HITS Algorithm ◾ decision tree ■ C4.5 ■ k-means clustering ■ Bayesian Classification ■ Or any algorithms you are interested in ●  Deadline: May 7, Friday, 2021. I will ask you to present in the lecture on May 10. ■ Mail to the report takeda@nii.ac. Takeda / National Institute of Informatics  NII r