KakaoTech Bootcamp - (2024.09.19 ~ 12.27)

KTB-Sixmen

KTB-Sixmen has 5 repositories available. Follow their code on GitHub.

GitHub

Notion – The all-in-one workspace for your notes, tasks, wikis, and databases.

A new tool that blends your everyday work apps into one. It’s the all-in-one workspace for you and your team

Notion

프로젝트 개요

깃트폴리오 - GitHub API를 활용한 LLM 기반 이력서 자동 생성 서비스

• 깃허브 계정을 연동하여 이력서를 자동 생성할 수 있는 기능
• 다른 사람의 이력서를 열람할 수 있는 SNS 기능

프로젝트 추진배경

프로젝트 목표

기술 스택

아키텍쳐 구조

AI 서비스 플로우

주요 기능

추가기능 고도화

기대효과

경쟁 서비스

비즈니스 모델

Flow-Chart (MVP)

기능구현

팀 문화

프로젝트 개선 과정

Appendix, (AI Observability System)

langfuse를 활용한, AI 모니터링 시스템 구축

• 트레이싱을 활용하여, 모델 사용 토큰 및 가격 트래킹
• 서비스 로깅을 하며, 에러케이스들 체킹
• 이력서생성 개선을 위한 병목 구간 체킹

kakao x goorm, Hackathon (2024.09.04 ~ 09.07)

KakaoTech-Hackathon-Dream

KakaoTech-Hackathon-Dream has 5 repositories available. Follow their code on GitHub.

GitHub

프로젝트 개요

• 생성형 AI(LLM, RAG, Diffusion model)를 활용하여 노년층이 이루지 못한 꿈을 바탕으로 ‘꿈을 이룬 나’에 대한 이야기와 이미지를 생성하고, 이를 통해 관련된 교육 프로그램 및 직업을 추천하는 서비스

추진배경

현재 우리 사회가 직면한 주요 문제는 저출산으로 인한 급격한 고령화이다. 노년층 인구 비율은 꾸준히 증가하며 인구 구조가 노년층에 집중되는 반면, 이들의 사회적 고립은 더욱 심화되고 있다. 이러한 사회적인 고립의 확산은 노년층의 삶의 만족도 저하로 이어진다.‘국민 삶의 질 보고서’에 따르면 노년층 중 삶에 만족한다고 답한 비율은 29.9%로, 이는 아동/청소년(56.6%), 청년(41.8%), 중장년(38.0%)에 비해 상대적으로 낮은 수치를 보인다. (통계청 - 2022년)

 이를 완화할 수단으로 ‘시니어 교육’이 주목받고 있으며, 노년층의 사회 참여와 교육을 촉진함으로써 낮은 삶의 만족도를 개선할 수 있는 적합한 방안으로 평가되고 있다. 하지만, 방대한 정보와 복잡한 경로 때문에 시니어 교육이 제공되더라도 접근이 어렵고, 이로 인해 자존감이 낮아져 새로운 시도를 주저하게 되어 고령층의 사회적 소외가 심화되는 악순환이 이어지고 있다.

(통계청 -2018)

 이러한 문제를 해결하기 위해, 우리는 생성형 AI 기술을 활용하여 노년층이 꿈꾸던 이야기와 사진을 만들어가는 놀이 방식으로 디지털 장벽을 낮추려 한다. 또한, 이러한 접근 방식을 통해 시니어 교육 프로그램과 구직 관련 정보를 제공하며, 추천 시스템을 기반으로 교육 및 채용 회사들로부터 커미션을 받는 B2B 모델로 운영할 계획이다. 더 나아가, 차후 정부와 협력하여 노인 복지기관을 통해 서비스를 보급하고, 이를 B2G 디지털 문화/교육 플랫폼으로 확장하고자 한다.

주요 기능

1. 핵심 내용:

• 사용자 맞춤형 이야기 생성: 사용자가 입력한 정보를 바탕으로 LLM generation model이 RAG 기법과 Diffusion model 활용하여 독창적인 이야기와 이미지를 생성. 이 과정에서 최신 텍스트 및 이미지 생성 기술을 활용.
• 교육 프로그램 및 취업 정보 매칭: 생성된 이야기에서 주요 키워드를 자동 추출하고, 이를 바탕으로 유사도가 높은 교육 프로그램이나 취업 정보를 추천하여 사용자에게 실질적인 학습과 진로 선택을 돕는 서비스 제공.

2. 기술적 활용:

1. AI 기반 텍스트 생성 (LLM - GPT, RAG, langchain 등):
   • 자연어 처리 기술을 활용하여 사용자가 제공한 입력을 기반으로 사용자가 꿈꾸던 스토리를 생성.여기서 LLM(대규모 언어 모델)을 사용하여 문맥을 이해하고 자연스러운 텍스트를 생성 RAG(Relevance-Augmented Generation) 기법과 Langchain을 활용하여 외부 데이터 소스를 참조, 관련성 높은 정보를 텍스트 생성에 반영.
     - RAG 활용방안: 자서전 데이터들을 카테고리별로 디비에 저장한 뒤 스토리생성 부분에 맞게 가져올 것
     - Langchain 활용방안: 책을 작성하는 방법과 유사하게, 기승전결과 같은 맥락으로 스토리를 뽑을수 있도록 프롬프트를 작성할것.
   • 선택 이유:GPT 같은 대규모 언어 모델은 문맥 이해와 자연스러운 언어 생성에 뛰어나며, 특히 사용자 맞춤형 이야기를 생성하는 데 강력한 성능을 보임. RAG 기법을 통해 실시간 외부 데이터 검색과 참조가 가능해 더욱 풍부하고 최신 정보를 바탕으로 한 텍스트 생성을 지원. Langchain은 이러한 데이터 소스와 LLM을 효과적으로 연결하여 사용자 맞춤형 스토리를 효율적으로 생성하는 데 기여.
2. 텍스트 기반 이미지 생성 (DALL-E, Stable Diffusion 등):
   • 생성된 이야기를 시각적으로 구현하기 위해 AI 기반 이미지 생성 기술을 사용. 이는 스토리와 일치하는 맞춤형 이미지를 제공하여 사용자 경험을 극대화.
   • 선택 이유: 최신 텍스트-이미지 모델은 간단한 텍스트 설명을 기반으로 창의적인 이미지를 생성할 수 있어, 시각적 콘텐츠를 제공함으로써 사용자 만족도를 높일 수 있음.
3. 추천 시스템 (유사도 기반 매칭):
   • 생성된 이야기에서 BERT와 같은 NLP모델로 키워드를 추출하고 교육 및 취업 데이터베이스의 내용을 비교하여 유사도가 높은 프로그램을 사용자에게 맞춤 추천.
   • 선택 이유: 개인화 추천 시스템은 사용자의 관심사와 연계된 교육 및 취업 정보를 제시하여 사용자 만족도를 높이고, 교육 및 취업 연결성을 강화

3. 독창성, 우수성: 

기존 교육 및 취업 정보 추천 서비스는 노인층이나 고령층이 접근하기 어렵고, 사용자의 과거 목표와 감정을 연결하지 못한다는 한계가 있다.

• 과거 꿈 기반 몰입형 경험: 사용자가 어린 시절 꿈을 입력하면, AI가 스토리와 이미지를 생성해 감정적 몰입을 제공하여 교육에 대한 동기를 부여
• 고령층 맞춤형 서비스: 과거의 꿈을 되살려 감정적 연결을 강화하는 몰입형 서비스를 제공하며, 고령층이 쉽게 접근할 수 있도록 설계
• 교육 및 직업 추천 연계: 스토리에서 추출된 키워드로 관련 교육 프로그램과 직업 정보를 추천하여, 사용자가 자신의 꿈을 실현할 수 있는 실질적인 경로를 제시

이 서비스는 노년층의 꿈을 기반으로 한 몰입형 경험과 맞춤형 교육 및 직업 추천을 제공하여 실질적인 동기 부여와 학습 기회 확대를 지원하는 점에서 독창적인 차별점을 가진다.

생성형 AI 기술

서비스 흐름

아키텍쳐 구조

이번 프로젝트는 Kakao x Groom 해커톤과 KDT 해커톤에 연이어 참여하면서 진행됐었다. 팀원들은 부트캠프에서 마음맞는 동료들로 구성됐고, 우리는 의미 있는 결과물을 만들어내기 위해 제한된 시간 속에서 각자의 열정을 쏟아부었었다. 특히 두 해커톤에 동시에 참여해야 했던 상황이라, KDT 해커톤에 제출할 아이디어를 먼저 선정하고 나서 Kakao 해커톤을 통해 이를 미리 테스트하며 서비스의 가능성을 검증해보기로 했었다.

초기에 아이디어를 정하는 단계에서는 팀원들이 다양한 창의적인 서비스 아이디어를 제안했었다. 노인과 아이들을 위한 그림 치료 애플리케이션이나, 노인 베이비시터 매칭 플랫폼, 시니어를 위한 맞춤형 커뮤니케이션 서비스(할카오톡) 등 여러 가지 방향으로 논의가 오갔었다. 하지만 이미 존재하는 서비스들과 차별성도 부족했고, 기술적으로 구현 가능한지, 그리고 짧은 기간 안에 실현할 수 있을지를 고민하면서 최종적으로 구현할 서비스 아이디어를 확정하는 데 시간이 꽤 걸렸었다. 팀원 모두가 비판적인 시각으로 토론에 참여하며, 각자의 관점에서 아이디어를 검토하고 다듬어가는 과정을 거치면서 더 나은 방향성을 정리할 수 있었었다.

특히 KDT 해커톤에 제출할 기획서를 작성하는 데 정말 많은 시간을 쏟아부었었다. 이 기획서 작성은 단순히 아이디어를 정리하는 것을 넘어서, 실질적인 사업성과 사용자의 요구를 충족시키는 서비스로 발전시키기 위한 중요한 과정이었다. 우리는 시장 조사를 통해 서비스 수요를 분석했고, 관련 통계 자료를 조사하면서 기획서를 더 탄탄하게 만들었었다. 이 과정에서 모든 팀원이 단순히 개발자의 역할을 넘어 PM 역할까지 경험할 수 있었고, 서비스 기획과 문서 작성 역량도 크게 성장할 수 있었었다.

그런데 기획에 너무 많은 시간을 쓰다 보니 실제 구현할 시간이 많이 부족해졌었다. 해커톤 중 기간 4일 중에 3일을 KDT서비스 기획서를 작성하느라 모든 시간을 보냈다. 그래서 우리는 부가적인 기능들을 생략하고, 핵심 기능에만 집중하기로 결정했었다. 먼저 서비스의 전반적인 흐름과 기술적인 이해를 팀원들 간에 맞추고, 각자 역할을 명확히 분담했었다. 기술적인 부분을 서로 이해시키는 과정에서 여러 차례 논의를 거쳤고, 서비스 아키텍처를 다시 정리하면서 각 파트에서 발생하는 문제들을 빠르게 해결하기 위해 계속 소통했었다.

개발 과정에서 자잘한 이슈들이 계속 발생했었지만, 팀원들의 협력 덕분에 그런 문제들을 빠르게 해결해 나갔었다. 우리는 끊임없이 서로를 지원하고 피드백을 주고받으면서 밤을 새우며 기능 구현에 집중했었다. 특히 기술적 어려움들이 발생할 때마다 서로의 경험과 지식을 공유하면서 문제들을 해결했고, 끝까지 포기하지 않고 목표를 달성하는 데 주력했었다.

결국 우리는 핵심 기능을 성공적으로 구현할 수 있었다. 이 과정을 통해 팀워크의 중요성을 다시 한 번 깨달았고, 제한된 시간 안에서도 효율적으로 협업하면서 기능을 완성해 나가는 방법을 배웠었다. 더불어 개발자로서의 기술적인 역량뿐만 아니라, 기획과 협업, 문제 해결 능력 등 다방면에서 성장할 수 있었던 값진 경험이었다.

우리는 원했던 서비스를 정확하게 만들게 되었고, 대상을 받지않을까라는 기대에 부풀었지만 아쉽게도 수상은 하지못했다. 하지만 짧은기간동안 몰입해서 목표했던 서비스를 만들어내는 과정에서 협업하고 맡은바를 다하면서 많이 성장했다고 생각한다. 좋은 팀원들을 만났고 여기서 그치지않고 다른 대회들을 함께 나가면서 발전하기로 약속했다.

다들 고생많았어 :) ㅎㅎ

서비스에 관한 회고

