INLS 110-122 Spring 2005 Knowledge Discovery

Lecture Wednesday 06 April 2005

2005-04-06T15:15:00.000-07:00

Summarization

Mani, I and Bloedorn, E; Summarizing similarities and differences among related documents. Information Retrieval, 1999. 1(1-2): p. 35-67.

automatic text summarization
analysis phase
refinement phase
synthesis phase

why salient information?
establish similarities & differences
easier to compate salient items than the entire text body

by identifying both commonalities and differences, we can see what's novel
(very different than the nnotion of centroids)

represent each document of a graph with nodes as a word instance and edges are multiple types: ADJACENCY, SAME, ALPHA, PHRASE, NAME, COREFERENTIAL
weights of graph nodes: activation vector

phrase extraction:
WordNet as HP

topic-related text region spreading activation (think of nodes being lit up by queries)

two types of evaluation: extrinsic evaluation & intrinsic evaluation
extrinsic: how summary affects outcome of some other task
intrinsic: judgements of informativeness

what is it you should evaluate?
what if users disagree?
force disagreement?
compare it to system....

Okurowski, M. et al (2000). Text summarizer in use: lessons learned from real world deployment and evaluation. Proceedings of the ANLP/NAACL Workshop on Automatic Summarization, 49-58.

Mark Pope presenting

Question: we seem to be making the assumption that we are improving upon relevance rather than leaving it behind, that we are trying to get things "faster"

maybe we already know what our most relevant documents are, and instead of getting a "more efficient" representation, maybe we want to learn something remarkable
maybe we pick our favorite papers on a topic, we've read them and have grokked them well, but maybe we feel we might be missing something.

this idea of the technology suggesting the task is good
but also being more creative with problem identification than "information overload" in the "millions of relevant document" sense
let's IMAGINE some uses that are not currently part of any professional's task

Lecture Wednesday 30 March 2005

2005-03-30T15:15:00.000-08:00

Shift focus from retrieval to synthesis

Users making consequential decisions

Information systems in augmenative role

130k+ breast cancer articles (MeSH term: "breast neoplasm")
cancer 'cures' often worse than symptoms
beyond age + gender, risk factors don't explain half of breast cancer incidence

desirable properties of a system:
integrate well with work practices