• 비즈니스모델에 대한 고민 ( 그냥 스토리,이미지 생성하여 교육프로그램을 추천하는것이 아닌 고령층들을 위한 교육플랫폼만들기로 바꿔야하나?, 개발하려는 서비스가 디지털장벽을 허물기위한 수단중 하나라고 어필하지만 설득력이 없어보임…등등)
• 기술적인 부분( 모델을 gpt4가 아닌 기존 llm모델 사용해서 스토리생성하는 모델 만들어보기(서버의 한계), TTS를 추가한다던지, RAG를 사용할때 한국의 시대적 배경을 넣어서 텍스트 생성하기, 이미지에 사용자 얼굴 삽입하기)

2024 KakaoTech Bootcamp - Machine Learning Model Serving (2024.07 - 2024.08)

KakaoTechBC-GOATNINE

KakaoTechBC-GOATNINE has 3 repositories available. Follow their code on GitHub.

GitHub

프로젝트 개요

• 사용자에게 개인 맞춤형 맛집 추천 서비스를 제공하기 위해 머신러닝 모델을 서빙하는 웹 애플리케이션을 개발 
• 사용자가 원하는 음식 종류나 키워드를 입력하면, 모델은 실시간으로 사용자 근방의 적합한 맛집 리스트를 추천

주요 기능

API 엔드포인트 설계:

• 사용자의 입력(음식 종류, 키워드)을 받아, 현재 위치 기반으로 추천 맛집 리스트(가게이름, 점수, 빈도수가 높은 단어)를 제공하는 API를 설계함
• 추천된 맛집 리스트는 사용자 근방에서 접근 가능하도록 정렬되어 제공되며, 지도 상에 시각적으로 표시함

데이터 수집:

• 데이터 소스: 리뷰 신뢰성이 높은, 카카오 맵을 활용하여 식당의 별점, 방문자 리뷰 텍스트, 방문자 수, 사용자 별 평균평점 등의 데이터를 수집
• 데이터 수집: selenium, beautifulSoup을 활용하여 병렬 크롤링을 진행한뒤, elastic search에 데이터를 저장하고 kibana로 데이터를 분석

데이터 전처리 및 레이블링:

• 리뷰 텍스트 전처리: 리뷰 데이터는 정규표현식 및 토큰화를 통해 필요 없는 부분을 제거하고, 분석에 적합한 형태로 가공, 이러한 전처리 과정을 통해 모델이 텍스트 데이터를 효과적으로 학습
• 라벨링: 사용자 만의 평균 평점을 기반으로 라벨링 작업을 수행한뒤, 차후에 직접 만든 모델로 레이블링(0,1,2)된 리뷰들을 다시 평가 진행하며 라벨링 직접 수정 과정을 거침.

특색있는 기능:

• KcELENTRA, pre-trained된 모델과 직접수집하고 레이블링한 데이터를 활용한 감성평가 모델보유.
• Sentence-BERT 모델을 사용해 리뷰 텍스트를 임베딩으로 변환.
• UMAP으로 임베딩을 차원 축소하여 군집화 효율성증가.
• HDBSCAN을 사용해 리뷰들을 자동으로 군집화 1:가장 많은 군집, 0:적은 군집, -1: 노이즈
• 군집별 단어 분석: 각 군집에 속한 리뷰들에서 자주 언급된 단어들을 추출.

기술스택

아키텍쳐 구조

Data Pipeline, AI Model, Clustering

Issues & Problem-Solving

Notion – The all-in-one workspace for your notes, tasks, wikis, and databases.

A new tool that blends your everyday work apps into one. It’s the all-in-one workspace for you and your team

Notion

성능 이슈를 해결하기 위해 주기적으로 모델 성능을 분석하고, 각종 하이퍼파라미터를 조정하며 최적화 과정을 거쳤음. 특히, 성능 개선을 위한 주요 접근 방식으로는 다음과 같은 방법을 시도함:

• 데이터 전처리 개선
• 모델 아키텍처 조정
• 학습 속도와 성능의 균형을 고려한 최적화

기존에 222초 걸리던 시간을 벡터 디비를 생성하고 랭킹화 할 때 배치를 설정하고 클러스터링 할 때, 일일이 모델을 다운하던 구조랑 허깅페이스에서 끌어오던 것을 서버에 모델을 올려 진행해 총 26초 정도로 응답속도를 줄임.

협업 과정-Agile

회고

차후로 진행해볼것 - ONNX도입 및 멀티프로세싱있는것에 멀티스레딩 추가해서 둘다 진행해보기

MetLife_Hack4Job - 고객 맞춤형 AI 보험 도우미 서비스

GitHub - MetLife-Hackathon/MetLife-Hackathon: 2024년 3월 23 ~ 2024년 3월 24일까지 MetLife 사에서 주최한 Hackathon 대상 수상작

2024년 3월 23 ~ 2024년 3월 24일까지 MetLife 사에서 주최한 Hackathon 대상 수상작 - GitHub - MetLife-Hackathon/MetLife-Hackathon: 2024년 3월 23 ~ 2024년 3월 24일까지 MetLife 사에서 주최한 Hackathon 대상 수상작

GitHubMetLife-Hackathon

※보안 이슈로 인한 간단한 정리 및 회고

프로젝트 개요

메트라이프의 300종의 보험 상품 및 약관 데이터를 활용하여 사용자에게 맞춤형 응답을 제공하는 서비스입니다. 주요 기능은 다음과 같습니다:

• 개인의 필요에 맞는 보험 추천
• 특정 보험의 장점 안내
• 보험 가입 조건 및 가능 여부 확인
• 고객의 정보와 대화 기록을 바탕으로 보험 상담사에게 효율적으로 연결

AI 기반 플랫폼은 최적의 응답 템플릿을 제공하여 상담사와의 연결뿐만 아니라 상담의 질을 향상시킵니다.

주요 기술

1. Elastic Search Vector Database 구축: 보험 약관의 저장 및 검색을 위해 구축되었습니다.
2. Elastic Search Vector 유사도 검색: Elastic Search를 이용한 벡터 유사도 검색
3. ChatGPT OCR Text 추출: Chat GPT OCR 모델을 통한 PDF 파일 내 텍스트 추출
4. Chat GPT Embedding: Chat GPT Embedding 모델을 활용한 문서 및 쿼리 임베딩
5. Chat GPT4-1106-preview: Chat GPT API 호출로 사용자 맞춤형 검색 답변 생성

기술 스택

• FrontEnd:
  • React (UI library)
  • TypeScript (Programming language)
  • UI Components: MUI (Material-UI)
  • State Management: Recoil Design Framework: Tailwind CSS
• AI & BackEnd :
  • JDK 11: ElasticSearch,Spring Boot 환경 통일
  • ElasticSearch 8.7.0: 보험 약관 데이터 저장 및 검색
  • Spring boot 3.2.4 / 2.7.0, Spring Data JPA, Spring Security 3.1.5: API 제공 서버 개발
  • (GPT)text-embedding-3-small,text-embedding-3-large 모델: 문서 및 쿼리 임베딩
  • GPT-4-1106-preview: 사용자 질의에 대한 답변 생성
  • Python FastAPI: pdf 파일 실시간 임베딩 및 ElasticSearch 색인 서버 개발

해커톤을 진행하기 전에 팀은 사전에 구성된 것이 아니라 임의로 편성되었고, 모두 처음 만나는 사이였다. 그 과정에서 서로의 기술 스택을 공유하고 프로젝트를 기획하는 일이 쉽지만은 않았다. 나는 주로 파이썬을 사용해왔고, 팀원 중 한 명은 프론트엔드, 또 다른 한 명은 안드로이드 개발자였으며, 나머지 대부분은 자바 기반 백엔드 개발자였다.

기술 스택의 차이로 인해 나는 새로운 도전을 즐기고 빠르게 학습할 수 있다는 자신감으로, 다른 자바 개발자들이 프론트엔드로 전환하기보다는 내가 그 역할을 맡는 것이 협업에 유리하다고 판단했다. 그래서 프론트엔드로 넘어가, 대회전 MUI를 사용해보며 컴포넌트를 익히고 React 초기 설정을 해두며 대회를 준비했었다.

AI의 평가 비중이 높은 점을 고려해 우리 팀은 AI 파트도 나누어 맡기로 했다. AI에 관심이 있었지만, 팀 내 AI 경험이 풍부한 팀원이 그 부분을 리딩하고, 나머지 백엔드 팀원들이 그쪽으로 넘어가 팀당 3명씩 나눠 해커톤에 임하기로 결정했다. 또한, 해커톤에 앞서 Azure 기반의 CI/CD 인프라를 미리 구축하고, 파트별로 사용할 기술 스택을 논의하여 뼈대 코드를 마련했다.

대회 전에는 AI 관련 기사와 OpenAI 기술, 데이터셋 등을 미리 조사하면서 오픈된 보험사 데이터와 프롬프트 엔지니어링, 모델 리스트 등을 탐색했다. 이러한 사전 작업 덕분에 열정이 고취되었고, 좋은 결과를 얻을 수 있을 것 같은 확신이 생겼다.

대회 당일에는 주제를 정하는 데에 많은 시간이 소요되었다. 팀원들 모두 다양한 독창적인 아이디어를 제시하고, 비판적인 시각으로 검토하며 의견을 조율하느라 오후의 대부분을 사용했다. 비록 시간이 걸렸지만, 기획 단계가 프로젝트의 핵심 중 하나라는 점에서 이는 값진 시간이었다고 생각한다.

이후 우리는 설정한 목표를 향해 나아가, 대회 마감 직전까지 각자의 역할을 충실히 수행하며 목표했던 기능들을 성공적으로 구현해냈다. 발표 당시에는 핵심 기능의 구현에 실패했지만, 대회 동안 심사위원들이 인터뷰하듯 진행 상황을 지속적으로 관찰하고 궁금한 사항들을 질문했기 때문에, 우리의 협업 능력과 프로젝트 추진 방식이 긍정적으로 평가되었는지 결국 대상을 받을 수 있었다.

나는 프론트엔드 파트에서 React 기반의 채팅 대화 주제 가이드라인 토글 구현, 상담사 매칭 고객 리스트 확인 테이블 컴포넌트 개발, 에러 핸들링 및 예외 처리를 맡아 작업했다.

팀의 주요 이슈 중 하나는 Elastic Search에 저장된 보험사 데이터의 쿼리 유사도를 비교할 때 발생했다. 상위 스코어를 가진 문서를 가져오려고 했으나, 항상 연관성이 낮은 문서들이 포함되었다. 예를 들어, 쿼리에 "보험"이라는 단어가 있으면, 문서 내에 "보험"이라는 단어가 많이 포함된 문서가 관련도가 낮아도 결과로 나타나는 경우가 있었다. 이를 해결하기 위해 연관도가 낮은 키워드를 따로 매핑하여 검색에 사용하지 않는 로직을 도입한 결과, 성능을 크게 개선할 수 있었다.

또 다른 문제는 OpenAI API 호출 시, 응답 시간이 1분 이상 지연되면 연결이 자동으로 끊기는 점이었다. GPT-4 모델을 사용할 때, 많은 토큰 수와 아웃풋 대용량 텍스트 처리가 시간이 오래 걸리는 원인이었다. 이를 해결하기 위해 타임아웃 재시도 횟수를 늘리고, 벡터 DB 내 데이터가 없을 경우 대비해 스코어 값을 조정하며 파인튜닝을 시도해 성능을 향상시켰다.

이번 해커톤을 통해 낯선 사람들과 하나의 목표를 위해 협력하며 발생하는 다양한 문제와 어려움을 해결해 나가는 과정에서 큰 보람을 느꼈다. 또한, 스스로도 성장할 수 있는 소중한 기회였다. AI에 대한 흥미가 더욱 커졌으며, 이번 경험을 통해 AI 기술의 가능성과 지식을 쌓아 언젠가 직접 팀을 이끌어 멋진 서비스를 만들어 보고 싶다는 생각이 깊게 자리 잡았다.

감사합니다, 우리 10팀! 다들 고생하셨어요ㅎ :)

• Graph

A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.

Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like linkedIn, Facebook. Each person is a node that consists of the individuals metadata and the edges are friendships.

• A graph is a mathematical representation of a network

  • Set of nodes (vertices) V
  • Set of pairs of nodes (edges) E (a relation)
  • Graph G = (V,E)
  • Notation: n = |V |, m = |E| (almost always used)

• Definitions: Edge, Path

  • Edge e = {u, v} — but usually written e = (u, v) u and v are neighbors, adjacent, endpoints of e, e is incident to u and v.

  • A path is a sequence P = v1, v2, . . . , vk−1, vk such that each consecutive pair vi, vi+1 is joined by an edge in G.
    Called: path “from v1 to vk”. Or: a v1–vk path.
    Special case: empty path from any v to itself (just node, no edges).

• Simple path: path where all vertices are distinct

  • Exercise. Prove: If there is a path from u to v then there is a simple path from u to v.
  • Different terms elsewhere: walk: arbitrary (called path here), trail: no repeated edges, path (here: simple path)

• Distance from u to v: minimum number of edges in a u–v path

• (Simple) Cycle: path v1, . . . , vk−1, vk where

  • v1 = vk
  • First k − 1 nodes distinct
  • All edges distinct

• Connected component: maximal subset of nodes such that a path exists between each pair in the set.

  • maximal = if a new node is added to the set, there will no longer be a path between each pair
    
    Node set: {1, 2, 4}: there is a path between any two nodes. But it is not maximal: can add 3, property still holds. {1, 2, 3, 4} is maximal: can’t add any other node

• Trees

Tree = a connected graph with no cycles

• Tree properties
  Let G be an undirected graph with n nodes. Then any two of the following statements imply the third:
  • G is connected
  • G does not contain a cycle
  • G has n − 1 edges
• Rooted tree: tree with parent-child relationship
  • Pick root r and “orient” all edges away from root
  • Parent of v = predecessor on path from r to v

• Directed graph G = (V,E)
  • Directed edge e = (u, v) is now an ordered pair
  • e leaves u (source) and enters v (sink)
    
  • Directed path, cycle: same as before, but with directed edges
  • Strongly connected: directed graph with directed path
    between every pair of vertices
  • Note: graphs undirected if not otherwise specified

• Breadth-First Search (BFS)

• Explore outward from starting node s.
• Define layer Li = all nodes at distance exactly i from s.
• Layers
  • L0 = {s}
  • L1 = nodes with edge to L0
  • L2 = nodes with an edge to L1 that don’t belong to L0 or L1
  • . . .
  • Li+1 = nodes with an edge to Li that don’t belong to any earlier layer.
• Observation: There is a path from s to t if and only if t appears in some layer.

Running time: O(m + n). More precisely: Θ(m + n) (why?)
Assumption: can efficiently iterate over neighbors of v. OK with adjacency list.

How to explore entire graph even if it is disconnected?

Running time? Does it change? No, still O(m + n)
Naive: O(m + n) per component ⇒ O(c(m + n)) if c components.
Better: Search on component C only works on nodes/edges in C
- Time for component C: O(#edges in C + #nodes in C)
- O(n) to detect all components (why? how many tests for “unexplored node”?)
- Total time: O(m + n)

• BFS Tree

Any graph search builds a spanning tree (per connected component)
Tree edges = edges that reach a node for the first time.

• Claim: let T be the tree discovered by BFS on graph G = (V,E), and let (x, y) be any edge of G. Then the layer of x and y in T differ by at most 1.

• Proof

  • Let (x, y) be an edge
  • Assume x is discovered first and placed in Li
  • Then y ∈ Lj for j ≥ i
  • When neighbors of x are explored, y is either already in Li, or is discovered and added to Li+1

• Can we use BFS to detect cycles ?
  What if we find a neighbor that’s already discovered?
  Cycle! but only if it is not the parent (same edge backwards)

• Depth-First Search (DFS)

Depth-first search (DFS): keep exploring from the most recently added node until you have to backtrack.

• DFS: Recursive Implementation

How to analyze if algorithm is recursive?
Same: count executions of each line, including recursive call

Running time: O(m + n) same complexity as BFS
Same assumptions: can traverse neighbor list in time proportional to
node degree

• DFS Tree

Claim: Non-tree edges lead to (indirect) ancestors

• Claim: Let T be the tree discovered by DFS, and let (x, y) be an edge of G that is not in T. Then x or y is an ancestor of the other.
• Proof:
  All nodes marked explored between call to and return from DFS(v)
  are descendents of v. (due to workings of recursion/call stack)
  • Let x be the first of the two nodes explored
  • Is y explored at beginning of DFS(x)? No.
  • At some point during DFS(x), we examine the edge (x, y). Is y explored then? Yes, otherwise we would put (x, y) in T
  • ⇒ y was explored during DFS(x) ⇒ is a descendant of x

We first see the edge as (y, x) when exploring y: ancestor x is already marked explored, so (y, x) is a back edge.
x can’t be parent of y, since then (x, y) is a tree edge.

• Traversal Implementations

Generic approach:
maintain set of explored nodes and discovered nodes

• Explored = have seen this node and explored its outgoing edges
• Discovered = the “frontier”.
  Have seen the node, but not explored its outgoing edges.

Let A = data structure of discovered nodes

BFS: A is a queue (FIFO) / DFS: A is a stack (LIFO)
Can a node be discovered (placed in A) multiple times? Yes.
For DFS, node is explored from parent that added it last (LIFO).
For BFS, can avoid by not adding discovered nodes.

How to explore entire graph even if it is disconnected?

GitHub - IlMinCho/Data-Structure

Contribute to IlMinCho/Data-Structure development by creating an account on GitHub.

GitHubIlMinCho

Heuristic Function
• A heuristic function h(n) yields the estimated cost of the cheapest path from the state at node n to a goal state.
• What do we mean by “heuristic”?

• Oxford Dictionary: Proceeding to a solution by trial and error or by rules that are only loosely defined.
• Wikipedia: A technique designed to solve a problem that ignores whether the solution can be proven to be correct, but which usually produces a good solution or solves a simpler problem that contains or intersects with the solution of the more complex problem.
• In this post - ex) Greedy Best-First Search and A*

Search Terminology

• Tree Search

• Graph Search

• Tree Search vs. Graph Search

  1. Without some sort of bookkeeping, naive tree search methods may repeat themselves, possibly ad infinitum
  2. Graph search methods maintain a data structure to track previously explored states, avoiding repetition
  3. Graph search is going to take up more space given the extra data structure
  4. For our purposes, we’ll always assume that we’re using graph search unless explicitly said otherwise

• Breadth-First Search (BFS)

1. Complete? Yes (if branching factor b is finite)
2. Optimal? Yes, if step costs are identical, but not in general
3. Time? 1+b+b2+b3+…+bd = O(bd)
4. Space? O(bd) (b = branching factor, d = depth of solution)

• Depth-First Search (DFS)

DFS ( Graph )

DFS ( Tree )

• Uniform-Cost Search

• How can we modify BFS to retain optimality in problems with different transition costs?
• Intuition: expand nodes in order of least path cost so far
• Instead of FIFO or LIFO queue, store frontier as a priority queue
• Recall: priority queues are an abstract data type that holds a collection of elements associated with a (usually numeric) priority, such that higher priority items are dequeued (popped) before lower ones.

1. Complete? Yes
2. Optimal? Yes
3. Time? O(b^(1+[C*/ϵ]))
4. Space? O(b^(1+[C*/ϵ]))
   (b = branching factor, C* = cost of optimal solution, ϵ = minimum step cost)

• Greedy Best-First Search

• A* Search

• Intuition: avoid expanding paths that are already expensive, but still prefer those that seem closest to the goal
• Evaluation function:
  • f(n) = g(n) + h(n)
  • g(n) = cost so far to reach state n (like UCS)
  • h(n) = est. cost of cheapest path from n to goal (like Greedy)
  • f(n) = est. cost of cheapest path through n to goal

Local Search

• Local search algorithms that keep a single current state, and then try to improve it.
• State space is the set of complete configurations
• In many optimization problems, the path to the goal is irrelevant; the goal state itself is the solution
• We may not know what the goal is! In that case, the search becomes an optimization problem — we return the best state we can find.

• Hill Climbing Search

= 8-Puzzle Hill Climbing

Challenges for Hill Climbing

• Local Maxima/Minima – every move has a worse result than the current state. Once a local maximum is reached, there is no way to backtrack or move out of that maximum.
• “Shoulders/Plateaux” – there are no better moves, but some are just as good. Do we keep exploring? Hill climbing can have difficult time finding its way off of a flat portion of the objective function landscape.

So why use local search?
• Low memory requirements – usually constant
• Effective – Can often find good solutions in extremely large state spaces
• Can be useful for optimization problems with continuous, infinite branching factors
• Randomized variants of hill climbing can mitigate many of the drawbacks in practice

GitHub - IlMinCho/AI-8Puzzle

Contribute to IlMinCho/AI-8Puzzle development by creating an account on GitHub.

GitHubIlMinCho

Reference: Matthew Hale Rattigan

Principles Of Reliable Data Transfer

Complexity of reliable data transfer protocol will depend (strongly) on characteristics of unreliable channel (lose, corrupt, reorder data?) = Sender, receiver do not know the “state” of each other, e.g.

Reliable Data Transfer Protocol (rdt): Interfaces

• Incrementally develop sender, receiver sides of reliable data transfer protocol (rdt)
• Consider only unidirectional data transfer -But control info will flow in both directions!
• Use finite state machines (FSM) to specify sender, receiver

rdt1.0: Reliable Transfer Over A Reliable Channel

• Underlying channel perfectly reliable = No bit errors / No loss of packets
• Separate FSMs for sender, receiver: Sender sends data into underlying channel , Receiver reads data from underlying channel

rdt2.0: Channel With Bit Errors

• Underlying channel may flip bits in packet = Checksum to detect bit errors

• The question: how to recover from errors:

  1. Acknowledgements (ACKs): receiver explicitly tells sender that pkt received OK
  2. Negative acknowledgements (NAKs): receiver explicitly tells sender that pkt had errors
  3. Sender retransmits pkt on receipt of NAK

• New mechanisms in rdt2.0 (beyond rdt1.0): Error detection / Receiver feedback: control messages (ACK,NAK) receiver ➔ sender
  

• What happens if ACK/NAK corrupted?

  1. Sender doesn’t know what happened at receiver!
  2. Can’t just retransmit: possible duplicate

• Handling duplicates:

  1. Sender retransmits current packet if ACK/NAK corrupted
  2. Sender adds sequence number to each packet
  3. Receiver discards (doesn’t deliver up) duplicate packet

rdt2.1: Sender, Handling Garbled ACK/NAKs

rdt2.1: Receiver, Handles Garbled ACK/NAKs

rdt2.2: Sender, Receiver Fragments

rdt3.0: Channels With Errors And Loss

• New assumption: underlying channel can also lose packets (data, ACKs)
  = Checksum, seq. #, ACKs, retransmissions will be of help … but not enough

• Approach: sender waits “reasonable” amount of time for ACK

  1. Retransmits if no ACK received in this time
  2. If pkt (or ACK) just delayed (not lost):
     =Retransmission will be duplicate, but seq. #’s already handles this
     =Receiver must specify seq # of pkt being ACKed
  3. Use countdown timer to interrupt after “reasonable” amount of time

• rdt3.0 Sender
  

• rdt3.0 In action
  

• rdt3.0 Receiver
  

• Performance Of rdt3.0

1. rdt3.0 is correct, but ….
   =performance stinks
2. Example: 1 Gbps link, 15 ms prop/net delay, 8K bit packet:
   =Time to transmit packet into channel:
   =U sender: utilization – fraction of time sender busy sending
   =If RTT=30 msec, 1KB pkt every 30 msec: 33kB/sec throughput over 1 Gbps link
3. Network protocol limits use of physical resources!

• Stop-And-Wait Operation
  

GitHub - IlMinCho/CN-RDT

Contribute to IlMinCho/CN-RDT development by creating an account on GitHub.

GitHubIlMinCho

This sender and receiver will communicate with each other through an intermediary server running on gaia.cs.umass.edu, as shown below in Figure, that will function as an unreliable channel connecting this sender and receiver. This sender and receiver will each send messages to the server, and the server will relay (after possibly corrupting, losing or delaying but not reordering) the message to the other side.

In this project, the task involves writing transport-level code for a simple reliable data transfer protocol, specifically an implementation of the rdt 3.0 protocol. This protocol is designed to operate over a channel that may corrupt, lose, or delay messages but will not reorder them. The implementation is close to what is required in real-world scenarios.

The project requires programming a sender and a receiver to reliably transfer the first 200 characters of a text file, using the rdt 3.0 protocol. Unlike the standard rdt 3.0 protocol, the sender in this project will not use rdt_send(data) to send data, nor will the receiver use udt_send(data) to deliver data. Instead, the sender will reliably deliver a file from sender to receiver. Both the sender and receiver will communicate over sockets on the Internet.

The specific task is to transfer the first 200 characters of the Declaration of Independence, available at a given URL, from the sender to the receiver. This process will be executed within the network environment described in the project, employing the rdt 3.0 protocol's sender and receiver finite state machines (FSMs).

Flowchart

Outcomes:

Reference:Prof. Parviz Kermani

Internet Protocol Stack