In epidemiology, becasue of the non-experimental design of the studies, we should expect results to be controversial (http://www.hsph.harvard.edu/Organizations/DDIL/gep_PE.html)
risk factors should be skeptically treated in exploring any notion of causality

Cochrane reviews (http://www.cochrane.org/index2.htm)

Are there results Epi studies, RCTs, mixtures?

Conchrane reviews pertain mainly to RCTs:
"The Cochrane Collaboration and the Cochrane Reviewers’ Handbook focus particularly on systematic reviews of randomised controlled trials (RCTs) because they are likely to provide more reliable information than other sources of evidence on the differential effects of alternative forms of healthcare (Kunz 2003). Systematic reviews of other types of evidence can also help those wanting to make better decisions about healthcare, particularly forms of care where RCTs have not been done and may not be possible or appropriate. The basic principles of reviewing research are the same, whatever type of evidence is being reviewed. Although we focus mainly on systematic reviews of RCTs we address issues specific to reviewing other types of evidence when this is relevant. Fuller guidance on such reviews is being developed."
(http://www.cochrane.dk/cochrane/handbook/1_introduction/1_0_introduction.htm)

Cohort studies: (http://servers.medlib.hscbklyn.edu/ebm/2400.htm)
"A Cohort Study is a study in which patients who presently have a certain condition and/or receive a particular treatment are followed over time and compared with another group who are not affected by the condition under investigation.

"For instance, since a randomized controlled study to test the effect of smoking on health would be unethical, a reasonable alternative would be a study that identifies two groups, a group of people who smoke and a group of people who do not, and follows them forward through time to see what health problems they develop.

"Cohort studies are not as reliable as randomized controlled studies, since the two groups may differ in ways other than in the variable under study. For example, if the subjects who smoke tend to have less money than the non-smokers, and thus have less access to health care, that would exaggerate the difference between the two groups.

"The main problem with cohort studies, however, is that they can end up taking a very long time, since the researchers have to wait for the conditions of interest to develop. Physicians are, of course, anxious to have meaningful results as soon as possible, but another disadvantage with long studies is that things tend to change over the course of the study. People die, move away, or develop other conditions, new and promising treatments arise, and so on. Even so, cohort studies are generally preferred to case control studies, since they involve far fewer statistical problems and generally produce more reliable answers. "

More on Epi tests/experimental design:
http://www.vetmed.wsu.edu/courses-jmgay/GlossClinStudy.htm

Concept of "ever drinker"
working in tox labs, dosage was everything

I want to see dimensions that express dosage mean & variance
and clinical experiment OR observational study
use the height of the bar or the shade/intensity of color

Lecture Monday 28 March 2005

2005-03-28T12:15:00.000-08:00

Visualization of text data

ThemeRiver
Reminds me of babynamewizard
http://babynamewizard.com/namevoyager/lnv0105.html

Indicates a growth of newsfeeds with certain events. That there's more text.

Jon: frustrated with the neglect of some dimentions

Kohonen maps (SOM)

Pratt's DynaCat (1997):
approach is to establish predefined questions
then generate dynamic categories--hierarchical categories

Lecture Wednesday 23 March 2005

2005-03-23T15:21:00.000-08:00

Clifton, C, Cooley, R, , JM, and Rauch, J; TopCat: data mining for topic identification in a text corpus. in Principles of Data Mining and Knowledge Discovery. Third European

Experimental Design:
Factor: something you are changing
keywords being assigned
interst instead of support-confidence
person-org-place: using this representation other entities,

Level: what you are setting the factor to
It is important to cite reasons for why it is you're selecting factors, why it is you're fixing those factors

e.g., setting minimum and maximum term frequencies to get documents with a minimum of five terms in both docs. to retain as close as half of the original document corpus

e.g., why ten-fold cross-validation? because most people use it....

Blake, C. & Pratt, W. (2001). Better rules fewer features: A semantic approach to selecting features from text. In Proceedings of the Institute of Electrical and Electronics Engineers Data Mining Conference (IEEE DM 2001), San Jose, CA.

Lecture Monday 07 March 2005: CLUSTERING!

2005-03-07T15:15:00.000-08:00

Document clustering
Lecture Monday 07 March 2005: CLUSTERING!

Papers covered:

* Tao Li, Sheng Ma, Mitsunori Ogihara Clustering: Document clustering via adaptive subspace iteration, Proceedings of the 27th annual international conference on Research and development in information retrieval (2004)

* Mark Steyvers , Padhraic Smyth, Michal Rosen-Zvi, Thomas Griffiths, Probabilistic author-topic models for information discovery, Proceedings of the 2004 ACM SIGKDD international conference on Knowledge discovery and data mining (2004)

Presented by Elxsas, J.

1. What is clustering?
2. Two articles
3. Discussion

Jain, Murty, Flynn. Data clustering: a review. ACM Computing Surveys. Vol 31, No. 3, pp. 264-323, 1999.

Partitional vs hierarchical clustering
k-means: partitional square error

text clustering: locate topically similar(?) documents

open problems:
- how do you represent docs in a way these algos can take advantage of them
- document or term similarity: how is similarity measured?
- cluster interpretation: what does that cluster mean?
- cluster evaluation: are the clusters any good?

Li, Ma, Ogihara: Document clustering via adaptive subspace iteration
- addresses document similaritu & cluster interpretation
- subspace clustering

ASI:
in: M: term-document matrix
k: number of clusters (k can be estimated)
out:
D: cluster for each doc
F: subspace for each cluster

partitions docs in to k groups (optimizing D)
reduces distiance between docs and centroids

help me out: why should I expect my clusters should correspond to topics? Because we want them to? clusters aren't being defined on one-dimensional topics; we know they're probably not, and we don't know what they mean exactly, even if explicitly described.

mutual information score!!!
can be used for disambiguation: p.239 schutze

Probabilistic author-topic models for info discovery

modeling topics: a model of word generation based on statistics
modeling authors: model of author association based on topics and terms

showing increase and decrease of topics over time

association of words with language fashions: e.g., use of greek letterings vs. french letterings

assigning topics to unseen documents; separating two abstracts that have been merged; detecting an author's surprizing papers - problems well-definied by what data we have by the system...the method recommends such things by nature

EM clustering

Lecture Monday 28 February 2005

2005-02-28T15:15:00.000-08:00

Information Extraction
----------------------

Two general approaches to information systems:

1. knowledge engineering
- hand-constructed grammars
- human experts design rules
- e.g., Paice & Jones, Blaschke et al

2. trained systems
- use stats where possible to learn rules
- Riloff less info, not fully learned; Califf & Mooney

Even trained system approaches require background knowledge of some sort

knowledge vs. data trade-off
1.2 million words needed to learn statistically

levels of info

text
words e.g., POS
noun phrase e.g., phrase units
sentence level
inter sentence level e.g., anaphoric resolution & discourse analysis
template level -vchanges format to output required

effort increased as

AAAI Applet & Hobbes

IE techniques:
KB -
Semi-learned
Learned

Representation for Learning
---------------------------

pre filler pattern
filler: what you want
post filler pattern

RAPIER: Robust automated production of information extraction rules

covering algorithm: takes a sentence that is a positive example
while more positive examples remain, create a rule that removes majority of positive examples

(seems like it would have pretty good precision but not so good recall)

RAPIER is one good example of a covering algo

To do week of 28 Feb 2005

2005-02-28T14:51:00.000-08:00

TO DO FOR THE TM PROJECTS (independent study/kdd)

load hypernym tree
correct synset tree
regenerate webterm+lragr+synset table
regenerate statistics for table

for each term with multiple POS,
find hypernym I-V
add hypernym I-V columns & add those hypernyms
find lowest level reduction

figure out how to backtrack to POS
install POS tagger
for every sentence
retrieve & reconstruct sentence
submit sentence to pos tagger
retrieve results
insert POS info back to webterm data set

now retrieve data set limited to POS={N, V, ADJ, ADV}
create as table webtermtagged

equijoin webtermtagged on webtermlragrsynset

generate statistics again

Lecture Monday 14 February 2005

2005-02-14T15:15:00.000-08:00

papers:
Marti Hearst
Henry Small

heavy stemming good for high recall

Pruning our document space tf*idf

term freq * inverse doc freq

term frequency in document
idf: two options
inverse of the number of documents with term i
inverse of the log of the number of total docs ( more typical; controls for wide range) which is log (n/dfi)

co-occurrence analysis

send in statistics
how many unique words?
stemmed words?
some data that describes the dataset

we can avoid using a "search-centric" approach by assuming we're discovering knowledge? by assuming

but at the end of the day
we still want to generate hypotheses

generate vs. discover
discovery seems to be a search paradigm

avoiuding search-centric: removing the document as the denominator

if it's already explicit then it's searching not discovery
if it's not explicit then it's discovery (or hypothesis generation)

generation:
vs:
discovery:

we had an experiment where we cited a percentage of truth to a statement, but we need a reliable denominator that says, this is 100% true

concern surrounds user

Swanson:
something is not in the literature

if we are generating hypotheses, then it is besides the point as to whether we should predicate discovery in a relative or absolute sense

testable hypotheses
unverifiable statements:
unfalsifiable statements:
generating poetry

Thoughts on knowledge discovery versus hypothesis generation

2005-02-11T21:47:00.000-08:00

reading some of the philosophy behind scientific reasoning...discussions of incommensurability from Polanyi, Kuhn, Feyerabend...noting that Kuhn believed alternate hypotheses should be entertained only when science is at a point of crisis while Feyerabend suggested we might always want to entertain alternatives as a necessity perhaps of scientific reasoning...someone suggests that Kuhn's theories do not apply to biology...oxidative phosphorylation is perhaps a good example for examining incommensurability, as two competing theories battled from 1960 or 61 until the late 70s....

Some argument

If it is our goal to mine information from the literature, and if the best we can do with mining text is to generate hypotheses rather than make discoveries (because making knowledge discoveries requires a tight coupling between the signifier and the signifiedm between the world and the language used to describe it, whereas generating hypotheses suggests we are merely producing ideas that need to be tested based on what's already present--generated hypotheses as emergent properties of the interaction of texts and text mining applications), then, given that information is essentialy what captures variance, we might want to generate as best as possible orthodox hypotheses--hypotheses with a majority of data already confirming those hypotheses--and, more importantly, heterodox hypotheses--hypotheses suggested by the literature with little or no data supporting them. The more heterodox a hypothesis, the greater the potential for information. It's a risk/reward trade-off: the costs in testing heterodox hypotheses given the reduced likelihood of veracity may be offset by the motherlode potential of confirming but one extremely heterodox theory.

Further, we may want to mine the various ways these hypotheses, whether heterodox or orthodox, are contradicted in the literature. It seems out burden in science is to posit a hypothesis and then try our best to disprove it in every way possible, rather than try to prove it.

http://tinyurl.com/4y39s
http://tinyurl.com/5j5b5

Metaphors defining our cognitive scaffolding, which in turns defines and limits how it is we witness novel things (or any thing, for that matter) and deem them interesting

Friday CRADLE Talk Mining Spatial Patterns from Protein Structures

2005-02-11T13:03:00.000-08:00

Luke Huan

Seq->Struct->Function

Structure indicates function

Mine frequent subgraphs; retrieve spatial motifs frm protein structure data

Global vs. local alignments of protein structures
local lignments are motifs

Mining for subgraphs/spatial motifs is a challenging problem for data mining

How to model protein w/ set of points
each aa us presented by a point in a 3d space; protein structure is a point set
LCP largest common point set problem

Is clique hashing a useful pattern finding approach for other domains?
Heavy combinmatorial approach

SCOP Structureal Classification of Proteins DB
10 classes
800 folds
1294 superfamilies
2327 families

every protein entered into this db is annotated using this scheme

hypergeometirc distribution:
The problem of finding the probability of such a picking problem is sometimes called the "urn problem," since it asks for the probability that i out of N balls drawn are "good" from an urn that contains n "good" balls and m "bad" balls. It therefore also describes the probability of obtaining exactly i correct balls in a pick-N lottery from a reservoir of r balls (of which n = N are "good" and are "bad"). (from MathWorld http://mathworld.wolfram.com/HypergeometricDistribution.html)

Searching for biological relevance:
reading papers: key word search, drawing from experience
website search
talking to people who know the subjects

presented an algo for finding frequently occurring spatial motifs
discovered motifs are specific, measured by low P-values using the hypergeometric distribution

motifs they discover are highly specific, measured by low P-values

mapping structures to highly specific motifs
how about mapping sequence

Monday 07 February 2005 Lecture: Interstingness

2005-02-07T15:15:00.000-08:00

Silberschatz & Tuzhilin

Actionable & Unexpected makes for interestingness

possibly: unexpectedness is roughly equivalent to actionability

unexpectedness as a criteria for interestingness is uninteresting

valid
understandable
novel
-->interestingness<--

Are there uninteresting facts that arise that somehow might cause beliefs to change? Or a lack of facts, can they cause beliefs to change?

the data vs the processing of it?

this statement is either trivial or false

terms change? terms must stay the same

statements

what is my confidence factor that all birds can fly? my confidence is low but some birds can fly
unexpectedness roughly equivalent

confidence factor & CYC: assign confidence associated with facts

Rational agency:
http://www.ryerson.ca/~dgrimsha/courses/cps720/rational.html

expected data returned
but
beliefs change

something between data and belief that seems absent form the discussion in the paper
there must be some sort of representation in between that converts data to belief that might be rational and might convert expected data into new beliefs
e.g., we might be able to test for significance

understanding was somewhat removed; a telltale sign is this elimination of the intermediary between the receipt of data and the formulation of belief

throw in data that is wildly aberrant & witness change?
unexpected data witness belief changes

monoitor belief changes, see if enough data is out there

what's better? monotinicity is conserved or maximally rejected?

reaction essay for every paper?....

(x/y)
correctly classified/incorrectly classified

homework:
pick a UCI dataset that starts with the same letter as your first name, if not, then last name
explore different classification algos within the WEKA toolkit
email Cathy the decision tree + 1 more classifier

2005-02-03T09:15:00.000-08:00

Evaluations

Novelty
C. D. Fellbaum. WordNet: An Electronic Lexical Database. MIT Press, Cambridge, MA, 1998.

Basu,S. Mooney,R.J., Pasupuleti, K.V. and Ghosh,J. Evaluating the Novelty of Text-Mined Rules using Lexical Knowledge KDD-2001

Understandability Bias
Pazzani, M.J., Mani,S., Shankle,W.R. (2001). Acceptance of Rules Generated by Machine Learning among Medical Experts. Methods of Information in Medicine; 40: 380-385

Monday 31 January 2005 Lecture

2005-01-31T15:15:00.000-08:00

KD: Association

Typically used for recommendations
Also called market basket analysis
What do people buy together? What attributes are associated

left hand side: antecedent
right hand side: consequent

association rule must have an associated population P
- pop consists of a set of instances
e.g., each sale at a store is an instance
- set of all transactions is the population

set of items I {I1, I2, ..., Im}
transactions: D = {t1, t2, ... tn}
Itemset
set of items that satisfy some criteria or other

association rule algo
we are generally only intersted in association rules w/ generally high support

A priori algorithm
If {ACD} is frequent, then all subsets of {ACD} are frequent ({AC}, {AD}, {CD})

Two questions: why is unidirectional causaility implied by the terminology (e.g., antecedent, consequent)? Isn't it bidirectional by nature? Direction on the graph as we speak of it now is not temporal

Also, why aren't we interested in low support? Do we want to get only the best association rules in all cases, or sometimes do we want to describe the population space as completely as possible? isn't that determined by some extent to how we plan on using the results?

Re: different feature representations yield different

Confidence vs. support: interestingness!

We may have that info already present in a DB...

Another algo: Instance-Based Learning

Decision trees, clustering and association rules are created on historical data, then model us used to predict/describe class of new instance

Instance based: no model is created ahead of time
- learned when a new instance arrives
- identify historical data that is simlar

Similar challenges as clustering with respect to distance
symbolic distances are particualarly difficult
instance-based learning effective when efficient db design
similarity is being pushecd into the db--next-generation dbs will enable similarity-based queries

Wednesday 26 January 2005 Lecture: Clustering

2005-01-26T15:15:00.000-08:00

Clustering

Qualities of a similarity metric
Clustering algos
evaluation discussion

finding natural groupings among collection of objects into k sets such that the avg distance of points form the centroid of their assigned group is minimized
centroid: average of coordinates in each dimension
mimimum avg pairwise distance

question: we typically pick a k, cluster, then consider whether we'd like to change k. are there more systematic ways of doing this? setting k to a range; have a formal means for deciding between k values

how is unsupervided learning different from dredging?

finding patterns and then assigning meaning

we can come up with a set of features
clustering is subjective because deciding what groupings are best is a subjective process, and deciding what serves as the basis for similarity is likewise subjective

Distance metric props
symmetry
constancy of self-similarity
positivity (separation)
triangular inequality

two types of clustering
partitional
hierarchical/subspace

use dendograms: root/terminal branch/internal branch/internal node/leaf

desirable props of a clustering algo
scalabilty
ability to dela with diff data types
minimal req's for domain knowledge to determine input params
able to deal with noice & outliers

(number of objects)!/2 - number of objects

hierarchival is O(n2); exponentials don't scale well

simple clustering: with numeric data only - K-means
pick a number of (K) of cluster centers
move each centroid to the mean of each cluster
repeat (2,3) until movement is less than a sentinel value

value of your k selection

inter and intracluser distance values

partitioned clustering
----------------------

how do we evaluate clustering?

birch algo example

question:
we're hoping that our clusters are somehow meaningful summaries of subsets of the attributes
but aren't we somehow more prone to data dredging in unsupervised approaches

well, everything is subject to verification, validity, meaningfulness

Distance revisited: measuring a distance been an object and a cluster or two clusters
single linkage (or nearest neighbor) - distance of the two clostest objects in the different clusters
complete linkage (furthest neighbor) - greatest distance between any two objects in the different clusters
group average

For class presentation:

B1 - Introduction to KD est Feb 9
Don R. Swanson & Neil R. Smalheiser An interactive system for finding complementary literatures: a stimulus to scientific discovery. Artifical Intelligence 91:183-203; 1997.

B8 - Document Summarization est Mar 28 or 30
Generating Patient-Specific Summaries of Online Literature
Kathleen R. McKeown, Desmond A. Jordan, Vasileios Hatzivassiloglou
*http://www.ics.uci.edu/~pratt/courses/papers/TextMining/patient-specific-summaries.pdf

Monday 24 January Lecture: Classification

2005-01-24T15:15:00.000-08:00

Classification example: selecting safe fruit from dangerous fruit on a deserted island with no info

nominal attributes
empirical approach
requires knowledge of the conclusion: THE CLASS

Conclusion|Skin|Color|Size|Flesh
----------------------------------
class nom nom nom nom

decision trees! if attribute 1=value1, then subtree 1
else if attribute 1=value2 then subtree 2

(Question for later: are there decision tree algos that use something other than number of instances in each class to calculate information gain [or some discriminant other than information gain]?)

decision tree classification:
assume you know the conclusion C that has any pof the values c1...cn
that an attribute can take values a1...an

then you can calculate P(cj|ao)

P(C=safe|skin=hairy) = 6/8=0.75
P(C=safe|size=small) = 5/9=0.55

conditional probability close to 1 is a

Step 1: partition data into groups based on a partitioning attribute and partioning condition
Step 2: continue until stop condition reached
- all or more of items belong to the same class
- all attributes have been considered and no further partitioning is possible
- such a node is a leaf node

INfo[2,3] = 0.972 bits
Info[4,0] = 0.0 bits
Info[3,2] = 0.971 bits
goodness for conditions = 0.693 bits
(5/14)*.971 + 4/14* 0.0 + (5/14)*0.971 = 0.693
Gain=0.247
no partiti

(Is there some way to handle assume our attribute list is complete?)

(Rescaling/revaluing attribute values may be helpful for useless attributes)

Thursday 19 January 2005 Lecture: Terminology

2005-01-19T15:15:00.000-08:00

central questions of KD
what data should you use?
what goes into the mining task?
what will the patterns look like?

what data should you use?

Inputs required:
attribute type
nominal/ordinal/interval/ratio
(vals are names/scale with meaningless interval but meaningful order/scale with meaningful interval/scale with true zero; zero is a true zero)
type
symbolic/symbolic/numeric/numeric
order
n/y/y/y
e.g.,
zip/ranking/deg Celcius/kelvin

attributes can be considered along a spectrum:
from a two-valued nominal attribute to a ratio

nominal takes two bits
ordinal: as many symbols as needed
interval: integer
ratio: float

Concept is
‘the thing to be learned’ p38

concepts can be predictive or descriptive, supervised or unsupervised, transparent or black box

goal of predictive dm: induction
predictive mechanisms
- classification
- regression (linear: y=ax+b):
given a set of param-value-to-function-result mappings,
WITHOUT KNOWING THE REAL FUNCTION,
predict the function result for a new param-value

descriptive concepts
association rules & clusters
associations are often first step in detecting causation (or making a prediction)
clustering good for epidemiology; for detecting source of a problem

supervised vs. unsupervised
supervised:
input: labeled data
goal: identify the attribute combination that maximizes chance you get correct concept label
unsupervised:
input: unlabelled data
goal: identify groups within the data

black box vs. transparent

is the output black box or transparent?
neural network good example of a black box
id3 decision tree good example of a transparent

black box: goal is to get categories right (good for control systems)
transparent: understanding the rules or ways is also useful

bias
------

high-dimensional data will have multiple "correct" concept descriptions
bias is not bad
algos are greedy and sometimes insist their results are best

we CAN use low quality data? yes, but we need high quality data to map it to the low quality

what role does database design principles play in KD process?
flexibility in kinds of queries you might write/difficulty as well for accessible data
without those queries you might not be able to pick what inputs you want, what data you use
scalability, maintenance, indexability in RDBMS

A1 Readings Pt. 3 DeGruy; Guernsey

2005-01-17T17:24:00.000-08:00

DeGruy, Healthcare Applications of Knowledge Discovery in Databases, Journal of Healthcare Information Management, vol 14 no 2, summer 2000

DeGruy makes the case for KDD in healthcare. Am painfully familiar with the questions, slogans, debates, & players.

Successful helathcare KDD implementations:

HMO determined disease-specific risk for its members: potential for targeted intervention (or potential denial of coverage); means can likewise be used to identify new risk factors in a population
fraud detection in insurance claims
NY Worker's Compensation Board decision trees for streamlining compensation claims
EHRs (electronic health records) are ripe for KDD - who needs flu shots; who isn't following needed treatments, etc.
medical marketing

NYT article oct 16 2003 "Digging for Nuggets of Wisdom", Lisa Guernsey

Text mining vs. information retrieval: text mining goes beyond tokens, categorization, linking unconnected documents, creating visual representation of related docs, synthesizing new ideas

Text mining vs. data mining: text starts with unstructured data: text

Determine context/resolve ambiguity/select semantic concepts

Text mining might not recognize subtlety

A1 Readings Pt. 2 Fayyad

2005-01-17T16:55:00.000-08:00

Fayadd, et. al, "KDD Process for Extracting Useful Knowledge from Volumes of Data", Communications of the ACM, November 1996, Vol 39, no 11.

Manual data analysis is swiftly becoming impractical. The number of databases is growing, and so too is the average dimensionality (records times attributes). Automation is the answer, Fayadd, et al, contend.

Fayadd et al labor to differentiate KDD from DM. DM is but a step in the KDD process which involves:

Data collection
Data selection (picking our topic)
preprocessing of target data (prepping our relevant data)
transformation of preprocessed data (creating useful structured representations of relevant data)
mining of transformed data
interpreting discovered patterns (deriving knowledge)

DM is only step 5 of this six step process.

The authors raise the concern that the discovery of a pattern from transformed data does not always mean that the pattern is statistically significant. Fundamental is the statistician's art of hypothesis selection.

Ahh, method.

Discovered patters should neither be underfit or overfit: overfitted patterns typically fail to be predictive, while underfit models don't provide very much information.

Interestingness:
Process is assumed to be nontrivial
Patterns should be valid for new data to some degree of certainty
Patterns should be novel to the system, and hopefully to the user as well
Patterns should be understandable - simplicity?

Model functions in DM:

classification
regression
clustering
summarization
dependency modeling
link analysis
sequence analysis

Challenges & issues:

What's interesting or useful? What's not? Knowledge leverages some amout of subjectivity, and that subjectivity is the very essence of making judgments about such things as usability, interestingness, informativeness, relevance, and so on. Insert here the role of the information scientist.

A1 Readings Pt. 1 Lesk

2005-01-17T15:50:00.000-08:00

Lesk, M. "How Much Information...?"

In 1997 M. Lesk estimated volume of information in the world at several exabytes (~ several billion GB). Spirit of article is dedicated to haphazard guessing & makeshift counting method (e.g., estimates of hard drive sales), but entertaining nonetheless. Less entertaining and more haphazard is the later speculation on the "volume" of "human memory;" Lesk cites Landauer's estimate of brain capacity at 200MB, which is manifestly dubious, and then Lesk calculates total human memory to be just over one exabyte. Oops. Landauer, at least according to Lesk, figures the brain holds 1,000 to 100,000 neurons per bit of memory, based on Landauer's recal tests of human memory. There are obvious reasons why recall tests are a bad way of measuring the amount of memory (more in the computer sense than in the sentimental sense) a human brain can retain. Computers of course store memories in 0s and 1s, but, importantly, those 0s and 1s do not always add up to high level, semantically-rich information. Some of this memory can be very low-level. So human recall tests prima facie bias results to be very low.

To be fair, just as we measure hard disk capacity (and just as Lesk uses hard drive *capacity* quantity figures for his argument) we should guess the very same way with the human brain: count the number of bits. Now, a human brain has ~10e14 neurons, but hardly is a neuron a single bit. Neurons have a fairly high order of ways in which they can articulate: number & length of dendrites & axons alone are but two dimensions which we may count to get an idea of a possible number of states for each neuron. We might also have a few dimensions for measuring neural cell signalling; it's unlikely that nerve cells have just one signal to pass, and it's equally unlikely that the signal is strictly digital. There may be many other dimensions with respect to neurons to countas well, various location-dependent interactions with other aspects of the brain, for example. But we'll skip that arena. We might also count possible states for astrocytes, a species of glial cell, since they may also be involved in "saving state."

10e14 nerve cells

conservative estimate of states per cell
---------------------------------------
avg number of synapses: 10e4
avg number of sodium pumps: 10e6

10e4*10e6=10e10

total number our bits based on neurons: 10e14 * 10e10 = 10e24

one exabyte is approximately 10e19 bits
10e24 bits, our current estaimate for storage capacity of a single human brain without counting astrocytes, is approximately 100,000 times larger than Lesk's estimate for the total of the world's information, and is 10e16 larger than Landauer's estimate for a single brain.

By the numbers, and by the paper's current methods, the storage needed to cover the capacity of human neurons would be in the order of 10e34 (6*10e9*10e24) bits, or approximately 100 trillion exabytes.

It cannot be remembered for us wholesale.

To be very honest, I don't take seriously any claims to strong AI, and don't fancy the parallels routinely drawn between human experience and computer I/O. The metaphors of computing just don't work very well, except maybe to dumb down and underestimate our understanding of the myriad complexities of this lump of gray matter and its correlated but yet-to-be-verified partner, the mind. For example, there's simply *no* equivalence between an actual sentence in an ASCII file and that same sentence memorized and "inside" a human head. That sentence "inside" the human head ("inside" is in quotes, because no one can actually locate it, touch it, verify it) . probably has a tonb of other information attached to it, and the recall task brings with it tons of other information. In other words, when it comes to the human mind, a sentence is not a sentence. A sentence (e.g., ASCII) is not a sentence (either in the mind's eye OR in the brain).

So I digress. Lesk's more mild claim that we will be able to store all our media digitally seems reasonable. What this means for text mining is that we will have data, lots of data, for mining (if we gain access to it), and that the quantity of data will demand more and more mining work for information retrieval, classification, discovery, and synthesis.