• Application: supporting network applications - FTP, SMTP, HTTP
• Transport: process-process data transfer - TCP, UDP
• Network: routing of datagrams from source to destination - IP, routing protocols
• Link: data transfer between neighboring network elements - Ethernet, 802.111 (WiFi), PPP
• Physical: bits “on the wire”

What Transport Service Does An App Need?

• Data integrity
  -Some apps (e.g., File transfer, web transactions) require 100% reliable data transfer
  -Other apps (e.g., Audio) can tolerate some loss
• Timing
  -Some apps (e.g., Internet telephony, interactive games) require low delay to be “effective”
• Throughput
  -Some apps (e.g., multimedia) require minimum amount of throughput to be “effective”
  -Other apps (“elastic apps”) make use of whatever throughput they get
• Security
  -Encryption, data confidentiality, …

Internet Transport Protocols Services

• TCP service:

Reliable transport: between sending and receiving process.
Flow control:sender won’t overwhelm receiver.
Congestion control: throttle sender when network overloaded.
Does not provide: timing, minimum throughput guarantee, security.
Connection-oriented: setup required between client and server processes.

• UDP service:

Unreliable data transfer: between sending and receiving process.
Does not provide: reliability, flow control, congestion control, timing, throughput guarantee, security, or connection setup.

Socket Programming

• Goal: learn how to build client/server applications that communicate using sockets
• Socket: door between application process and end-end-transport protocol
  

Two socket types for two transport services:

• UDP: unreliable datagram
• TCP: reliable, byte stream-oriented

Application Example:

1. Client reads a line of characters (data) from its keyboard and sends data to server
2. Server receives the data and converts characters to uppercase
3. Server sends modified data to client
4. Client receives modified data and displays line on its screen

Socket Programming With UDP

• UDP: no “connection”between client & server

No handshaking before sending data.
Sender explicitly attaches IP destination address and port # to each packet.
Receiver extracts sender IP address and port# from received packet.

• UDP: transmitted data may be lost or received out-of-order
• Application viewpoint: UDP provides unreliabletransfer of groups of bytes (“datagrams”) between client and server

Client/Server Socket Interaction: TCP

• Client must contact server

Server Process Must First Be Running.
Server Must Have Created Socket (Door) That Welcomes Client’s Contact.

• Client contacts server by:

Creating TCP socket, specifying IP address, port number of server process.
When client creates socket: client TCP establishes connection to server TCP.

• When contacted by client, server TCP creates new socketfor server process to communicate with that particular client

Allows server to talk with multiple clients.
Source port numbers used to distinguish clients (more in Chap 3).

• Application viewpoint: TCP provides reliable, in-order Byte-stream transfer (“pipe”) between client and server

GitHub - IlMinCho/CN-TCP-UDP

Contribute to IlMinCho/CN-TCP-UDP development by creating an account on GitHub.

GitHubIlMinCho

a. TCP Client/Server (2 Programs)
b. Reliable UDP Client/Server (2 programs)
c. Unreliable UDP Client/Server (2 Programs)

A good reference for Python socket programming : https://docs.python.org/3/howto/sockets.html

The Server - a reliable environment
The server performs the Operation Code (OC) requested on the two integer numbers it receives from the sender and returns the result. The format of the returned result is “status-code numeric-result” (without quote), as explained below. More specifically the steps (or algorithm) performed by the server are:

1. Open a TCP Socket:
   • Initialize and bind a TCP socket to listen for incoming connections.
2. Listen to the Socket:
   • Put the socket into listening mode to accept connection requests.
3. Accept Connection and Receive Request:
   • Accept a new connection.
   • Receive a request consisting of an Operation Code (OC) and two integer numbers.
4. Validate Request:
   • Check if OC is one of +, -, *, /.
   • Ensure both operands are integers.
   • Handle division by zero for /.
5. Error Handling:
   • For invalid OC, send status code 620 and result -1.
   • For invalid operands or division by zero, send status code 630 and result -1.
6. Process Valid Request:
   • If request is valid, perform the operation.
   • Send back status code 200 and the result.
7. Logging:
   • Output {received_line} -> {status_code} {result} to standard output.
8. Loop Back:
   • Return to Step 2 for handling new requests.
9. Shutdown:
   • Respond to ^C (Control-C) signal to gracefully stop the server.

The Client - a reliable environment
The client sends an Operation Code (OC), and the two numbers it has acquired from the user. OC can be: Addition (+), Subtraction (-), Multiplication (*), and Division (/)
To make the problem simple, your client sends two numbers that are integers.
The two numbers and the OC are read from a file which the user has prepared. The algorithm is specified as follows:

1. Start and Read Input File:
   • Start the client program, accepting a filename as a command-line argument.
   • Read the file line by line, where each line contains an OC and two integers, separated by spaces.
2. Display Input Request:
   • For each line read, display Input request: {input_line}.
3. Open a TCP Socket:
   • Establish a TCP connection to the server.
4. Send Request to Server:
   • Send the line read from the file to the server.
5. Receive Response:
   • Wait for and receive the response from the server (status code and result).
6. Process Response:
   • If status code is 200, display The result is: {result}.
   • For other status codes, display Error {status_code}: {description}.
7. Close Socket:
   • Close the TCP connection.
8. Repeat for 7 Lines:
   • Repeat steps 2-6 for a total of 7 lines from the file.
9. Terminate Program:
   • Stop the client program.

The UDP Server - an unreliable environment

1. Start and Read Command Line Parameters:
   • On startup, read two parameters from the command line: the probability p of dropping a received datagram and a string for seeding a random number generator.
2. Seed Random Number Generator:
   • Use random.seed(sys.argv[2]) to seed the random number generator with the provided string. This ensures reproducibility of the random behavior.
3. Open a UDP Socket:
   • Initialize and bind a UDP socket for the server.
4. Listen to the Socket:
   • Wait for incoming UDP datagrams.
5. Receive a Datagram:
   • Receive a request in the form of a datagram.
6. Simulate Datagram Drop:
   • With probability p, determined by if random.random() <= p, drop the request.
   • If dropped, print {received_line} -> dropped and return to Step 4.
7. Parse the Request:
   • Extract the operation code (OC) and two integer numbers from the received datagram.
8. Validate the Request:
   • Check if OC is one of +, -, *, /.
   • Ensure both operands are integers.
   • Handle division by zero for /.
9. Handle Invalid Requests:
   • For an invalid OC, return status code 620 and result -1.
   • For invalid operands or division by zero, return status code 630 and result -1.
10. Process Valid Requests:
    • If the request is valid, perform the operation.
    • Return status code 200 and the operation result.
11. Logging:
    • Print {received_line} -> {status_code} {result} to standard output.
12. Loop Back:
    • Return to Step 4 for handling new datagrams.
13. Shutdown Handling:
    • The server should respond to ^C (Control-C) for graceful termination.

The UDP Client - an unreliable environment

1. Start and Read Input File:
   • Start the client and read the name of a file passed as a command-line parameter.
   • The file contains lines with three values: an Operation Code (OC) and two integer numbers, separated by spaces.
2. Initialize Timer Value:
   • Set d = 0.1 seconds (initial timeout duration).
3. Open a UDP Socket:
   • Create and configure a UDP socket.
4. Send Request to Server:
   • Read a line from the file and send it to the server via the UDP socket.
5. Start Timer and Wait for Reply:
   • Start a timer for d seconds.
   • Wait for a reply from the server within this time frame.
6. Handle Timer Expiry:
   • If the timer expires before a reply is received:
     • Double the timer value (d = 2 * d).
     • If d > 2 seconds:
       1. Raise an exception.
       2. Notify the user with “Request timed out: the server is DEAD”.
       3. Set status code to 300 (indicating server unavailability).
       4. Proceed to Step 8 (turn off the timer).
     • Otherwise, print “Request timed out: resending” and go back to Step 4.
7. Receive Reply from Server:
   • If a reply is received before timeout, receive the status code and result.
8. Turn Off Timer:
   • Stop the timer.
9. Process Server Response:
   • If the status code is 200, display “Result is {result}”.
   • For other status codes, display “Error {status_code}: {description}”.
10. Close the Socket:
    • Close the UDP socket.
11. Repeat for Additional Requests:
    • Repeat steps 2-10 six more times, processing a total of seven lines from the input file.
12. Stop the Program:
    • Terminate the client program.

Reference:Prof. Parviz Kermani

2023 Fall Team Project_ EliteKoders

GitHub - IlMinCho/Patient-Tracker-System

Contribute to IlMinCho/Patient-Tracker-System development by creating an account on GitHub.

GitHubIlMinCho

Team Member: Ilmin Cho, Kunal Kumar, Matthew Lyons, Esha Sangramsinh Ghorpade

Presentation Video:

Overview: The Patient Tracker project is designed to revolutionize patient data management in healthcare facilities. Its primary goal is to create a digital platform for efficient handling of medical records, treatment histories, prescriptions, and appointments. This centralization aims to improve patient care quality and operational efficiency in healthcare settings. By digitizing records, the project seeks to streamline administrative processes, ensure robust data security, and make comprehensive patient information easily accessible to healthcare professionals.

Healthcare providers and administrative staff benefit from simplified management of patient records and streamlined administrative tasks such as scheduling and billing. Patients, on the other hand, enjoy enhanced healthcare services, better communication, and convenient access to their medical records. Transitioning to this digital system addresses the challenges of manual paperwork, including potential delays and errors, by providing real-time access to updated data. This facilitates faster decision-making, coordinated care among providers, and compliance with privacy regulations like HIPAA. Ultimately, the Patient Tracker project aims to foster a more efficient, secure, and patient-centric healthcare environment.

Features:

1.     User Authentication: Secure login/logout mechanism ensuring enhanced security.

2.     Profile Management: Tailored profiles for both doctors and patients.

3.     Prescription Management: Functionality for doctors to modify and update prescriptions.

4.     Customizable Dashboard: Separate landing page for patients and doctors showing its profile, appointments, etc.

5.     Data Visualization: Insightful graphical representations of patient data. Example - Patients can add health reports (in pdf, jpg) which can be shared with doctors.

Functional Requirements (Use cases)

1.     As a doctor, I want to view the list of patients scheduled for the day so that I can prepare for the consultations.

2.     As a doctor, I want to view a patient's medical records before the consultation so that I can provide the best care possible.

3.     As a doctor, I want to upload prescriptions electronically on the server so that the patients can check it.

4.      As a doctor, I want to create and modify treatment plans for my patients so that they have a structured approach to their recovery.

5.     As a doctor, I want to set my available hours and days so that patients can book appointments when I'm available. 

6.     As a doctor, I accept appointments requested by patients and meet with them to conduct consultations.

7.     As a patient, I want to book an appointment with my doctor so that I can discuss my health concerns

8.     As a patient, I want to cancel my appointment if I am unable to attend so that the slot can be used by someone else.

9.     As a patient, I want to view and download my prescriptions so that I can acquire the necessary medications.

10.  As a patient, I want to update my health status and information so that my doctor can check.

11. As a user, I want to sign up to the website as a doctor or patient.

12. As a user, I want to log in to the website as a doctor or as a patient.

Detailed user story document: https://docs.google.com/document/d/1vrmnM1z2uqO-OHWNotnq2yvDB7C41wfAYM4kzMxOkrw/edit?usp=sharing

Non-Functional Requirements

1. Security: The system should ensure robust data encryption, guaranteeing the secure transmission and storage of patient data. Regular vulnerability assessments and penetration tests should be conducted to safeguard against potential threats. We have used user authentication to ensure security.
2. Understandability: The interface should be intuitive and user-friendly, allowing users, even those with minimal technical proficiency, to easily navigate and understand the system's features. We have committed the changes with proper comments, we have documented the readme files with proper instructions to ensure understandability.
3. Performance: The system should exhibit quick response times, ensuring users can retrieve and input data efficiently. Optimal server performance and minimal downtime are imperative to guarantee smooth operations. We will work on caching and sharding whichever applicable to boost performance.
4. Scalability: As user numbers grow, the system should be able to handle an increasing amount of data and user requests without compromising performance or security. We will work on more generic design to make the system more scalable.
5. Maintainability: Updates, bug fixes, and system improvements should be feasible without significant downtime, ensuring continuity of service for users. We will work on testing and buggy free code to support maintainability.

Application

Architecture Diagram

Technology Stack with Justification

A.     Python: It is renowned for its simplicity and readability, which reduces the cost of program maintenance. It supports modules and packages, which encourages program modularity and code reuse.

Advantages: Python has a vast ecosystem of libraries and frameworks that can be leveraged for various functionalities. It's also versatile and can be used for web development, data analysis, machine learning, automation, and more. This makes it a suitable choice for diverse project requirements.

B.     Flask: We chose Flask for backend development due to its lightweight nature and flexibility in developing web applications. Flask provides the essentials to get a web application up and running without imposing a specific structure, which means more freedom in design and architecture. We are using RESTful APIs like GET and POST in Flask for client-server communication.

Advantages: Flask is unobtrusive and gives developers more control over how they structure their application and which components they want to use. It's also easy to set up and can be extended with a wide variety of plugins.

C.    Sqlite3: It is an embedded database, meaning it's serverless, zero-configuration, and transactional. For projects that don't require a full-fledged database system, Sqlite3 is a lightweight option.

Advantages: Sqlite3 is self-contained, meaning there are no external dependencies. It's best suited for smaller applications, development, and testing, and can handle low to moderate traffic web applications. The footprint is minimal, and the setup is straightforward.

D.    Anaconda: It is a distribution of Python and R for scientific computing and data science. We chose it to manage libraries and dependencies within our project and to maintain a consistent environment.

Advantages: Anaconda simplifies package management and deployment. Its environment manager, Conda, allows for easy creation, sharing, and replication of environments, ensuring consistency across development, testing, and production stages.

E.     HTML: It is the standard markup language for creating web pages. It's essential for any web application to structure and present content.

Advantages: Being the backbone of web content, HTML is universally understood by web browsers. It allows for the creation of structured documents and is integral to web application development.

F.     CSS: It is used to describe how HTML elements should be displayed on screen. It's vital for styling and designing the look and feel of the web application.

Advantages: CSS separates content from presentation, allowing for flexibility in design without altering the underlying HTML. With CSS, developers can create responsive designs, ensuring the web application looks good on all devices.

G.    Jinja: It is a Python template engine commonly used in web development. It enables dynamic content generation by replacing placeholders with actual values during rendering.

Advantages: Template inheritance for code reusability, expression evaluation, filters and macros for enhanced functionality, and seamless integration with Python in frameworks like Flask. Jinja facilitates the creation of flexible and maintainable web applications.

H.    Pytest: It is a widely-used testing framework for Python.

Advantages: Its fixture system allows efficient setup and teardown of resources, and parameterized testing facilitates running the same test with different inputs. Pytest's powerful assertions, built-in test discovery, and seamless integration with other testing tools make it a versatile choice

Data Model

Implementation

We have followed the client-server design pattern methodology for this project. The client-server design pattern is a common architecture for networked applications. It involves clients, which request services, and servers, which provide those services. Clients initiate requests, and servers respond to those requests, allowing for efficient resource sharing, scalability, centralized control, and enhanced security. This model is widely used in various applications, such as web and email servers, to facilitate communication and data exchange over networks.

Version Control and Collaboration

We employed Git for version control in our project, adopting a feature-branch workflow to enable independent development of each feature. This approach facilitated organized coding and pull requests for code reviews before merging into the main branch, ensuring code quality and seamless integration. Our team maintained clear communication, minimizing conflicts during merges. When conflicts did arise, we promptly collaborated to resolve them, leveraging Git's version control capabilities. This disciplined process contributed to an efficient and streamlined development workflow.

Coding Standards and Practices

Our team prioritized code quality by following the PEP 8 style guide for Python and implementing best practices. We emphasized consistent naming conventions, indentation, and modular code organization. Documentation played a crucial role, with descriptive comments at various levels to enhance code understanding. Effective version control practices, including detailed commit messages and regular code reviews, contributed to a maintainable and collaborative codebase. Overall, our approach aimed at fostering readability, maintainability, and a positive development environment. We created different folders for different functionalities to support modularity. All the frontend html files are stored under Template folder, the main flask  application, database and testing module are outside of all folders, all the tables of database like Patients, Doctors, Appointments, etc. are under models, uploaded reports are saved under files folders. Furthermore, we have added docstrings and comments for Understandability of the code. Also, we have also restructured our README file by adding explanations of all the use cases, installation guidelines, collaborators details & presentation video.

Data Security

1. Description of the potential threats and vulnerabilities - Potential threats may include unauthorized access to patient data, either through external cyberattacks or internal security breaches. Vulnerabilities could arise from weaknesses in the application's authentication system, insufficient data encryption, or inadequate security measures in the database storage and transmission of data.
2. Measures taken to prevent unauthorized data access - To mitigate the risks of unauthorized data access, we used a user authorization mechanism for a secure login which will enable only one user to login and it can’t access other patients details.  Moreover, we have used encrypted passwords to map user passwords to a hashed password. Hence, anyone with an encrypted password can’t access the system. Therefore, if there is a security threat to the database and patient sensitive information is leaked, then one cannot login into the system until we have encoded the original password which was never stored.

HIPAA Compliance (in case of Patient Tracker)

1. Explanation of the Health Insurance Portability and Accountability Act (HIPAA) and its relevance to the project - HIPAA is a federal law in the United States that sets the standards for protecting sensitive patient data. It aims to ensure the confidentiality, integrity, and availability of electronic protected health information (ePHI). Compliance with HIPAA is crucial to safeguard patient privacy and prevent unauthorized disclosure of sensitive medical information. With respect to this project, the patient's medical history or current medications should not be leaked to any other patients or to another doctor who is not relevant for given symptoms.
2. Steps and protocols followed to ensure the system's compliance with HIPAA - To ensure compliance with HIPAA, we have implemented data encryption practices, establish stringent access controls, and enforce thorough audit trails to monitor data access and usage. Additionally, we are following policies (as explained before) for securely managing and disposing of patient records, as outlined in the HIPAA guidelines.

Testing

This comprehensive unit test suite ensures that critical aspects of the Patient Tracker System are thoroughly tested, contributing to the overall reliability and functionality of the system. Our test cases cover the integration testing as different units or components interact and work together. From the image shared above we can see how unit tests, integration tests and systems show their respective coverage and passed status. The achieved test coverage of 94% reflects a robust testing approach.

●       Performance: To evaluate our system’s performance, we tested the response speed of some of our crucial API endpoints using Postman. We tested our login, book appointment, and doctor search endpoints, which all had incredibly fast response times of 11ms, 11ms, and 5ms respectively.

●       Scalability: To evaluate our system’s scalability, we filled our database with dummy accounts (approximately 1,000 doctors and 10,000 patients), and re-performed our performance tests while running Locust to simulate approximately 100 concurrent users. Our login, doctor search, and book appointment endpoints executed in 123ms, 17ms, and 6ms, which were acceptable results.

●       Maintainability: We have fulfilled maintainability by creating a well-organized and crafted code base. Despite programming in Python, we created an OOP design by designating classes for our data tables (patients, doctors, appointments, etc.) which allows for modular design. API endpoints are sectioned off relative to their function, with comments on the more nuanced functions. This allows for the system to be debugged and diagnosed easily as well as add new features quickly.

Challenges and Limitations

Integration Challenges: While we successfully addressed many challenges, integrating the new features into the existing system presented some difficulties. The need for substantial modifications to the codebase, as well as potential conflicts with the current functionalities, posed integration challenges. Ensuring a seamless transition without disrupting existing operations required careful planning and execution.

Time Constraints: Time constraints were a significant limitation throughout the project. Although we successfully delivered a functional system, certain features or optimizations might not have been fully realized due to the restricted time frame. This limitation might have implications for the scalability and robustness of the system under more extensive usage.

User Surveys for Understandability: Although attempts were made to evaluate the understandability of the software, the absence of user surveys is a limitation. Conducting comprehensive user surveys would have provided more in-depth insights into user experiences and potential barriers to understanding the system.

Performance Metrics under Real-world Load: While performance tests under simulated load conditions were conducted, the real-world performance of the system under varying loads remains an open question. Actual usage patterns might differ from simulated scenarios, and further analysis under real-world conditions could reveal additional performance considerations

Future Development Plans

Enhanced Performance Monitoring: To address potential performance bottlenecks and ensure optimal response times under varying loads, we plan to implement enhanced performance monitoring. Real-time monitoring tools can help identify and address issues promptly, ensuring a consistently high level of service.

User Feedback Mechanism: Incorporating a systematic user feedback mechanism, such as user surveys and feedback forms, will be a priority. This will provide valuable insights into user experiences, allowing for continuous improvements in usability and understandability.

AI-driven Personalization: Considering the project's nature as a patient tracker system, integrating AI-driven features for personalized patient care could be a future development. Machine learning algorithms could assist doctors in predicting patient needs and tailoring treatment plans accordingly. ML algorithms can predict patient health trends, and optimize appointment scheduling dynamically. Data visualization tools could offer insights into health trends, and continuous learning from new data will ensure the system evolves with changing healthcare dynamics.

Integration with Health Information Systems: To further enhance the project's scope and utility, integration with larger health information systems or electronic health record (EHR) systems could be explored. This could facilitate seamless data sharing and collaboration across different healthcare platforms.

Ethical and Societal Implications

The Patient Tracker system, while aiming to enhance healthcare efficiency and patient care, presents ethical considerations related to data privacy and security. Safeguarding patient information is paramount, necessitating stringent adherence to ethical standards and regulatory requirements like HIPAA. During development, the team addressed concerns regarding the potential misuse or unauthorized access to sensitive medical records by encrypting passwords of the users, sharing only relevant information to patients or doctors like patients doesn’t share all the reports, patients or doctors can select what they want to view in their profile, each user’s data are in separate table in database providing isolation etc. Ensuring transparency in data handling practices and obtaining informed consent from patients are essential ethical considerations. Additionally, the system is designed to minimize the risk of errors or inaccuracies in patient records, as such discrepancies could have serious consequences for patient care. Striking a balance between technological advancements and ethical responsibility is crucial to building trust among healthcare professionals and patients. Overall, the ethical implications revolve around protecting patient confidentiality, maintaining data integrity, and fostering a system that prioritizes the well-being and trust of all stakeholders in the healthcare ecosystem.

What is White Paper: A white paper is a comprehensive report or guide that informs readers concisely about a complex issue and presents the issuing body's philosophy on the matter. It is meant to help readers understand an issue, solve a problem, or make a decision. White papers are commonly used in policy, business, and technical fields.

Most original research results in computer sciences are published in conference proceedings. 

Most research papers follow a standard structure, abbreviated IMRaD: Introduction, Methods, Results, and Discussion. This structure is helpful for understanding and navigating the article. 

How will Metaverse, a new virtual digital platform, develop as an educational medium?

Research Methods
My research methodology prioritized peer-reviewed articles to ensure reliability, utilizing a diverse array of resources including the UMass Library website, academic journals, industry reports, and comprehensive online databases like Google Scholar. Initially, my focus was on the technical aspects of the metaverse. However, during the course of my research, I identified a significant intersection between the metaverse and educational studies. This discovery led me to delve into topics pertaining to the integration of the metaverse in educational settings, examining its evolving role in educational technology and its potential to influence future learning paradigms. Key subtopics included the technological advancements in Virtual Reality (VR) and Augmented Reality (AR), as well as the challenges and opportunities of implementing the metaverse in diverse educational environments. My search strategy employed terms such as 'metaverse in education,' 'virtual reality in learning,' and 'digital platforms in education,' enabling a comprehensive exploration driven by emerging trends and insights. This approach facilitated a nuanced understanding of the transformative role of the metaverse in reshaping educational landscapes.

What is Metaverse?
The Metaverse, bridging the virtual and real realms, represents a 'third space' that transcends traditional environments, a concept that has evolved significantly in recent years [3, 4]. Markedly, the Metaverse, as a transformative realm, integrates advanced technologies like virtual reality, augmented reality, blockchain, and the Internet of Things, indicating a paradigm shift from theoretical ideas to tangible applications across diverse sectors, notably education [3, 5, 7]. Additionally, the Metaverse is characterized by its virtual nature and immersive technology, fostering a dynamic digital society with its own economy and social interactions [5]. Nonetheless, the complexity and evolving nature of the Metaverse is highlighted by the absence of a universally accepted definition, reflecting a wide spectrum of interpretations about its potential and scope [7]. Furthermore, the development of the Metaverse is heavily influenced by the rapid advancement of supporting technologies, crucial for crafting immersive and interconnected virtual experiences [5, 7]. Consequently, as the Metaverse evolves, it presents both challenges and opportunities, particularly in reshaping educational paradigms where it offers novel avenues for interactive and immersive learning [1, 3, 7]. This ongoing discourse around the Metaverse underscores its potential as a groundbreaking platform, yet simultaneously calls for deeper understanding and broader consensus within the academic and technological communities [5, 7]. Possibilities and Values of the Educational Part of the Metaverse The Metaverse in education represents a significant paradigm shift, offering immersive and interactive experiences that transcend traditional classrooms [3]. Furthermore, the integration of virtual reality (VR) and augmented reality (AR) in the Metaverse signifies a transition from theoretical concepts to practical applications in education [7]. Additionally, the Metaverse fosters global interconnectedness, enhancing collaborative learning opportunities in the educational sector [1]. Moreover, the Metaverse promises personalized and adaptive learning experiences, reflecting its potential to revolutionize educational paradigms [2]. Also, the Metaverse's evolution is marked by blending virtuality and immersion, offering novel avenues for interactive learning [5]. Consequently, as the Metaverse evolves, it presents both challenges and opportunities in reshaping educational paradigms [1, 3, 7]. Therefore, this ongoing discourse around the Metaverse underscores its potential as a transformative platform, necessitating deeper understanding and broader consensus within academic and technological communities [5, 7].

Educational Use Cases for Metaverse
The Metaverse's role in education is marked by its diverse and innovative applications, significantly transforming traditional learning methods [3, 5]. For instance, the Metaverse offers immersive environments in language learning that enhance linguistic skills through realistic, interactive practice, providing a new dimension to language acquisition [1]. Furthermore, in STEM education, the Metaverse facilitates experiential learning via virtual laboratories and simulations, allowing students to explore scientific concepts in a controlled, risk-free environment, enhancing their comprehension and engagement [6, 7]. Additionally, the Metaverse enables unique learning experiences such as virtual field trips and cultural immersions, broadening the scope of education beyond the confines of physical classrooms and offering a broader, more comprehensive understanding of various subjects [3, 4, 5]. These varied applications underscore the Metaverse's potential to enrich educational experiences, demonstrating its transformative impact across different disciplines [5]. The versatility of the Metaverse in enhancing traditional learning methods, and providing more engaging and diverse educational experiences, is a testament to its potential to revolutionize the educational sector [5].

Limitations of the Current Educational Use of Metaverse
While the Metaverse offers vast potential for education, integrating it into educational systems faces technical and pedagogical challenges [1, 2, 3, 4, 5, 6, 7]. Particularly, technical constraints such as the need for advanced hardware and reliable internet significantly limit accessibility, especially in less technologically advanced areas [2, 5]. Moreover, the digital divide, stemming from these technical constraints, poses a major barrier to the widespread adoption of the Metaverse in education [2, 3]. Additionally, the absence of tailored pedagogical models for Metaverse-based learning complicates its integration into current educational frameworks [6, 7]. Consequently, the lack of such models hinders the effective incorporation and application of the Metaverse in education [6, 7]. Furthermore, ethical concerns, including issues of data privacy and the potential for misuse of immersive technology, necessitate robust governance and safety measures [1, 4]. These ethical issues require careful management to ensure a safe and responsible learning environment within Metaverse-utilizing educational settings [1, 4]. Therefore, addressing these challenges is crucial for leveraging the full capabilities of the Metaverse in education and necessitates collaborative efforts from educators, technologists, and policymakers [1, 2, 3, 4, 5, 6, 7]. Ultimately, overcoming these obstacles is key to harnessing the transformative power of the Metaverse in the educational sector effectively [1, 2, 3, 4, 5, 6, 7].

Conclusion
The exploration of the Metaverse as an educational medium reveals its vast potential to redefine the landscape of learning. Bridging virtual and real realms, the Metaverse stands as a pioneering 'third space', offering immersive, interactive experiences that surpass the limitations of traditional classrooms. Its integration of VR and AR signifies a leap from theoretical constructs to practical educational applications, fostering global interconnectedness and personalized learning experiences. However, this digital platform's evolution also brings challenges, particularly in technical and pedagogical integration, necessitating robust governance and collaborative efforts across educational and technological sectors. In conclusion, while the Metaverse presents technical and ethical complexities, its transformative impact on education is undeniable, offering innovative avenues for interactive and immersive learning that could revolutionize educational paradigms. The need for deeper understanding and consensus among academics and technologists is crucial as we navigate this uncharted digital terrain in education.

Works Cited
[1] Andrea Antonio Cantone, Rita Francese, Raffaele Sais, Otino Pio Santosuosso, Aurelio Sepe, Simone Spera, Genoveffa Tortora, and Giuliana Vitiello. 2023. Contextualized Experiential Language Learning in the Metaverse. In Proceedings of the 15th Biannual Conference of the Italian SIGCHI Chapter (CHItaly '23). Association for Computing Machinery, New York, NY, USA, Article 20, 1–7. https://doi-org.silk.library.umass.edu/10.1145/3605390.3605395

[2] Clegg, N. 2023. How the Metaverse Can Transform Education. Medium. Available: https://nickclegg.medium.com/how-the-metaverse-can-transform-education-20ed9d355b5f

[3] Hirsh-Pasek, K., Zosh, J. M., Golinkoff, R. M., Gray, J. H., Robb, M. B., and Kaufman, J. 2023. A whole new world: Education meets the metaverse. Brookings. Available: https://www.brookings.edu/articles/a-whole-new-world-education-meets-the-metaverse/

[4] Jiangnan Xu, Konstantinos Papangelis, John Dunham, Jorge Goncalves, Nicolas James LaLone, Alan Chamberlain, Ioanna Lykourentzou, Federica L Vinella, and David I Schwartz. 2022. Metaverse: The Vision for the Future. In Extended Abstracts of the 2022 CHI Conference on Human Factors in Computing Systems (CHI EA '22). Association for Computing Machinery, New York, NY, USA, Article 167, 1–3. https://doi-org.silk.library.umass.edu/10.1145/3491101.3516399

[5] Linlu Weng, Zhengkai Wei, Fanbo Li, and Fat Iam Lam. 2023. Research on the innovative integration application of metaverse and education. In Proceedings of the 9th International Conference on Education and Training Technologies (ICETT '23). Association for Computing Machinery, New York, NY, USA, Article 18, 1–6. https://doi-org.silk.library.umass.edu/10.1145/3599640.3599660

[6] Kun Yue. 2022. Breaking down the Barrier between Teachers and Students by Using Metaverse Technology in Education: Based on A Survey and Analysis of Shenzhen City, China. In Proceedings of the 2022 13th International Conference on E-Education, E-Business, E-Management, and E-Learning (IC4E '22). Association for Computing Machinery, New York, NY, USA, 40–44. https://doi-org.silk.library.umass.edu/10.1145/3514262.3514345

[7] Lijun Zhao. 2023. Study on the Recent Development of Metaverse Application in College Teaching. In Proceedings of the 2023 8th International Conference on Distance Education and Learning (ICDEL '23). Association for Computing Machinery, New York, NY, USA, 30–35. https://doi org.silk.library.umass.edu/10.1145/3606094.3606141

Reflection

I recently undertook a week-long endeavor to research and write about an innovative topic in the realm of new technologies. The focus of my exploration was a specific and cutting-edge area, which presented both challenges and learning opportunities. I recognize that the resulting article, crafted in this short period, lacked depth in specific examples and detailed explanations. This was primarily due to the limited availability of extensive research and reliable information in this nascent field. The specificity of the topic, along with its emerging nature, made it difficult to find comprehensive studies and data.

Despite these obstacles, the process was immensely enlightening. It underscored the difficulties one might face when delving into emerging technologies where foundational research is still in development. The scarcity of detailed resources contributed to the article's vagueness, reflecting the current state of knowledge in this cutting-edge area. However, I remain optimistic about future developments. As the technology evolves and more products related to the metaverse are introduced, there will be greater opportunities for in-depth analysis and richer insights. This evolution will undoubtedly enable the creation of articles with more clarity and specificity.

This experience also significantly impacted my skills and interests. It greatly enhanced my ability to navigate and understand research papers, a vital skill in the constantly advancing field of computer science. More importantly, it ignited a deeper interest in new technologies within the CS domain. This project expanded my knowledge base and strengthened my aspiration to contribute to the field of emerging technologies. As I continue to engage in computer science, I am eager to delve deeper into such innovative topics, now equipped with a better understanding of the unique challenges and opportunities they present.

2023 Spring Team Project

GitHub - IlMinCho/Activity-Detecting

Contribute to IlMinCho/Activity-Detecting development by creating an account on GitHub.

GitHubIlMinCho

GitHub - IlMinCho/Fall-Detection_Mobile-Sensing

Contribute to IlMinCho/Fall-Detection_Mobile-Sensing development by creating an account on GitHub.

GitHubIlMinCho

Team Member: Ilmin, Owen, Arman

Activity Detecting: Through the sensor logger application, we developed an application that detects running, jumping, walking, and sitting activities in real time based on the acceleration sensor.

Fall Detecting: In a significant advancement for personal safety technology, this project has led to the development of an fall detection system. This state-of-the-art system is specifically designed to assist the elderly and those living alone, employing advanced sensor technology to differentiate between normal activities and falls. At its core, the system utilizes accelerometer to analyze movement patterns accurately. A critical feature is the implementation of a low pass filter, effectively isolating significant movements and removing irrelevant high-frequency noise. The system's precision is further enhanced by dynamic thresholding, with movement peak thresholds being adjusted in real-time based on the data's running mean and standard deviation.

The meticulous approach to data collection and analysis is a cornerstone of this project. An extensive dataset comprising 200 fall scenarios, including various types of falls, and 200 non-fall scenarios, such as walking and jumping, was compiled to ensure comprehensive coverage of potential movements. The team also conducted detailed research to determine the most effective placement of the smartphone on the user’s body for optimal data accuracy. This project not only marks a technological breakthrough in elderly care but also paves the way for future innovations in health and safety monitoring. With a focus on continuous improvement and adaptation, this fall detection system promises to enhance personal safety and independence for vulnerable populations, demonstrating the profound impact of technology in improving everyday lives.

Activity Detecting:

It detects running, jumping, walking, and sitting in real time by linking the sensor logger application and our development program. Overall, based on the acceleration sensor, detection is done through the data we collected and preprocessed, and you can see acceleration and filtered signals in real time.

Data Acquisition and Preprocessing

• Activity Selection: Chose four activities for classification, including sitting and walking, running and jumping.
• Data Collection: Used the Sensor Logger app to record accelerometer data for each activity. Ensured a minimum of 5 minutes of data per activity, maintaining equal data length across activities.
• Data Preparation: Exported recordings as Zipped CSV files, unzipped and renamed (e.g., “Walking-Accelerometer.csv”), and consolidated them into a single CSV file using a custom Python script.

Feature Extraction

• Feature Extraction (features.py): Developed functions to extract statistical, FFT, and other relevant features from the accelerometer data.

1. Statistical Features
   • Description: Extracted fundamental statistical measures such as mean, variance, zero- or mean-crossings rate, as well as minimum, maximum, and median values.
   • Application: Applied these measures to each axis and the magnitude of acceleration, focusing on signals most informative for differentiating activities.
   • Tools: Utilized numpy for calculating comprehensive statistical features, including histogram-based analyses.
2. FFT (Fast Fourier Transform) Features
   • Purpose: Identified dominant frequencies in the accelerometer signal to distinguish between activities, such as differentiating running from walking.
   • Method: Implemented numpy’s rfft() function for real-valued Discrete Fourier Transform, analyzing each axis and magnitude separately.
   • Consideration: Addressed the complex nature of FFT output by focusing on real components.
3. Entropy and Other Features
   • Entropy Calculation: Computed entropy using numpy’s histogram() function to create a discrete distribution of accelerometer values.
     ∑_(p(x)) p(x) log(p(x))
   • Integration of Acceleration: Experimented with deriving velocity and distance signals from acceleration data, mindful of the sensitivity to drift in these calculations.
     δv = a δt
     δs = 1/2 aδt^2+v_o δt
   • Challenges and Solutions: Addressed the challenge of large value accumulation in integrated signals by focusing on short-term changes.
4. Peak Features
   • Implementation: Analyzed peaks and troughs in the accelerometer signal to determine the type of activity.
   • Specific Techniques: Employed methods such as peak count per window and average duration between peaks.

Fall Detecting:

This project developed an application that detects whether a person has fallen based on the overall acceleration sensor by applying Activity Detecting above.

Data Collection, Model Training, and Testing/ Analysis

We collected 200 samples related to fall based on acceleration using a sensor logger application. Each data is less than 1 minute long, and the first 30 seconds are based on general movements such as walking or standing, then falling down, and then lying down on the floor for 10 to 15 seconds. Then, it went through a process of labeling the fallen section for each data, and removed unnecessary high frequencies in the data by using a low-pass filter.

Overall, based on the acceleration information for each axis, the model was trained and fall was detected using the features of Mean, Variance, Minimum, Maximum, Median, Dominant frequency, Entropy, and Number of peaks. Additionally, 10 fold cross validation and decision trees were generated.

To perform the data smoothing process, Low-pass filter, one of the Freq-domain Filtering methods, was applied.

• Low-pass filter: A low-pass filter passes signals with frequency lower than a certain cutoff frequency and attenuates (i.e. reduces the effect of) signals that are higher than the cutoff frequency. An example where a low-pass filter is used is to remove baseline variations in an ECG signal

Classifier Training : Utilized the Decision Tree Classifier with 10-fold cross-validation. Implemented metrics like accuracy, precision, and recall to evaluate the model.

• Data labeling: The initial step involved classifying the activity of the fall, which was used to decode the classifier's predictions. It is based on labeling each data by time, taking into account the section where the person fell and the section where the person is lying on the floor.
• Data Windowing Strategy: A critical decision was to label data windows based on the midpoint label, streamlining the classification process.
• Classifier Training and Validation: Utilizing the scikit-learn library, I trained a decision tree classifier using a 10-fold cross-validation approach (model_selection.KFold), ensuring a robust evaluation of the model.
  The classifier was configured with entropy as the criterion and a depth cap of 3, balancing complexity and computational efficiency.

• Performance Analysis: By employing the fit and predict functions, I trained the model and made predictions on the test data. I then used a confusion matrix to evaluate the accuracy, precision, and recall of the model, providing a comprehensive assessment of its performance.
• Visualization and Finalization: The decision tree was visualized using export_graphviz, creating an insightful representation of the model's decision-making process. A PNG image of the tree was generated using Graphviz, offering a clear visual understanding of the classifier's structure.
• Saving the Classifier: The final classifier was saved using pickle, ensuring that the trained model could be efficiently reused or referenced in future work.

Key learnings
• Data filtering and processing using features such as Maximum, Median, Dominant frequency, Entropy.
• Implement Numpy, scipy, matplotlib and, pandas.
• Sensor logger application
• Training a Decision Tree Classifier

How to Improve the Project Further:

Other sensors, such as gyroscopes, can be used to provide more accurate detection. We only considered falls in everyday situations such as standing or walking, but this can be expanded to include falls during running, cycling, and other activities. Additionally, a process can be applied to detect falls in real time and send a message confirming personal safety.

Reference : https://dganesan.github.io/mhealth-course/

Indexing

• Indexes are data structures designed to make search faster
• Text search has unique requirements, which leads to unique data structures
• Most common data structure is inverted index
  – general name for a class of structures
  – “inverted” because documents are associated with words, rather than words with documents

Indexes and Ranking

• Indexes are designed to support search
  – faster response time, support updates
• Text search engines use a particular form of search: ranking
  – documents are retrieved in sorted order according to a score computing using the document representation, the query, and a ranking algorithm
• Let’s develop an abstract model for ranking
  – enables discussion of indexes without details of retrieval model
  

How do we implement ranking?

• Brute force approach
  For each document D in collection: Calculate score and then, Sort the scores
• Drawbacks?
  – Most documents contain no query terms
  – Very slow for a large collection

Handle with an inverted Index

• Each term associated with an inverted list
  – Contains lists of documents, or lists of word occurrences in documents, and other information
  – Each entry is called a posting
  – The part of the posting that refers to a specific document or location is called a pointer
  – Each document in the collection is given a unique number
  – Lists usually document-ordered (sorted by document number)

Query Processing

• Document-at-a-time
  – Calculates complete scores for documents by processing all term lists, one document at a time
• Term-at-a-time
  – Accumulates scores for documents by processing term lists one at a time
• Both approaches have optimization techniques that significantly reduce time required to generate scores

Pseudocode Function Descriptions

• Need to be able to traverse inverted lists
  – Recall that they are sorted by document number
• Abstraction is a “you are here” pointer
• InvList.getCurrentDocument()
  – Returns the document number of the current posting of the inverted list (“you are here”)
• InvList.movePastDocument(d)
  – Moves forward in the inverted list until getCurrentDocument() > d

Pseudocode Function Descriptions

• getCurrentDocument()
  – Returns the document number of the current posting of the inverted list.
• movePastDocument(d)
  – Moves forward in the inverted list until getCurrentDocument() <= d.
• moveToNextDocument()
  – Moves to the next document in the list. Same as movePastDocument(getCurrentDocument()).

Ranking/Retrieval

Retrieval Models

• Provide a mathematical framework for defining the search process
  – includes explanation of assumptions
  – basis of the ranking algorithms
• Progress in retrieval models has corresponded with improvements in effectiveness
• Theories about relevance

Boolean Retrieval

• Two possible outcomes for query processing
  – TRUE and FALSE
  – “exact-match” retrieval
  – simplest form of ranking
• Query usually specified using Boolean operators
  – AND, OR, NOT
  – proximity operators and wildcards also used
  – Extra features like date or type

Vector Space Model

• Key idea is that everything is a vector
  – In an extremely high-dimensional space
  – e.g., 100K dimensions
  – documents, queries, terms

• Dimensions are not specified

• Magnitude on them is not specified

• Typically, a document is the sum of its parts

• Provides a framework
  – Dimensions most commonly are terms (tokens)
  – Term weighting for magnitude -> Which terms are more important?
  – So weighted vectors are doc and query models
  – How to rank? -> Which documents are more relevant?
  – Relevance Feedback -> How to employ feedback from searcher?

• Documents and query represented by a vector of term weights

• Collection represented by a matrix of term weights
  

How do we weigh doc terms?

• Is just the number of times it occurs enough?
• Intuition:
  – Terms that appear often in a document should get high weights
  – Terms that appear in many documents should get low weights
• How do we capture this mathematically?
  – Term frequency
  – Inverse document frequency

Term frequency tf

• The term frequency tfd,t of term t in document d is defined as the number of times that t occurs in d.
• We want to use tf when computing query-document match scores. But how?
• Raw term frequency is not what we want:
  – A document with 10 occurrences of the term is more relevant than a document with 1 occurrence of the term.
  – But not 10 times more relevant.
• Relevance does not increase proportionally with term frequency.

Log-frequency weighting

• The log frequency weight of term t in d is
• 0 → 0, 1 → 1, 2 → 1.3, 10 → 2, 1000 → 4, etc.
• Score for a document-query pair: sum over terms t in both q and d:
• Score is 0 if none of the query terms is in the document – i.e., if intersection is empty

idf weight

• nk is the document frequency of term k: the number of documents that contain k
  – nk is an inverse measure of the “informativeness” ofa term that occurs k times
  – nk <= N
• We define the idf (inverse document frequency) of k by: idfk = log10 (N/nk )
  – We use log (N/nk) instead of N/nk to “dampen” the effect of idf.
  – A term that occurs zero times has an undefined idf

Term Weights

• tf·idf weight
  – Term frequency weight measures importance in document
  – Inverse document frequency measures importance in collection
  – Heuristic combination (length normalized)
  

BM25

• BM25 was created as the result of a series of experiments on variations of the probabilistic model
• A good term weighting is based on three principles
  – inverse document frequency
  – term frequency
  – document length normalization
• The classic probabilistic model (just talked about) covers only the first of these principles
• This reasoning led to a series of experiments which led to the BM25 ranking formula
• Popular and effective ranking algorithm based on binary independence model
  – adds document and query term weights
  – k1, k2 and K are parameters whose values are set empirically
  – dl is doc length
  – Typical TREC values: k1 is 1.2, k2 varies from 0 to 1000, b = 0.75

BM25 Example

• Query with two terms, “president lincoln”, (qf = 1)
• No relevance information (ri and R are zero)
• N = 500,000 documents
• “president” occurs in 40,000 documents (n1 = 40, 000)
• “lincoln” occurs in 300 documents (n2 = 300)
• “president” occurs 15 times in doc (f1 = 15)
• “lincoln” occurs 25 times (f2 = 25)
• document length is 90% of the average length (dl/avdl = .9)
• k1 = 1.2, b = 0.75, and k2 = 100
• K = 1.2 · (0.25 + 0.75 · 0.9) = 1.11
  

Query-Likelihood Model (QL)

• Rank documents by the probability that the query could be generated by the document model (i.e., same topic)
• Given a query, we are interested in P(D|Q)
• One way is to use Bayes’ Rule
• Assuming prior is uniform, and assuming independence, we get the unigram
  

Smoothing

• Document texts are a sample from the language model
  – Missing words should not have zero probability of occurring
  – A document is a very small sample of words, and the maximum likelihood estimate will be inaccurate.
• Smoothing is a technique for estimating probabilities for missing (or unseen) words
  – reduce (or discount) the probability estimates for words that are seen in the document text
  – assign that “left-over” probability to the estimates for the words that are not seen in the text

Query Likelihood Example

• For the term “president”
  – fqi,D = 15, cqi = 160,000
• For the term “lincoln”
  – fqi,D = 25, cqi = 2,400
• number of word occurrences in the document, |D|, is assumed to be 1,800
• number of word occurrences in the collection is 109
  – 500,000 documents times an average of 2,000 words
• Score using JM smoothing with λ=0.1 ?
• Score using Dirichlet smoothing with μ = 2,000?
• Using natural log (doesn’t really matter)
• Query Likelihood Example (Dirichlet)

GitHub - IlMinCho/SE-Indexing

Contribute to IlMinCho/SE-Indexing development by creating an account on GitHub.

GitHubIlMinCho

Analysis

1. What is the average length of a story in this collection? What is the shortest story (and how short it is)? What is the longest story (and how longis it)? Note that for this project, "short" and "long" are measured by the number of tokens, not the number of characters.
   Average length = 1215.1629098360656 / 19406-art53 = 4 / 8951-id_6 = 26139
2. What word occurs in the most stories and how many stories does it occur in? What word has the largest number of occurrences and how many does it have?
   ‘the’: 966 docs / ‘the’: 96151 times
3. How many unique words are there in this collection? How many of them occur only once? What percent is that? Is that what you would expect? Why or why not?
   27217 unique terms, 10056 only once. It is around 37%. It is difficult for me to predict the exact value, but it can be calculated to some extent using zipf'law and the larger the size of the corpus and the more diverse the types, the higher the rate of unique words that appear only once, so our sample has a moderate amount of sample and diversity, so 37% is a reasonable number.
4. Your training queries have two queries that are roughly about the scientific american supplement. Suppose that you wanted to judge stories for relevance using a pooling strategy that takes the top 100 documents from each of those two queries. How many unique documents will you be judging? What if you only considered the top 20? Suppose you had a budget that allowed you to judge at most 25 documents. How deeply could you go into the two queries for judging to get 25 judged, no more, no less?
   58 unique documents on top 100 docs. / 0 unique documents on top 20.
   To get 25 unique documents, go in to 64 ranking
5. Run the query amherst college – where that means the two words separately and not the phrase – using either BM25 or QL (your choice). For any 10 of the top 50 top ranked documents, look at the text of the document and mark whether it is relevant. Put your judgments in a file called amherst-YOURUSERNAME.qrels Your should include the 10 storyIDs and a judgement of relevant that is 0 = has nothing to do with Amherst College, 1 = Amherst College is mentioned, or 2 = substantially relates to someone from or
   something that happened at Amherst College. Use the qrels file format from P2, with the queryname being "amherst", then the skip value of 0, then the storyID (NOT your internal docid), and then the 0/1/2 judgment, one of those per line.

Reference: Prof. James Allan

Evaluation

• Evaluation is key to building effective and efficient search engines
  – measurement usually carried out in controlled laboratory experiments
  – online testing can also be done
• Efficiency measures similar to those used in database systems
  – e.g., indexing time, query throughput, index size
• Our focus here is on effectiveness metrics
  – Comparing systems
  – Parameter tuning

Evaluation Corpus

• Test collections consisting of documents, queries, and relevance judgments
• Some examples:

Evaluation Measures

• Precision
  – Proportion of a retrieved set that is relevant
  – Precision = |relevant ∩ retrieved| ÷ |retrieved|
  = P( relevant | retrieved )
• Recall
  – proportion of all relevant documents in the collection included in the retrieved set
  – Recall = |relevant ∩ retrieved| ÷ |relevant| = P( retrieved | relevant )

EX) Precision and Recall example

Average precision of a query

• Provides a single-number effectiveness measure
  – E.g., for a machine-learning algorithm to detect improvement
• Average precision is widely used in IR
  – assumes user interested in finding many relevant documents for each query, preferably at top of list
  – requires many relevance judgments in text collection
• Calculate by averaging precision when recall increases

Another average: F Measure

• Harmonic mean of recall and precision
  
  – harmonic mean emphasizes the importance of small values, whereas the arithmetic mean is affected more by outliers that are unusually large
• More general form (for those who are curious)
  
  – β is a parameter that determines relative importance of recall and precision
  – People usually use balanced F1 measure

Averaging across queries

• Two main types of averaging
  – Micro-average - each relevant document is a point in the average
  – Macro-average - each query is a point in the average
• Also done with average precision value
  – Average of many queries’ average precision values
  – Called mean average precision (MAP)/ “Average average precision” sounds weird

Discounted Cumulative Gain (DCG)

• Popular measure for evaluating web search and related tasks
• Two assumptions:

1. Highly relevant documents are more useful than marginally relevant document
   -> Implies we need multi-valued relevance judgments
2. The lower the ranked position of a relevant document, the less useful it is for the user, since it is less likely to be examined
   -> AP captures this, too, but normally binary judgments

• Uses graded relevance as a measure of the usefulness, or gain, from examining a document
• Gain is accumulated starting at the top of the ranking and may be reduced, or discounted, at lower ranks
• Typical discount is 1/log (rank)
  – With base 2, the discount at rank 4 is 1/2, and at rank 8 it is 1/3
• DCG is the total gain accumulated at a particular rank p:
• Alternative formulation:
  – used by some web search companies

Normalized DCG (NDCG)

• DCG numbers are averaged across a set of queries at specific rank values
  – e.g., DCG at rank 5 is 6.89 and at rank 10 is 9.61
• DCG values are often normalized by comparing the DCG at each rank with the DCG value for the ideal (perfect) ranking
  – makes averaging easier for queries with different numbers of relevant documents

GitHub - IlMinCho/SE-Evaluation

Contribute to IlMinCho/SE-Evaluation development by creating an account on GitHub.

GitHubIlMinCho

Analysis

1.

2.

Looking at the data, we can find several results with a slightly higher value of BM25 than the value of QL and the highest value of DPR. In other words, the percentage tends to improve gradually. However, if you look at the ‘all’ part row, the values increase in the order of BM25 and Ql, DPR.

It depends on which query you look at, but while QL directly checks the probability of a term appearing in a document, BM25 relies on a more complex combination of features. In other words, QL may be better suited for situations where there is a clear semantic relationship between a query and related documents. However, for other data sets or other types of queries, bm25 may work better.

DPR is a model that uses vectors to encode queries and documents. DPR is more sophisticated than QL and BM25 because it takes advantage of similarities between queries and documents to handle complex queries and documents more effectively.

3.

The MAP is intended to evaluate the efficiency of the search system. Without a retrieved document, it is difficult to find the relevance of the document to the query. As a result, MAP calculation is not easy because precision and recall rate cannot be calculated. This also means that there is nothing to evaluate the efficiency of the system, and MAP calculations for these queries can lead to inaccurate results.

4.

Reference: Prof. James Allan

Tokenizing

• Forming words from sequence of characters

• Surprisingly complex in English, can be harder in other languages

• Early IR systems:
  – any sequence of alphanumeric characters of length 3 or more
  – terminated by a space or other special character
  – upper-case changed to lower-case

• Example:
  –> “We’d like to see Illinois become a right-to-work state,” he said.
  –> we d like to see illinoisbecome a right to work state he said

• Too simple for search applications or even large-scale experiments

• Why?
  – Too much information lost
  – Small decisions in tokenizing can have major impact on effectiveness of some queries

Tokenizing Problems

• Small words can be important in some queries, usually in combinations
• xp, ma, pm, bene king, el paso, master p, gm, j lo, world war II
• Both hyphenated and non-hyphenated forms of many words are common
  – Sometimes hyphen is not needed (e-bay, wal-mart, active-x, cd-rom, t-shirts)
  – At other times, hyphens should be considered either as part of the word or a word separator (winston-salem, mazdarx-7, e-cards, pre-diabetes, t-mobile, spanish-speaking )
  – Data base, data-base, database 10
• Special characters are an important part of tags, URLs, code in documents
• Capitalized words can have different meaning from lower case words
  – Bush, Apple, Trump
• Apostrophes can be a part of a word, a part of a possessive, or just a mistake
  – rosieo'donnell, can't, don't, 80's, 1890's, men's straw hats, master's degree, england'sten largest cities, shriner's
• Numbers can be important, including decimals
  – iphone14, top 10 courses, 9/11, united 93, quicktime7.7.9, WMUA 91.1, 867-5309, cs446
• Periods can occur in numbers, abbreviations, URLs, ends of sentences, and other situations
  – I.B.M., Ph.D., cs.umass.edu, 192.168.0.1, F.E.A.R.
• Note: tokenizing steps for queries must be identical to steps for documents

Tokenizing Process

• First step is to use parser to identify appropriate parts of document to tokenize
• Candefer complex decisions to other components
  – word is any sequence of alphanumeric characters, terminated by a space or special character, with everything converted to lower-case
  – everything indexed
  – example: 92.3 → 92 3 but expect search to find documents with 92 and 3 adjacent
  – incorporate some rules to reduce dependence on query transformation components
• Not that different than simple tokenizing process used in past
• Examples of rules used with TREC
  – Apostrophes in words ignored (squeezed out) -> o’connor→ oconnor
  – Periods in abbreviations ignored with one-character tokens, else treated as space ( I.B.M. → ibm / Ph.D. → ph d )

Stopping

• Function words (determiners, prepositions) have little meaning on their own
• High occurrence frequencies
• Treated as stopwords(i.e., removed)
  – reduce index space, improve response time, improve effectiveness
• Stopwordscan be important in combinations
  – e.g., “to be or not to be” or “the The”
• Stopwordlist can be created from high-frequency words or based on a standard list
• Lists are customized for applications, domains, and even parts of documents
  – “click” and “here” good stopwordsfor anchor text
• Best policy is often to index all words in documents, make decisions about which words to use at query time

Stemming

• Many morphological variations of words
  – inflectional(plurals, tenses)
  – derivational(making verbs into nouns etc.)
• In most cases, these have the same or very similar meanings
• Stemmers attempt to reduce morphological variations of words to a common stem
  – usually involves removing suffixes
  – Can include exceptions like mice → mouse
• Can be done at indexing time or as part of query processing (like stopwords)
• Generallya small but significant effectiveness improvement
  – can be crucial for some languages
  – e.g., 5-10% improvement for English, up to 50% in Arabic
  
• Two basic types
  – Dictionary-based: uses lists of related words
  – Algorithmic: uses program to determine related words
• Algorithmic stemmers
  – suffix-s: remove ‘s’ endings, assuming plural

  -e.g., cats → cat, lakes → lake, wiis→ wii
  -Many false negatives: supplies → supplie(cf. supply)
  -Some false positives: ups → up

Porter Stemmer

• Algorithmic stemmer used in IR experiments since the 70s
• Series of rules designed to remove the longest possible suffix at each step
• Effective in IR system evaluations
• Produces stems not words
• Makes a number of errors and difficult to modify

Text Statistics

Zipf’s Law

• Distribution of word frequencies is very skewed
  – a few words occur very often, many words hardly ever occur
  – e.g., two most common words (“the”, “of”) make up about 10% of all word occurrences in text documents
  – e.g., almost half of the terms occur once
• Zipf’s“law” (more generally, a “power law”):
  – observation that rank (r) of a word times its frequency (f) is approximately a constant (k) / assuming words are ranked in order of decreasing frequency
  – i.e., r·f≈k or r·Pr≈c, where Pr is probability of word occurrence and c≈ 0.1 for English
  
  

What else does Zipf tell us?

• We know that the most common word
  accounts for about 10% of the total
  occurrences
  – r=1, c=0.1, so P(r) = 0.1/1 = 10%
• How often does the second most frequent
  term occur? r*Pr = c, 2pr= 0.1 -> Pr = 0.12 = 0.05
• How many words occur 10 times? 3 times ?

Heaps’ Law

• Predictions for TREC collections are accurate for large numbers of words
  – e.g., first 10,879,522 words of the AP89 collection scanned
  – prediction is 100,151 unique words
  – actual number is 100,024
• Predictions for small numbers of words (i.e. < 1000) are much worse

GitHub - IlMinCho/SE-Tokenization

Contribute to IlMinCho/SE-Tokenization development by creating an account on GitHub.

GitHubIlMinCho

– Tokenization (spaces or fancy)
– Stopping (not or with a list)
– Stemming (not or Porter steps 1a-1c)
– Input (gzip!): train, S&S
– Output: Prefix / Tokens, heaps, stats

Analysis

1. Run your program with fancy tokenization, stopping, and Porter stemming on sense-and-sensibility.gz and look at the -tokens.txt -stats.txt file to see the most frequent terms from Sense and Sensibility. Are the top terms relevant to the story or do they seem like everyday words that aren't particularly to the novel? Support your answer with examples. You may find it useful to skim the summary on Wikipedia to know what words are part of the story.

Based on my data, the most frequently found word was her at number 2561. In fact, it is difficult to find a big connection because it is a word that appears in most novels, but in this novel, two sisters named Elinor and Marianne appear as the main characters, and considering this information, it can be inferred that a woman is the main character.

2. Are there any of those top terms that should have been stopwords? Do the top terms or the list of all tokens suggest any changes to the tokenizing or stemming rules? What are they and why should they be made?

Among the top terms, words such as i, not, you, had, but, have, all, so, my, which, could, no... are unnecessary words to grasp the contents of the novel. These are words that can appear in any novel you read, so we don't need them to get information about the content. However, stopwords need to be modified for the purpose you are trying to get via stat. If we add the stopwords mentioned above, we get a value that ranks the names of characters like Elinor and Marianne higher. In addition, it would be nice not to add additional tokenizing or stemming rules.

3. Figure 4.4. in the textbook (p. 82) displays a graph of vocabulary growth for the TREC GOV2 collection. Create a similar graph for Sense and Sensibility and upload an image of your graph. Note that you should be able to use the -heaps.txt file to generate the graph.

This is a graph using the heap data of Sense and Sensibility, the x-axis is the number of tokens, and the y-axis shows the number of unique tokens.

4. Does Sense and Sensibility follow Heaps Law? Why do you think so or think not?

This follows the heap's law. Looking at the data, as the number of tokens increases, the number of unique tokens continues to increase. And since the increasing rate is gradually decreasing, it can be seen as a case of heap's law. Additionally, looking at the graph, it increases relatively steeply at the beginning and gradually flattens as the number of tokens increases, which is a model of heap's law.

Reference: Prof. James Allan

Information Retrieval
“Information retrieval is a field concerned with the structure, analysis, organization, storage, searching, and retrieval of information.”(Salton, 1968)

- General definition that can be applied to many types of information and search applications

- Primary focus of IR since the 50s has been on textand documents

Basic Approach to IR

1. Most (but not all!) successful approaches are statistical
   • Directly, or an effort to capture and use probabilities
2. Why not natural language understanding?
   • i.e., computer understands docs and query and matches them
   • State of the art is brittle in unrestricted domains
   • Can be highly successful in predictable settings, though
   • ChatGPTsuggests things are improving, but it still makes plenty of mistakes (and doesn’t really “understand” anything)
3. Could use manually assigned headings
   • e.g., Library of Congress headings, Dewey Decimal headings
   • Hard to predict what headings are “interesting”
   • Expensive and human agreement is not good

“Bag of Words”

• An effective and popular approach
• Compares words without regard to order
• Consider reordering words in a headline
  • Random: beating takes points falling another Dow 355
  • Alphabetical: 355 another beating Dow falling points
  • “Interesting”: Dow points beating falling 355 another
  • Actual: Dow takes another beating, falling 355 points

Statistical language model

• Document comes from a topic

• Topic (unseen) describes how words appear in documents on the topic

• Use document to guesswhat the topic looks like
  -Words common in document are common in topic
  -Words not in document much less likely to be in the topic
  

• Assign probability to words based on document

  • P(w|Topic) ≈P(w|D) = tf(w,D) / len(D)

• Index estimated topics

What does LM look like implemented?

• Hypothesis of statistical language model
  – Documents with topic models that are highly likely to generate the query are more likely to be relevant (to query)

• Index collection in advance (chs. 3&4)
  – Convert documents into set of P(ti|D)
  – Store in an appropriate data structure for fast access

• Query arrives (ch.6&7)
  – Convert it to set P(qi|D)
  – Calculate P(Q|TD) for all documents
  – Sort documents by their topics’ probability
  – Present ranked list

• Generally good results (ch.8) though not with version of the model that is this simple (ch.5)

Some issues that arise in IR

• Text representation
  – what makes a “good” representation?
  – how is a representation generated from text?
  – what are retrievable objects and how are they organized?

• Representing information needs
  – what is an appropriate query language?
  – how can interactive query formulation and refinement be supported?

• Comparing representations
  – what is a “good” model of retrieval?
  – how is uncertainty represented?

• Evaluating effectiveness of retrieval
  – what are good metrics?
  – what constitutes a good experimental test bed?

Reference: Prof. James Allan